A membrane-inspired algorithm with a memory mechanism for knapsack problems

Juan-juan HE; Jian-hua XIAO; Xiao-long SHI; Tao SONG

doi:10.1631/jzus.C1300005

Your Location：

Home >

Browse articles >

A membrane-inspired algorithm with a memory mechanism for knapsack problems

计算机与自动化 | Updated：2022-12-09

- A membrane-inspired algorithm with a memory mechanism for knapsack problems
- A membrane-inspired algorithm with a memory mechanism for knapsack problems
- 信息与电子工程前沿（英文） 2013年14卷第8期页码：612-622
- Affiliations：
  
  1.Key Laboratory of Image Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China
  2.The Logistics Research Center, Nankai University, Tianjin 300071, China
- Author bio：
  
  [ "Juan-juan HE, hejuanjuan1117@gmail.com" ]
  Tao SONG, songtao0608@hotmail.com
- Funds：
  
  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), and the Natural Science Foundation of Hubei Province, China (No. 2011CDA027)
- DOI：10.1631/jzus.C1300005
  中图分类号： TP301
- 收稿：2013-01-03，
  
  修回：2013-;7-12，
  
  纸质出版：2013-08
- Accepted：
Scan QR Code
A membrane-inspired algorithm with a memory mechanism for knapsack problems[J]. 信息与电子工程前沿（英文）, 2013,14(8):612-622.

