Performance analysis of the partial use of a local optimization operator on the genetic algorithm for the Travelling Salesman Problem
Grgurovič Marko and
Additional contact information
Brodnik Andrej: Department of Information Science and Technology, University of Primorska, Koper, Slovenia
Business Systems Research, 2012, vol. 3, issue 1, 14-22
Background: The Travelling Salesman Problem is an NP-hard problem in combinatorial optimization with a number of practical implications. There are many heuristic algorithms and exact methods for solving the problem. Objectives: In this paper we study the influence of hybridization of a genetic algorithm with a local optimizer on solving instances of the Travelling Salesman Problem. Methods/Approach: Our algorithm uses hybridization that occurs at various percentages of generations of a genetic algorithm. Moreover, we have also studied at which generations to apply the hybridization and hence applied it at random generations, at the initial generations, and at the last ones. Results: We tested our algorithm on instances with sizes ranging from 76 to 439 cities. On the one hand, the less frequent application of hybridization decreased the average running time of the algorithm from 14.62 sec to 2.78 sec at 100% and 10% hybridization respectively, while on the other hand, the quality of the solution on average deteriorated only from 0.21% till 1.40% worse than the optimal solution. Conclusions: In the paper we have shown that even a small hybridization substantially improves the quality of the result. Moreover, the hybridization in fact does not deteriorate the running time too much. Finally, our experiments show that the best results are obtained when hybridization occurs in the last generations of the genetic algorithm.
Keywords: genetic algorithm; travelling salesman problem; hybridization; optimization; grafted genetic algorithm (search for similar items in EconPapers)
References: View complete reference list from CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:bit:bsrysr:v:3:y:2012:i:1:p:14-22
Access Statistics for this article
Business Systems Research is currently edited by Mirjana Pejić Bach
More articles in Business Systems Research from Sciendo
Bibliographic data for series maintained by Peter Golla ().