An Improved Quantum-Inspired Evolutionary Algorithm Based on P Systems with a Dynamic Membrane Structure for Knapsack Problems

Abstract:

To improve the performance of Quantum-inspired Evolutionary algorithm based on P Systems (QEPS), this paper presents an improved QEPS with a Dynamic Membrane Structure (QEPS-DMS) to solve knapsack problems. QEPS-DMS combines quantum-inspired evolutionary algorithms (QIEAs) with a P system with a dynamic membrane structure. In QEPS-DMS, a QIEA is considered as a subalgorithm to put inside each elementary membrane of a one-level membrane structure, which is dynamically adjusted in the process of evolution by applying a criterion for measuring population diversity. The dynamic adjustment includes the processes of membrane dissolution and creation. Knapsack problems are applied to test the effectiveness of QEPS-DMS. Experimental results show that QEPS-DMS outperforms QEPS and three variants of QIEAs recently reported in the literature.

• Periodical: Applied Mechanics and Materials (Volumes 239-240)
• Pages: 1528-1531
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.239-240.1528
• Online since: December 2012
• Authors: Xue Bai Zhang, Ge Xiang Zhang, Ji Xiang Cheng
• Keywords: Dynamic Membrane Structure, Knapsack Problem, Membrane Algorithm, P System, QEPS

References

[1] T.Y. Nishida: An application of P system: a new algorithm for NP-complete optimization problems. In Proc of the 8th world multiconference on systems, cybernetics and informatics, Orlando, p.109–112. (2006)

[2] G.X. Zhang, C.X. Liu, H.N. Rong: Analyzing radar emitter signals with membrane algorithms. Mathematical and Computer Modelling. vol. 52(11-12), p.997–2010. (2010)

DOI: 10.1016/j.mcm.2010.06.002

[3] Gh Păun: A quick introduction to membrane computing. vol. 79(6), p.291–294. (2010)

[4] G.X. Zhang, M Gheorghe: A membrane algorithm with quantum-inspired subalgorithms and its application to image processing. Natural Computing. DOI 10.1007/s11047-012-9320-2. (2012)

DOI: 10.1007/s11047-012-9320-2

[5] G.X. Zhang: A Quantum-Inspired Evolutionary Algorithm Based on P systems for Knapsack Problem. Fundamenta Informaticae. vol. 87(1), p.93–116. (2008)

[6] G.X. Zhang: Quantum-inspired evolutionary algorithms: a survey and empirical study. Journal of Heuristics. vol. 17(3), p.303–351. (2011)

DOI: 10.1007/s10732-010-9136-0

[7] K.H. Han, J.H. Kim: Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization. IEEE Transactions on Evolutionary Computation. vol. 6(6), p.580–593. (2002)

DOI: 10.1109/tevc.2002.804320

[8] K.H. Han, J.H Kim: Quantum-Inspired Evolutionary Algorithms With a New Termination Criterion, HGate, and Two-Phase Scheme. IEEE Transactions on Evolutionary Computation. vol. 8(2), p.156–169. (2004)

DOI: 10.1109/tevc.2004.823467

[9] G.X. Zhang, J.X. Cheng, M. Gheorghe: A membrane-inspired approximate algorithm for traveling salesman problems, Romanian Journal of Information Science and Technology, vol. 14(1), p.3–19. (2011)

[10] F. Zhou, G.X. Zhang, H.N. Rong, J.X. Cheng, M. Gheorghe, F. Ipate, R. Lefticaru: A particle swarm optimization based systems, In Proc of the 6th international conference on natural computation, p.3003–3007, Yantai, China. (2010)

DOI: 10.1109/icnc.2010.5582450

[11] J.X. Cheng, G.X. Zhang, X.X. Zeng: A novel membrane algorithm based on differential evolution for numerical optimization, International Journal of Unconventional Computing, vol. 7(3), p.159–183. (2011)

[12] J.G. Vlachogiannis, K.Y. Lee:Quantum-Inspired Evolutionary Algorithm for Real and Reactive Power Dispatch. IEEE Transactions on Power Systems. vol. 23(4), p.1627–1636. (2008)

DOI: 10.1109/tpwrs.2008.2004743