Please wait a minute...
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
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

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 wordsMembrane algorithm      Memory mechanism      Knapsack problem     
Received: 03 January 2013      Published: 02 August 2013
CLC:  TP301  
Cite this article:

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.

URL:

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


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.

关键词: Membrane algorithm,  Memory mechanism,  Knapsack problem 
[1] Hamid Reza Boveiri. An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 498-510.
[2] Juan Yu, Pei-zhong Lu. AGCD: a robust periodicity analysis method based on approximate greatest common divisor[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(6): 466-473.
[3] Hamid Tabatabaee, Mohammad Reza Akbarzadeh-T, Naser Pariz. Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems[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. A new artificial bee swarm algorithm for optimization of proton exchange membrane fuel cell model parameters[J]. Front. Inform. Technol. Electron. Eng., 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.