The oil drilling model and iterative deepening genetic annealing algorithm for the traveling salesman problem

• Main Authors: LAU, Hoong Chuin, XIAO, Fei
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2008
• Subjects: Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/240; https://ink.library.smu.edu.sg/context/sis_research/article/1239/viewcontent/OilDrillingModelTSP_2008_afv.pdf
• Institution: Singapore Management University

In this work, we liken the solving of combinatorial optimization problems under a prescribed computational budget as hunting for oil in an unexplored ground. Using this generic model, we instantiate an iterative deepening genetic annealing (IDGA) algorithm, which is a variant of memetic algorithms. Computational results on the traveling salesman problem show that IDGA is more effective than standard genetic algorithms or simulated annealing algorithms or a straightforward hybrid of them. Our model is readily applicable to solve other combinatorial optimization problems.