It was indicated from the recent research that Quantum Genetic Algorithm(QGA) outperformed conventional genetic algorithm in its lower running time and ability of finding better solution when it solved a class of numerical and knapsack of combinatorial optimization problems.However,with qutbit of quantum individual interfering,parameter γ of the termination criterion is difficult to determine.The rotate gate which can promote the population is difficult to change its state of qutbit,and this phenomenon often induces premature.To improve the performance of the QGA,a controllable rotate gate and a new termination criterion are proposed in this paper.The controllable rotation gate can induce the convergence of qutbit not only to either 0 or 1,but also to either e or 1-e,and make the proposed algorithm to escape the local optimum.Based on gathering factor and qutbit convergence factor,a new termination criterion is proposed.The qutbit decreases the impact on parameter γ,and the new terminate criterion can efficiently control the relation of better solution and its running time.In addition,the Simplex method is introduced as a local searching scheme,which greatly improves the performance of algorithm.At last,the global convergence of the proposed algorithm is proved in theory,and comparable numerical experiments show that the proposed algorithm is more powerful than the compared algorithm in solution quality and speed.
It was indicated from the recent research that Quantum Genetic Algorithm(QGA) outperformed conventional genetic algorithm in its lower running time and ability of finding better solution when it solved a class of numerical and knapsack of combinatorial optimization problems.However,with qutbit of quantum individual interfering,parameter γ of the termination criterion is difficult to determine.The rotate gate which can promote the population is difficult to change its state of qutbit,and this phenomenon often induces premature.To improve the performance of the QGA,a controllable rotate gate and a new termination criterion are proposed in this paper.The controllable rotation gate can induce the convergence of qutbit not only to either 0 or 1,but also to either e or 1-e,and make the proposed algorithm to escape the local optimum.Based on gathering factor and qutbit convergence factor,a new termination criterion is proposed.The qutbit decreases the impact on parameter γ,and the new terminate criterion can efficiently control the relation of better solution and its running time.In addition,the Simplex method is introduced as a local searching scheme,which greatly improves the performance of algorithm.At last,the global convergence of the proposed algorithm is proved in theory,and comparable numerical experiments show that the proposed algorithm is more powerful than the compared algorithm in solution quality and speed.
Aiming at the issue that quantum genetic algorithm is not suitable for continuons function optimization,an improved quantum genetic algorithm is proposed.This algorithm directly compares the quantum chromosomes with the current best solution to determine the rotating angle of the rotating gate.Every individual in population evolves with different rates to complete local search and global search simultaneously.Mutation operation is used to prevent the premature convergence.After analyzing the algorithm and its global convergence,this algorithm is applied to solve the function extremum and to optimize the PID controller parameters,and it is compared with the standard genetic algorithm and the quantum genetic algorithm.Experimental results illustrate that the proposed algorithm has better performance.
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 algorithms(QGA) typically construct traditional quantum chromosomes as independent quantum bit systems, which has facilitated the enhancement of search speed and precision in genetic algorithms, demonstrating powerful problem-solving capabilities in optimization issues. Although traditional QGA have enriched population diversity, they still tend to fall into local optima, and the evolutionary update operations require rotation directions to be determined by lookup tables, a process involving multiple conditional judgments that affect algorithm efficiency. To address these issues, an improved method has been proposed to further enhance the performance of QGA. In the initial population selection, a population grouping evolution method based on microhabitat coevolution strategy is used to prevent the algorithm from getting trapped in local optima when solving complex function problems. Additionally, quantum entanglement is introduced on top of quantum super-position by implementing quantum entanglement using quantum registers, and higher-order quantum rotation gates are employed that do not involve multiple conditional judgments of lookup tables, thus improving the efficiency of quantum chromosome measurement and evolutionary updates. Finally, traditional QGA and higher-order quantum genetic algorithms were applied to test functions in multiple experiments. The results indicate that, compared to traditional QGA, the higher-order quantum genetic algorithms have achieved an increase in convergence speed, an approximate 14.3% improvement in convergence precision, and possess enhanced global search capabilities.
In order to save computation time and avoid falling into local optima in quantum genetic algorithm (QGA), this paper proposes a quantum genetic algorithm based on Boltzmann selection mechanism (B_QGA). The proposed algorithm has several novel characteristics. Firstly, Quantum bits are encoded by angle and introduce the constant factor, aiming at enhancing calculated amount. Secondly, a new dynamic rotation angle adjustment strategy is presented to achieve updated chromosome, and individuals directly evolve to the current optimal solution with linear increasing rate, which greatly improve the rate of convergence and the ability of global search. Thirdly, instead of roulette selection mode, Boltzmann selection mechanism is employed for avoiding the local optimal problem. Finally, for the selected offspring's individuals, Hadamard door is proposed to perform mutation operation to sustain stability and diversity of population. The experiment results on three complicated continuous functions show the proposed algorithm is able to find the best solution in very short time and has excellent global search ability comparing to quantum genetic algorithm (QGA) and genetic algorithm (GA).
From recent research on combinatorial optimization of the knapsack problem, quantum-inspired evolutionary algorithm (QEA) was proved to be better than conventional genetic algorithms. To improve the performance of the QEA, this paper proposes research issues on QEA such as a termination criterion, a Q-gate, and a two-phase scheme, for a class of numerical and combinatorial optimization problems. A new termination criterion is proposed which gives a clearer meaning on the convergence of Q-bit individuals. A novel variation operator H/sub /spl epsi// gate, which is a modified version of the rotation gate, is proposed along with a two-phase QEA scheme based on the analysis of the effect of changing the initial conditions of Q-bits of the Q-bit individual in the first phase. To demonstrate the effectiveness and applicability of the updated QEA, several experiments are carried out on a class of numerical and combinatorial optimization problems. The results show that the updated QEA makes QEA more powerful than the previous QEA in terms of convergence speed, fitness, and robustness.
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.