A Hybrid Cellular Genetic Algorithm for the Traveling Salesman Problem

Yanlan Deng, Juxia Xiong and Qiuhong Wang

Mathematical Problems in Engineering, 2021, vol. 2021, 1-16

Abstract:

The traveling salesman problem (TSP), a typical non-deterministic polynomial (NP) hard problem, has been used in many engineering applications. Genetic algorithms are useful for NP-hard problems, especially the traveling salesman problem. However, it has some issues for solving TSP, including quickly falling into the local optimum and an insufficient optimization precision. To address TSP effectively, this paper proposes a hybrid Cellular Genetic Algorithm with Simulated Annealing (SA) Algorithm (SCGA). Firstly, SCGA is an improved Genetic Algorithm (GA) based on the Cellular Automata (CA). The selection operation in SCGA is performed according to the state of the cell. Secondly, SCGA, combined with SA, introduces an elitist strategy to improve the speed of the convergence. Finally, the proposed algorithm is tested against 13 standard benchmark instances from the TSPLIB to confirm the performance of the three cellular automata rules. The experimental results show that, in most instances, the results obtained by SCGA using rule 2 are better and more stable than the results of using rule 1 and rule 3. At the same time, we compared the experimental results with GA, SA, and Cellular Genetic Algorithm (CGA) to verify the performance of SCGA. The comparison results show that the distance obtained by the proposed algorithm is shortened by a mean of 7% compared with the other three algorithms , which is closer to the theoretical optimal value and has good robustness.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2021/6697598.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2021/6697598.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:6697598

DOI: 10.1155/2021/6697598

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().