Full Text:   <1840>

Summary:  <1530>

CLC number: TP301

On-line Access: 2013-08-02

Received: 2013-01-03

Revision Accepted: 2013-06-17

Crosschecked: 2013-07-12

Cited: 7

Clicked: 4444

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2013 Vol.14 No.8 P.612-622

http://doi.org/10.1631/jzus.C1300005


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


Author(s):  Juan-juan He, Jian-hua Xiao, Xiao-long Shi, Tao Song

Affiliation(s):  Key Laboratory of Image Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China; more

Corresponding email(s):   hejuanjuan1117@gmail.com, songtao0608@hotmail.com

Key Words:  Membrane algorithm, Memory mechanism, Knapsack problem


Juan-juan He, Jian-hua Xiao, Xiao-long Shi, Tao Song. A membrane-inspired algorithm with a memory mechanism for knapsack problems[J]. Journal of Zhejiang University Science C, 2013, 14(8): 612-622.

@article{title="A membrane-inspired algorithm with a memory mechanism for knapsack problems",
author="Juan-juan He, Jian-hua Xiao, Xiao-long Shi, Tao Song",
journal="Journal of Zhejiang University Science C",
volume="14",
number="8",
pages="612-622",
year="2013",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1300005"
}

%0 Journal Article
%T A membrane-inspired algorithm with a memory mechanism for knapsack problems
%A Juan-juan He
%A Jian-hua Xiao
%A Xiao-long Shi
%A Tao Song
%J Journal of Zhejiang University SCIENCE C
%V 14
%N 8
%P 612-622
%@ 1869-1951
%D 2013
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1300005

TY - JOUR
T1 - A membrane-inspired algorithm with a memory mechanism for knapsack problems
A1 - Juan-juan He
A1 - Jian-hua Xiao
A1 - Xiao-long Shi
A1 - Tao Song
J0 - Journal of Zhejiang University Science C
VL - 14
IS - 8
SP - 612
EP - 622
%@ 1869-1951
Y1 - 2013
PB - Zhejiang University Press & Springer
ER -
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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Han, K.H., Kim, J.H., 2002. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE Trans. Evol. Comput., 6(6):580-593.

[2]Hey, T., 1999. Quantum computing: an introduction. Comput. Control Eng. J., 10(3):105-142.

[3]Huang, L., Wang, N., 2006. An optimization algorithm inspired by membrane computing. LNCS, 4222:49-52.

[4]Huang, L., He, X., Wang, N., Xie, Y., 2007. P systems based multi-objective optimization algorithm. Progr. Nat. Sci., 17(4):458-465.

[5]Huang, L., Suh, I.H., Abranham, A., 2011. Dynamic multi-objective optimization based on membrane computing for control of time-varying unstable plants. Inf. Sci., 181(11):2370-2391.

[6]Ishdorj, T.O., Leporati, A., Pan, L., Zeng, X., Zhang, X., 2010. Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. Theor. Comput. Sci., 411(25):2345-2358.

[7]Li, X., 2010. Niching without niching parameters: particle swarm optimization using a ring topology. IEEE Trans. Evol. Comput., 14(1):150-169.

[8]Nishida, T.Y., 2006. Membrane algorithms. LNCS, 3850:55-66.

[9]Niu, Y., Pan, L., Pérez-Jiménez, M.J., Font, M.R., 2011. A tissue systems based uniform solution to tripartite matching problem. Fundam. Inf., 109(2):179-188.

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

[11]Pan, L., Pǎun, G., 2010. Spiking neural P systems: an improved normal form. Theor. Comput. Sci., 411(6):906-918.

[12]Pan, L., Daniel, D.P., Pérez-Jiménez, M.J., 2011a. Computation of Ramsey numbers by P system with active membranes. Int. J. Found. Comput. Sci., 22(1):29-38.

[13]Pan, L., Pǎun, G., Pérez-Jiménez, M.J., 2011b. Spiking neural P systems with neuron division and budding. Science China Inf. Sci., 54(8):1596-1607.

[14]Pan, L., Zeng, X., Zhang, X., 2011c. Time-free spiking neural P systems. Neur. Comput., 23(5):1320-1342.

[15]Wang, J., Hoogeboom, H.J., Pan, L., Pǎun, G., Pérez-Jiménez, M.J., 2010. Spiking neural systems with weights. Neur. Comput., 22(10):2615-2646.

[16]Yang, S., Wang, N., 2012a. A novel P systems based optimization algorithm for parameter estimation of proton exchange membrane fuel cell model. Int. J. Hydr. Energy, 37(10):8465-8476.

[17]Yang, S., Wang, N., 2012b. A P systems based optimization algorithm for parameter estimation of FCCU reactor-regenerator model. Chem. Eng. J., 211-212:508-518.

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

[19]Zhang, G., Zhou, F., Huang, X., Cheng, J., Gheorghe, M., Ipate, F., Lefticaru, R., 2012a. A novel membrane algorithm based on particle swarm optimization for solving broadcasting problems. J. Univ. Comput. Sci., 18(13):1821-1841.

[20]Zhang, G., Gheorghe, M., Li, Y., 2012b. A membrane algorithm with quantum-inspired subalgorithms and its application to image processing. Nat. Comput., 11(4):701-717.

[21]Zhang, G., Cheng, J., Gheorghe, M., Meng, Q., 2013. A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems. Appl. Soft Comput., 13(3):1528-1542.

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

[23]Zhang, X., Zeng, X., Pan, L., 2009b. On languages generated by asynchronous spiking neural P systems. Theor. Comput. Sci., 410(26):2478-2488.

[24]Zhang, X., Jiang, Y., Pan, L., 2010. Small universal spiking neural P systems with exhaustive use of rules. J. Comput. Theor. Nanosci., 7(5):890-899.

[25]Zhang, X., Wang, S., Niu, Y., Pan, L., 2011. Tissue P systems with cell separation: attacking the partition problem. Sci. China Inf. Sci., 54(2):293-304.

[26]Zhao, J., Wang, N., 2011. A bio-inspired algorithm based on membrane computing and its application to gasoline blending scheduling. Comput. Chem. Eng., 35(2):272-283.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE