Nomzamo Ntombela
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.
- B. A. Alsalibi, M. B. Jelodar, and I. Venkat. A comparative study between the nearest neighbour and genetic algorithms: A revisit to the traveling salesman problem. International Journal of Computer Science and Electronics Engineering, 34--38, 2013.Google Scholar
- M. Bader-El-Den, R. Poli, and S. Fatima. Evolving timetabling heuristics using grammar-based genetic programming hyper-heuristic framework. Memetic Computing, 1:205--219, 2009.Google ScholarCross Ref
- J. Branke, S. Nguyen, C. W. Pickardt, and M. Zhang. Automated design of production scheduling heuristics: A review. IEEE Transactions on Evolutionary Computaiton, 20(1):110--124, February 2016.Google ScholarCross Ref
- M. Hyde. A Genetic Programming Hyper-Heuristic Approach to Automated Packing. PhD thesis, School of Computer Science, University of Nottingham, March 2010.Google Scholar
- F. A. Karkory and A. A. Abudalmola. Implementation of heuristics for solving travelling salesman problem using nearest neighbour and minimum spanning tree algorithms. International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering, 7(10):1524--1534, 2013.Google Scholar
- J. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection, volume 1st. MIT, 1992. Google ScholarDigital Library
- G. Laporte. The travelling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59:231--247, 1992.Google ScholarCross Ref
- N. Pillay. Evolving construction heuristics for the curriculum based university course timetabling problem. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC '16), pages 4437--4443. IEEE, 2016.Google ScholarCross Ref
- G. Reinelt. Tsplib 95. http://comopt.ifi.uniheidelberg.de/software/TSPLIB95/tsp95.pdf, 1995.Google Scholar
- K. Sim and E. Hart. A combined generative and selective hyper-heuristic for the vehicle routing problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '16), pages 1093--1100. ACM, 2016. Google ScholarDigital Library
- G. Skorobohatyj. Vlsi benchmark set. http://elib.zib.de/pub/mptestdata/tsp/tsplib/tsp/index.html, June 1995.Google Scholar
Recommendations
Generating Human-readable Algorithms for the Travelling Salesman Problem using Hyper-Heuristics
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary ComputationHyper-heuristics search the space of heuristics and metaheuristics, so that it can generate high-quality algorithms. It is a growing area of interest in the research community. Algorithms have been constructed iteratively using "templates of operations" ...
Discrete symbiotic organisms search algorithm for travelling salesman problem
The objective is to evaluate the efficiency of DSOS algorithm to solve TSP.To verify the performance of the DSOS, using several benchmark instances from the TSPLIB.Experimental results show that DSOS competes favourably with other existing techniques. A ...
The effect of construction heuristics on the performance of a genetic algorithm for the school timetabling problem
SAICSIT '11: Proceedings of the South African Institute of Computer Scientists and Information Technologists Conference on Knowledge, Innovation and Leadership in a Diverse, Multidisciplinary EnvironmentThis paper examines the effect of using construction heuristics on the evolutionary process for the domain of school timetabling. The paper firstly presents a genetic algorithm to solve the school timetabling problem. the paper compares the performance ...
Comments