Balanced Quantum-Inspired Evolutionary Algorithm for Multiple Knapsack Problem

Full Text (PDF, 658KB), PP.1-11

Views: 0 Downloads: 0


C. Patvardhan 1 Sulabh Bansal 1,* Anand Srivastav 2

1. Faculty of Engineering, Dayalbagh Educational Institute, Dayalbagh, Agra. 282005

2. Christian-Albrechts-Universität zu Kiel, Institut für Informatik, Christian-Albrechts-Platz 4, 24118 Kiel, Germany

* Corresponding author.


Received: 26 Jan. 2014 / Revised: 20 May 2014 / Accepted: 14 Jul. 2014 / Published: 8 Oct. 2014

Index Terms

Hybrid Evolutionary Algorithm, Quantum Inspired Evolutionary Algorithm, Combinatorial Optimization, Multiple Knapsack Problem


0/1 Multiple Knapsack Problem, a generalization of more popular 0/1 Knapsack Problem, is NP-hard and considered harder than simple Knapsack Problem. 0/1 Multiple Knapsack Problem has many applications in disciplines related to computer science and operations research. Quantum Inspired Evolutionary Algorithms (QIEAs), a subclass of Evolutionary algorithms, are considered effective to solve difficult problems particularly NP-hard combinatorial optimization problems. A hybrid QIEA is presented for multiple knapsack problem which incorporates several features for better balance between exploration and exploitation. The proposed QIEA, dubbed QIEA-MKP, provides significantly improved performance over simple QIEA from both the perspectives viz., the quality of solutions and computational effort required to reach the best solution. QIEA-MKP is also able to provide the solutions that are better than those obtained using a well known heuristic alone.

Cite This Paper

C. Patvardhan, Sulabh Bansal, Anand Srivastav, "Balanced Quantum-Inspired Evolutionary Algorithm for Multiple Knapsack Problem", International Journal of Intelligent Systems and Applications(IJISA), vol.6, no.11, pp.1-11, 2014. DOI:10.5815/ijisa.2014.11.01


[1]C. Chekuri and S. Khanna, "A PTAS for the multiple knapsack problem," SIAM Journal on Computing, vol. 35, pp. 713-728, 2006. 

[2]S.Y. Yang, M. Wang, and L.C. Jiao, "A novel quantum evolutionary algorithm and its application," in Proc CEC, 2004, pp. 820-826.

[3]C. Patvardhan, Apurva Narayan, and A. Srivastav, "Enhanced Quantum Evolutionary Algorithms for Difficult Knapsack Problems," in PReMI'07 Proceedings of the 2nd international conference on Pattern recognition and machine intelligence, 2007, pp. 252-260.

[4]M. D. Platel, S. Schliebs, and N. Kasabov, "A versatile quantum-inspired evolutionary algorithm," in Proc. CEC, 2007, pp. 423-430.

[5]G. S. Sailesh Babu, D. Bhagwan Das, and C. Patvardhan, "Real-Parameter quantum evolutionary algorithm for economic load dispatch," IET Gener. Transm. Distrib., vol. 2, no. 1, pp. 22-31, 2008.

[6]A. Mani and C. Patvardhan, "A Hybrid quantum evolutionary algorithm for solving engineering optimization problems," International Journal of Hybrid Intelligent Systems, vol. 7, pp. 225-235, 2010.

[7]Ling Wang and Ling-po Li, "An effective hybrid quantum-inspired evolutionary algorithm for parameter estimation of chaotic systems," Expert Systems with Applications, vol. 37, no. 2, pp. 1279–1285, 2010.

[8]Shuyuan Yang, Min Wang, and Licheng Jiao, "Quantum-inspired immune clone algorithm and multiscale Bandelet based image representation," Pattern Recognition Letters, vol. 31, no. 13, pp. 1894–1902, 2010.

[9]Jing Xiao, YuPing Yan, Jun Zhang, and Yong Tang, "A quantum-inspired genetic algorithm for k-means clustering," Expert Systems with Applications, vol. 37, no. 7, pp. 4966–4973, 2010.

[10]P. Arpaia, D. Maisto, and C. Manna, "A Quantum-inspired Evolutionary Algorithm with a competitive variation operator for Multiple-Fault Diagnosis," Applied Soft Computing, vol. 11, no. 8, pp. 4655–4666, 2011.

[11]C Patvardhan, P Prakash, and A Srivastav, "A novel quantum-inspired evolutionary algorithm for the quadratic knapsack problem," Int. J. Mathematics in Operational Research, vol. 4, no. 2, pp. 114-127, 2012.

[12]K. Han and J. Kim, "On setting the parameters of quantum-inspired evolutionary algorithm for practical application.," in Proc. CEC, 2003, pp. 178-184.

[13]K-H Han, "On the Analysis of the Quantum-inspired Evolutionary Algorithm with a Single Individual," in IEEE Congress on Evolutionary Computation, Vancouver, Canada, 2006.

[14]M. D. Platel, Stefan Schliebs, and Nikola Kasabov, "Quantum-Inspired Evolutionary Algorithm: A Multimodel EDA," IEEE Transactions on Evolutionary Computation, vol. 13, no. 6, pp. 1218-1232, 2009.

