An efficient swarm evolution algorithm with probability learning for the black and white coloring problem
Abstract 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 d...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-07-01
|
| Series: | Scientific Reports |
| Subjects: | |
| Online Access: | https://doi.org/10.1038/s41598-025-06855-4 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849234951220756480 |
|---|---|
| author | Zhiqiang Zhang Li Zhang Xiujun Zhang |
| author_facet | Zhiqiang Zhang Li Zhang Xiujun Zhang |
| author_sort | Zhiqiang Zhang |
| collection | DOAJ |
| description | Abstract 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. |
| format | Article |
| id | doaj-art-dce9e2bb2e5a41e1a09d76d0f52adddb |
| institution | Kabale University |
| issn | 2045-2322 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj-art-dce9e2bb2e5a41e1a09d76d0f52adddb2025-08-20T04:02:56ZengNature PortfolioScientific Reports2045-23222025-07-0115113310.1038/s41598-025-06855-4An efficient swarm evolution algorithm with probability learning for the black and white coloring problemZhiqiang Zhang0Li Zhang1Xiujun Zhang2Key Laboratory of Digital Innovation of Tianfu Culture, Sichuan Provincial Department of Culture and Tourism, Chengdu UniversitySchool of Foreign Languages, Sichuan Normal UniversitySchool of Computer Science, Chengdu UniversityAbstract 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.https://doi.org/10.1038/s41598-025-06855-4Black and white coloringSwarm evolution algorithmImproved simulated annealingProbability learningEvolutionary |
| spellingShingle | Zhiqiang Zhang Li Zhang Xiujun Zhang An efficient swarm evolution algorithm with probability learning for the black and white coloring problem Scientific Reports Black and white coloring Swarm evolution algorithm Improved simulated annealing Probability learning Evolutionary |
| title | An efficient swarm evolution algorithm with probability learning for the black and white coloring problem |
| title_full | An efficient swarm evolution algorithm with probability learning for the black and white coloring problem |
| title_fullStr | An efficient swarm evolution algorithm with probability learning for the black and white coloring problem |
| title_full_unstemmed | An efficient swarm evolution algorithm with probability learning for the black and white coloring problem |
| title_short | An efficient swarm evolution algorithm with probability learning for the black and white coloring problem |
| title_sort | efficient swarm evolution algorithm with probability learning for the black and white coloring problem |
| topic | Black and white coloring Swarm evolution algorithm Improved simulated annealing Probability learning Evolutionary |
| url | https://doi.org/10.1038/s41598-025-06855-4 |
| work_keys_str_mv | AT zhiqiangzhang anefficientswarmevolutionalgorithmwithprobabilitylearningfortheblackandwhitecoloringproblem AT lizhang anefficientswarmevolutionalgorithmwithprobabilitylearningfortheblackandwhitecoloringproblem AT xiujunzhang anefficientswarmevolutionalgorithmwithprobabilitylearningfortheblackandwhitecoloringproblem AT zhiqiangzhang efficientswarmevolutionalgorithmwithprobabilitylearningfortheblackandwhitecoloringproblem AT lizhang efficientswarmevolutionalgorithmwithprobabilitylearningfortheblackandwhitecoloringproblem AT xiujunzhang efficientswarmevolutionalgorithmwithprobabilitylearningfortheblackandwhitecoloringproblem |