Knowledge Transfer Genetic Programming With Auxiliary Population for Solving Uncertain Capacitated Arc Routing Problem

Mazhar Ansari ARDEH, Yi MEI, Mengjie ZHANG, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

1 Citation (Scopus)

Abstract

The uncertain capacitated arc routing problem (UCARP) is an NP-hard combinatorial optimization problem with a wide range of applications in logistics domains. Genetic programming (GP) hyper-heuristic has been successfully applied to evolve routing policies to effectively handle the uncertain environment in this problem. The real world usually encounters different but related instances due to events, such as season change and vehicle breakdowns, and it is desirable to transfer knowledge gained from solving one instance to help solve another related one. However, the solutions found by the GP process can lack diversity, and the existing methods use the transferred knowledge mainly during initialization. Thus, they cannot sufficiently handle the change from the source to the target instance. To address this issue, we develop a novel knowledge transfer GP with an auxiliary population. In addition to the main population for the target instance, we initialize an auxiliary population using the transferred knowledge and evolve it alongside the main population. We develop a novel scheme to carefully exchange the knowledge between the two populations, and a surrogate model to evaluate the auxiliary population efficiently. The experimental results confirm that the proposed method performed significantly better than the state-of-the-art GP approaches for a wide range of uncertain arc routing instances, in terms of both final performance and convergence speed. © 1997-2012 IEEE.
Original languageEnglish
Pages (from-to)311-325
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Volume27
Issue number2
DOIs
Publication statusPublished - 2023
Externally publishedYes

Keywords

  • Arc routing
  • genetic programming (GP)
  • hyper-heuristics
  • transfer optimization

Fingerprint

Dive into the research topics of 'Knowledge Transfer Genetic Programming With Auxiliary Population for Solving Uncertain Capacitated Arc Routing Problem'. Together they form a unique fingerprint.

Cite this