Local optima correlation assisted adaptive operator selection

Pei，Jiyuan1; Tong，Hao2; Liu，Jialin1; Mei，Yi3; Yao，Xin1

10.1145/3583131.3590399

2023-07-15

Genetic and Evolutionary Computation Conference (GECCO)

GECCO 2023 - Proceedings of the 2023 Genetic and Evolutionary Computation Conference

339-347

JUL 15-19, 2023

null,Lisbon,PORTUGAL

1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES

ASSOC COMPUTING MACHINERY

For solving combinatorial optimisation problems with metaheuristics, different search operators are applied for sampling new solutions in the neighbourhood of a given solution. It is important to understand the relationship between operators for various purposes, e.g., adaptively deciding when to use which operator to find optimal solutions efficiently. However, it is difficult to theoretically analyse this relationship, especially in the complex solution space of combinatorial optimisation problems. In this paper, we propose to empirically analyse the relationship between operators in terms of the correlation between their local optima and develop a measure for quantifying their relationship. The comprehensive analyses on a wide range of capacitated vehicle routing problem benchmark instances show that there is a consistent pattern in the correlation between commonly used operators. Based on this newly proposed local optima correlation metric, we propose a novel approach for adaptively selecting among the operators during the search process. The core intention is to improve search efficiency by preventing wasting computational resources on exploring neighbourhoods where the local optima have already been reached. Experiments on randomly generated instances and commonly used benchmark datasets are conducted. Results show that the proposed approach outperforms commonly used adaptive operator selection methods.

adaptive operator selection capacitated vehicle routing problem combinatorial optimisation experience-based optimisation local search metaheuristics

第一

英语

CPCI-S ; EI

National Natural Science Foundation of China["62250710682","61906083"]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Information Systems

WOS:001031455100041

20233314553755

Benchmarking ; Heuristic algorithms ; Local search (optimization) ; Vehicle routing

Computer Programming:723.1 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Optimization Techniques:921.5

2-s2.0-85167714267

Scopus

1.Southern University of Science and Technology,Shenzhen,China
2.The University of Birmingham,Birmingham,United Kingdom
3.Victoria University of Wellington,Wellington,New Zealand

Pei，Jiyuan,Tong，Hao,Liu，Jialin,et al. Local optima correlation assisted adaptive operator selection[C]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2023:339-347.