Local optima correlation assisted adaptive operator selection

Jiyuan PEI, Hao TONG, Jialin LIU, Yi MEI, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

1 Citation (Scopus)


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. © 2023 ACM.
Original languageEnglish
Title of host publicationGECCO 2023 Companion : Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
EditorsSara SILVA, Luís PAQUETE
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Number of pages9
ISBN (Print)9798400701191
Publication statusPublished - 15 Jul 2023
Externally publishedYes
EventGenetic and Evolutionary Computation Conference 2023 - Lisbon, Portugal
Duration: 15 Jul 202319 Jul 2023


ConferenceGenetic and Evolutionary Computation Conference 2023
Abbreviated titleGECCO’23 Companion

Bibliographical note

This work was supported by the National Natural Science Foundation of China Grant Nos. 62250710682, 61906083, the Guangdong Provincial Key Laboratory Grant No. 2020B121201001, the Program for Guangdong Introducing Innovative and Enterpreneurial Teams Grant No. 2017ZT07X386, the Shenzhen Science and Technology Program Grant No. KQTD2016112514355531, the Shenzhen Fundamental Research Program Grant No. JCYJ20190809121403553, and the Research Institute of Trustworthy Autonomous Systems.


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


Dive into the research topics of 'Local optima correlation assisted adaptive operator selection'. Together they form a unique fingerprint.

Cite this