A hybrid algorithm based on modified chemical reaction optimization and best-first search algorithm for solving minimum vertex cover problem

• Published in: Neural computing & applications 2022-09, Vol.34 (18), p.15513-15541
• Main Authors: Khattab, Hebatullah, Mahafzah, Basel A., Sharieh, Ahmad
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial Intelligence; Business metrics; Chemical reactions; Computational Biology/Bioinformatics; Computational Science and Engineering; Computer Science; Data Mining and Knowledge Discovery; Genetic algorithms; Heuristic methods; Image Processing and Computer Vision; Optimization; Original Article; Performance measurement; Populations; Probability and Statistics in Computer Science; Search algorithms
• ISSN: 0941-0643; 1433-3058
• DOI: 10.1007/s00521-022-07262-w

The minimum vertex cover problem (MVCP) is one of the well-known NP-complete problems that can be used to formulate numerous real-life applications. The MVCP has been solved using different approaches, exact, heuristic, and metaheuristic. Chemical reaction optimization (CRO) is a population-based metaheuristic algorithm that simulates what happens in chemical reactions to solve many problems. In this paper, the MVCP is solved using hybridization of a modified version of the CRO algorithm and the best-first search (BFS) algorithm. This hybridization is symbolized by MCROA-BFS. The BFS algorithm is exploited to generate initial populations with high-quality initial solutions in comparison with the random bit-vector (RBV) approach as a traditional approach for generating initial populations for several population-based metaheuristic algorithms. At first, the MCROA is evaluated analytically in terms of run time complexity. Then the performance of the MCROA is evaluated experimentally to show the effectiveness of exploiting the BFS in terms of quality of gained solutions and run time. The most valuable player algorithm (MVPA), genetic algorithm (GA), and hybrid CRO algorithm (HCROA) are metaheuristic algorithms that used the RBV approach to generate the initial population. MCROA-BFS is compared, under the selected performance metrics, with these metaheuristic algorithms in addition to MCROA with the RBV approach (MCROA-RBV). The conducted experiments were carried out using 18 instances of DIMACS and BHOSLIB benchmarks. The experimental results revealed the superiority of MCROA-BFS over MVPA, GA, and MCROA-RBV in terms of both performance metrics. Although HCROA has the smallest run time, it failed to obtain high-quality solutions in comparison with MCROA.