Solving Travelling Salesman Problem: a Hybrid Optimization Algorithm
No Thumbnail Available
Date
2019
Authors
Sozen,N.
Sözen, Nergiz
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers Inc.
Open Access Color
OpenAIRE Downloads
OpenAIRE Views
Abstract
There are numerous selection, crossover, and mutation methods suggested in the literature when it comes to genetic algorithms. However, behavior of each different method changes when used in combination with other methods. In this paper, a brief and clear explanation of many popular selection, crossover and mutation techniques has been presented and the combination of various optimization methods using Genetic Algorithm has been implemented to generate a hybrid algorithm as a solution to the well-known NP-hard Travelling Salesman Problem (TSP). In this study, 10 different hybrid algorithms are implemented and experimented. Each of these algorithms are formed combining two different selection methods, 3 different crossover methods and 2 different mutation methods. Each of the ten different algorithms have been implemented and their performance have been tested with two different datasets to understand which algorithm outperforms the others. Performance of the combination of various methods have been presented and the findings illustrated that combination of specific crossover, selection and mutation methods outperform in terms of the ultimate optimal result. The results have been compared with the algorithms in the literature that combines Roulette Wheel Selection (RWS), and Stochastic Universal Selection (SUS); each implemented in combination with Partially Mapped Crossover, Cycle Crossover, and Ordered Crossover. Each combination has been tried on various population sizes, mutation and crossover rates. It is found that combining specific selection, mutation and crossover methods can outperform the methods suggested in the literature in equal circumstances-when the same population size, generation size, mutation and crossover rates are used. © 2019 IEEE.
Description
Keywords
Genetic algorithms, hybrid algorithm, natural computing, travelling salesman problem, TSP
Turkish CoHE Thesis Center URL
Fields of Science
Citation
2
WoS Q
Scopus Q
Source
1st International Informatics and Software Engineering Conference: Innovative Technologies for Digital Transformation, IISEC 2019 - Proceedings -- 1st International Informatics and Software Engineering Conference, IISEC 2019 -- 6 November 2019 through 7 November 2019 -- Ankara -- 157111