New Method For Geometric Constraint Solving Based on the Genetic Quantum Algorithm

Chunhong Cao, Wenhui Li

Published Jan 1, 2004• 0 citations

Abstract

This paper proposes a novel genetic quantum algorithm (GQA) to solve geometric constraint problems. Instead of binary, numeric or symbolic representation, we introduce qubit chromosome representation. GQA is based on qubit and superposition of states and is used in the process of geometric constraint solving in order to get the solution sequence. As GQA has diversity caused by the qubit representation, there is no need to use the genetic operator. Qubit chromosome can be updated by proper quantum gate in the circulation. The experiment indicates GQA can solve the geometric constraint problem effectively. Keywords Geometric constraint solving geometric decomposing genetic algorithm quantum computing genetic quantum algorithm quantum gate qubit chromosome 1. Geometric Constraint Solving Geometric constraint solving is a remarkable problem based on the constraint design. Once a user defines a series of relations, the system will satisfy the constraints by selecting proper state after the

Related papers

Genetic quantum algorithm and its application to combinatorial optimization problem

Kuk-Hyun Han, Jong-Hwan Kim

This paper proposes a novel evolutionary computing method called a genetic quantum algorithm (GQA). GQA 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 qubit chromosome as a representation GQA can represent a linear superposition of solutions due to its probabilistic representation. As genetic operators, quantum gates are employed for the search of the best solution. Rapid convergence and good global search capability characterize the performance of GQA. The effectiveness and the applicability of GQA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that GQA is superior to other genetic algorithms using penalty functions, repair methods and decoders.

IEEE Congress on Evolutionary Computation (CEC)Nov 7, 2002672 citations

Function Optimization Based on Quantum Genetic Algorithm

Ying Sun, Hegen Xiong

Optimization method is important in engineering design and application. Quantum genetic algorithm has the characteristics of good population diversity, rapid convergence and good global search capability and so on. It combines quantum algorithm with genetic algorithm. A novel quantum genetic algorithm is proposed, which is called Variable-boundary-coded Quantum Genetic Algorithm (vbQGA) in which qubit chromosomes are collapsed into variable-boundary-coded chromosomes instead of binary-coded chromosomes. Therefore much shorter chromosome strings can be gained. The method of encoding and decoding of chromosome is first described before a new adaptive selection scheme for angle parameters used for rotation gate is put forward based on the core ideas and principles of quantum computation. Eight typical functions are selected to optimize to evaluate the effectiveness and performance of vbQGA against standard Genetic Algorithm (sGA) and Genetic Quantum Algorithm (GQA). The simulation results show that vbQGA is significantly superior to sGA in all aspects and outperforms GQA in robustness and solving velocity, especially for multidimensional and complicated functions.

Research Journal of Applied Sciences Engineering and TechnologyJan 1, 201412 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 xuebaoJan 1, 200417 citations

A Novel Variable-Boundary-Coded Quantum Genetic Algorithm for Function Optimization

Hegen Xiong, Kai Xiong, Qiuhua Tang

Quantum genetic algorithm is a recently proposed new optimization algorithm combining quantum algorithm with genetic algorithm. It characterizes good population diversity, rapid convergence and good global search capability and so attracts serious and wide attentions. This paper proposes a novel quantum genetic algorithm called variable-boundary-coded quantum genetic algorithm (vbQGA) in which qubit chromosomes are collapsed into variable-boundary-coded chromosomes instead of binary-coded chromosomes. In this way we can obtain much shorter chromosome strings. The method of encoding and decoding of chromosome is first described before a new adaptive selection scheme for angle parameters used for rotation gate is put forward based on the core ideas and principles of quantum computation. Eight typical functions are selected to optimize to evaluate the effectiveness and performance of vbQGA against standard genetic algorithm (sGA) and genetic quantum algorithm (GQA) proposed by Han in [6]. The results show that vbQGA is significantly superior to sGA in all aspects and outperforms GQA in robustness and solving velocity, especially for multidimensional and complicated functions.

IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech)Dec 1, 20097 citations

A novel genetic algorithm based on the quantum chromosome

Shuyuan Yang, Fang Liu

The genetic algorithm is an efficient optimization tool for its independence of problems, intrinsic parallelism and inherent learning capacity; however, it has some disadvantages such as slow convergence and prematurity. In this paper, a novel algorithm, called the quantum genetic algorithm—QGA, is proposed based on the combination of the quantum theory with the evolutionary theory. By adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. The random observation simulating the quantum collapse can bring diverse individuals, and the evolution of quantum chromosome can also pilot the evolution. So it has better diversity than the classical genetic algorithm. Rapid convergence and good global search capacity characterize the performance of QGA. The paper not only proves the global convergence of the QGA, but also some simulation experiments are shown to prove its superiority over other algorithms.

Journal of Xidian UniversityJan 1, 200413 citations

Hybrid quantum search with genetic algorithm optimization

Mihai Udrescu, Sebastian Mihai Ardelean

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.

Jun 19, 20230 citations