期刊
COMPUTERS & OPERATIONS RESEARCH
卷 158, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2023.106284
关键词
Combinatorial optimization; Evolutionary search; Parallel search; Heuristics; Partial graph coloring; Latin square problems
This paper presents a massively parallel evolutionary algorithm for the partial Latin square extension problem based on graph coloring. The algorithm utilizes a large population and modern GPUs to perform intensive exploitation of the search space. Experimental results show its high competitiveness compared to other methods.
The partial Latin square extension problem is to fill as many as possible empty cells of a partially filled Latin square. This problem is a useful model for a wide range of applications in diverse domains. This paper presents the first massively parallel evolutionary algorithm for this computationally challenging problem based on a transformation of the problem to partial graph coloring. The algorithm features the following original elements. Based on a very large population (with more than 104 individuals) and modern graphical processing units, the algorithm performs many local searches in parallel to ensure an intensive exploitation of the search space. The algorithm employs a dedicated crossover with a specific parent matching strategy to create a large number of diversified and information-preserving offspring at each generation. Extensive experiments on 1800 benchmark instances show a high competitiveness of the algorithm compared to the current best performing methods. Competitive results are also reported on the related Latin square completion problem. Analyses are performed to shed lights on the roles of the main algorithmic components.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据