Abstract: In recent years, Graph Coloring Problem (GCP) is one of the main optimization problems from literature. Many real world problems interacting with changing environments can be modeled by dynamic graphs. Graph vertex coloring with a given number of colors is a w
More
Abstract: In recent years, Graph Coloring Problem (GCP) is one of the main optimization problems from literature. Many real world problems interacting with changing environments can be modeled by dynamic graphs. Graph vertex coloring with a given number of colors is a well-known and much-studied NP-hard problem. Meta-heuristic algorithms are a good choice to solve GCP because they are suitable for problems with NP-hard complexity. However, in many previously proposed algorithms, there are common problems such as runtime algorithm and low convergence of algorithm. Therefore, in this paper, we propose the Fuzzy Whale Optimization Algorithm (FWOA), a variety of basic Whale Optimization Algorithm (WOA), to improve runtime and convergence of algorithm in the GCP. Since WOA at first was introduced for solving continuous problem, we need a discrete WOA. Hence, to use FWOA to discrete search space, the standard arithmetic operators such as addition, subtraction and multiplication extant in FWOA encircling prey, exploitation phase and exploration phase operators based on distance’s theory needs to be redefined in the discrete space. Parameters p and r, are defined randomly in the WOA algorithm in FWOA algorithm defined as fuzzy and are selected in fuzzy tragedy. A set of graph coloring benchmark problems are solved and their performance are compared with some well-known heuristic search methods. Results illustrate that FWOA algorithm are the original focus of this work and in most cases success rate is nearly 100% and the runtime and convergence algorithm has been improved on some graphs. But as we have illustrated that comparison with other manners, we cannot deduce that our algorithm is the best in all instance of graphs. It can be said that a proposed algorithm is able to compete with other algorithms in this context. Obtained results approved the high performance of proposed method.
Manuscript profile
