Quantum-inspired evolutionary algorithm (QEA) has been designed by integrating some quantum mechanical principles in the framework of evolutionary algorithms. They have been successfully employed as a computational technique in solving difficult optimization problems. It is well known that QEAs provide better balance between exploration and exploitation as compared to the conventional evolutionary algorithms. The population in QEA is evolved by variation operators, which move the Q-bit towards an attractor. A modification for improving the performance of QEA was proposed by changing the selection of attractors, namely, versatile QEA. The improvement attained by versatile QEA over QEA indicates the impact of population structure on the performance of QEA and motivates further investigation into employing fine-grained model. The QEA with fine-grained population model (FQEA) is similar to QEA with the exception that every individual is located in a unique position on a two-dimensional toroidal grid and has four neighbors amongst which it selects its attractor. Further, FQEA does not use migrations, which is employed by QEAs. This paper empirically investigates the effect of the three different population structures on the performance of QEA by solving well-known discrete benchmark optimization problems.
Quantum-inspired evolutionary algorithm (QEA) has been designed by integrating some quantum mechanical principles in the framework of evolutionary algorithms. They have been successfully employed as a computational technique in solving difficult optimization problems. It is well known that QEAs provide better balance between exploration and exploitation as compared to the conventional evolutionary algorithms. The population in QEA is evolved by variation operators, which move the Q-bit towards an attractor. A modification for improving the performance of QEA was proposed by changing the selection of attractors, namely, versatile QEA. The improvement attained by versatile QEA over QEA indicates the impact of population structure on the performance of QEA and motivates further investigation into employing fine-grained model. The QEA with fine-grained population model (FQEA) is similar to QEA with the exception that every individual is located in a unique position on a two-dimensional toroidal grid and has four neighbors amongst which it selects its attractor. Further, FQEA does not use migrations, which is employed by QEAs. This paper empirically investigates the effect of the three different population structures on the performance of QEA by solving well-known discrete benchmark optimization problems.
This paper proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, evaluation function, and population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. A Q-gate is introduced as a variation operator to drive the individuals toward better solutions. To demonstrate its effectiveness and applicability, experiments were carried out on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that QEA performs well, even with a small population, without premature convergence as compared to the conventional genetic algorithm.
In this paper, some guidelines for setting the parameters of quantum-inspired evolutionary algorithm (QEA) are presented. QEA is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. However, QEA is not a quantum algorithm, but a novel evolutionary algorithm. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, the evaluation function, and the population dynamics. From recent research on the knapsack problem, the results of QEA are better than those of CGA (conventional GA). Although the performance of QEA is excellent, there is relatively little or no research on the effects of different settings for its parameters. This paper describes some guidelines for setting these parameters. The guidelines are drawn up based on extensive experiments carried out for a class of combinatorial and numerical optimization problems. Through the guidelines, the performance of QEA can be maximized.
Quantum-Inspired Evolutionary Algorithm (QEA), a type of stochastic algorithm for solving combinatorial optimization problems, is evolutionary computation using quantum bits and superposition states in quantum computation. Although coarse-grained parallel, QEA has many parameters that must be adjusted manually. The simpler algorithm, Quantum-inspired Evolutionary Computation with Pair Swap operator (QEAPS), the authors propose involves just one population and a simple genetic operation exchanging best solution information between two individuals chosen randomly, instead of the migration operation used in QEA, and thereby fewer parameters to be adjusted. The authors found in experiments that QEAPS finds highly qualified solutions, is more robust against constraint handling, and has a higher search performance of thanks to diversified best solution information.
In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search space. In the operator, first, the Q-bits of each individual in the population are updated based on the personal best measurement of that individual and the best measurement of current generation. Then, a restriction is applied to each Q-bit to prevent the premature convergence of its values. The results of experiments on the 0-1 knapsack and NK-landscapes problems show that NQEA performs better than a classical genetic algorithm, CGA, and two quantum-inspired evolutionary algorithms, QEA and vQEA, in terms of convergence speed and accuracy.
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.
Quantum inspired Evolutionary Algorithms were proposed more than a decade ago and have been employed for solving a wide range of difficult search and optimization problems. A number of changes have been proposed to improve performance of canonical QEA. However, canonical QEA is one of the few evolutionary algorithms, which uses a search operator with relatively large number of parameters. It is well known that performance of evolutionary algorithms is dependent on specific value of parameters for a given problem. The advantage of having large number of parameters in an operator is that the search process can be made more powerful even with a single operator without requiring a combination of other operators for exploration and exploitation. However, the tuning of operators with large number of parameters is complex and computationally expensive. This paper proposes a novel heuristic method for tuning parameters of canonical QEA. The tuned QEA outperforms canonical QEA on a class of discrete combinatorial optimization problems which, validates the design of the proposed parameter tuning framework. The proposed framework can be used for tuning other algorithms with both large and small number of tunable parameters.