Using quantum amplitude amplification in genetic algorithms. (15th December 2022)

• Record Type: Journal Article
• Authors: Acampora, Giovanni; Schiattarella, Roberto; Vitiello, Autilia
• Is Part Of: Expert systems with applications. Volume 209(2022)
• Publication Date: 2022-12-15
• Subjects: 81P68; Evolutionary computation -- Genetic algorithm -- Genetic operators -- Quantum computing -- Quantum algorithms -- Quantum states; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2022.118203
• Languages: English
• ISSNs: 0957-4174

Abstract

Abstract: 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. Highlights: Selection operators may cause premature convergence of genetic algorithms. Quantum computer stochasticity can be used to design innovative genetic operators. QGS is a quantum algorithm used to sample individuals from a genetic population. QGS outperforms selection operators through high diversity sampling of individuals.