Paper Info
Title
Parallel improved quantum inspired evolutionary algorithm to solve large size Quadratic Knapsack Problems.
Abstract
Quadratic Knapsack Problem (QKP), an extension of the canonical simple Knapsack Problem, is NP Hard in the stronger sense. No pseudo-polynomial time algorithm is known to exist which can solve QKP instances. QKP has been studied intensively due to its simple structure yet challenging difficulty and numerous applications. A few attempts have been made to solve large size instances of QKP due to its complexity. Quantum Inspired Evolutionary Algorithm (QIEA) provides a generic framework that has often been carefully tailored for a given problem to obtain an effective implementation. In this work, an improved and parallelized QIEA, dubbed IQIEA-P is presented. Several additional features make it more balanced in exploration and exploitation and thus have better applicability. Computational experiments are presented on large QKP instances of 1000 and 2000 items. The improvements are inherently parallelizable and, therefore, good speedups are obtained on a multi-core machine. No parallel algorithm is available for QKP. The solutions provided by QIEA-P are competitive with those obtained from the state of the art algorithm.
Year
DOI
Venue
2016
10.1016/j.swevo.2015.09.005
Swarm and Evolutionary Computation
Keywords
Field
DocType
Combinatorial Optimization,Large Size Quadratic Knapsack Problem,Parallel Algorithm,Quantum Inspired Evolutionary Algorithm
Parallelizable manifold,Quantum,Mathematical optimization,Evolutionary algorithm,Parallel algorithm,Quadratic equation,Combinatorial optimization,Continuous knapsack problem,Knapsack problem,Mathematics
Journal
Volume
ISSN
Citations 
26
2210-6502
2
PageRank 
References 
Authors
0.37
22
3
Name
Order
Citations
PageRank
C. Patvardhan131.06
Sulabh Bansal2152.31
Anand Srivastav324836.81