Name
Abstract | ||
|---|---|---|
The symmetric travelling salesman problem is a real world combinatorial optimization problem and a well researched domain. When solving combinatorial optimization problems such as the travelling salesman problem a low-level construction heuristic is usually used to create an initial solution, rather than randomly creating a solution, which is further optimized using techniques such as tabu search, simulated annealing and genetic algorithms, amongst others. These heuristics are usually manually derived by humans and this is a time consuming process requiring many man hours. The research presented in this paper forms part of a larger initiative aimed at automating the process of deriving construction heuristics for combinatorial optimization problems. The study investigates genetic programming to induce low-level construction heuristics for the symmetric travelling salesman problem. While this has been examined for other combinatorial optimization problems, to the authors' knowledge this is the first attempt at evolving low-level construction heuristics for the travelling salesman problem. In this study a generational genetic programming algorithm randomly creates an initial population of low-level construction heuristics which is iteratively refined over a set number of generations by the processes of fitness evaluation, selection of parents and application of genetic operators. The approach is tested on 23 problem instances, of varying problem characteristics, from the TSPLIB and VLSI benchmark sets. The evolved heuristics were found to perform better than the human derived heuristic, namely, the nearest neighbourhood heuristic, generally used to create initial solutions for the travelling salesman problem. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2987491.2987525 | SAICSIT |
Field | DocType | Citations |
Vehicle routing problem,Mathematical optimization,Extremal optimization,Computer science,Quadratic assignment problem,Combinatorial optimization,Travelling salesman problem,Heuristics,2-opt,Lin–Kernighan heuristic | Conference | 0 |
PageRank | References | Authors |
0.34 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nomzamo Ntombela | 1 | 0 | 0.34 |
| Nelishia Pillay | 2 | 237 | 33.72 |