AN ADAPTIVE MEMBRANE ALGORITHM FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS  

作　　者：贺娟娟 肖建华 邵泽辉 

机构地区：[1]Key Laboratory of Image Processing and Intelligent Control, School of Automation,Huazhong University of Science and Technology [2]The Research Center of Logistics, Nankai University [3]School of Information Science and Technology, Chengdu University

出　　处：《Acta Mathematica Scientia》2014年第5期1377-1394,共18页数学物理学报（B辑英文版）

基　　金：supported by the National Natural Science Foundation of China(60903105,61373066,61309015,61033003 and 61320106005)

摘　　要：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.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.

关 键 词：membrane algorithm ADAPTATION travelling salesman problem 

分 类 号：O224[理学—运筹学与控制论] O242.23[理学—数学]