Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Dianzi xuebao

A Novel Improved Quantum Genetic Algorithm for Combinatorial Optimization Problems

Xihua Zou

Published Jan 1, 2007• 15 citations
OpenAlex

Abstract

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.

Related papers

Network Optimization Method Based on Improved Quantum Genetic Algorithm

Xin Fan, Wei Li, Zhihuan Chen +1 more

To solve structure optimization problems of the information transmission networks, based on quantum genetic algorithm (QGA), the paper proposes an improved quantum genetic algorithm (IQGA). The core of the algorithm is to take full advantage of interference and entanglement of quantum states, through adopting the quantum gates rotation corner dynamic adjusting mechanism, quantum crossover and mutation operations, genetic operation parameters dynamic adaptive adjustment mechanism and solution elites control strategy. The algorithm has better performance in solving combinatorial optimization problems of the weak correlation between genes.

International Symposium on Information Science and Engineering•Dec 1, 2012•2 citations

A Quantum Genetic Algorithm to Solve Combinatorial Optimization Problem

Xing-Fu Wang

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.

Dianzi xuebao•Jan 1, 2004•17 citations

Parallel quantum-inspired genetic algorithm for combinatorial optimization problem

Kuk-Hyun Han, Kui-Hong Park, Ci-Ho Lee +1 more

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.

IEEE Congress on Evolutionary Computation (CEC)•Nov 13, 2002•193 citations

Novel improved quantum evolutionary algorithm for combinatorial optimization problems

Zhang Zong-fei

According to the characteristics of combinatorial optimization problems,a novel improved quantum evolutionary algorithm for combinatorial optimization problems(NIQEA) is proposed.The NIQEA initializes population based on the idea of niche cooperative evolutionary,increasing the diversity of individuals,and adopts the dynamic adjustment strategy to adjust the quantum rotation corner,speeding up convergence rate,and uses the cross strategy of excellent individuals to get crossover operation,enhancing local search ability.To validate its performance,the NIQEA is applied to solve the typical combinatorial optimization problems: two examples of multidimensional 0/1 knapsack problem,and the results show that the NIQEA is feasible and effective.

Jisuanji gongcheng yu sheji•Jan 1, 2010•0 citations

An improved quantum genetic algorithm with mutation and its application to 0-1 knapsack problem

Rui Wang, Ning Guo, Fenghong Xiang +1 more

An improved quantum genetic algorithm (IQGA) is proposed in this paper, which codes the chromosome with probability amplitudes represented by sine and cosine functions, and uses an adaptive strategy of the rotation angle to update the population. Then the mutation operation is considered in this improved quantum genetic algorithm (MIQGA). Rapid convergence and good global search capability characterize the performance of MIQGA. While testing, a variance function is introduced to estimate the stability of the algorithm. When solving 0-1 knapsack problem, greedy repair function is used to repair unfeasible solutions. Experimental results show MIQGA has better comprehensive performance than traditional genetic algorithm (GA), standard quantum genetic algorithm (QGA) and IQGA, especially the superiority in terms of optimization quality and population diversity.

International Conference on Measurement, Information and Control•May 1, 2012•4 citations

A Novel Quantum Genetic Algorithm for TSP

Yu Wang

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.

Chinese Journal of Computers•Jan 1, 2007•19 citations
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.
To solve structure optimization problems of the information transmission networks, based on quantum genetic algorithm (QGA), the paper proposes an improved quantum genetic algorithm (IQGA). The core of the algorithm is to take full advantage of interference and entanglement of quantum states, through adopting the quantum gates rotation corner dynamic adjusting mechanism, quantum crossover and mutation operations, genetic operation parameters dynamic adaptive adjustment mechanism and solution elites control strategy. The algorithm has better performance in solving combinatorial optimization problems of the weak correlation between genes.
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.
According to the characteristics of combinatorial optimization problems,a novel improved quantum evolutionary algorithm for combinatorial optimization problems(NIQEA) is proposed.The NIQEA initializes population based on the idea of niche cooperative evolutionary,increasing the diversity of individuals,and adopts the dynamic adjustment strategy to adjust the quantum rotation corner,speeding up convergence rate,and uses the cross strategy of excellent individuals to get crossover operation,enhancing local search ability.To validate its performance,the NIQEA is applied to solve the typical combinatorial optimization problems: two examples of multidimensional 0/1 knapsack problem,and the results show that the NIQEA is feasible and effective.
An improved quantum genetic algorithm (IQGA) is proposed in this paper, which codes the chromosome with probability amplitudes represented by sine and cosine functions, and uses an adaptive strategy of the rotation angle to update the population. Then the mutation operation is considered in this improved quantum genetic algorithm (MIQGA). Rapid convergence and good global search capability characterize the performance of MIQGA. While testing, a variance function is introduced to estimate the stability of the algorithm. When solving 0-1 knapsack problem, greedy repair function is used to repair unfeasible solutions. Experimental results show MIQGA has better comprehensive performance than traditional genetic algorithm (GA), standard quantum genetic algorithm (QGA) and IQGA, especially the superiority in terms of optimization quality and population diversity.
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.