In this paper, a Hybrid Cultural-Hierarchical Clustering Algorithm (HCHCA) is presented to solve the graphcoloring problem. The algorithm proposed here is an implementation of a modified cultural algorithm, which uses the genetic algorithm to represent the population space, besides the clique number and the max degree graph formulas are deployed to initialize the belief space. Moreover, the communication protocols between the two spaces (belief and population) are ensured by the best individuals depending on their fitness and number of used colors. The hierarchical clustering is included in the genetic algorithm to verify the similarity between clusters and inside clusters. In the first case, if the similarity between them exceeds a certain rate the two clusters are merged. However in the second case, the cluster is destroyed if the similarity between vertices is less than a certain rate. So, the vertices are distributed between the others clusters. This phase is added after crossover and mutation and it contributes to increase the rate of convergence toward the chromatic number and avoid finishing with a local solution. Experiments on a set of 23 well-known DIMACS benchmark instances show that the proposed algorithm achieves competitive results in comparison with three states of art algorithms in terms of either success rate and solution quality.
Volume 11 | 06-Special Issue
Pages: 1834-1842