A Carnivorous Plant Algorithm With Heuristic Decoding Method for Traveling Salesman Problem

Abstract

The traveling salesman problem (TSP) is one of the most extensively studied problems in the combinatorial optimization area and still presents unsolved challenges due to its NP-hard attribute. Although many real-coded algorithms are available for TSP, they still have some performance challenges in the switch from continuous space to discrete space and perform at low convergence speed. This paper proposes a real-coded carnivorous plant algorithm with a heuristic decoding method (CPA-HDM) to solve the traveling salesman problem (TSP), which exhibits good convergence speed and solution accuracy. In this improved method, a new heuristic decoding method (HDM) is designed, which helps to map continuous variables to discrete ones without losing information, maintain population diversity, and enhance the solution quality after decoding. To balance the algorithm’s search capability and enhance the probability of preferable individuals generated, an adaptive attraction probability (AAP), an improved growth model of carnivorous plants (IGMOCP), and a position update method of prey (IPUMOP) are developed. Aiming to reduce the probability of premature and prevent search stagnation, an improved reproduction strategy (IRS) and an adaptive combination perturbation are reconstructed. Finally, a local search algorithm is employed to improve the exploitation capability. To verify its validation, CPA-HDM is compared with six algorithms, for solving 28 TSP instances. The simulation results and statistical analyses demonstrate the superior performance of the proposed algorithm.

Keywords

• Real-coded carnivorous plant algorithm
• traveling salesman problem
• heuristic decoding method
• adaptive combination perturbation