Performance analysis of the partial use of a local optimization operator on the genetic algorithm for the Travelling Salesman Problem

• Authors: Milan Djordjevic , Marko Grgurovič , Andrej Brodnik

Abstracts

EN

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

EN

genetic algorithm; travelling salesman problem; hybridization; optimization; grafted genetic algorithm

• Publisher: Sciendo
• Journal: Business Systems Research Journal
• Year: 2012
• Volume: 3
• Issue: 1
• Pages: 14-22

Dates

published

2012-06-01

online

2012-09-17

Contributors

author

Milan Djordjevic

• Department of Information Science and Technology, University of Primorska, Koper, Slovenia

author

Marko Grgurovič

• Department of Information Science and Technology, University of Primorska, Koper, Slovenia

author

Andrej Brodnik

• Department of Information Science and Technology, University of Primorska, Koper, Slovenia

References

• Applegate, D., Bixby, R., Chvátal, V., Cook, W. (2001), "TSP cuts which do not conform to the template paradigm", in Jünger, M., Naddef, D., (Eds), Computational Combinatorial Optimization, Springer, London, pp. 261-303.
• Bosman, P., Thierens, D. (1999), "On the modelling of evolutionary algorithms", in Postma, E., Gyssens, M. (Eds), Proceedings of the 11th Belgium-Netherlands Conference on Artificial Intelligence, BNAIC, Vaeshartelt, pp. 67-74.
• Djordjevic, M., Brodnik, A. (2011), "Quantitative analysis of separate and combined performance of local searcher and genetic algorithm", in Proceedings of the 33rd International Conference on Information Technology Interfaces, ITI2011, Faculty of Mathematics, Natural Sciences & Information Technologies, University of Primorska, Koper, pp. 515-520.
• Djordjevic, M., Tuba, M., Djordjevic, B. (2009), "Impact of Grafting a 2-opt Algorithm Based Local Searcher Into the Genetic Algorithm", in Proceedings of the 9th WSEAS international conference on Applied informatics and communications, World Scientific and Engineering Academy and Society (WSEAS), Stevens Point, pp. 485-490.
• Dorigo, M., Gambardella, L. M. (1997), "Ant colony system: A cooperative learning approach to the traveling salesman problem", IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66.
• Engels, C., Manthey, B. (2009), "Average-case approximation ratio of the 2-opt algorithm for the TSP", Operations Research Letters, Vol. 37, No. 2, pp. 83-84.[WoS]
• Freisleben, B., Merz, P. (1996), "New genetic local search operators for the traveling salesman problem", in Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, Springer, London, pp. 890-899.
• Garey, M. R., Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness, New York: WH Freeman & Co.
• Gutin, G., Punnen, A. P. (2002). The Traveling Salesman Problem and Its Variations, Dordrecht: Kluwer Academic Publishers.
• Hahsler, M., Hornik, K. (2007), "TSP-Infrastructure for the traveling salesperson problem", Journal of Statistical Software, Vol. 23, No. 2, pp. 1-21.
• Haupt, R. L., Haupt, S. E. (2004). Practical Genetic Algorithms, 2nd ed., New York: John Wiley & Sons.
• Helsgaun, K. (2000), "An effective implementation of the Lin-Kernighan traveling salesman heuristic", European Journal of Operational Research, Vol. 126, No. 1, pp. 106-130.
• Holland, J. (1975). Adaptation in natural and artificial systems, Ann Arbor: The University of Michigan Press.
• Hoos, H. H., Stützle, T. (2005). Stochastic local search: Foundations and applications, Waltham: Morgan Kaufmann.
• Merz, P., Freisleben, B. (2001), "Memetic algorithms for the traveling salesman problem", Complex Systems, Vol. 13, No. 4, pp. 297-345.
• Reinelt, G. (1991), "TSPLIB - A traveling salesman problem library", ORSA Journal on Computing, Vol. 3, No. 4, pp. 376-384.
• Sels, V., Vanhoucke, M. (2011), "A hybrid dual-population genetic algorithm for the single machine maximum lateness problem", in Merz, P., Hao, J. K., (Eds), Evolutionary Computation in Combinatorial Optimization, Springer, Berlin, pp. 14-25.

Identifiers

DOI

10.2478/v10305-012-0002-4