RESEARCH ARTICLE


Influence of Probability of Variation Operator on the Performance of Quantum-Inspired Evolutionary Algorithm for 0/1 Knapsack Problem



Mozammel H.A. Khan*
Department of Computer Science and Engineering, East West University, 43 Mohakhali, Dhaka 1212, Bangladesh

Article Information


Identifiers and Pagination:

Year: 2010
Volume: 4
First Page: 37
Last Page: 48
Publisher Id: TOAIJ-4-37
DOI: 10.2174/1874061801004010037

Article History:

Electronic publication date: 26/5/2010
Collection year: 2010

© 2017 Khan et al.;

open-access license: This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International Public License (CC-BY 4.0), a copy of which is available at: (https://creativecommons.org/licenses/by/4.0/legalcode). This license permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

* Address correspondence to this author at the Department of Computer Science and Engineering, East West University, 43 Mohakhali, Dhaka 1212, Bangladesh; Tel: +8802 9882308; Fax: +8802 8812336; E-mail: mhakhan@ewubd.edu


Abstract

Quantum-Inspired Evolutionary Algorithm (QEA) has been shown to be better performing than classical Genetic Algorithm based evolutionary techniques for combinatorial optimization problems like 0/1 knapsack problem. QEA uses quantum computing-inspired representation of solution called Q-bit individual consisting of Q-bits. The probability amplitudes of the Q-bits are changed by application of Q-gate operator, which is classical analogous of quantum rotation operator. The Q-gate operator is the only variation operator used in QEA, which along with some problem specific heuristic provides exploitation of the properties of the best solutions. In this paper, we analyzed the characteristics of the QEA for 0/1 knapsack problem and showed that a probability in the range 0.3 to 0.4 for the application of the Q-gate variation operator has the greatest likelihood of making a good balance between exploration and exploitation. Experimental results agree with the analytical finding.

Keywords: 0/1 knapsack problem, entropy of the probability distribution for the search space, evolutionary algorithm, performance analysis, quantum-inspired evolutionary algorithm.