Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming
The traveling-salesman problem can be regarded as an NP-hard problem. To better solve the best solution, many heuristic algorithms, such as simulated annealing, ant-colony optimization, tabu search, and genetic algorithm, were used. However, these algorithms either are easy to fall into local optimi...
Main Authors: | , , , , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2018-12-01
|
Series: | Information |
Subjects: | |
Online Access: | http://www.mdpi.com/2078-2489/10/1/7 |
_version_ | 1798043159075225600 |
---|---|
author | Ai-Hua Zhou Li-Peng Zhu Bin Hu Song Deng Yan Song Hongbin Qiu Sen Pan |
author_facet | Ai-Hua Zhou Li-Peng Zhu Bin Hu Song Deng Yan Song Hongbin Qiu Sen Pan |
author_sort | Ai-Hua Zhou |
collection | DOAJ |
description | The traveling-salesman problem can be regarded as an NP-hard problem. To better solve the best solution, many heuristic algorithms, such as simulated annealing, ant-colony optimization, tabu search, and genetic algorithm, were used. However, these algorithms either are easy to fall into local optimization or have low or poor convergence performance. This paper proposes a new algorithm based on simulated annealing and gene-expression programming to better solve the problem. In the algorithm, we use simulated annealing to increase the diversity of the Gene Expression Programming (GEP) population and improve the ability of global search. The comparative experiments results, using six benchmark instances, show that the proposed algorithm outperforms other well-known heuristic algorithms in terms of the best solution, the worst solution, the running time of the algorithm, the rate of difference between the best solution and the known optimal solution, and the convergent speed of algorithms. |
first_indexed | 2024-04-11T22:45:41Z |
format | Article |
id | doaj.art-c32ac88ef10d4e5492e0422af224c4c6 |
institution | Directory Open Access Journal |
issn | 2078-2489 |
language | English |
last_indexed | 2024-04-11T22:45:41Z |
publishDate | 2018-12-01 |
publisher | MDPI AG |
record_format | Article |
series | Information |
spelling | doaj.art-c32ac88ef10d4e5492e0422af224c4c62022-12-22T03:58:46ZengMDPI AGInformation2078-24892018-12-01101710.3390/info10010007info10010007Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression ProgrammingAi-Hua Zhou0Li-Peng Zhu1Bin Hu2Song Deng3Yan Song4Hongbin Qiu5Sen Pan6Global Energy Interconnection Research Institute Co., Ltd., Beijing 102200, ChinaGlobal Energy Interconnection Research Institute Co., Ltd., Beijing 102200, ChinaGlobal Energy Interconnection Research Institute Co., Ltd., Beijing 102200, ChinaInstitute of Advanced Technology, Nanjing University of Posts and Telecommunications, Nanjing 230001, ChinaElectric Power Research Institute of State Grid Shanghai Municipal Electric Power Company, Shanghai 200437, ChinaGlobal Energy Interconnection Research Institute Co., Ltd., Beijing 102200, ChinaGlobal Energy Interconnection Research Institute Co., Ltd., Beijing 102200, ChinaThe traveling-salesman problem can be regarded as an NP-hard problem. To better solve the best solution, many heuristic algorithms, such as simulated annealing, ant-colony optimization, tabu search, and genetic algorithm, were used. However, these algorithms either are easy to fall into local optimization or have low or poor convergence performance. This paper proposes a new algorithm based on simulated annealing and gene-expression programming to better solve the problem. In the algorithm, we use simulated annealing to increase the diversity of the Gene Expression Programming (GEP) population and improve the ability of global search. The comparative experiments results, using six benchmark instances, show that the proposed algorithm outperforms other well-known heuristic algorithms in terms of the best solution, the worst solution, the running time of the algorithm, the rate of difference between the best solution and the known optimal solution, and the convergent speed of algorithms.http://www.mdpi.com/2078-2489/10/1/7graph traversal optimizationgene-expression programmingsimulated annealing algorithmtraveling-salesman problem |
spellingShingle | Ai-Hua Zhou Li-Peng Zhu Bin Hu Song Deng Yan Song Hongbin Qiu Sen Pan Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming Information graph traversal optimization gene-expression programming simulated annealing algorithm traveling-salesman problem |
title | Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming |
title_full | Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming |
title_fullStr | Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming |
title_full_unstemmed | Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming |
title_short | Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming |
title_sort | traveling salesman problem algorithm based on simulated annealing and gene expression programming |
topic | graph traversal optimization gene-expression programming simulated annealing algorithm traveling-salesman problem |
url | http://www.mdpi.com/2078-2489/10/1/7 |
work_keys_str_mv | AT aihuazhou travelingsalesmanproblemalgorithmbasedonsimulatedannealingandgeneexpressionprogramming AT lipengzhu travelingsalesmanproblemalgorithmbasedonsimulatedannealingandgeneexpressionprogramming AT binhu travelingsalesmanproblemalgorithmbasedonsimulatedannealingandgeneexpressionprogramming AT songdeng travelingsalesmanproblemalgorithmbasedonsimulatedannealingandgeneexpressionprogramming AT yansong travelingsalesmanproblemalgorithmbasedonsimulatedannealingandgeneexpressionprogramming AT hongbinqiu travelingsalesmanproblemalgorithmbasedonsimulatedannealingandgeneexpressionprogramming AT senpan travelingsalesmanproblemalgorithmbasedonsimulatedannealingandgeneexpressionprogramming |