International Journal of Intelligent Systems and Applications(IJISA)
ISSN: 2074-904X (Print), ISSN: 2074-9058 (Online)
Published By: MECS Press
IJISA Vol.6, No.11, Oct. 2014
Balanced Quantum-Inspired Evolutionary Algorithm for Multiple Knapsack Problem
Full Text (PDF, 657KB), PP.1-11
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
C. Chekuri and S. Khanna, "A PTAS for the multiple knapsack problem," SIAM Journal on Computing, vol. 35, pp. 713-728, 2006.
S.Y. Yang, M. Wang, and L.C. Jiao, "A novel quantum evolutionary algorithm and its application," in Proc CEC, 2004, pp. 820-826.
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.
M. D. Platel, S. Schliebs, and N. Kasabov, "A versatile quantum-inspired evolutionary algorithm," in Proc. CEC, 2007, pp. 423-430.
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.
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.
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.
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.
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.
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.
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.
K. Han and J. Kim, "On setting the parameters of quantum-inspired evolutionary algorithm for practical application.," in Proc. CEC, 2003, pp. 178-184.
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.
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.
Gexiang Zhang, "Quantum-inspired evolutionary algorithms: a survey and empirical study," Journal of Heuristics, vol. 17, no. 3, pp. 303-351, 2011.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
S. Eilon and N. Christofides, "The loading problem," Management Science, vol. 17, pp. 259-268, 1971.
Hans Kellerer, Ulrich Pferschy, and David Pisinger, Knapsack Problems. Berlin.Hiedelberg: Springer-Verlag, 2004.
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.
S. Martello and P. Toth, "A bound and bound algorithm for the zero-one," Discrete Applied Mathematics, vol. 3, pp. 275-288, 1981.
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.
K. Jansen, "Parameterized approximation scheme for the multiple knapsack problem," Siam Journal on Computing, vol. 39, no. 4, pp. 665-674, 2009.
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.
S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations. Chichester, UK: Wiley, 1990.