Liu 2017 Automated heuristic design using genetic programming hyper-heuristic.pdf (851 kB)

Automated heuristic design using genetic programming hyper-heuristic for uncertain capacitated arc routing problem

Download (851 kB)
conference contribution
posted on 31.03.2021, 02:14 by Yuxin Liu, Yi Mei, Mengjie Zhang, Zili Zhang
Uncertain Capacitated Arc Routing Problem (UCARP) is a variant of the well-known CARP. It considers a variety of stochastic factors to reflect the reality where the exact information such as the actual task demand and accessibilities of edges are unknown in advance. Existing works focus on obtaining a robust solution beforehand. However, it is also important to design effective heuristics to adjust the solution in real time. In this paper, we develop a new Genetic Programming-based Hyper-Heuristic (GPHH) for automated heuristic design for UCARP. A novel effective meta-algorithm is designed carefully to address the failures caused by the environment change. In addition, it employs domain knowledge to filter some infeasible candidate tasks for the heuristic function. The experimental results show that the proposed GPHH significantly out performs the existing GPHH methods and manually designed heuristics. Moreover, we find that eliminating the infeasible and distant tasks in advance can reduce much noise and improve the efficacy of the evolved heuristics. In addition, it is found that simply adding a slack factor to the expected task demand may not improve the performance of the GPHH. © 2017 ACM . This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in 'GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference', https://doi.org/10.1145/3071178.3071185.

History

Preferred citation

Liu, Y., Mei, Y., Zhang, M. & Zhang, Z. (2017, January). Automated heuristic design using genetic programming hyper-heuristic for uncertain capacitated arc routing problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) GECCO '17: Genetic and Evolutionary Computation Conference, ACM (pp. 290-297). ACM. https://doi.org/10.1145/3071178.3071185

Conference name

GECCO '17: Genetic and Evolutionary Computation Conference

Conference Place

ACM

Title of proceedings

Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)

Contribution type

Published Paper

Publication or Presentation Year

01/01/2017

Pagination

290-297

Publisher

ACM

Publication status

Published

Exports