Phased Genetic Programming for Application to the Traveling Salesman Problem
Created by W.Langdon from
gp-bibliography.bib Revision:1.8028
- @InProceedings{chitty:2023:GECCOcomp,
-
author = "Darren Chitty and Ed Keedwell",
-
title = "Phased Genetic Programming for Application to the
Traveling Salesman Problem",
-
booktitle = "Proceedings of the 2023 Genetic and Evolutionary
Computation Conference",
-
year = "2023",
-
editor = "Sara Silva and Luis Paquete and Leonardo Vanneschi and
Nuno Lourenco and Ales Zamuda and Ahmed Kheiri and
Arnaud Liefooghe and Bing Xue and Ying Bi and
Nelishia Pillay and Irene Moser and Arthur Guijt and
Jessica Catarino and Pablo Garcia-Sanchez and
Leonardo Trujillo and Carla Silva and Nadarajen Veerapen",
-
pages = "547--550",
-
address = "Lisbon, Portugal",
-
series = "GECCO '23",
-
month = "15-19 " # jul,
-
organisation = "SIGEVO",
-
publisher = "Association for Computing Machinery",
-
publisher_address = "New York, NY, USA",
-
keywords = "genetic algorithms, genetic programming, traveling
salesman problem: Poster",
-
isbn13 = "9798400701191",
-
DOI = "doi:10.1145/3583133.3590673",
-
size = "4 pages",
-
abstract = "The Traveling Salesman Problem (TSP) is a difficult
permutation-based optimisation problem typically solved
using heuristics or meta-heuristics which search the
solution problem space. An alternative is to find sets
of manipulations to a solution which lead to
optimality. Hyper-heuristics search this space applying
heuristics sequentially, similar to a program. Genetic
Programming (GP) evolves programs typically for
classification or regression problems. This paper
hypothesizes that GP can be used to evolve heuristic
programs to directly solve the TSP. However, evolving a
full program to solve the TSP is likely difficult due
to required length and complexity. Consequently, a
phased GP method is proposed whereby after a phase of
generations the best program is saved and executed. The
subsequent generation phase restarts operating on this
saved program output. A full program is evolved
piecemeal. Experiments demonstrate that whilst pure GP
cannot solve TSP instances when using simple operators,
Phased-GP can obtain solutions within 4\% of optimal
for TSPs of several hundred cities. Moreover, Phased-GP
operates up to nine times faster than pure GP.",
-
notes = "GECCO-2023 A Recombination of the 32nd International
Conference on Genetic Algorithms (ICGA) and the 28th
Annual Genetic Programming Conference (GP)",
- }
Genetic Programming entries for
Darren M Chitty
Ed Keedwell
Citations