The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem
The traveling salesman problem (TSP) widely exists in real-life practical applications; it is a topic that is under investigation and presents unsolved challenges. The existing solutions still have some challenges in convergence speed, iteration time, and avoiding local optimization. In this work, a...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-09-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/18/3249 |
| _version_ | 1827659227238236160 |
|---|---|
| author | Pan-Li Zhang Xiao-Bo Sun Ji-Quan Wang Hao-Hao Song Jin-Ling Bei Hong-Yu Zhang |
| author_facet | Pan-Li Zhang Xiao-Bo Sun Ji-Quan Wang Hao-Hao Song Jin-Ling Bei Hong-Yu Zhang |
| author_sort | Pan-Li Zhang |
| collection | DOAJ |
| description | The traveling salesman problem (TSP) widely exists in real-life practical applications; it is a topic that is under investigation and presents unsolved challenges. The existing solutions still have some challenges in convergence speed, iteration time, and avoiding local optimization. In this work, a new method is introduced, called the discrete carnivorous plant algorithm (DCPA) with similarity elimination to tackle the TSP. In this approach, we use a combination of six steps: first, the algorithm redefines subtraction, multiplication, and addition operations, which aims to ensure that it can switch from continuous space to discrete space without losing information; second, a simple sorting grouping method is proposed to reduce the chance of being trapped in a local optimum; third, the similarity-eliminating operation is added, which helps to maintain population diversity; fourth, an adaptive attraction probability is proposed to balance exploration and the exploitation ability; fifth, an iterative local search (ILS) strategy is employed, which is beneficial to increase the searching precision; finally, to evaluate its performance, DCPA is compared with nine algorithms. The results demonstrate that DCPA is significantly better in terms of accuracy, average optimal solution error, and iteration time. |
| first_indexed | 2024-03-09T23:16:34Z |
| format | Article |
| id | doaj.art-5be8600e7b3b4243913e7c6915a6e86e |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T23:16:34Z |
| publishDate | 2022-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-5be8600e7b3b4243913e7c6915a6e86e2023-11-23T17:35:16ZengMDPI AGMathematics2227-73902022-09-011018324910.3390/math10183249The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman ProblemPan-Li Zhang0Xiao-Bo Sun1Ji-Quan Wang2Hao-Hao Song3Jin-Ling Bei4Hong-Yu Zhang5College of Engineering, Northeast Agricultural University, Harbin 150030, ChinaCollege of Engineering, Northeast Agricultural University, Harbin 150030, ChinaCollege of Engineering, Northeast Agricultural University, Harbin 150030, ChinaCollege of Engineering, Northeast Agricultural University, Harbin 150030, ChinaCollege of Engineering, Northeast Agricultural University, Harbin 150030, ChinaCollege of Engineering, Northeast Agricultural University, Harbin 150030, ChinaThe traveling salesman problem (TSP) widely exists in real-life practical applications; it is a topic that is under investigation and presents unsolved challenges. The existing solutions still have some challenges in convergence speed, iteration time, and avoiding local optimization. In this work, a new method is introduced, called the discrete carnivorous plant algorithm (DCPA) with similarity elimination to tackle the TSP. In this approach, we use a combination of six steps: first, the algorithm redefines subtraction, multiplication, and addition operations, which aims to ensure that it can switch from continuous space to discrete space without losing information; second, a simple sorting grouping method is proposed to reduce the chance of being trapped in a local optimum; third, the similarity-eliminating operation is added, which helps to maintain population diversity; fourth, an adaptive attraction probability is proposed to balance exploration and the exploitation ability; fifth, an iterative local search (ILS) strategy is employed, which is beneficial to increase the searching precision; finally, to evaluate its performance, DCPA is compared with nine algorithms. The results demonstrate that DCPA is significantly better in terms of accuracy, average optimal solution error, and iteration time.https://www.mdpi.com/2227-7390/10/18/3249discrete carnivorous plant algorithmtraveling salesman problemsimple sorting groupingsimilarity eliminationiterative local search |
| spellingShingle | Pan-Li Zhang Xiao-Bo Sun Ji-Quan Wang Hao-Hao Song Jin-Ling Bei Hong-Yu Zhang The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem Mathematics discrete carnivorous plant algorithm traveling salesman problem simple sorting grouping similarity elimination iterative local search |
| title | The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem |
| title_full | The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem |
| title_fullStr | The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem |
| title_full_unstemmed | The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem |
| title_short | The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem |
| title_sort | discrete carnivorous plant algorithm with similarity elimination applied to the traveling salesman problem |
| topic | discrete carnivorous plant algorithm traveling salesman problem simple sorting grouping similarity elimination iterative local search |
| url | https://www.mdpi.com/2227-7390/10/18/3249 |
| work_keys_str_mv | AT panlizhang thediscretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT xiaobosun thediscretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT jiquanwang thediscretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT haohaosong thediscretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT jinlingbei thediscretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT hongyuzhang thediscretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT panlizhang discretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT xiaobosun discretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT jiquanwang discretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT haohaosong discretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT jinlingbei discretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem AT hongyuzhang discretecarnivorousplantalgorithmwithsimilarityeliminationappliedtothetravelingsalesmanproblem |