A Generalized Parallel Quantum Inspired Evolutionary Algorithm Framework for Hard Subset Selection Problems: A GPQIEA for Subset Selection

A Generalized Parallel Quantum Inspired Evolutionary Algorithm Framework for Hard Subset Selection Problems: A GPQIEA for Subset Selection

Sulabh Bansal (School of Computing and Information Technology, Manipal University Jaipur, Jaipur, India) and C. Patvardhan (Department of Electrical Engineering, Dayalbagh Educational Institute, Agra, India)
Copyright: © 2019 |Pages: 38
DOI: 10.4018/IJAEC.2019100101

Abstract

Quantum-inspired evolutionary algorithms (QIEAs) like all evolutionary algorithms (EAs) perform well on many problems but cannot perform equally better than random for all problems due to the No Free Lunch theorem. However, a framework providing near-optimal solutions on reasonably hard instances of a large variety of problems is feasible. It has an effective general strategy for easy incorporation of domain information along with effective control on the randomness in the search process to balance the exploration and exploitation. Moreover, its effective parallel implementation is desired in the current age. Such a Generalized Parallel QIEA framework designed for the solution of Subset Selection Problems is presented here. The computational performance results demonstrate its effectiveness in the solution of different large-sized hard SSPs like the Difficult Knapsack Problem, the Quadratic Knapsack Problem and the Multiple Knapsack problem. This is the first such a generalized framework and is a major step towards creating an adaptive search framework for combinatorial optimization problems.
Article Preview
Top

1. Introduction

Evolutionary Algorithms (EAs) are popular population- based meta-heuristic techniques inspired from the natural process of evolution which have been used with advantage in a large variety of applications (Goldberg, 1989; Mitchell, 1996; Bäck, Fogel, & Michalewicz, 1997a; Bäck, Hammel, & Schwefel, 1997b; Zhou, et al., 2011). However, slow convergence remains a huge problem especially for large problem instances. Quantum computers use quantum bits (qubits) as the smallest unit of information (Hey, 1999). Quantum Inspired Evolutionary Algorithms (QIEAs) (Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization, 2002) form a subclass of EAs. These exploit the advantages of quantum representation, superposition of states and operators to mitigate some of the limitations in EAs for better search and optimization (Zhang G., 2011). A variety of QIEAs, shown to be effective for search and optimization problems, have been developed. Conceptual comparison between EAs and QIEAs is summarized in Table 1.

Table 1.
Comparison between EAs and QIEAs
SimilaritiesDifferences
1.Both EAs and QIEAs work with individuals and population(s)EA represents solutions as individuals specifying parameter values of problem being solved. QIEA utilizes Q-bit strings. A Q-bit string is a superposition of all possible solutions. Thus, individuals in EAs are particular solutions in search space while the individuals in QIEAs are probabilistic representations of the search space.
2.Both EAs and QIEAs use operators to update individualsReproduction operators in EAs are applied directly on solutions while in QIEAs operators are applied on the Q-bit strings.
3.Both evaluate solutions to measure their fitness.In EAs a set of good solutions are selected to be used as parents for producing better children in future generations. While in QIEAs, a few good solutions are selected, these may then be used to update Q-bit strings so that solutions closer to the best solutions found are generated in subsequent iterations.
4.Both generate new solutions in each iterationIn EAs, solutions are generated through reproductive operations on existing solutions while in QIEAs solutions are generated through observation on updated Q-bit individuals.

Although QIEAs are inspired from quantum computing, they are not meant for quantum computers. QIEA is another evolutionary algorithm for a classical computer. The basic building blocks of a typical QIEA are explained as follows:

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing