Solving Graph Coloring Problem Using an Enhanced Binary Dragonfly Algorithm

Karim Baiche, Yassine Meraihi, Manolo Dulva Hina, Amar Ramdane-Cherif and Mohammed Mahseur
Additional contact information
Karim Baiche: Applied Automation Laboratory, University of MHamed Bougara Boumerdes, Boumerdes, Algeria
Yassine Meraihi: Department of Automation, Applied Automation Laboratory, University of M'Hamed Bougara Boumerdes, Boumerdes, Algeria
Manolo Dulva Hina: ECE Paris School of Engineering, Paris, France
Amar Ramdane-Cherif: LISV Laboratory, University of Versailles St-Quentin-en-Yvelines, Versailles, France
Mohammed Mahseur: University of Sciences and Technology Houari Boumediene, Bab Ezzouar, Algeria

International Journal of Swarm Intelligence Research (IJSIR), 2019, vol. 10, issue 3, 23-45

Abstract: The graph coloring problem (GCP) is one of the most interesting classical combinatorial optimization problems in graph theory. It is known to be an NP-Hard problem, so many heuristic algorithms have been employed to solve this problem. In this article, the authors propose a new enhanced binary dragonfly algorithm to solve the graph coloring problem. The binary dragonfly algorithm has been enhanced by introducing two modifications. First, the authors use the Gaussian distribution random selection method for choosing the right value of the inertia weight w used to update the step vector (∆X). Second, the authors adopt chaotic maps to determine the random parameters s, a, c, f, and e. The aim of these modifications is to improve the performance and the efficiency of the binary dragonfly algorithm and ensure the diversity of solutions. The authors consider the well-known DIMACS benchmark graph coloring instances to evaluate the performance of their algorithm. The simulation results reveal the effectiveness and the successfulness of the proposed algorithm in comparison with some well-known algorithms in the literature.

Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/IJSIR.2019070102 (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:jsir00:v:10:y:2019:i:3:p:23-45

Access Statistics for this article

International Journal of Swarm Intelligence Research (IJSIR) is currently edited by Yuhui Shi

More articles in International Journal of Swarm Intelligence Research (IJSIR) from IGI Global
Bibliographic data for series maintained by Journal Editor ().