Genetic Algorithms for the Travelling Salesman Problem: A Crossover Comparison

Tariq Alzyadat; Mohammad Yamin; Girija Chetty

doi:10.1007/s41870-019-00377-9

Genetic Algorithms for the Travelling Salesman Problem: A Crossover Comparison

Tariq Alzyadat, Mohammad Yamin, Girija Chetty

Information, Technology (IT) & Systems

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

Abstract

This paper addresses an application of genetic algorithms (GA) for solving the travelling salesman problem (TSP), it compares the results of implementing two different types of two-point (1 order) genes crossover, the static and the dynamic approaches, which are used to produce new offspring. By changing three factors; the number of cities, the number of generations and the population size, the goal is to show which approach is better in terms of finding the optimal solution (the shortest path) in as short time as possible as a result of these changes. Besides, it will explore the effect of changing the above factors on finding the optimal solution.

Original language	English
Pages (from-to)	209-213
Number of pages	5
Journal	International Journal of Information Technology
Volume	12
Issue number	1
DOIs	https://doi.org/10.1007/s41870-019-00377-9
Publication status	Published - Mar 2020
Event	11th INDIACom: 2017 4th International Conference on Computing for Sustainable Global Development - Bharati Vidyapeeth's Institute of Computer Applications and Management (BVICAM), New Delhi, India Duration: 1 Mar 2017 → 3 Mar 2017 Conference number: 40353

Access to Document

10.1007/s41870-019-00377-9

https://www.bvicam.ac.in/news/INDIACom%202017%20Proceedings/Main/papers/270.pdf

Cite this

@article{8a75fae9f20340359a02840a839c54fe,

title = "Genetic Algorithms for the Travelling Salesman Problem: A Crossover Comparison",

abstract = "This paper addresses an application of genetic algorithms (GA) for solving the travelling salesman problem (TSP), it compares the results of implementing two different types of two-point (1 order) genes crossover, the static and the dynamic approaches, which are used to produce new offspring. By changing three factors; the number of cities, the number of generations and the population size, the goal is to show which approach is better in terms of finding the optimal solution (the shortest path) in as short time as possible as a result of these changes. Besides, it will explore the effect of changing the above factors on finding the optimal solution.",

keywords = "Dynamic crossover, Genetic algorithms, Permutation, Static crossover, Travelling salesman problem",

author = "Tariq Alzyadat and Mohammad Yamin and Girija Chetty",

note = "Funding Information: We thank the Statistical consultant Mr. Julio Romero for his assistance in the statistical analysis of the data in this experiment. Publisher Copyright: {\textcopyright} 2019, Bharati Vidyapeeth's Institute of Computer Applications and Management. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 11th INDIACom : 2017 4th International Conference on Computing for Sustainable Global Development ; Conference date: 01-03-2017 Through 03-03-2017",

year = "2020",

month = mar,

doi = "10.1007/s41870-019-00377-9",

language = "English",

volume = "12",

pages = "209--213",

journal = "International Journal of Information Technology ",

issn = "2511-2112",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Genetic Algorithms for the Travelling Salesman Problem

T2 - 11th INDIACom

AU - Alzyadat, Tariq

AU - Yamin, Mohammad

AU - Chetty, Girija

N1 - Conference code: 40353

PY - 2020/3

Y1 - 2020/3

N2 - This paper addresses an application of genetic algorithms (GA) for solving the travelling salesman problem (TSP), it compares the results of implementing two different types of two-point (1 order) genes crossover, the static and the dynamic approaches, which are used to produce new offspring. By changing three factors; the number of cities, the number of generations and the population size, the goal is to show which approach is better in terms of finding the optimal solution (the shortest path) in as short time as possible as a result of these changes. Besides, it will explore the effect of changing the above factors on finding the optimal solution.

AB - This paper addresses an application of genetic algorithms (GA) for solving the travelling salesman problem (TSP), it compares the results of implementing two different types of two-point (1 order) genes crossover, the static and the dynamic approaches, which are used to produce new offspring. By changing three factors; the number of cities, the number of generations and the population size, the goal is to show which approach is better in terms of finding the optimal solution (the shortest path) in as short time as possible as a result of these changes. Besides, it will explore the effect of changing the above factors on finding the optimal solution.

KW - Dynamic crossover

KW - Genetic algorithms

KW - Permutation

KW - Static crossover

KW - Travelling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=85089740417&partnerID=8YFLogxK

U2 - 10.1007/s41870-019-00377-9

DO - 10.1007/s41870-019-00377-9

M3 - Article

SN - 2511-2112

VL - 12

SP - 209

EP - 213

JO - International Journal of Information Technology

JF - International Journal of Information Technology

IS - 1

Y2 - 1 March 2017 through 3 March 2017

ER -

Genetic Algorithms for the Travelling Salesman Problem: A Crossover Comparison

Abstract

Access to Document

Other files and links

Fingerprint

Cite this