Using quantum amplitude amplification in genetic algorithms

Giovanni Acampora

doi:10.1016/j.eswa.2022.118203

2022-12-01

PRE

Giovanni Acampora *

Roberto Schiattarella

Autilia Vitiello

DOI：10.1016/j.eswa.2022.118203

原文链接

原文求助

摘要

En 中文

The selection mechanism of genetic algorithms can play a key role in leading the optimization process towards suitable solutions of a given problem, as their application can affect the trade-off between exploration and exploitation. However, some selection operators suffer from an excessive exploitation that may lead to the loss of population diversity and to a premature convergence, and others present an excessive exploration that may cause genetic algorithms to produce poor results near to random. As a consequence, there is a strong need to rethink how a mating pool is created and introduce alternative approaches to genetic selection. In this paper, a quantum algorithm, named Quantum Genetic Sampling (QGS), has been designed to replace selection operators so as to provide an increased population diversity in genetic evolution and reduce the possibility that the optimization process converge to low quality solutions. The proposed approach is based on two sequential steps. In the first step, QGS models a problem's search space through a quantum state, where each quantum basis state is related to a possible solution of the problem. In the second step, QGS uses quantum amplitude amplification to properly adjust the probability of measuring an individual and placing it in the mating pool according to its fitness value. Unlike conventional selection operators, the quantum mechanical nature of the proposed approach allows for a non-zero probability of introducing new genetic material into the mating pool. Experiments based on well-known benchmark functions show the suitability of the proposed quantum operator for embedding in genetic algorithms, both in terms of accuracy and population diversity.

Keyword:

Evolutionary computation

Genetic algorithm

Genetic operators

Quantum computing

Quantum algorithms

Quantum states