.png){kind=icon}
.png){kind=icon}
Return
A distribution evolutionary algorithm for the graph coloring problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.swevo.2023.101324.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Graph coloring is a challenging combinatorial optimization problem with a wide range of applications. In this paper, a distribution evolutionary algorithm based on a population of probability model (DEA-PPM) is developed to address it efficiently. Unlike existing estimation of distribution algorithms where a probability model is updated by generated solutions, DEA-PPM employs a distribution population based on a novel probability model, and an orthogonal exploration strategy is introduced to search the distribution space with the assistance of an refinement strategy. By sampling the distribution population, efficient search in the solution space is realized based on a tabu search process. Meanwhile, DEA-PPM introduces an iterative vertex removal strategy to improve the efficiency of k-coloring, and an inherited initialization strategy is implemented to address the chromatic number problem well. The cooperative evolution of the distribution population and the solution population leads to a good balance between exploration and exploitation. Numerical results demonstrate that the DEA-PPM of small population size is competitive to the state-of-the-art metaheuristics.
Keywords:
Distribution evolutionary algorithm
Orthogonal exploration
Inherited initialization
Graph coloring
Estimation of distribution algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
8.5
Papers:
2.2K
Citations:
1.0W
Organization
View more organizations