Quantum computing is a new interdisciplinary science combining information science and quantum mechanics. This paper presents a hybrid quantum genetic algorithm based on spin, which implements quantum crossover on quantum individuals, which is beneficial to retain relatively good gene segments. The strategy of updating quantum gate and adaptively adjusting search grid by using quantum bit phase method; In this paper, the critical properties of quantum Heisenberg model with mixed spins on simple cubic lattice are studied by using the mean field approximation of two spin groups, and the hybrid quantum genetic algorithm based on spins is applied to solve knapsack problem. At present, many problems in the fields of industry and financial investment can be transformed into backpack problems to solve. The effectiveness of spin-based hybrid quantum genetic algorithm in solving knapsack problem has been proved by several groups of experiments.
Quantum computing is a new interdisciplinary science combining information science and quantum mechanics. This paper presents a hybrid quantum genetic algorithm based on spin, which implements quantum crossover on quantum individuals, which is beneficial to retain relatively good gene segments. The strategy of updating quantum gate and adaptively adjusting search grid by using quantum bit phase method; In this paper, the critical properties of quantum Heisenberg model with mixed spins on simple cubic lattice are studied by using the mean field approximation of two spin groups, and the hybrid quantum genetic algorithm based on spins is applied to solve knapsack problem. At present, many problems in the fields of industry and financial investment can be transformed into backpack problems to solve. The effectiveness of spin-based hybrid quantum genetic algorithm in solving knapsack problem has been proved by several groups of experiments.
This paper proposes an Improved Hybrid Quantum Genetic Algorithm(IHQGA).First,the quantum crossover is used which can maintain the relatively good gene blocks.Second,the strategies of updating quantum gate using qubit phase approach and adjusting search grid adaptively are introduced.Third,the similar Newton method is introduced as a local searching scheme,which is characterized by rapid convergence,good global searching capability and short computing time.Test results of complex functions and application example demonstrate that the algorithm is superior to conventional genetic algorithms and quantum genetic algorithm in quality and efficiency.
Quantum algorithm (QA) with updating of quantum gates and catastrophe of population is compared with quantum genetic algorithm (QGA) by including crossover and mutation for quantum bits. Furthermore, a framework of hybrid quantum GA is proposed which combines the quantum based search and classic genetic search, and hybrid QGA with binary encoding (BQGA) and hybrid QGA with real encoding (RQGA) are presented. Numerical simulation on typical problems show that the performances of RQGA are the best among all testing algorithms and it is much robust on parameters and initial conditions.
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.
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.
Quantum Genetic Algorithm (QGA) has a number of advantages in comparison with its classical version: operating speed, small population size and auto-balance between the global search and the local search. It is based on the ideas of traditional evolutionary algorithms, applied to the quantum computations technology, which operate with quantum bits, superposition of states and quantum measurements. This paper proposes a QGA with a new adaptive quantum gate operator and a restoring technology for the quantum chromosome during the process of solving combinatorial problems with constraints. Meta-optimization of the primary algorithm parameters is used for providing the algorithm efficiency. The productiveness of the suggested approach is proven by the model studies, carried out using a wide range of test 0–1 knapsack problems.
Abstract Quantum Genetic Algorithms (QGAs) integrate genetic programming and quantum computing to address search and optimization problems. Most QGA approaches add quantum features to genetic algorithm operators, such as selection, crossover, or mutation. Oppositely, the Reduced Quantum Genetic Algorithm (RQGA) is a fully quantum algorithm that encodes the entire search space (i.e., population) as a superposition of all possible solutions (chromosomes) using the individuals’ quantum register; the fitness function takes the individuals’ quantum register as input to generate corresponding fitness values within the chromosomes’ superposition. RQGA finds the best fitness value and its corresponding chromosome (i.e., the solution or one of the solutions) using Grover’s algorithm. The complexity of Grover’s algorithm is O(2N⁄2), where N is the number of superposed individual chromosomes. However, RQGA operates on an exponentially-big search space (N = 2n, where n is the number of qubits in the individuals’ quantum register), which entails an exponential runtime of O(2n⁄2). This paper introduces an optimization solution for RQGA that controls the algorithm complexity by selecting a limited number of qubits in the individuals’ register and fixing the remaining ones as classical values of ’0’ and ’1’ with a genetic algorithm. We also improve the performance of the RQGA by discarding unfit solutions and bounding the search only in the valid individuals’ area. Putting it all together, we introduce a novel quantum genetic algorithm—Hybrid Quantum Algorithm with Genetic Optimization (HQAGO)—that solves search problems in O(2(n-k)⁄2) oracle queries, where k is the number of fixed classical bits in the individuals’ register. We illustrate instantiations of HQAGO that solve the NP-hard knapsack and graph coloring problems, analyze the complexity of the new algorithm, and study the convergence of its heuristic part.