arXiv:1007.4221 · Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

Building Blocks Propagation in Quantum-Inspired Genetic Algorithm

Robert Nowotniak, Jacek Kucharski

Published Jul 23, 2010• 8 citations

Abstract

This paper presents an analysis of building blocks propagation in Quantum-Inspired Genetic Algorithm, which belongs to a new class of metaheuristics drawing their inspiration from both biological evolution and unitary evolution of quantum systems. The expected number of quantum chromosomes matching a schema has been analyzed and a random variable corresponding to this issue has been introduced. The results have been compared with Simple Genetic Algorithm. Also, it has been presented how selected binary quantum chromosomes cover a domain of one-dimensional fitness function.

DOI: 10.48550/arxiv.1007.4221

Related papers

A new Quantum Inspired Genetic Algorithm for Evolvable Hardware

Rustem Popa, Viorel Nicolau, Silviu Epure

The developments in the area of Evolvable Quantum Hardware (QEHW) are based on successful quantum genetic algorithms (QGAs) that take advantage of both the Genetic Algorithms (GAs) and Quantum Computation (QC) parallelism. This paper presents a new Quantum Inspired Genetic Algorithm (QIGA) based on the evolution of a single chromosome. A simple combinational circuit has been implemented using a conventional GA (CGA), a single chromosome QGA (SCQGA), and the new QIGA. In the last case, the total evolution time has been considerably reduced, by changing the population size used in the evolution.

Sep 1, 20105 citations

Evolutionary algorithm based on evaluating quantum chromosomes

Quan Hui-yun

A novel quantum-inspired evolutionary algorithm is proposed in this paper.The rotation angle is calculated through current best solution of its group and the binary individual by evaluating a quantum chromosome,and adjusts with evolution.Compared with some other quantum inspired genetic algorithms the novel algorithm shows the outstanding performance on function optimization and Knapsack problems even if the population size is 1.

Computer Engineering and Applications JournalJan 1, 20071 citation

Searching ability of qubit-inspired genetic algorithm

Noriyuki Muramoto, Nobuyuki Matsui, Teijiro Isokawa

Qubit-inspired Genetic Algorithm (QGA) is an extension of genetic algorithm in which quantum mechanics and its representations are introduced. A chromosome in our QGA is concretized as a series of quantum-bit (qubit) described by its complex-valued representation, and phase-rotation gates are embedded into the selection process over generations. In our previous work, it has been shown that this scheme has better performances than the classical ones in several problems such as N-K landscape problem, Knapsack Problem, Maximum Search, and Construction of image filters. In this paper, we make clear the effectiveness of the QGA by comparing QGA with GA through minimum solution problem on De Jong's functions.

Society of Instrument and Control Engineers of JapanJan 1, 20120 citations

A Simple Quantum Inspired Evolutionary Algorithm and Its Application to Numerical Optimization Problems

Qing Yang

The paper develops a Simple Quantum Inspired Evolutionary Algorithm and evaluates it on some classical numerical optimization problems and the Need-in-a-haystack problem.The proposed algorithm represents a qubit with a radian and uses only one quantum chromosome.Special operators of rotation and mutation and the method to evaluate a quantum chromosome are presented too.Compared with some other quantum inspired genetic algorithms and the classical genetic algorithm,the novel algorithm shows the outstanding performance and solves the Need-in-a-haystack problem perfectly.

Journal of Wuhan UniversityJan 1, 20067 citations

Quantum-inspired genetic algorithm based on phase encoding

Xiande Liu, Xiaoming Liu

Due to frequent decoding operations, the efficiency of optimization is severely reduced when the binary quantum genetic algorithm based on qubits measure is applied to the continuous space optimization. To solve this problem, a quantum genetic algorithm based on phase encoding is proposed in this paper. In this method, the chromosomes are encoded by the phase of qubits, evolved by quantum rotation gates, and mutated by quantum Pauli-Z gates. As the optimization process is performed in [0, 2π], which has nothing to do with specific issues, therefore, the proposed method has good adaptability for a variety of optimization problems. With application of function extremum optimization, the simulation results show that the approach is superior to common quantum genetic algorithm and simple genetic algorithm in both search capability and optimization efficiency.

International Conference on Natural Computation (ICNC)Jul 1, 20138 citations

A Dynamic Quantum-Inspired Genetic Algorithm with Lengthening Chromosome Size

Shahin Hakemi, Mahboobeh Houshmand, Seyyed Abed Hosseini

Abstract This paper proposes a Dynamic Quantum-inspired Genetic Algorithm (DQGA), which combines the quantum mechanics concepts with metaheuristics principles to enhance the search capability of the genetic algorithm. The proposed algorithm also introduces the lengthening chromosome strategy for a balanced and smooth transition between exploration and exploitation phases. Apart from that, a novel adaptive look-up table for rotation gates is presented to boost the algorithm's optimization abilities. To evaluate the effectiveness of these ideas, the DQGA is tested by various mathematical benchmark functions as well as real-world constrained engineering problems against several well-known and state-of-the-art algorithms. The obtained results indicate the merits of the proposed algorithm.

Nov 8, 20220 citations