International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 6, No. 11, 8 Oct. 2014
Cover page and Table of Contents: PDF (size: 658KB)
Balanced Quantum-Inspired Evolutionary Algorithm for Multiple Knapsack Problem
Full Text (PDF, 658KB), PP.1-11
Views: 0 Downloads: 0
Author(s)
Index Terms
Hybrid Evolutionary Algorithm, Quantum Inspired Evolutionary Algorithm, Combinatorial Optimization, Multiple Knapsack Problem
Abstract
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
Reference
[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.