Article

Article title HYBRID APPROACH FOR TRAVELLING SALESMAN PROBLEM
Authors A.V. Martinov, V.M. Kureichik
Section SECTION I. MODELING AND DESIGN
Month, Year 04, 2015 @en
Index UDC 004.023
DOI
Abstract The purpose of this work is to develop an effective hybrid method for solving the traveling salesman problem based on evolutionary and swarm techniques. Ant colony optimization and genetic algorithms are alternatives for solving discrete optimization problems. Genetic algorithm is a heuristic search algorithm used for solving optimization problems and modeling by random selection, combinations and variations of the unknown parameters using mechanisms similar to natural selection in nature, and the ant colony optimization, in turn, uses a decentralized selforganizing behavioral tools of ant colony which search the optimal route in the graph model. This paper presents a combination study for genetic algorithm and ant colony optimization applied in the travelling salesman problem. This hybridization is not only successively use of genetic algorithm and ant colony optimization, but also integrating the genetic information in ant colony optimization selection path rule. The genetic algorithm operators used for recombination of candidate solutions obtained in the course of the ant colony optimization algorithm. A heuristic evaluation of the solutions found by agents of ant algorithm to further their selection genetic algorithm is presented. In the course of this work was developed computer programs that implements the algorithm described above. A comparison of the test results and the hybrid ant algorithms on international benchmarks is presented. The results obtained in the experiments showed that hybrid algorithm searches solution higher quality than the conventional ant algorithm.

Download PDF

Keywords Ant colony optimization; genetic algorithm; swarm intelligence; traveling salesman problem; discrete optimization.
References 1. Dorigo M., Stutzle T. Ant Colony Optimization, Bradford Books, 2004.
2. Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem, BioSystems, July 1997, Vol. 43, No. 2, pp. 73-81.
3. Hahsler M., Hornik K. TSP – Infrastructure for the Traveling Salesperson Problem, Journal of Scientific Software, 2007, Vol. 32, Issue 2, pp. 1-21.
4. Paschos V., Monnot J., Toulouse S. The travelling salesman problem and its variations, Paradigms of Combinatorial Optimization, 2014, pp. 173-214.
5. Boroznov V.O. Issledovanie resheniya zadachi kommivoyazhera [Study on the solution of traveling salesman problem], Vestnik Astrakhanskogo gosudarstvennogo tekhnicheskogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika [Vestnik of Astrakhan State Technical University. Control, computer engineering and computer science], 2009, pp. 147-151.
6. Kazharov A.A. Kureychik V.M. Murav'inye algoritmy dlya resheniya transportnykh zadach [Ant algorithms for the solution of transport problems], Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy upravleniya [Journal of Computer and Systems Sciences International], 2010, No. 1, pp. 32-45.
7. Shtovba D.S. Murav'inye algoritmy: teoriya i primenenie [Ant algorithms: theory and application], Matematika v prilozheniyakh [Mathematics in applications], 2004, pp. 70-75.
8. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning, USA: Addison-Wesley Publishing Company, Inc., 1989.
9. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2006, 320 p.
10. Goldberg D.E., Lingle R. Alleles, Loci, and the Traveling Salesman Problem, Proceedings of the First International Conference on Genetic Algorithms and Their Application, 1985, pp. 154-159.
11. Chernyshev Yu.O., Basova A.V., Poluyan A.Yu. Reshenie zadach transportnogo tipa geneticheskimi algoritmami [The solution of problems of transportation type of genetic algorithms]. Rostov-on-Don: Izd-vo YuFUGOU, 2008, 73 p.
12. Kumar N., Karambir, Kumar R. A comparative analysis of PMX, CX and OX Crossover operators for solving traveling salesman problem, International Journal of Latest Research in Science and Technology, 2012, pp. 98-101.
13. Kureychik V.M., Lebedev B.K., Lebedev O.K. Poiskovaya adaptatsiya: teoriya i praktika [Search adaptation: theory and practice]. Moscow: Fizmatlit, 2006, 272 p. ISBN 5-9221-0749-6.
14. Abdoun O., Abouchakaba J, Tajani C. Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem, CoRR, Vol. abs/1203.3099, 2012, pp. 66-77.
15. Parametry i klassy protokolov marshrutizatsii [The parameters and classes of routing protocols]. Available at: http://skif.bas-net.by/bsuir/base/node360.html (Accessed 23 February 2015).
16. TSPLIB. Available at: http://www.iwr.uni-heidelberg.de/groups/comopt/ software/TSPLIB95/tsp/ (Accessed 23 February 2015).
17. Ciba M., Sekaj I. Ant colony optimization with re-initialization, Automation, Control and Intelligent Systems, 2013, No. 1 (3), pp. 53-66.
18. Dai Q., Junzhong J., Chunnian L., An effective initialization strategy of pheromone for ant colony optimization, Bio-Inspired Computing, 2009.
19. Zhu Q.B., Yang Z.J. An Ant Colony Optimization Algorithm Based on Mutation and Dynamic Pheromone Updating, Journal of Software, 2004, No. 2 (15), pp. 185-192.
20. Solomon M.M. Algorithms for the vehicle routing and scheduling problems with time windows constraints, Operations Research, 1987, 35, pp. 254-265.

Comments are closed.