Engineering of Quantum Inspired Evolutionary Algorithm for the Solution of Some Hard Combinatorial Optimization Problems

Abstract

Combinatorial Optimization Problems (COPs) form a subclass of optimization problems which is interesting to researchers and have immense practical applications. The exact algorithms have to be designed specifically for each such problem and they take large computation times to solve COPs. Thus, several meta-heuristic techniques are popular to find good solutions in reasonable time for COPs. Evolutionary Algorithms (EAs) inspired from natural process of evolution form a class of such algorithms. Quantum Inspired Evolutionary Algorithms (QIEAs) in turn are EAs where concepts of Quantum Computing are used. newlineThe meta-heuristics in general and QIEAs in particular provide a framework which is believed to be applicable to different problems to find a suitable solution. However, to make such population based search methods specialized to a specific problem; the domain knowledge has to be incorporated in their mechanism for the effective search. The existing studies on QIEAs provide a limited application of one or two ideas of modifications and study the impact on a given problem or some given problem instances generally of small sizes. The objective of the research is to strengthen QIEAs so that they can be used to solve a variety of hard COPs. newlineA generalized QIEA framework is proposed in this work. It is embedded with various features that can be selected for inclusion in an implementation of an algorithm based on the requirements to solve a given problem. Some of the proposed features help to increase determinism while guiding the search. Several other features help the search process to deviate from the path set by deterministic features in order to search in different regions. The overall objective is to develop an effective framework, which is balanced in its capability to exploit and explore the search space as required in a particular problem. The proposed framework can be engineered with hybridization of concepts from the problem specific heuristics / approximation algorithms proposed in the literature. The aim of this engineering is to solve complex and large sized problems effectively. The proposed framework is also implemented to take advantage of the multiple core architectures available today for engineering the solution of problems which are computationally more complex. newlineThe proposed generalized framework is applied and implementations engineered to solve various problems as follows. newline1. Difficult Knapsack Problems newline2. Quadratic Knapsack Problem newline3. Multiple Knapsack Problem newline4. Minimum Vertex Cover newline5. Royal Road Function newlineIt is shown that these problems can be solved in a significantly better way by proposed framework as compared to QIEA. The implementation of proposed framework for these problems has been shown to reach very close to optimal for all instances and outperform other existing non-exact approaches in terms of time and/or quality of solutions. For some hard problems/instances the implementation of proposed framework outperform the best known exact algorithm in terms of computation time and provide nearly optimal solutions. newlineThe proposed generalized framework can be used in similar ways to solve several other COPs easily and effectively. Generalized frameworks based on other population based random search techniques apart from QIEA can also be developed using the ideas presented in this work. newline newline newline