Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2013, Vol. 14 Issue (8): 612-622    DOI: 10.1631/jzus.C1300005
    
A membrane-inspired algorithm with a memory mechanism for knapsack problems
Juan-juan He, Jian-hua Xiao, Xiao-long Shi, Tao Song
Key Laboratory of Image Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China; The Logistics Research Center, Nankai University, Tianjin 300071, China
A membrane-inspired algorithm with a memory mechanism for knapsack problems
Juan-juan He, Jian-hua Xiao, Xiao-long Shi, Tao Song
Key Laboratory of Image Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China; The Logistics Research Center, Nankai University, Tianjin 300071, China
 全文: PDF 
摘要： 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.
关键词： Membrane algorithm;  Memory mechanism;  Knapsack problem    
Abstract: 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.
Key words: Membrane algorithm    Memory mechanism    Knapsack problem
收稿日期: 2013-01-03 出版日期: 2013-08-02
CLC:  TP301  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Juan-juan He
Jian-hua Xiao
Xiao-long Shi
Tao Song

引用本文:

Juan-juan He, Jian-hua Xiao, Xiao-long Shi, Tao Song. A membrane-inspired algorithm with a memory mechanism for knapsack problems. Front. Inform. Technol. Electron. Eng., 2013, 14(8): 612-622.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/jzus.C1300005    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2013/V14/I8/612

[1] Hamid Reza Boveiri. 基于渐进式蚁群优化的多处理器任务分配[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 498-510.
[2] Juan Yu, Pei-zhong Lu. AGCD：一种基于最大公因子逼近的鲁棒周期分析方法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(6): 466-473.
[3] Hamid Tabatabaee, Mohammad Reza Akbarzadeh-T, Naser Pariz. 非结构化异构多处理器系统中的动态任务调度建模[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(6): 423-434.
[4] Saeid Arish, Ali Amiri, Khadije Noori. FICA: fuzzy imperialist competitive algorithm[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(5): 363-371.
[5] Li-wei Huang, Gui-sheng Chen, Yu-chao Liu, De-yi Li. Enhancing recommender systems by incorporating social information[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(9): 711-721.
[6] Reza Rezaei, Thiam-kian Chiew, Sai-peck Lee. A review of interoperability assessment models[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(9): 663-681.
[7] Jorge A. Ruiz-Vanoye, Joaquín Pérez-Ortega, Rodolfo A. Pazos Rangel, Ocotlán Díaz-Parra, Héctor J. Fraire-Huacuja, Juan Frausto-Solís, Gerardo Reyes-Salgado, Laura Cruz-Reyes. Application of formal languages in polynomial transformations of instances between NP-complete problems[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(8): 623-633.
[8] Mo-fei Song, Zheng-xing Sun, Yan Zhang, Fei-qian Zhang. Synthesis of 3D models by Petri net[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(7): 521-529.
[9] Suiang-Shyan Lee, Ja-Chen Lin. An accelerated K-means clustering algorithm using selection and erasure rules[J]. Front. Inform. Technol. Electron. Eng., 2012, 13(10): 761-768.
[10] Ommolbanin Yousefi, Mirbahadorgholi Aryanezhad, Seyed Jafar Sadjadi, Arash Shahin. Developing a multi-objective, multi-item inventory model and three algorithms for its solution[J]. Front. Inform. Technol. Electron. Eng., 2012, 13(8): 601-612.
[11] Alireza Askarzadeh, Alireza Rezazadeh. [J]. Frontiers of Information Technology & Electronic Engineering, 2011, 12(8): 638-646.
[12] Wei Wang, Peng-tao Zhang, Ying Tan, Xin-gui He. An immune local concentration based virus detection approach[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(6): 443-454.
[13] Xi-chuan Zhou, Hai-bin Shen, Jie-ping Ye. Integrating outlier filtering in large margin training[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(5): 362-370.