Two genetic algorithms for the bandwidth multicoloring problem (Q2853289)

The author considers two coloring problems: the Bandwidth Multicoloring Problem (BMCP) and the Bandwidth Coloring Problem (BCP). The author implements two genetic algorithms GA1 and GA2 for solving the considered problems.NEWLINENEWLINE Both GA approaches use integer representation of solutions and existing genetic operators from the literature: fine-grained tournament selection, mutation with frozen bits and one-point. The initial population is generated to be feasible and applied GA operators preserve the feasibility of solutions. The main difference between the proposed algorithms is that the GA1 is a constructive-based, while the GA2 is an improvement-based metaheuristic.NEWLINENEWLINE Both GA1 and GA2 are tested on the publicly-available GEOM instances from the literature. The proposed GA1 achieved better solution compared to the calculated upper bound for a given problem, while the GA2 has significantly improved the solutions obtained by GA1. Computational experiments on GEOM instances show the appropriateness of the applied GA components in the proposed GA1 and GA2.NEWLINENEWLINE However, when compared the best results of GA1 and GA2 with the results of existing methods for solving the BMPP and BCP, it can be seen that the genetic approaches presented in this paper do not improve (and in some cases do not reach) the previous best-known solution values. The presented comparative results show that only GA2 results are comparable with the results of other methods applied to the BCP and BMCP, such as hill-climbing techniques, squeaky wheel optimization and its combination with tabu search, hybridization of local search with constraint programming, etc. Although the idea of applying GA approach to graph coloring problem has certain potential, the contribution of the paper is not convincing when compared to existing methods and the proposed GA algorithms need to be improved.