Quantum-inspired evolutionary algorithm for a class of combinatorial optimization

TLDR

Evolutionary algorithms are characterized by representation, evaluation, and population dynamics. This paper introduces a quantum‑inspired evolutionary algorithm (QEA) that leverages quantum computing concepts such as qubits and superposition. QEA represents individuals as strings of qubits, employs a Q‑gate variation operator, and is evaluated on the knapsack problem to demonstrate its effectiveness. Experiments show that QEA outperforms conventional genetic algorithms by achieving good performance with a small population and avoiding premature convergence.

Abstract

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.