A membrane-inspired approximate algorithm for traveling salesman problems

This paper proposes a membrane-inspired approximate algorithm to solve traveling salesman problems, which is a well-known and extensively studied NP-complete combinatorial optimization problem. The algorithm combines P systems with ant colony optimization, called ACOPS. ACOPS uses the pheromone model and pheromone update rules defined by ant colony optimization algorithms, and the hierarchical membrane structure and transformation/communication rules of P systems. First, the parameter setting of ACOPS is discussed. Second, extensive experiments are conducted and statistical analysis are investigated. It is shown that ACOPS is superior to Nishida's membrane algorithms and its counterpart ant colony optimization algorithms, in terms of the quality of solutions and the number of function evaluations.