Paper Info
Title
Solution of "Hard" Knapsack Instances Using Quantum Inspired Evolutionary Algorithm
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.
Year
DOI
Venue
2014
10.4018/ijaec.2014010104
International Journal of Applied Evolutionary Computation
Keywords
DocType
Volume
quantum-inspired evolutionary algorithm,knapsack problem,combinatorial optimization problem,spanner instances,meta-heuristic
Journal
5
Issue
Citations 
PageRank 
1
1
0.35
References 
Authors
20
3
Name
Order
Citations
PageRank
C. Patvardhan131.06
Sulabh Bansal2152.31
Anand Srivastav324836.81