数学物理学报(英文版) ›› 2014, Vol. 34 ›› Issue (5): 1377-1394.doi: 10.1016/S0252-9602(14)60090-4

• 论文 • 上一篇    下一篇

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, Wuhan 430074, China； The Research Center of Logistics, Nankai University, Tianjin 300071, China； School of Information Science and Technology, Chengdu University, Chengdu 610106, China
  • 收稿日期:2013-10-23 修回日期:2014-01-06 出版日期:2014-09-20 发布日期:2014-09-20
  • 通讯作者: 肖建华，jhxiao@nankai.edu.cn E-mail:hejuanjuan1117@gmail.com；jhxiao@nankai.edu.cn；zshao@cdu.edu.cn
  • 基金资助:

    This work was supported by the National Natural Science Foundation of China (60903105, 61373066, 61309015, 61033003 and 61320106005).

AN ADAPTIVE MEMBRANE ALGORITHM FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS

 HE Juan-Juan, XIAO Jian-Hua*, SHAO Ze-Hui   

  1. Key Laboratory of Image Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China； The Research Center of Logistics, Nankai University, Tianjin 300071, China； School of Information Science and Technology, Chengdu University, Chengdu 610106, China
  • Received:2013-10-23 Revised:2014-01-06 Online:2014-09-20 Published:2014-09-20
  • Contact: XIAO Jian-Hua，jhxiao@nankai.edu.cn E-mail:hejuanjuan1117@gmail.com；jhxiao@nankai.edu.cn；zshao@cdu.edu.cn
  • Supported by:

    This work was supported by the National Natural Science Foundation of China (60903105, 61373066, 61309015, 61033003 and 61320106005).

PDF (PC)

1340

摘要：

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

Abstract:

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.

Key words: membrane algorithm, adaptation, travelling salesman problem

中图分类号: 

  • 90C08
版权所有 © 《数学物理学报(英文版)》杂志社
地址：武汉市71010号信箱(430071)　电话: 027-87199206(中文版)　027-87199087(英文版)
E-mail: actams@apm.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发