کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4638476 1632006 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solving the 0–1 Quadratic Knapsack Problem with a competitive Quantum Inspired Evolutionary Algorithm
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
Solving the 0–1 Quadratic Knapsack Problem with a competitive Quantum Inspired Evolutionary Algorithm
چکیده انگلیسی

Quadratic Knapsack Problem (QKP) extends the canonical simple Knapsack Problem where the value obtained by selecting a subset of objects is a function dependent not only on the value corresponding to individual objects selected but also on their pair-wise selection. QKP is NP Hard in stronger sense i.e. 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. Quantum Inspired Evolutionary Algorithm (QIEA) belongs to the class of Evolutionary Algorithms and exhibits behaviour of an Estimation of Distribution Algorithm (EDA). QIEA provides a generic framework that has to be carefully tailored for a given problem to obtain an effective implementation. Thus, several forms of QIEA exist in the literature. These have been successfully applied on many hard problems. A new QIEA, QIEA-PSA is proposed with improved exploration and exploitation capabilities. Computational experiments on these benchmarks show that QIEA-PSA is improved significantly both in terms of the quality of solutions and speed of convergence on several benchmark QKP instances. The ideas incorporated are general enough and can be utilized with advantage on other similar and not so similar problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computational and Applied Mathematics - Volume 285, September 2015, Pages 86–99
نویسندگان
, , ,