Solving Graph Coloring Problem Using an Enhanced Binary Dragonfly Algorithm
| Autor: | Amar Ramdane-Cherif, Karim Baiche, Manolo Dulva Hina, Mohammed Mahseur, Yassine Meraihi |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Combinatorics
Computational Theory and Mathematics Artificial Intelligence Computer science 020208 electrical & electronic engineering 0202 electrical engineering electronic engineering information engineering Binary number 020201 artificial intelligence & image processing Dragonfly algorithm 02 engineering and technology Graph coloring Computer Science Applications |
| Zdroj: | International Journal of Swarm Intelligence Research. 10:23-45 |
| ISSN: | 1947-9271 1947-9263 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|