Juan-juan HE, Jian-hua XIAO, Xiao-long SHI, et al. A membrane-inspired algorithm with a memory mechanism for knapsack problems[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(8): 612-622.
A membrane-inspired algorithm with a memory mechanism for knapsack problems[J]. 信息与电子工程前沿（英文）, 2013,14(8):612-622. DOI： 10.1631/jzus.C1300005.

Juan-juan HE, Jian-hua XIAO, Xiao-long SHI, et al. A membrane-inspired algorithm with a memory mechanism for knapsack problems[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(8): 612-622. DOI： 10.1631/jzus.C1300005.

摘要

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.

关键词

Keywords

references

K.H. Han , , , J.H. Kim . . Quantum-inspired evolutionary algorithm for a class of combinatorial optimization . . IEEE Trans. Evol. Comput. , , 2002 . . 6 ( ( 6 ): ): 580 - - 593 . . DOI: 10.1109/TEVC.2002.804320 http://doi.org/10.1109/TEVC.2002.804320 . .

T. Hey . . Quantum computing: an introduction . . Comput. Control Eng. J. , , 1999 . . 10 ( ( 3 ): ): 105 - - 142 . . DOI: 10.1049/cce:19990303 http://doi.org/10.1049/cce:19990303 . .

L. Huang , , , N. Wang . . An optimization algorithm inspired by membrane computing . . LNCS , , 2006 . . 4222 49 - - 52 . . DOI: 10.1007/11881223_7 http://doi.org/10.1007/11881223_7 . .

L. Huang , , , X. He , , , N. Wang , , , Y. Xie . . P systems based multi-objective optimization algorithm . . Progr. Nat. Sci. , , 2007 . . 17 ( ( 4 ): ): 458 - - 465 . . DOI: 10.1080/10020070708541023 http://doi.org/10.1080/10020070708541023 . .

L. Huang , , , I.H. Suh , , , A. Abranham . . Dynamic multiobjective optimization based on membrane computing for control of time-varying unstable plants . . Inf. Sci. , , 2011 . . 181 ( ( 11 ): ): 2370 - - 2391 . . DOI: 10.1016/j.ins.2010.12.015 http://doi.org/10.1016/j.ins.2010.12.015 . .

T.O. Ishdorj , , , A. Leporati , , , L. Pan , , , X. Zeng , , , X. Zhang . . Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources . . Theor. Comput. Sci. , , 2010 . . 411 ( ( 25 ): ): 2345 - - 2358 . . DOI: 10.1016/j.tcs.2010.01.019 http://doi.org/10.1016/j.tcs.2010.01.019 . .

X. Li . . Niching without niching parameters: particle swarm optimization using a ring topology . . IEEE Trans. Evol. Comput. , , 2010 . . 14 ( ( 1 ): ): 150 - - 169 . . DOI: 10.1109/TEVC.2009.2026270 http://doi.org/10.1109/TEVC.2009.2026270 . .

T.Y. Nishida . . Membrane algorithms . . LNCS , , 2006 . . 3850 55 - - 66 . . DOI: 10.1007/11603047_4 http://doi.org/10.1007/11603047_4 . .

Y. Niu , , , L. Pan , , , M.J. Prez-Jimnez , , , M.R. Font . . A tissue systems based uniform solution to tripartite matching problem . . Fundam. Inf. , , 2011 . . 109 ( ( 2 ): ): 179 - - 188 . . . .

L. Pan , , , G. Pǎun . . Spiking neural P systems with antispikes . . Int. J. Comput. Commun. Control , , 2009 . . 4 ( ( 3 ): ): 273 - - 282 . . . .

L. Pan , , , G. Pǎun . . Spiking neural P systems: an improved normal form . . Theor. Comput. Sci. , , 2010 . . 411 ( ( 6 ): ): 906 - - 918 . . DOI: 10.1016/j.tcs.2009.11.010 http://doi.org/10.1016/j.tcs.2009.11.010 . .

L. Pan , , , D.P. Daniel , , , M.J. Prez-Jimnez . . Computation of Ramsey numbers by P system with active membranes . . Int. J. Found. Comput. Sci. , , 2011a . . 22 ( ( 1 ): ): 29 - - 38 . . DOI: 10.1142/S0129054111007800 http://doi.org/10.1142/S0129054111007800 . .

L. Pan , , , G. Pǎun , , , M.J. Prez-Jimnez . . Spiking neural P systems with neuron division and budding . . Science China Inf. Sci. , , 2011b . . 54 ( ( 8 ): ): 1596 - - 1607 . . DOI: 10.1007/s11432-011-4303-y http://doi.org/10.1007/s11432-011-4303-y . .

L. Pan , , , X. Zeng , , , X. Zhang . . Time-free spiking neural P systems . . Neur. Comput. , , 2011c . . 23 ( ( 5 ): ): 1320 - - 1342 . . DOI: 10.1162/NECO_a_00115 http://doi.org/10.1162/NECO_a_00115 . .

J. Wang , , , H.J. Hoogeboom , , , L. Pan , , , G. Pǎun , , , M.J. Prez-Jimnez . . Spiking neural systems with weights . . Neur. Comput. , , 2010 . . 22 ( ( 10 ): ): 2615 - - 2646 . . DOI: 10.1162/NECO_a_00022 http://doi.org/10.1162/NECO_a_00022 . .

S. Yang , , , N. Wang . . A novel P systems based optimization algorithm for parameter estimation of proton exchange membrane fuel cell model . . Int. J. Hydr. Energy , , 2012a . . 37 ( ( 10 ): ): 8465 - - 8476 . . DOI: 10.1016/j.ijhydene.2012.02.131 http://doi.org/10.1016/j.ijhydene.2012.02.131 . .

S. Yang , , , N. Wang . . A P systems based optimization algorithm for parameter estimation of FCCU reactorregenerator model . . Chem. Eng. J. , , 2012b . . 211-212 508 - - 518 . . DOI: 10.1016/j.cej.2012.08.040 http://doi.org/10.1016/j.cej.2012.08.040 . .

G. Zhang , , , M. Gheorghe , , , C. Wu . . A quantum-inspired evolutionary algorithm based on P systems for knapsack problem . . Fundam. Inf. , , 2008 . . 87 ( ( 1 ): ): 93 - - 116 . . . .

G. Zhang , , , F. Zhou , , , X. Huang , , , J. Cheng , , , M. Gheorghe , , , F. Ipate , , , R. Lefticaru . . A novel membrane algorithm based on particle swarm optimization for solving broadcasting problems . . J. Univ. Comput. Sci. , , 2012a . . 18 ( ( 13 ): ): 1821 - - 1841 . . DOI: 10.3217/jucs-018-13-1821 http://doi.org/10.3217/jucs-018-13-1821 . .

G. Zhang , , , M. Gheorghe , , , Y. Li . . A membrane algorithm with quantum-inspired subalgorithms and its application to image processing . . Nat. Comput. , , 2012b . . 11 ( ( 4 ): ): 701 - - 717 . . DOI: 10.1007/s11047-012-9320-2 http://doi.org/10.1007/s11047-012-9320-2 . .

G. Zhang , , , J. Cheng , , , M. Gheorghe , , , Q. Meng . . A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems . . Appl. Soft Comput. , , 2013 . . 13 ( ( 3 ): ): 1528 - - 1542 . . DOI: 10.1016/j.asoc.2012.05.032 http://doi.org/10.1016/j.asoc.2012.05.032 . .

X. Zhang , , , J. Wang , , , L. Pan . . A note on the generative power of axon systems . . Int. J. Comput. Commun. Control , , 2009a . . 4 ( ( 1 ): ): 92 - - 98 . . . .

X. Zhang , , , X. Zeng , , , L. Pan . . On languages generated by asynchronous spiking neural P systems . . Theor. Comput. Sci. , , 2009b . . 410 ( ( 26 ): ): 2478 - - 2488 . . DOI: 10.1016/j.tcs.2008.12.055 http://doi.org/10.1016/j.tcs.2008.12.055 . .

X. Zhang , , , Y. Jiang , , , L. Pan . . Small universal spiking neural P systems with exhaustive use of rules . . J. Comput. Theor. Nanosci. , , 2010 . . 7 ( ( 5 ): ): 890 - - 899 . . DOI: 10.1166/jctn.2010.1436 http://doi.org/10.1166/jctn.2010.1436 . .

X. Zhang , , , S. Wang , , , Y. Niu , , , L. Pan . . Tissue P systems with cell separation: attacking the partition problem . . Sci. China Inf. Sci. , , 2011 . . 54 ( ( 2 ): ): 293 - - 304 . . DOI: 10.1007/s11432-010-4162-y http://doi.org/10.1007/s11432-010-4162-y . .

J. Zhao , , , N. Wang . . A bio-inspired algorithm based on membrane computing and its application to gasoline blending scheduling . . Comput. Chem. Eng. , , 2011 . . 35 ( ( 2 ): ): 272 - - 283 . . DOI: 10.1016/j.compchemeng.2010.01.008 http://doi.org/10.1016/j.compchemeng.2010.01.008 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据