Combined with quantum computing and genetic algorithm, quantum genetic algorithm (QGA) shows considerable ability of parallelism. Experiments have shown that QGA performs quite well on TSP, job shop problem and some other typical combinatorial optimization problems. The other problems like nutritional diet which can be transformed into specific combinational optimization problem also can be solved through QGA smoothly. This paper sums up the main points of QGA for general combinatorial optimization problems. These points such as modeling of the problem, qubit decoding and rotation strategy are useful to enhance the convergence speed of QGA and avoid premature at the same time.
Combined with quantum computing and genetic algorithm, quantum genetic algorithm (QGA) shows considerable ability of parallelism. Experiments have shown that QGA performs quite well on TSP, job shop problem and some other typical combinatorial optimization problems. The other problems like nutritional diet which can be transformed into specific combinational optimization problem also can be solved through QGA smoothly. This paper sums up the main points of QGA for general combinatorial optimization problems. These points such as modeling of the problem, qubit decoding and rotation strategy are useful to enhance the convergence speed of QGA and avoid premature at the same time.
Based on quantum mutation, a quantum genetic algorithm (QGA) to solve combinatorial optimization problem is proposed.It has good features of genetic quantum algorithm (GQA) and traditional genetic algorithm,which can obtain the best solution with one chromosome in a short time.Comparing experiments have been conducted on a typical combinatorial optimization problem——0/1 knapsack problem.Experimental results have shown that the proposed quantum genetic algorithm is superior to genetic quantum algorithm and traditional genetic algorithm on performance.
This paper proposes a new parallel evolutionary algorithm called parallel quantum-inspired genetic algorithm (PQGA). Quantum-inspired genetic algorithm (QGA) is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. QGA is suitable for parallel structures because of rapid convergence and good global search capability. That is, QGA is able to possess the two characteristics of exploration and exploitation simultaneously. The effectiveness and the applicability of PQGA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that PQGA is superior to QGA as well as other conventional genetic algorithms.
Recent development in quantum technology have shown that quantum computer can provide a dramatic advantage over classical computers for some algorithms. In particular, a polynomial-time algorithm for factoring, a problem which was previously thought to be hard for classical computers, has recently been developed [13]. Similarly, a quantum algorithm searching for unsorted database in square root of time it would take on a classical computer has also been described by Grover [4] - [3]. Both algorithms rely upon the inherent parallelism, superposition and entanglement property of quantum computing to achieve their improvements. Since most problems of real interest for genetic algorithms have a vast search space, it seems appropriate how quantum parallelism can be applied to Genetic Algorithms. In this paper we provide a brief background of quantum computers. We explain why and how quantum algorithms provides a fundamental improvements over classical ones for some problems. Further, we present here the Conventional Genetic Algorithm and the quantum approach of Genetical Algorithms(QGA) as well. The benefits and drawbacks of QGA are also analyzed. Moreover, this paper provides an improved version over the conventional QGA. This improvement originates from the best partial immigration technique applied to the quantum chromosomes. The main objective of the best partial immigration is to consider the string of qubits from the quantum chromosomes having best fitness and transfer the same randomly to the chromosomes of next generation for better mixing. The process is reiterated. To observe the performance the best partial immigration technique we have considered some popular optimization problems and performed the experiment on it. These problems are namely Travelling Salesman Problem(TSP), Binpacking Problem and Vertex Cover Problem. It has been observed that the obtained results outperforms the conventional QGA.
This paper presents a comprehensive review of recent advancements in Genetic Quantum Algorithms (GQAs) and their application to combinatorial optimization problems.As quantum computing gains momentum, researchers are increasingly integrating quantum principles with classical metaheuristics like genetic algorithms to address NP-hard challenges such as the traveling salesman problem (TSP), job-shop scheduling, and graph coloring.This review synthesizes peer-reviewed studies published between 2023 and 2025.It highlights key innovations, performance outcomes, convergence behavior, scalability, and hardware constraints.The analysis reveals that GQAs offer significant improvements in solution accuracy, search efficiency, and robustness over classical techniques, though issues such as decoherence, quantum noise, and circuit depth remain open areas of exploration.
Based on quantum genetic algorithm(QGA),a novel improved quantum genetic algorithm(NIQGA)to solve combinatorial optimization problem is proposed.To make full use of interference and entanglement characteristics of quantum state,dynamic step length in adjustment of angle of quantum gate,quantum crossover operation and quantum mutation operation are introduced,therefore high efficiency for optimization is achieved.Two typical combinatorial optimization problems—0/1 knapsack problem and route selection problem,are adopted to confirm the performance of NIQGA.Experimental results show that compared with GA and QGA,NIQGA is characterized by fast convergence rate and excellent capability on global optimization,especially better performance for combinatorial optimization problem with less correlation of genes.
Quantum genetic algorithm(QGA) was proved to be better than the conventional genetic algorithms on numerical and combinational optimization problems,but it is usually used to solve the knapsack problems of the combinational optimization.It is also possible to use its strong ability of exploitation and exploration to other difficult problems,for example,the TSP,a class of NP-hard combinatorial optimization problems.First,a new encoding scheme with pairs of amplitudes is designed.A quantum individual is corresponding to a vector,and the vector is corresponding to the unique valid tour,and vice versa.The advantages of the encoding scheme are that it always generates feasible solution,uses less population size and storage,and can effectively enhance the diversity of the population.Second,the quantum crossover can maintain the relatively good gene blocks.Third,the two-phase local search for edge evolving is integrated into QGA to accelerate its convergent speed.The first phase is used to optimize the sparsely located cities,and the second phase is used to optimize densely located cities.Based on these,a novel and efficient QGA for TSP is proposed,and its convergence to global optimal solution with probability one is proved.The numerical experiments show that the proposed algorithm can find the global optimal solution with less computation and evolving time.