Integrated Crossover Based Evolutionary Algorithm for Coloring Vertex-Weighted Graphs

Abstract

Graph coloring is one of the main optimization problems widely studied in the literature. In this study, we propose a novel evolutionary algorithm called Integrated Crossover Based Evolutionary Algorithm with its unique crossover operator and local search technique for coloring vertex-weighted graphs. The integrated crossover operator targets to use the domain-specific information in the individuals and the local search technique aims to explore neighborhood solutions using weighted-swap operations. The performance of the proposed work is evaluated on synthetic benchmarks and DIMACS instances by comparing it with leading evolutionary algorithms from the literature. The experimental study indicates that our algorithm outperforms the related work in 71% of the test cases and achieves the same result in 17% of the test cases provided in the synthetic benchmarks. The experiments performed on DIMACS benchmarks denote that our algorithm finds the best number of colors in 70 out of 73 graphs, so the proposed work is very successful in coloring vertex-weighted graphs within a reasonable amount of time.