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

Research Projects

Organizational Units

Organizational Unit
Computer Engineering
(1998)
The Atılım University Department of Computer Engineering was founded in 1998. The department curriculum is prepared in a way that meets the demands for knowledge and skills after graduation, and is subject to periodical reviews and updates in line with international standards. Our Department offers education in many fields of expertise, such as software development, hardware systems, data structures, computer networks, artificial intelligence, machine learning, image processing, natural language processing, object based design, information security, and cloud computing. The education offered by our department is based on practical approaches, with modern laboratories, projects and internship programs. The undergraduate program at our department was accredited in 2014 by the Association of Evaluation and Accreditation of Engineering Programs (MÜDEK) and was granted the label EUR-ACE, valid through Europe. In addition to the undergraduate program, our department offers thesis or non-thesis graduate degree programs (MS).

Journal Issue

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

Volume

Issue

Start Page

End Page