The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem

Abstract

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.

Keywords

• discrete carnivorous plant algorithm
• traveling salesman problem
• simple sorting grouping
• similarity elimination
• iterative local search