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 em-pirical 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 net-work 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.

A membrane-inspired algorithm with a memory mechanism for knapsack problems

Membrane algorithms are a class of distributed and parallel algorithms inspired by the structure and behavior of living cells. Many attractive features of living cells have already been abstracted as operators to improve the performance of algorithms. In this work, inspired by the function of biological neuron cells storing information, we consider a memory mechanism by introducing memory modules into a membrane algorithm. The framework of the algorithm consists of two kinds of modules (computation modules and memory modules), both of which are arranged in a ring neighborhood topology. They can store and process information, and exchange information with each other. We test our method on a knapsack problem to demonstrate its feasibility and effectiveness. During the process of approaching the optimum solution, feasible solutions are evolved by rewriting rules in each module, and the information transfers according to directions defined by communication rules. Simulation results showed that the performance of membrane algorithms with memory cells is superior to that of algorithms without memory cells for solving a knapsack problem. Furthermore, the memory mechanism can prevent premature convergence and increase the possibility of finding a global solution.

Evolutionary algorithm based on dynamical structure of membrane systems in uncertain environments

In this paper, a new evolutionary algorithm based on a membrane system is proposed to solve the dynamic or uncertain optimization problems. The proposed algorithm employs objects, a dynamical membrane structure and several reaction rules of the membrane systems. The object represents a candidate solution of the optimization problems. The dynamical structure consists of the nested membranes where a skin membrane contains several membranes, which is useful for the proposed algorithm that finds optimal solutions. The reaction rules are designed to locate and track the optimal solutions of the dynamic optimization problems （DOPs）, which are inspired by processing the chemical compounds in the region of cellular membranes. Experimental study is conducted based on the moving peaks benchmark to evaluate the performance of the proposed algorithm in comparison with three state-of-the-art dynamic optimization algorithms. The results indicate the proposed algorithm is effective to solve the DOPs.