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 ControlSchool of AutomationHuazhong University of Science and Technology The Logistics Research CenterNankai University 

出 版 物：《Journal of Zhejiang University-Science C(Computers and Electronics)》 (浙江大学学报C辑（计算机与电子（英文版）)

年 卷 期：2013年第14卷第8期

页      面：612-622页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Project supported by the National Natural Science Foundation of China(Nos. 61033003, 91130034, 61100145, 60903105, and 61272071) the PhD Programs Foundation of the Ministry of Education of China(Nos. 20100142110072 and 2012014213008) the Natural Science Foundation of Hubei Province, China (No. 2011CDA027) 

主　　题：Membrane algorithm Memory mechanism Knapsack problem 

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