MEATSP: A Membrane Evolutionary Algorithm for Solving TSP

Abstract

In recent years, heuristic intelligent algorithms have achieved rapid development in solving combinatorial optimization problems. Travelling salesman problem(TSP) is one of the classical NP-hard problems in combinatorial optimization, and it needs for more accurate and faster algorithms. Combining heuristic algorithm and cell-like P system, this article proposes a membrane evolutionary algorithm for solving TSP(MEATSP). MEATSP abstracts the behaviors of biological cells such as fusion, division, cytolysis and selection into operators, and obtains the optimal solution of the problem through the evolution of membrane structure and objects within the membrane. Experiments on TSPLIB data sets show that the proposed algorithm performs well in both optimal solution and average residual, and it has strong stability when solving TSP with different scales.

Keywords

• Membrane evolutionary algorithm
• heuristic intelligent
• TSP
• membrane computing