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

International Conference on Measurement, Information and Control

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

Rui Wang, Ning Guo, Fenghong Xiang, Jianlin Mao

Published May 1, 2012• 4 citations
Publisher

Abstract

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.

DOI
10.1109/mic.2012.6273347

Related papers

A quantum genetic algorithm with repair function and its application in knapsack question

Xinghua Zhang

A Quantum Genetic Algorithm(QGA) with repair function was proposed in this paper.This algorithm codes the chromosomes in the way of quantum bit probability,and makes the population evolve by the operation of quantum gate.When solving the knapsack question,repair function was used to repair unfeasible code.The implementation and procedure of this algorithm were introduced in detail in the paper.The test results of several typical knapsack questions show that this algorithm has better comprehensive performance than conventional genetic algorithm.

Journal of Computer Applications•Jan 1, 2007•6 citations

A Novel Improved Quantum Genetic Algorithm for Combinatorial Optimization Problems

Xihua Zou

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.

Dianzi xuebao•Jan 1, 2007•15 citations

Improvement of Quantum Genetic Algorithm and Its Application

Ge ZHANG

An improved quantum genetic algorithm(IQGA) was proposed to overcome the shortcoming of the quantum genetic algorithm(QGA),i.e. local optimization, when it is used for the optimization of continuous functions with many extreme values. In IQGA, the strategies of updating quantum gate using the best solution obtained and population catastrophe were adopted. The test results for two typical functions show that the convergence speed of IQGA is faster than that of QGA, and IQGA can converge in a global solution space, overcoming the shortcoming of QGA. The application results indicate that IQGA is better than QGA and other genetic algorithms.

Journal of Southwest Jiaotong University•Jan 1, 2003•12 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

An Improved Quantum Genetic Algorithm

Jian Bao Guo, Lijuan Sun, Ruchuan Wang +1 more

Quantum genetic algorithm (QGA) is the combination between genetic algorithm and quantum computing. In this paper, a chromosome of the standard QGA is seen as a node and the chromosome population is regarded as a network. Then the reasons for the prematurity and the stagnation of the standard QGA are analyzed from the perspective of network structure. To solve the two problems, an improved quantum genetic algorithm (IQGA) based on the small world theory is proposed. In IQGA, chromosomes encoded with qubits are divided into some sub-groups and the NW network model is introduced into the population structure. When updating chromosomes, an optimal chromosome in locality or in other sub-groups is chosen based on a certain probability as the evolution target for each chromosome. The new network structure of the chromosome population has a relatively moderate clustering coefficient and is favorable to the diversity of individual chromosomes. Tests of three classic functions prove the effectiveness and superiority of IQGA.

International Conference on Genetic and Evolutionary Computing•Oct 1, 2009•22 citations

An Improved Quantum Genetic Algorithm

Bo Yang

This paper suggests an improved quantum genetic algorithm(IQGA).In encoding,a kind of encoding method to determine the quantum chromosome gene length is advanced in terms of accurate dynamics of the problem to be found out.This encoding method takes the equilibrium relations between the calculation solution accuracy and seeking for efficiency into consideration.Also,this paper discusses the dynamic adjustment and tactics of quantum rotation angle,whereby making operator realize the combination of a kind of rough searching with the fine searching under the different cases.The combination of quantum mutation operation can render the postmutation to be able to carry out searching in a larger neighborhood range in such a way that the algorithm is ensured to search for a solution with high accuracy within a rational calculation cost.In the end,IQGA is used to test several selected standard base functions.The tested results indicate that IQGA can obtain the best solusion,the best average value and convergence algebra as against the existing algorithm data cited in literature,and with a certain advantage.

Journal of Xi'an University of Technology•Jan 1, 2012•2 citations
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.
A Quantum Genetic Algorithm(QGA) with repair function was proposed in this paper.This algorithm codes the chromosomes in the way of quantum bit probability,and makes the population evolve by the operation of quantum gate.When solving the knapsack question,repair function was used to repair unfeasible code.The implementation and procedure of this algorithm were introduced in detail in the paper.The test results of several typical knapsack questions show that this algorithm has better comprehensive performance than conventional genetic algorithm.
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.
An improved quantum genetic algorithm(IQGA) was proposed to overcome the shortcoming of the quantum genetic algorithm(QGA),i.e. local optimization, when it is used for the optimization of continuous functions with many extreme values. In IQGA, the strategies of updating quantum gate using the best solution obtained and population catastrophe were adopted. The test results for two typical functions show that the convergence speed of IQGA is faster than that of QGA, and IQGA can converge in a global solution space, overcoming the shortcoming of QGA. The application results indicate that IQGA is better than QGA and other genetic algorithms.
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.
Quantum genetic algorithm (QGA) is the combination between genetic algorithm and quantum computing. In this paper, a chromosome of the standard QGA is seen as a node and the chromosome population is regarded as a network. Then the reasons for the prematurity and the stagnation of the standard QGA are analyzed from the perspective of network structure. To solve the two problems, an improved quantum genetic algorithm (IQGA) based on the small world theory is proposed. In IQGA, chromosomes encoded with qubits are divided into some sub-groups and the NW network model is introduced into the population structure. When updating chromosomes, an optimal chromosome in locality or in other sub-groups is chosen based on a certain probability as the evolution target for each chromosome. The new network structure of the chromosome population has a relatively moderate clustering coefficient and is favorable to the diversity of individual chromosomes. Tests of three classic functions prove the effectiveness and superiority of IQGA.
This paper suggests an improved quantum genetic algorithm(IQGA).In encoding,a kind of encoding method to determine the quantum chromosome gene length is advanced in terms of accurate dynamics of the problem to be found out.This encoding method takes the equilibrium relations between the calculation solution accuracy and seeking for efficiency into consideration.Also,this paper discusses the dynamic adjustment and tactics of quantum rotation angle,whereby making operator realize the combination of a kind of rough searching with the fine searching under the different cases.The combination of quantum mutation operation can render the postmutation to be able to carry out searching in a larger neighborhood range in such a way that the algorithm is ensured to search for a solution with high accuracy within a rational calculation cost.In the end,IQGA is used to test several selected standard base functions.The tested results indicate that IQGA can obtain the best solusion,the best average value and convergence algebra as against the existing algorithm data cited in literature,and with a certain advantage.