An adaptive membrane algorithm for solving combinatorial optimization problems

Membrane algorithms (MAs), which inherit from P systems, constitute a new parallel and distribute framework for approximate computation. In the paper, a membrane algorithm is proposed with the improvement that the involved parameters can be adaptively chosen. In the algorithm, some membranes can evolve dynamically during the computing process to specify the values of the requested parameters. The new algorithm is tested on a well-known combinatorial optimization problem, the travelling salesman problem. The empirical evidence suggests that the proposed approach is efficient and reliable when dealing with 11 benchmark instances, particularly obtaining the best of the known solutions in eight instances. Compared with the genetic algorithm, simulated annealing algorithm, neural network and a fine-tuned non-adaptive membrane algorithm, our algorithm performs better than them. In practice, to design the airline network that minimize the total routing cost on the CAB data with twenty-five US cities, we can quickly obtain high quality solutions using our algorithm.