{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T15:48:17Z","timestamp":1781106497307,"version":"3.54.1"},"reference-count":23,"publisher":"IGI Global Scientific Publishing","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,1,1]]},"abstract":"<p>This article describes how the 0\/1 Multiple Knapsack Problem (MKP), a generalization of popular 0\/1 Knapsack Problem, is NP-hard and harder than simple Knapsack Problem. Solution of MKP involves two levels of choice \u2013 one for selecting an item to be placed and the other for selecting the knapsack in which it is to be placed. Quantum Inspired Evolutionary Algorithms (QIEAs), a subclass of Evolutionary algorithms, have been shown to be effective in solving difficult problems particularly NP-hard combinatorial optimization problems. QIEAs provide a general framework which needs to be customized according to the requirements of a given problem to obtain good solutions in reasonable time. An existing QIEA for MKP (QIEA-MKP) is based on the representation where a Q-bit collapse into a binary number. But decimal numbers are required to identify the knapsack where an item is placed. The implementation based on such representation suffers from overhead of frequent conversion from binary numbers to decimal numbers and vice versa. The generalized QIEA (GQIEA) is based on a representation where a Q-bit can collapse into an integer and thus no inter conversion between binary and decimal is required. A set of carefully selected features have been incorporated in proposed GQIEA-MKP to obtain better solutions in lesser time. Comparison with QIEA-MKP shows that GQIEA-MKP outperforms it in providing better solutions in lesser time for large sized MKPs. The generalization proposed can be used with advantage in other Combinatorial Optimization problems with integer strings as solutions.<\/p>","DOI":"10.4018\/ijaec.2018010102","type":"journal-article","created":{"date-parts":[[2018,2,28]],"date-time":"2018-02-28T10:47:32Z","timestamp":1519814852000},"page":"17-51","source":"Crossref","is-referenced-by-count":2,"title":["An Improved Generalized Quantum-Inspired Evolutionary Algorithm for Multiple Knapsack Problem"],"prefix":"10.4018","volume":"9","author":[{"given":"Sulabh","family":"Bansal","sequence":"first","affiliation":[{"name":"School of Computing and Information Technology, Manipal University Jaipur, Jaipur, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Patvardhan","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Dayalbagh Educational Institute (DEI), Agra, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2432","reference":[{"key":"IJAEC.2018010102-0","article-title":"A Generalized Quantum-Inspired Evolutionary Algorithm for Combinatorial Optimization Problems.","author":"J. M.Alegria","year":"2013","journal-title":"XXXII International Conference of the Chilean Computer Science Society (SCCC),"},{"key":"IJAEC.2018010102-1","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2011.07.017"},{"key":"IJAEC.2018010102-2","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2011.02.032"},{"key":"IJAEC.2018010102-3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"IJAEC.2018010102-4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.74"},{"key":"IJAEC.2018010102-5","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.5.259"},{"key":"IJAEC.2018010102-6","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2002.804320"},{"key":"IJAEC.2018010102-7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-48413-4_6"},{"key":"IJAEC.2018010102-8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7"},{"key":"IJAEC.2018010102-9","doi-asserted-by":"publisher","DOI":"10.3233\/HIS-2010-0115"},{"key":"IJAEC.2018010102-10","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(80)90112-5"},{"key":"IJAEC.2018010102-11","author":"S.Martello","year":"1990","journal-title":"Knapsack Problems: Algorithms and Computer Implementations"},{"key":"IJAEC.2018010102-12","doi-asserted-by":"publisher","DOI":"10.5815\/ijisa.2014.11.01"},{"key":"IJAEC.2018010102-13","doi-asserted-by":"crossref","unstructured":"Patvardhan, C., Narayan, A., & Srivastav, A. (2007). Enhanced Quantum Evolutionary Algorithms for Difficult Knapsack Problems. In PReMI'07 Proceedings of the 2nd international conference on Pattern recognition and machine intelligence (pp. 252-260). Springer-Verlag Berlin.","DOI":"10.1007\/978-3-540-77046-6_31"},{"key":"IJAEC.2018010102-14","doi-asserted-by":"publisher","DOI":"10.1504\/IJMOR.2012.046373"},{"key":"IJAEC.2018010102-15","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00120-9"},{"key":"IJAEC.2018010102-16","unstructured":"Pisinger, D. (n.d.). David Pisinger\u2019s optimization codes. Retrieved November 2, 2012, from http:\/\/www.diku.dk\/~pisinger\/codes.html"},{"key":"IJAEC.2018010102-17","first-page":"423","article-title":"A versatile quantum-inspired evolutionary algorithm.","author":"M. D.Platel","year":"2007","journal-title":"Proc. of CEC"},{"key":"IJAEC.2018010102-18","doi-asserted-by":"publisher","DOI":"10.1049\/iet-gtd:20060495"},{"key":"IJAEC.2018010102-19","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2009.06.013"},{"key":"IJAEC.2018010102-20","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2009.12.017"},{"key":"IJAEC.2018010102-21","first-page":"820","article-title":"A novel quantum evolutionary algorithm and its application.","author":"S.Yang","year":"2004","journal-title":"Proc"},{"key":"IJAEC.2018010102-22","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2009.12.016"}],"container-title":["International Journal of Applied Evolutionary Computation"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=201585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T12:08:40Z","timestamp":1651838920000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/IJAEC.2018010102"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2018,1,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"URL":"https:\/\/doi.org\/10.4018\/ijaec.2018010102","relation":{},"ISSN":["1942-3594","1942-3608"],"issn-type":[{"value":"1942-3594","type":"print"},{"value":"1942-3608","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,1]]}}}