Solution of “Hard” Knapsack Instances Using Quantum Inspired Evolutionary Algorithm

C. Patvardhan, Sulabh Bansal and Anand Srivastav
Additional contact information
C. Patvardhan: Department of Electrical Engineering, Dayalbagh Educational Institute, Agra, India
Sulabh Bansal: Department of Electrical Engineering, Dayalbagh Educational Institute, Agra, India
Anand Srivastav: Institut für Informatik, Universität zu Kiel, Kiel, Germany

International Journal of Applied Evolutionary Computation (IJAEC), 2014, vol. 5, issue 1, 52-68

Abstract: Knapsack Problem (KP) is a popular combinatorial optimization problem having application in many technical and economic areas. Several attempts have been made in past to solve the problem. Various exact and non-exact approaches exist to solve KP. Exact algorithms for KP are based on either branch and bound or dynamic programming technique. Heuristics exist which solve KP non-exactly in lesser time. Heuristic approaches do not provide any guarantee regarding the quality of solution whereas exact approaches have high worst case complexities. Quantum-inspired Evolutionary Algorithm (QEA) is a subclass of Evolutionary Algorithm, a naturally inspired population based search technique. QEA uses concepts of quantum computing. An engineered Quantum-inspired Evolutionary Algorithm (QEA-E), an improved version of QEA, is presented which quickly solves extremely large spanner problem instances (e.g. 290,000 items) that are very difficult for the state of the art exact algorithm as well as the original QEA.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/ijaec.2014010104 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jaec00:v:5:y:2014:i:1:p:52-68

Access Statistics for this article

International Journal of Applied Evolutionary Computation (IJAEC) is currently edited by Sukhpal Singh Gill

More articles in International Journal of Applied Evolutionary Computation (IJAEC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().