A Modified Binary Crow Search Algorithm for Solving the Graph Coloring Problem

Yassine Meraihi, Mohammed Mahseur and Dalila Acheli
Additional contact information
Yassine Meraihi: University of M'Hamed Bougara, Boumerdes, Algeria
Mohammed Mahseur: University of Sciences and Technology Houari Boumediene, Bab Ezzouar, Algeria
Dalila Acheli: University of M'Hamed Bougara, Boumerdes, Algeria

International Journal of Applied Evolutionary Computation (IJAEC), 2020, vol. 11, issue 2, 28-46

Abstract: The graph coloring problem (GCP) is a well-known classical combinatorial optimization problem in graph theory. It is known to be an NP-Hard problem, so many heuristic algorithms have been employed to solve this problem. This article proposes a modified binary crow search algorithm (MBCSA) to solve the graph coloring problem. First, the binary crow search algorithm is obtained from the original crow search algorithm using the V-shaped transfer function and the discretization method. Second, we use chaotic maps to choose the right values of the flight length (FL) and the awareness probability (AP). Third, we adopt the Gaussian distribution method to replace the random variables used for updating the position of the crows. The aim of these contributions is to avoid the premature convergence to local optima and ensure the diversity of the solutions. To evaluate the performance of our algorithm, we use the well-known DIMACS benchmark graph coloring instances. The simulation results reveal the efficiency of our proposed algorithm in comparison with other existing algorithms in the literature.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/IJAEC.2020040103 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jaec00:v:11:y:2020:i:2:p:28-46

Access Statistics for this article

International Journal of Applied Evolutionary Computation (IJAEC) is currently edited by Sukhpal Singh Gill

More articles in International Journal of Applied Evolutionary Computation (IJAEC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().