An efficient swarm evolution algorithm with probability learning for the black and white coloring problem

There is a graph G = (V, E), which has n vertices and l edges. Color the vertices of G black or white, ensuring no black vertex is adjacent to any white vertex, thus partitioning them into disjoint black and white sets. The optimal solution of the black and white coloring (BWC) problem is defined as the coloring scheme that maximizes the number of white vertices in the corresponding set, given a fixed number of black vertices. This problem is a NP-complete problem, widely used in reagent product storage in chemical industry and the solution to the problem of black and white queens in chess. The paper presents a swarm evolution algorithm based on improved simulated annealing search and evolutionary operation with probability learning mechanism. Furthermore, crossover operation, perturbation operation, and tabu search strategy improve the search ability of the algorithm, while evolutionary operation with probability learning mechanism increases the probability of the algorithm finding better solutions. Using Cayley graphs, random graphs, semi-random graphs, and benchmark DIMACS graphs, experiments are conducted to compare the finding results from swarm evolution algorithm and other classical heuristic algorithms. Experimental results show that the swarm evolution algorithm outperforms other heuristic algorithms in solving the BWC problem, and the swarm evolution algorithm can improve the known best results of the BWC problem.