[15]Gexiang Zhang, "Quantum-inspired evolutionary algorithms: a survey and empirical study," Journal of Heuristics, vol. 17, no. 3, pp. 303-351, 2011.

[16]C. Blum, J. Puchinger, G. R. Raidl, and A. Roli, "Hybrid metaheuristics in combinatorial optimization: A survey," Applied Soft Computing, vol. 11, pp. 4135–4151, 2011.

[17]Kuk-Hyun Han and Jong-Hwan Kim, "Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization," IEEE Transactions on Evolutionary Computation, vol. 6, no. 6, pp. 580-593, December 2002.

[18]K. Han and J. Kim, "Quantum-inspired evolutionary algorithms with a new termination criterion, h-epsilon gate, and two-phase scheme.," IEEE Trans. Evol. Comput., vol. 8, no. 2, pp. 156-169, 2004.

[19]Zhongyu Zhao, Xiyuan Peng, Yu Peng, and Enzhe Yu, "An Effective Repair Procedure based on Quantum-inspired Evolutionary Algorithm for 0/1 Knapsack Problems," in Proceedings of the 5th WSEAS Int. Conf. on Instrumentation, Measurement, Circuits and Systems, Hangzhou, 2006, pp. 203-206.

[20]G.X. Zhang, M. Gheorghe, and C.Z. Wu, "A quantum-inspired evolutionary algorithm based on p systems for knapsack problem," Fund. Inf., vol. 87, no. 1, pp. 93-116, 2008.

[21]M. -H. Tayarani-N and M. -R. Akbarzadeh-T, "A Sinusoid Size Ring Structure Quantum Evolutionary Algorithm," in IEEE Conference on Cybernetics and Intelligent Systems, 2008, pp. 1165 - 1170.

[22]Zhiyong Li, Günter Rudolph, and Kenli Li, "Convergence performance comparison of quantum-inspired multi-objective evolutionary algorithms," Computers and Mathematics with Applications, vol. 57, pp. 1843-1854, 2009.

[23]Parvaz Mahdabi, Saeed Jalili, and Mahdi Abadi, "A multi-start quantum-inspired evolutionary algorithm for solving combinatorial optimization problems," in (GECCO '08) Proceedings of the 10th annual conference on Genetic and evolutionary computation, 2008, pp. 613-614.

[24]Takahiro Imabeppu, Shigeru Nakayama, and Satoshi Ono, "A study on a quantum-inspired evolutionary algorithm based on pair swap," Artif Life Robotics, vol. 12, pp. 148–152, 2008.

[25]T-C Lu and G-R Yu, "An adaptive population multi-objective quantum-inspired evolutionary algorithm for multi-objective 0/1 knapsack problems," Information Sciences, vol. 243, pp. 39-56, 2013.

[26]Y. Kim, J. H. Kim, and K. H. Han, "Quantum-inspired multiobjective evolutionary algorithm for multiobjective 0/1 knapsack problems," in Proc. CEC, 2006, pp. 2601-2606.

[27]K. Han, K. Park, C. Lee, and J. Kim, "Parallel quantum-inspired genetic algorithm for combinatorial optimization prblem," in Proc. CEC, vol. 2, 2001, pp. 1422-1429.

[28]R. Nowotniak and J. Kucharski, "GPU-based tuning of quantum-inspired genetic algorithm for a combinatorial optimization problem," BULLETIN OF THE POLISH ACADEMY OF SCIENCES: TECHNICAL SCIENCES, vol. 60, no. 2, pp. 323-330, 2012.

[29]S. Martello and P. Toth, "Solution of the zero-one multiple knapsack problem," European Journal of Operational Research, vol. 4, no. 4, pp. 276-283, 1980.

[30]F. Diedrich and K. Jansen, "Improved approximation algorithms for scheduling with fixed jobs," in Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA2009), 2009, pp. 675-684.

[31]S. Eilon and N. Christofides, "The loading problem," Management Science, vol. 17, pp. 259-268, 1971.

[32]Hans Kellerer, Ulrich Pferschy, and David Pisinger, Knapsack Problems. Berlin.Hiedelberg: Springer-Verlag, 2004.

[33]M. S. Hung and J. C. Fisk, "An algorithm for the 0-1 multiple knapsack problems," Naval Reserach Logistics Quarterly, vol. 24, pp. 571-579, 1978.

[34]S. Martello and P. Toth, "A bound and bound algorithm for the zero-one," Discrete Applied Mathematics, vol. 3, pp. 275-288, 1981.

[35]H. Kellerer, "A polynomial time approximation scheme for the multiple knapsack problem," in Proceedings of the 2nd Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX(1999), LNCS 1671, 1999, pp. 51-62.

[36]K. Jansen, "Parameterized approximation scheme for the multiple knapsack problem," Siam Journal on Computing, vol. 39, no. 4, pp. 665-674, 2009. 

[37]K. Jansen, "A fast approximation scheme for the multiple knapsack problem," in 38th Conference on Current Trends in Theory and Practice of Computer Science, LNCS 7147, 2012, pp. 313-324.

[38]S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations. Chichester, UK: Wiley, 1990.