Scientific Papers on Quantum-Inspired Evolutionary Algorithms

Robert Nowotniak, PhD


RNowotniak-quantum-inspired-bibliography-2013.pdf --- formatted full bibliography in PDF
quantum-inspired-bibliography-2013.bib --- full bibliography in BibTeX format
tags:
Show/hide abstracts and notes
author year title
Baojun, Zhang and Ruifang, Pan and Fujun, Ye 2014 Analyzing and Improving Load Balancing Algorithm of MooseFS. Google
Nowotniak, Robert and Kucharski, Jacek 2014 Higher-Order Quantum-Inspired Genetic Algorithms Google
Zhou, Rigui and Cao, Jian 2014 Quantum novel genetic algorithm based on parallel subpopulation computing and its application Google
Liang, JJ and Qu, BY and Suganthan, PN and Hern{\'a}ndez-D{\'\i}az, Alfredo G 2013 Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization Google
Song, Qiang and Liu, Xialing 2013 Hybrid Quantum Evolutionary Algorithm and Its Application in Multiuser Detection of Electronic Communication System   abstract Google
Abstract: This paper combines quantum evolutionary algorithm (QEA) with particle swarm optimization (PSO) together, proposes two kinds of hybrid quantum evolutionary algorithm. One is particle swarm embedded quantum evolutionary algorithm (PSEQEA); another one is quantum binary particle swarm optimization (QBPSO). The experiment results of multiuser detection problem show that both of the methods not only have simpler algorithm structure, but also perform better than conventional QEA and BPSO in terms of ability of global search optimum. In the third generation mobile communication system, multiuser detection technology is one of the most effective ways to solve multi-access interference in electronic communication system; these two algorithms can simplify and accelerate the detection process.
Charan Kumari, A. and Srinivas, K. and Gupta, M. P. 2013 Software Requirements Optimization Using Multi-Objective Quantum-Inspired Hybrid Differential Evolution   abstract Google
[multiobj][app]
Abstract: Multi-Objective Next Release Problem (MONRP) is an important software requirements optimization problem in Search-Based Software Engineering. As the customer requirements varies from time to time, often software products are required to incorporate these changes. It is a hard task to optimize the requirements from a large number of candidates, for the accomplishment of the business goals and at the same time, the satisfaction of the customers. MONRP identifies a set of requirements to be included in the next release of the product, by minimizing the cost in terms of money or resources, and maximizing the number of customers to get satisfied by including these requirements. The problem is multi-objective in nature and the objectives are conflicting objectives. The problem is NP-hard and since it cannot be solved effectively and efficiently by traditional optimization techniques especially for large problem instances, Metaheuristic Search and Optimization Techniques are required. Since MONRP has wide applicability in software companies and manufacturing companies, there is a need for efficient solution techniques especially for the large problem instances. Therefore, this paper presents a Multi-objective Quantum-inspired Hybrid Differential Evolution (MQHDE) for the solution of MONRP which combines the strengths of Quantum Computing, Differential Evolution and Genetic Algorithm. The features of MQHDE help in achieving consistency in performance in terms of convergence to Pareto-optimal front, good spread among the obtained Pareto-optimal front solutions, faster convergence and obtaining relatively more number of solutions along the Pareto-optimal front. The performance of MQHDE is tested on six benchmark problems using Spread and HyperVolume metrics. The comparison of the obtained results indicates consistent and superior performance of MQHDE over the other methods reported in the literature.
Bansal, Sulabh 2013 Algorithm Engineering for solution of some hard Combinatorial Optimization Problems Google
Perroni, Peter Frank 2013 Point spread function estimation of solar surface images with a cooperative particle swarm optmization on GPUS Google
Liang, JJ and Qu, BY and Suganthan, PN and Hern{\'a}ndez-D{\i}az, Alfredo G 2013 Problem definitions and evaluation criteria for the cec 2013 special session on real-parameter optimization Google
Bao, X.H. and Xu, X.F. and Li, C.M. and Yuan, Z.S. and Lu, C.Y. and Pan, J.W. 2012 Quantum teleportation between remote atomic-ensemble quantum memories Google
Nowotniak, R. and Kucharski, J. 2012 GPU-based tuning of quantum-inspired genetic algorithm for a combinatorial optimization problem Google
Muramoto, Noriyuki and Matsui, Nobuyuki and Isokawa, Teijiro 2012 Searching ability of qubit-inspired genetic algorithm   abstract PDF Google
Abstract: 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.
Dias, Douglas Mota and Pacheco, Marco AurĂŠlio C. 2012 Quantum-Inspired Linear Genetic Programming as a Knowledge Management System   abstract Google
Abstract: The superior performance of quantum computers in some problems lies in the direct use of quantum mechanics phenomena. This ability has originated the quantum-inspired evolutionary algorithms (QIEAs), which are classical algorithms (for classical computers) that exploit quantum mechanics principles to improve their performance. Several proposed QIEAs are able to outperform their traditional counterparts when applied to different kinds of problems. Aiming to exploit this new paradigm on genetic programming (GP), this paper introduces a novel QIEA model (quantum-inspired linear GP—QuaLiGP), which evolves machine code programs. QuaLiGP is inspired on multi-level quantum systems, and its operation is based on quantum individuals, which represent a superposition of all programs (solutions) of the search space. The tests use symbolic regression and binary classification as knowledge management problems to assess the QuaLiGP performance and compare it with Automatic Induction of Machine Code by Genetic Programming model, which is currently the most efficient GP model to evolve machine code. Results show that QuaLiGP outperforms the reference GP system for all these problems, by achieving better solutions from a smaller number of evaluations and by using fewer parameters and operators. This paper concludes that the quantum-inspired paradigm can be a competitive approach to evolve programs efficiently, encouraging improvements and extensions of QuaLiGP.
Yasin, Z.M. and Rahman, T.K.A. and Zakaria, Z. 2012 Multiobjective quantum-inspired evolutionary programming for optimal load shedding   abstract PDF Google
Abstract: This paper present new technique namely Quantum-Inspired Evolutionary Programming (QIEP) to determine the optimal location and optimal amount of load to be shed for undervoltage load shedding schemes. This approach is based on the concept of quantum mechanics in the Evolutionary Programming (EP). Quantum-Inspired is implemented according to three levels defined by quantum individuals, quantum groups and quantum universe in order to improve the speed of the algorithm. The QIEP is employed to search for the best location and amount of load to be shed based on multiobjective functions which are power loss minimisation, voltage profile improvement and power interruption cost minimisation. The effectiveness of multiobjective QIEP optimisation technique is illustrated in IEEE 33-bus distribution test system, IEEE 69-bus distribution test system and 141-bus distribution system. The results were also compared with other techniques in terms of fitness values and computation time.
Rui Wang and Ning Guo and Fenghong Xiang and Jianlin Mao 2012 An improved quantum genetic algorithm with mutation and its application to 0-1 knapsack problem   abstract PDF Google
[knapsack]
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 #x2013;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.
Li Hao and Li Shiyong 2012 Quantum particle swarm evolutionary algorithm with application to system identification   abstract Google
[swarm]
Abstract: Based on quantum evolutionary algorithm and particle swarm optimization, a quantum particle swarm evolutionary algorithm is proposed. In this algorithm, quantum angle is used to represent the qubit, a new method learning from the idea of particle swarm algorithm is presented to determine rotation angle, He gate is taken to prevent from premature convergence. Applying this algorithm to identify system parameter, and comparing with conventional genetic algorithm and quantum evolutionary algorithm, the experimental results illustrate that the proposed algorithm has better performance than that of others. Meanwhile, it can also keep high identification ability to the system with the existence of noise.
Zhang, Xiu Jie and Li, Shi Yong and Shen, Yi and Song, Shen Min 2012 Evaluation of several quantum genetic algorithms in medical image registration applications   abstract Google
[app]
Abstract: Registration is an important problem and a fundamental task in image processing. Recently, quantum-inspired evolutionary algorithms(QEA) have been proposed and applied to many optimization problems. However, few people study the application of QEA for image registration. This paper evaluate three kinds of QGAs in medical image registration applications, in which QGAs are implemented to find approximate solutions that maximizes the maximum mutual information(MI), and the experimental results are compared and analyzed.
Porownanie trzech alg (Han, Bloch-coordinates + QEA gradient info.) Taki sobie artykul
Bin Li and Zheng Zhou and Weixia Zou and Dejian Li 2012 Quantum Memetic Evolutionary Algorithm-Based Low-Complexity Signal Detection for Underwater Acoustic Sensor Networks   abstract Google
Abstract: Modern communication engineering has brought forward impractical requirements on powerful computation engines as well as simple implementations. Apparently, the two aspects are contradicted in most realistic applications. Because of the dispersive multipath propagation in underwater acoustic channels, traditional coherent and adaptive receivers are computationally intensive and, hence, inapplicable to the large-scale underwater sensor networks. Inspired by quantum computing and nature intelligence that are incorporated with the concept of culture evolution, in this paper, we suggest a novel quantum memetic algorithm (QMA) built with more qualified problem-solving ability. Instead of classical gene representations, the quantum bit structure is employed by chromosomes to enhance the population diversity of genetic searching. The quantum gate rotating is then explored to update chromosomes in an efficiently parallel way. As a hybridization strategy, quantum-rotation-based local search is integrated in the lifetime learning to further refine individuals' performance and accelerate their convergence toward the global optimality. As a significant real-world application, we develop a noncoherent underwater signal receiver that is based on a QMA framework. From a pattern recognition aspect, the suggested detection scheme includes two sequential phases: Features extraction and pattern classification. Finally, the highly computational optimization problem is elegantly addressed by QMA. Providing favorable robustness to various parameter configurations, QMA can considerably reinforce the search performance and improve the underwater signal detection. It is demonstrated from numerical experiments that QMA is much superior to genetic algorithm (GA) in this high-dimensional optimization. Meanwhile, QMA shows remarkable advantages in search performance, even to the current state-of-the-art quantum-inspired GA and memetic algorithm.
Si-Jung Ryu and Ki-Baek Lee and Jong-Hwan Kim 2012 Improved version of a multiobjective quantum-inspired evolutionary algorithm with preference-based selection   abstract Google
[selection]
Abstract: Multiobjective quantum-inspired evolutionary algorithm (MQEA) employs Q-bit individuals, which are updated using rotation gate by referring to nondominated solutions in an archive. In this way, a population can quickly converge to the Pareto optimal solution set. To obtain the specific solutions based on user's preference in the population, MQEA with preference-based selection (MQEA-PS) is developed. In this paper, an improved version of MQEA-PS, MQEA-PS2, is proposed, where global population is sorted and divided into groups, upper half of individuals in each group are selected by global evaluation, and selected solutions are globally migrated. The global evaluation of nondominated solutions is performed by the fuzzy integral of partial evaluation with respect to the fuzzy measures, where the partial evaluation value is obtained from a normalized objective function value. To demonstrate the effectiveness of the proposed MQEA-PS2, comparisons with MQEA and MQEA-PS are carried out for DTLZ functions.
Silveira, L.R. and Tanscheit, R. and Vellasco, M. 2012 Quantum-inspired genetic algorithms applied to ordering combinatorial optimization problems   abstract Google
[TSP][representation]
Abstract: This article proposes a new algorithm based on evolutionary computation and quantum computing. It attempts to resolve ordering combinatorial optimization problems, the most well known of which is the traveling salesman problem (TSP). Classic and quantum-inspired genetic algorithms based on binary representations have been previously used to solve combinatorial optimization problems. However, for ordering combinatorial optimization problems, order-based genetic algorithms are more adequate than those with binary representation, since a specialized crossover process can be employed in order to always generate feasible solutions. Traditional order-based genetic algorithms have already been applied to ordering combinatorial optimization problems but few quantum-inspired genetic algorithms have been proposed. The algorithm presented in this paper contributes to the quantum-inspired genetic approach to solve ordering combinatorial optimization problems. The performance of the proposed algorithm is compared with one order-based genetic algorithm using uniform crossover. In all cases considered, the results obtained by applying the proposed algorithm to the TSP were better, both in terms of processing times and in terms of the quality of the solutions obtained, than those obtained with order-based genetic algorithms.
objaśnienie jak uzywac QIEA dla TSP -- reprezentacja
Kumari, A.C. and Srinivas, K. and Gupta, M.P. 2012 Software requirements selection using Quantum-inspired Elitist Multi-objective Evolutionary algorithm   abstract Google
Abstract: This paper proposes a Quantum-inspired Elitist Multi-objective Evolutionary algorithm (QEMEA) for software requirements selection, a problem in search based software engineering. Most often software product developments are iterative and incremental in their nature, due to the changes in the customer requirements from time to time. It is a challenging task to select the requirements from a large number of candidates, for the accomplishment of the business goals. The problem is to identify a set of requirements to be included in the next release of the product, by minimizing the cost and maximizing the customer satisfaction. Since minimizing the total cost and maximizing the customer satisfaction are contradictory objectives, the problem has a multi-objective nature. This problem is NP-hard in its nature and so it cannot be solved efficiently by using traditional optimization techniques for large problem instances. QEMEA combines the best features of Evolutionary Algorithms and Quantum Computing. It employs the concepts of Quantum computing such as superposition and interference. The features of QEMEA help in achieving quality pareto-optimal front solutions and faster convergence while using a small population size. The performance of QEMEA is tested on six benchmark problems derived from the literature. The obtained results indicates consistent and superior performance of the algorithm.
Izadinia, H. and Ebadzadeh, M.M. 2012 Adaptive Quantum-inspired Evolution Strategy   abstract PDF Google
[!!!][real]
Abstract: Standard Evolution Strategy (ES) produces the next generation via the Gaussian mutation that is not directed toward the optimum. Additionally, self-adaptation mechanism is used in the standard ES to adapt mutation step-size. This paper presents a new evolution strategy which is called Quantum-inspired Evolution Strategy (QES). QES applies a new learning mechanism whereby the information of the mutants is used as a feedback to adapt the mutation direction and step-size simultaneously. To demonstrate the effectiveness of the proposed method, several experiments on a set of numerical optimization problems are carried out and the results are compared with the standard ES and Covariance Matrix Adaptation ES (CMA-ES) which is the state-of-the-art method for adaptive mutation. The results reveal that QES is superior to standard ES and CMA-ES in terms of convergence speed and accuracy.
Comparison with CMA-ES
Yongqiang Wang and Jianzhong Zhou and Li Mo and Shuo Ouyang and Yongchuan Zhang 2012 A clonal real-coded quantum-inspired evolutionary algorithm with Cauchy mutation for short-term hydrothermal generation scheduling   abstract Google
Abstract: The short-term hydrothermal generation scheduling (SHGS) problem considered valve-point effects and transmission losses is a complicated problem which has the characteristics of nonlinear and non-convex. This paper presents a clonal real-coded quantum-inspired evolutionary algorithm (CRQEA) with Cauchy mutation for solving SHGS problem. In this proposed algorithm, real-coded rule is adopted for handling continuous variables. Meanwhile, clonal operator and Cauchy mutation are integrated into the proposed algorithm to avoid premature convergence. Moreover, heuristic strategies are designed for dealing with all kinds of constraints effectively. Finally, three test systems are employed to verify the feasible and effectiveness the proposed CRQEA. Compared with other reported methods, the obtained results clearly illustrates that CRQEA has better performances.
Yongqiang Wang and Jianzhong Zhou and Li Mo and Rui Zhang and Yongchuan Zhang 2012 Short-term hydrothermal generation scheduling using differential real-coded quantum-inspired evolutionary algorithm   abstract PDF Google
[real]
Abstract: Short-term hydrothermal generation scheduling aims at determining optimal hydro and thermal generations to achieve minimum fuel cost of thermal plants for a 1 day or a 1 week while meeting various hydraulic and electric system constraints. The problem is viewed as a complex and nonlinear hard problem considering valve-points effects and transmission losses with a set of operation operational and physical constraints. This paper presents a novel effective differential real-coded quantum-inspired evolutionary algorithm (DRQEA) for solving this complicated problem. Some improvements like real-coded rule, adaptive differential mutation and crossover mechanism are proposed in DRQEA to enhance the global search ability in continuous space. Meanwhile, various constraints are handled effectively by using heuristic strategies designed by their characteristics. The effectiveness of the proposed approach is demonstrated on two hydrothermal test systems, which consist of two sub-systems: hydro sub-system and thermal sub-system. The obtained results of the proposed approach are compared with other methods, and simulation and comparison results clearly show that DRQEA is able to provide better solution than other reported methods, both in the solution quality and the convergence speed. The proposed algorithm can also apply to other dynamic optimization problem with nonlinear and non-convex characteristics in power system.
Andressa dos Santos Nicolau and Roberto Schirru and Alan Miranda Monteiro de Lima 2012 Nuclear reactor reload using Quantum Inspired Algorithm   abstract Google
Abstract: Nuclear Reactor Reload Optimization Problem (NRROP), which focuses on the economics and safety of the Nuclear Power Plant (NPP), is a classical problem in Nuclear Engineering that has been studied for more than 40 years. For decades, the NRROP was carried out by specialists that used their knowledge and experience to build configurations of the reactor core aiming at fulfilling the safety regulations of the NPP. Since the1980s, however, researchers have proposed metaheuristics optimization to automate this process. Recently, new researches have shown that Quantum Inspired Evolutionary Algorithms are among the best alternatives to deal with optimization problems in Nuclear Engineering. In the present work, Quantum Evolutionary Algorithm (QEA) is used for optimizing the NRROP of a Brazilian “2-loop” Pressurized Water Reactor (PWR) Nuclear Power Plant, Angra 1. The main goal of this research is to show the performance of QEA to solve the NRROP compared with its classical counterpart, the Genetic Algorithm (GA). In addition, manual reload and other optimization methods are also used to demonstrate the feasibility of QEA to solve cycle 7 of Angra 1. The performance of QEA, such as search ability and fast convergence, is better than GA and compatible with other Quantum Inspired Evolutionary Algorithms presented in the literature.
Yin, Guisheng and Li, Jia and Dong, Hongbin and Wei, Jijie 2012 Quantum Genetic Algorithm Using a Mixed Update Strategy   abstract Google
Abstract: In order to improve the adaptability of optimization algorithm and solve different types of function optimization problems, a quantum genetic algorithm using a mixed update strategy (MUSQGA) is proposed in this paper. It integrates particle swarm optimization and dynamic rotation gate into the quantum genetic algorithm. In the population each individual utilizes a mixed update strategy to update the angle of quantum rotation gate. To verify the performance of the algorithm, ten representative functions are selected as a testing function set and two groups of comparative experiments are carried out. The experimental results show that MUSQGA is effective and feasible.
Pla, J.J. and Tan, K.Y. and Dehollain, J.P. and Lim, W.H. and Morton, J.J.L. and Jamieson, D.N. and Dzurak, A.S. and Morello, A. 2012 A single-atom electron spin qubit in silicon Google
Kurzweil, R. 2012 How to Create a Mind: The Secret of Human Thought Revealed Google
Manju, A. and Nigam, M. 2012 Applications of quantum inspired computational intelligence: a survey   abstract PDF Google
[survey][!!!]
Abstract: This paper makes an exhaustive survey of various applications of Quantum inspired computational intelligence (QCI) techniques proposed till date. Definition, categorization and motivation for QCI techniques are stated clearly. Major Drawbacks and challenges are discussed. The significance of this work is that it presents an overview on applications of QCI in solving various problems in engineering, which will be very much useful for researchers on Quantum computing in exploring this upcoming and young discipline.
R. Nowotniak and J. Kucharski 2012 Convergence Analysis of Quantum-Inspired Evolutionary Algorithms Based on The Banach Fixed-Point Theorem Google
R. Nowotniak 2012 Meta-optimization of Quantum-Inspired Evolutionary Algorithms in The Polish Grid Infrastructure Google
Banerjee, A. and Abu-Mahfouz, I. 2011 Evolutionary algorithm-based parameter identification for nonlinear dynamical systems   abstract Google
Abstract: The inverse problem of parameter estimation for Duffing oscillator, a chaotic dynamical system well known in engineering is solved using quantum-inspired evolutionary algorithm, differential evolution and genetic algorithms. The paper focuses on such combination of parameters that produce periodic responses instead of purely chaotic responses. The feature set used is a set of displacement values of the first five Poincare points, after ignoring transient effects. All approaches correctly identify the target set of parameters as producing the given response; however, depending on the fitness landscape some parameters are more difficult to identify than others especially when using the canonical genetic algorithm. This paper is also the first to investigate the quantum-inspired evolutionary algorithm for such parameter identification problems.
Behnel, Stefan and Bradshaw, Robert and Citro, Craig and Dalcin, Lisandro and Seljebotn, Dag Sverre and Smith, Kurt 2011 Cython: The best of both worlds Google
Zak, M. 2011 From Quantum Computing to Intelligence Google
Nvidia, CUDA 2011 NVIDIA CUDA programming guide Google
Xu, N. and Zhu, J. and Lu, D. and Zhou, X. and Peng, X. and Du, J. 2011 Quantum factorization of 143 on a dipolar-coupling nmr system Google
Yin, X.F. and Khoo, L.P. 2011 An exact schema theorem for adaptive genetic algorithm and its application to machine cell formation PDF Google
[other][theoretical]
Seung-Yoon Cho and Joon-Woo Lee and Ju-Jang Lee 2011 Type-2 Fuzzy PD Controller Tuning using Quantum-inspired Evolutionary algorithm   abstract Google
Abstract: Fuzzy Logic Controller (FLC) is used widely since it can control non-linear system which are hard to be solved by conventional control method. The design of fuzzy logic controller (FLC), however, has some difficulties such as formation of the fuzzy rules, tuning of the scale factor and the rule explosion. The decision of fuzzy rules are not easy since the fuzzy rule is formed by the expert's experience. Finding suitable scale factor is difficult as conventional PID ones since it takes long time. As input increase, fuzzy rule increase exponentially. To overcome these problems, the information integration is used for preventing the rule explosion and fixed the fuzzy rules and scaling factor is used. we proposed Fuzzy PD Controller Tuning method by using Quantum-inspired Evolution algorithm (QEA). This proposed method also was demonstrated by control of double inverted pendulum.
Pareek, U. and Naeem, M. and Lee, D.C. 2011 Quantum Inspired Evolutionary algorithm for joint user selection and power allocation for uplink cognitive MIMO systems   abstract Google
Abstract: In this paper, we consider the uplink communication in a network of cognitive radio nodes. The transmitting nodes and the receiver are equipped with multiple antennas and MIMO processing abilities. For this network, we study the problem of interference-aware joint secondary user (SU) selection/scheduling and power control (JSUS-QPC). The main objective of the JSUS-QPC is to maximize the sum-rate capacity of the cognitive MIMO uplink communication system under the constraint that the interference to the primary users (PU) is below a specified level. We formulate this optimization problem as nonlinear integer programming problem. The computational complexity of finding an optimal solution to the JSUS-QPC problem by exhaustive search grows exponentially with the number of users and power levels. Therefore, we apply a Quantum Inspired Evolutionary algorithm (QIEA) to determine the suboptimal solution to the JSUS-QPC problem. The proposed scheme has low computational complexity and its results are comparable to the optimal exhaustive search algorithm.
Gao Lin 2011 A novel real-coded quantum-inspired genetic algorithm and its application in data reconciliation   abstract PDF Google
[real][app]
Abstract: Data reconciliation techniques play a significant role in the industrial manufacture process, especially in the petrochemical industry. Different heuristic optimization methods have been proposed to solve this problem in previous study. In this paper, a novel real-coded quantum-inspired genetic algorithm (RLCQGA) is proposed, which has stronger search ability and quicker convergence speed, not only because of the introduction of real number coding method, but also due to interval division technique. The proposed approach is tested with five standard benchmark functions and two industrial process cases. Detailed comparisons with similar approaches are given and discussed. The promising results illustrate the efficiency of the proposed method and show that it could be used as a reliable tool for solving nonlinear data reconciliation problems.
Shengqiu Yi and Ming Chen and Zhigao Zeng 2011 Convergence analysis on a class of quantum-inspired evolutionary algorithms   abstract Google
[theoretical]
Abstract: In this article we focus on the theoretical analysis of quantum-inspired evolutionary algorithms with H #x03F5; gate. Applying the theory and analytical techniques in non-homogeneous Markov chains, we obtain the conclusion that quantum-inspired evolutionary algorithms converge in probability under some mild conditions. Moreover, we estimate the convergence rate relating to parameters of algorithms.
Ali, H.M. and Ashrafinia, S. and Jiangchuan Liu and Lee, D.C. 2011 Wireless Mesh Network Planning Using Quantum Inspired Evolutionary Algorithm   abstract Google
Abstract: The latest increase in mobile data usage and emergence of new applications such as Multimedia Online Gaming (MMOG), mobile TV and streaming contents have motivated advances in wireless broadband systems. Recently, the Long-Term Evolution (LTE) technology, which is based on the Universal Mobile Telecommunications System (UMTS) specifications, joins WiMAX as a competitor to achieve increasing demands of the broadband wireless access. Careful deployment of such a network is required to fulfill the high data rate demands with minimal cost of infrastructure and comprehensive coverage of the subscribers. In this paper, a multi-objective network planning problem is defined as utilizing the minimum number of infrastructure sites (i.e. Base Stations or eNode B in UMTS systems) while maximum number of users in service. We proposed a Quantum Inspired Evolutionary Algorithm (QIEA) in order to achieve optimized solution for this problem. The QIEA can be viewed as a probabilistic evolutionary algorithm and thus it is plausible to expect a reasonably good performance in solving combinatorial optimization problems. In this algorithm, each individual is represented by a string of Q-bits, where a Q-bit is the probabilistic representation inspired by the qubit concept in the quantum computing. Computational experiments show that our algorithm is fairly efficient to different scenarios of the network planning problem and performs better than the Genetic Algorithm (GA).
Ibrahim, A.A. and Mohamed, A. and Shareef, H. and Ghoshal, S.P. 2011 An effective power quality monitor placement method utilizing quantum-inspired particle swarm optimization   abstract Google
Abstract: This paper presents an effective power quality monitor (PQM) placement method for voltage sag assessment by utilizing quantum-inspired particle swarm optimization technique. The optimization handles the observability constraints based on the topological monitor reach area concept and solves a multi-objective function in obtaining the optimal number and placement of PQMs in power systems. The objective function consists of two functions which are based on monitor overlapping index and sag severity index. In this study, the optimization performance of the proposed technique is compared to that of the standard binary particle swarm optimization and the existing method using genetic algorithm. All the optimization algorithms have been implemented and tested on the IEEE 69-bus and the 118-bus test systems to evaluate the effectiveness of the techniques.
Shill, P.C. and Hossain, M.A. and Amin, M.F. and Murase, K. 2011 An adaptive fuzzy logic controller based on real coded quantum-inspired evolutionary algorithm   abstract PDF Google
[real][app]
Abstract: In this paper, fuzzy logic control systems and real coded quantum inspired evolutionary algorithm (RCQIEA) are integrated for intelligent control. Here, RCQIEAs is utilized as an adaptive method for selection and definition of fuzzy control rules and for tuning the parameters of membership function for each fuzzy control rule in two different ways. The majority of fuzzy logic controllers (FLCs) to date are working based on the expert knowledge base derived from heuristic knowledge of experienced operators. These approaches are difficult and time consuming for experts. Moreover, because manual coded FLCs use expert knowledge, there is no guarantee that the FLCs obtained will have sufficiently good performance, especially for a complex system problem with a large number of input variables. On the contrary, our proposed approach is an automatic knowledge acquisition learning method for generating or adapting FLCs using RCQIEA. In order to check the effectiveness of our proposed approach, it has been applied to solve the truck-and-trailer controller, which is well known test-bed for fuzzy control systems. The fuzzy controller obtained by the proposed approach performs better and effectively realizes the trajectory control of the truck with trailer.
Gharipour, A. and Jazi, A.Y. and Sameti, M. 2011 Forecast combination with optimized SVM based on quantum-inspired hybrid evolutionary method for complex systems prediction   abstract Google
Abstract: Complex systems are complex, evolutionary, and dynamical system. One general method to predict such systems is use the previous and most recently behavior of a system to predict its future changes. The main advantage of this method is the ability to predict the behavior of systems without analytical prediction rules. In this situation, decision makers are often presented with several competing forecasts produced by different forecasting methods. A decision maker who needs a predict could choose a combined forecast that is generally more precise than any of the individual forecasts, for the combined forecast gets more information into consideration and the preciseness of the combined forecast improves as more methods are included in the combination. This article proposes a new forecast combination strategy, by using support vector machines that improve the forecasting capability of the model. Finally the results of using this method on two sample datasets are presented and the superiority of this method is demonstrated.
Li, Y.Y. and Wu, N.N. and Liu, R.C. 2011 Improved quantum-inspired immune clonal clustering algorithm applied to SAR image segmentation   abstract Google
Abstract: The goal of segmentation is to partition an image into disjoint regions. In this paper, the segmentation problem based on partition clustering is viewed as a combinatorial optimization problem. The original image is partitioned into small blocks by watershed algorithm, and the quantum-inspired immune clonal algorithm is used to search the optimal clustering centre, and make the sequence of maximum affinity function as clustering result, and finally obtain the segmentation result. Experimental results show that the proposed method is effective for SAR image segmentation.
Dias, D.M. and Singulani, A.P. and Pacheco, M.A.C. and de Souza, P.L. and Pires, M.P. and Neto, O.P.V. 2011 Self-assembly quantum dots growth prediction by quantum-inspired linear genetic programming   abstract Google
Abstract: In this work we present the application of quantum inspired linear genetic programming (QILGP) to the growth of self-assembled quantum dots. Quantum inspired linear genetic programming is a novel model to evolve machine code programs exploiting quantum mechanics principles. Quantum dots are nanostructures that have been widely applied to optoelectronics devices. The method proposed here relies on an existing database of growth parameters with a resulting quantum dot characteristic to be able to later obtain the growth parameters needed to reach a specific value for such a quantum dot characteristic. The computational techniques were used to associate the growth input parameters with the mean height of the deposited quantum dots. Trends of the quantum dot mean height behavior as a function of growth parameters were correctly predicted, improving on the results obtained by artificial neural network and classical genetic programming.
Yu Zheng and Jingfa Liu 2011 A novel quantum-inspired genetic algorithm for a weekly university scheduling optimization   abstract Google
Abstract: This paper presents a novel quantum-inspired algorithm(QGA) for the heavily constrained university scheduling problems(CUSP). The CUSP is a common problem for all institutions of higher education. It has been proved a NP problems. We propose a solving of CUSP based on the use of quantum-inspired algorithms. In the QGA, Q-bits based representation is employed by updating operator of quantum gate which is introduced as a variation operator to drive the individuals toward better solutions. The experimental results show that a set of high quality timetables can be achieved.
XiuLi Wu and SuJian Li 2011 A quantum inspired algorithm for the job shop scheduling problem   abstract Google
Abstract: The classical job shop scheduling problem (JSP) is typically NP hard. A quantum inspired algorithm is proposed to solve the JSP. Firstly, the JSP is formulated. Secondly, the detail of the quantum inspired algorithm is designed, including the quantum chromosome encoding and decoding mechanism, the updating method with the rotation gate matrix. The elitist strategy is integrated to speed up the convergence. Finally, the experiment with the FT06 instance shows the effectiveness and efficiency of the proposed approach.
Chung, C.Y. and Han Yu and Kit Po Wong 2011 An Advanced Quantum-Inspired Evolutionary Algorithm for Unit Commitment   abstract PDF Google
[app][initialization]
Abstract: Based on a quantum-inspired evolutionary algorithm for unit commitment, this paper proposed ways to advance the efficiency and robustness of the algorithm so that its capacity for application in large-scale unit commitment problems can be significantly enhanced. The paper develops an advanced quantum-inspired evolutionary unit commitment algorithm by developing a new initialization method based on unit priority list and a special Q-bit expression for ensuring diversity in the initial search area for improving the efficiency of solution searching. Different techniques such as multi-observation, single-search, and group-search are also proposed for incorporation in the advanced algorithm. The advanced algorithm is tested and compared with the earlier quantum-inspired evolutionary algorithm and a number of known methods through its applications to test systems with up to 100 generator units for a 24-h scheduling horizon.
Ming Chen and Lixin Ding 2011 Analysis on the Convergence of Quantum-inspired Evolutionary Algorithms   abstract PDF Google
[!!!][knapsack][theoretical]
Abstract: This article deals with the convergence of quantum-inspired evolutionary algorithms with one quantum individual and multiple observations. Applying the theory and analytical techniques in non-homogeneous Markov chain, we obtain the conclusion that quantuminspired evolutionary algorithms could converge in probability under some mild conditions imposed on the probability amplitude of the Q-bit individual. We also analyze three cases from both theoretical and experimental viewpoints. The QEA with rotation gate can not guarantee convergence in theory, while others with modified Q-gates meet the convergence conditions. Numerical results further illustrate feasibleness and effectiveness of the improved algorithms.
P.C. Li and K.P. Song and F.H. Shang 2011 Double chains quantum genetic algorithm with application to neuro-fuzzy controller design   abstract PDF Google
[!!!][real][app][operators][representation][theoretical]
Abstract: This paper proposes a double chains quantum genetic algorithm (DCQGA), and shows its application in designing neuro-fuzzy controller. In this algorithm, the chromosomes are composed of qubits whose probability amplitudes comprise gene chains. The quantum chromosomes are evolved by quantum rotation gates, and mutated by quantum non-gates. For the direction of rotation angle of quantum rotation gates, a simple determining method is proposed. The magnitude of rotation angle is computed by integrating the gradient of the fitness function. Furthermore, a normalized neuro-fuzzy controller (NNFC) is constructed and designed automatically by the proposed algorithm. Application of the DCQGA-designed NNFC to real-time control of an inverted pendulum system is discussed. Experimental results demonstrate that the designed NNFC has very satisfactory performance.
A novel DCQGA algorithm for continous global optimization + convergence analysis + application
P. Arpaia and D. Maisto and C. Manna 2011 A Quantum-inspired Evolutionary Algorithm with a competitive variation operator for Multiple-Fault Diagnosis   abstract Google
Abstract: A heuristic search algorithm, the Quantum-inspired Competitive Evolutionary Algorithm (QuCEA), based on both quantum and evolutionary computing, is proposed. The individuals of a population, coded as qubit strings, evolve by means of an original variation operator inspired by competitive learning. The proposed operator is application independent and intuitively controllable by a single real parameter. QuCEA has been applied to Multiple-Fault Diagnosis, a typical NP-hard problem for industrial diagnosis. In particular, the proposed algorithm gives remarkable results both in simulation and in on-field tests for a lift monitoring system, also in comparison with a standard genetic algorithm and a state-of-the-art Quantum-inspired Evolutionary Algorithm.
Tzyy-Chyang Lu and Jyh-Ching Juang 2011 Quantum-inspired space search algorithm (QSSA) for global numerical optimization   abstract PDF Google
[real]
Abstract: This work presents the evolutionary quantum-inspired space search algorithm (QSSA) for solving numerical optimization problems. In the proposed algorithm, the feasible solution space is decomposed into regions in terms of quantum representation. As the search progresses from one generation to the next, the quantum bits evolve gradually to increase the probability of selecting the regions that render good fitness values. Through the inherent probabilistic mechanism, the QSSA initially behaves as a global search algorithm and gradually evolves into a local search algorithm, yielding a good balance between exploration and exploitation. To prevent a premature convergence and to speed up the overall search speed, an overlapping strategy is also proposed. The QSSA is applied to a series of numerical optimization problems. The experiments show that the results obtained by the QSSA are quite competitive compared to those obtained using state-of-the-art IPOP-CMA-ES and QEA.
za trudne chyba
JĂşlio Xavier Vianna Neto and Diego Luis de Andrade Bernert and Leandro dos Santos Coelho 2011 Improved quantum-inspired evolutionary algorithm with diversity information applied to economic dispatch problem with prohibited operating zones   abstract Google
Abstract: The objective of the economic dispatch problem (EDP) of electric power generation, whose characteristics are complex and highly nonlinear, is to schedule the committed generating unit outputs so as to meet the required load demand at minimum operating cost while satisfying all unit and system equality and inequality constraints. Recently, as an alternative to the conventional mathematical approaches, modern meta-heuristic optimization techniques have been given much attention by many researchers due to their ability to find an almost global optimal solution in EDPs. Research on merging evolutionary computation and quantum computation has been started since late 1990. Inspired on the quantum computation, this paper presented an improved quantum-inspired evolutionary algorithm (IQEA) based on diversity information of population. A classical quantum-inspired evolutionary algorithm (QEA) and the IQEA were implemented and validated for a benchmark of EDP with 15 thermal generators with prohibited operating zones. From the results for the benchmark problem, it is observed that the proposed IQEA approach provides promising results when compared to various methods available in the literature.
Fei Li and Min Zhou and Haibo Li 2011 A novel neural network optimized by Quantum Genetic Algorithm for signal detection in MIMO-OFDM systems   abstract PDF Google
[app]
Abstract: Neural networks can easily fall into a local extremum and have slow convergence rate. Quantum Genetic Algorithm (QGA) has features of small population size and fast convergence. Based on the investigation of QGA, we propose a novel neural network model, Radial Basis Function (RBF) networks optimized by Quantum Genetic Algorithm (QGA-RBF model). Then we investigate the performance of the proposed QGA-RBF on solving MIMO-OFDM signal detection problem. A novel signal detector based on QGA-RBF for MIMO-OFDM system is also proposed. The simulation results show that the proposed detector has more powerful properties in bit error rate than QGA based detector, RBF based detector and MMSE algorithm based detector, namely a 4-6 dB gain in performance can be achieved. The performance of the proposed detector is closer to optimal, compared with the other detectors.
Application ONLY, nothing more interresting
R. Nowotniak 2011 Kwantowo inspirowane algorytmy ewolucyjne w zadaniach przeszukiwania i optymalizacji Google
He Zongyao and Liang Zhou 2011 A New Real-Coded Quantum-Inspired Evolutionary Algorithm   abstract PDF Google
[representation][real][operators]
Abstract: A new real-coded quantum evolutionary algorithm is proposed in this paper. The new algorithm consists of trigonometric quantum individuals (TQIs) which are different from traditional quantum individuals design. The new TQIs specify two potential parallel structures; they can react upon each other in order to improve the efficiency of the new algorithm. In the course of evolution, the population executes high frequency mutation operation to keep its diversity, and then use the prior information which include optimal solution and gradient information of objective function to implement the update operation with acceleration mechanism. Numerical results indicate that this new algorithm has the characteristics of fast convergence rate, and good global search capability.
trigonomentric quantum individuals (TQI)
Nowotniak, R. and Kucharski, J. 2011 GPU-based tuning of quantum-inspired genetic algorithm for a combinatorial optimization problem Google
Nowotniak, R. and Kucharski, J. 2011 GPU-based massively parallel implementation of metaheuristic algorithms Google
Penrose, R. and Hameroff, S. 2011 Consciousness in the Universe: Neuroscience, Quantum Space-Time Geometry and Orch OR Theory Google
Schaul, Tom and Bayer, Justin and Wierstra, Daan and Sun, Yi and Felder, Martin and Sehnke, Frank and R{\"u}ckstie{\ss}, Thomas and Schmidhuber, J{\"u}rgen 2010 PyBrain Google
Amer Draa and Souham Meshoul and Hichem Talbi and Mohamed Batouche 2010 A Quantum-Inspired Differential Evolution Algorithm for Solving the N-Queens Problem   abstract PDF Google
[app][ext]
Abstract: In this paper, a quantum-inspired differential evolution algorithm for solving the N-queens problem is presented. The N-queens problem aims at placing N queens on an NxN chessboard, in such a way that no queen could capture any of the others. The proposed algorithm is a novel hybridization between differential evolution algorithms and quantum computing principles. Accordingly, differential evolution algorithms have been enhanced by the adoption of some quantum concepts such as quantum bits and states superposition. The use of the quantum interference has allowed this hybrid approach to have a remarkable efficiency and good results.
Hybridization of quantum-inspired method with Differential Evolution
Han Xue and Xun Li and Hong-Xu Ma 2010 Random fuzzy chance-constrained programming based on adaptive chaos quantum honey bee algorithm and robustness analysis   abstract PDF Google
Abstract: Abstract This paper proposes an adaptive chaos quantum honey bee algorithm (CQHBA) for solving chance-constrained programming in random fuzzy environment based on random fuzzy simulations. Random fuzzy simulation is designed to estimate the chance of a random fuzzy event and the optimistic value to a random fuzzy variable. In CQHBA, each bee carries a group of quantum bits representing a solution. Chaos optimization searches space around the selected best-so-far food source. In the marriage process, random interferential discrete quantum crossover is done between selected drones and the queen. Gaussian quantum mutation is used to keep the diversity of whole population. New methods of computing quantum rotation angles are designed based on grads. A proof of convergence for CQHBA is developed and a theoretical analysis of the computational overhead for the algorithm is presented. Numerical examples are presented to demonstrate its superiority in robustness and stability, efficiency of computational complexity, success rate, and accuracy of solution quality. CQHBA is manifested to be highly robust under various conditions and capable of handling most random fuzzy programmings with any parameter settings, variable initializations, system tolerance and confidence level, perturbations, and noises.
Luitel, B. and Venayagamoorthy, G.K. 2010 Quantum inspired PSO for the optimization of simultaneous recurrent neural networks as MIMO learning systems   abstract PDF Google
[swarm][app]
Abstract: Training a single simultaneous recurrent neural network (SRN) to learn all outputs of a multiple-input-multiple-output (MIMO) system is a difficult problem. A new training algorithm developed from combined concepts of swarm intelligence and quantum principles is presented. The training algorithm is called particle swarm optimization with quantum infusion (PSO-QI). To improve the effectiveness of learning, a two-step learning approach is introduced in the training. The objective of the learning in the first step is to find the optimal set of weights in the SRN considering all output errors. In the second step, the objective is to maximize the learning of each output dynamics by fine tuning the respective SRN output weights. To demonstrate the effectiveness of the PSO-QI training algorithm and the two-step learning approach, two examples of an SRN learning MIMO systems are presented. The first example is learning a benchmark MIMO system and the second one is the design of a wide area monitoring system for a multimachine power system. From the results, it is observed that SRNs can effectively learn MIMO systems when trained using the PSO-QI algorithm and the two-step learning approach.
Zhang, G.X. 2010 Time-Frequency Atom Decomposition with Quantum-Inspired Evolutionary Algorithms   abstract PDF Google
[app]
Abstract: Time-frequency atom decomposition (TFAD) provides a flexible representation for non-stationary signals, but the extremely high computational effort greatly blocks its practical applications. Quantum-inspired evolutionary algorithms (QEA) are efficient optimization methods with strong search capability and rapid convergence. This paper proposes the application of a modified variant of QEA to the TFAD problem. The problem on TFAD with evolutionary algorithms is formulated. By using gray coding, elite groups, and an appropriate termination criterion, the modified QEA is developed to search the suboptimal time-frequency atoms from a very large and redundant time-frequency dictionary. Also, this paper discusses the reduction of the computational time in terms of parameter setting, and presents an application example of radar emitter signals. Extensive experiments show the effectiveness and practicability of the presented algorithm.
Ashish Mani and C. Patvardhan 2010 Solving Ceramic Grinding Optimization Problem by Adaptive Quantum Evolutionary Algorithm   abstract PDF Google
[app][real]
Abstract: Advanced structural ceramics are widely used in engineering applications. They are useful due to high chemical inertness and sublimation temperature. Optimization of ceramic grinding process is essential as ceramics have high hardness and low surface toughness which can lead to large number of defects. The ceramic grinding optimization problem is formulated as non-linear constrained optimization problem. This paper proposes to solve the optimization problem by using a recently proposed real coded Adaptive Quantum inspired Evolutionary Algorithm. It is free from user selectable parameters in evolutionary operators as the same is determined adaptively. The proposed algorithm does not require mutation for maintaining diversity. The results also show that the proposed algorithm is fast and robust in comparison to the known state of art methods available for solving such problems.
Zheng, T. and Yamashiro, M. 2010 Solving flow shop scheduling problems by quantum differential evolutionary algorithm   abstract PDF Google
[app][hybrid][ext]
Abstract: This paper proposed a novel quantum differential evolutionary algorithm (QDEA) based on the basic quantum-inspired evolutionary algorithm (QEA) for permutation flow shop scheduling problem (PFSP). In this QDEA, the quantum chromosomes are encoded and decoded by using the quantum rotating angle and a simple strategy named largest rotating angle value rule to determine job sequence based on job's quantum information is proposed for the representation of PFSP, firstly. Then, we merge the advantages of differential evolution strategy, variable neighborhood search and QEA by adopting the differential evolution to perform the updating of quantum gate and variable neighborhood search to raise the performance of the local search. We adopted QDEA to minimize the makespan, total flowtime and the maximum lateness of jobs and make the simulations. The results and comparisons with other algorithms based on famous benchmarks demonstrated the effectiveness of the proposed QDEA. Another contribution of this paper is to report new absolute values of total flowtime and maximum lateness for various benchmark problem sets.
Sisir Koppaka and Ashish Ranjan Hota 2010 Superior Exploration-Exploitation Balance with Quantum-Inspired Hadamard Walks   abstract PDF Google
[knapsack][operators]
Abstract: This paper extends the analogies employed in the development of quantum-inspired evolutionary algorithms by proposing quantum-inspired Hadamard walks, called QHW. A novel quantum-inspired evolutionary algorithm, called HQEA, for solving combinatorial optimization problems, is also proposed. The novelty of HQEA lies in it's incorporation of QHW Remote Search and QHW Local Search - the quantum equivalents of classical mutation and local search, that this paper defines. The intuitive reasoning behind this approach, and the exploration-exploitation balance thus occurring is explained. From the results of the experiments carried out on the 0,1-knapsack problem, HQEA performs significantly better than a conventional genetic algorithm, CGA, and two quantum-inspired evolutionary algorithms - QEA and NQEA, in terms of convergence speed and accuracy.
HQEA algorithm -- extension of QiGA, new quantum operators, inspired with random walks: QHW Remote and Local Search - quantum global and local exploration counterparts
F. Tao and L. Zhang and Z.H. Zhang and A.Y.C. Nee 2010 A quantum multi-agent evolutionary algorithm for selection of partners in a virtual enterprise   abstract PDF Google
[app][operators]
Abstract: Combining agents and quantum-bit, a novel quantum multi-agent evolutionary algorithm (QMAEA) for addressing partner selection problems (PSP) in a virtual enterprise is proposed. In QMAEA, each agent represented by a quantum-bit is defined as a candidate solution, and agents can reproduce, perish, compete for survival, observe and communicate with the environment. Operators such as energy evaluation, competition, crossover, mutation, and trimming are designed to specify the evolvement of QMAEA. Three evolutionary strategies are designed to balance the exploration and exploitation of QMAEA. The effectiveness and scalability of the proposed QMAEA in addressing PSP is demonstrated with experimental results and comparisons.
QMAEA algorithm
Ara\'{u}jo, Ricardo de A. and de Oliveira, Adriano L. I. and Soares, Sergio C. B. 2010 Hybrid evolutionary quantum inspired method to adjust time phase distortions in financial time series   abstract Google
[app][hybrid]
Abstract: This work presents a hybrid evolutionary quantum inspired method to adjust time phase distortions present in financial time series, overcoming the random walk dilemma for financial prediction. It is composed of a Qubit Multilayer Perceptron (QuMLP) with a Quantum Inspired Evolutionary Algorithm (QIEA), which is able to evolve the complete QuMLP architecture and parameters, as well as searches for the best time lags to describe the time series generator phenomenon. An experimental analysis is conducted with the proposed approach through two real world financial time series, and the obtained results are discussed and compared to results found with classical models in literature.
Application of QiEA to optimization of Qubit Multilayer Perceptron (QuMLP), finansial time series
Pedersen, M.E.H. 2010 Tuning \& Simplifying Heuristical Optimization PDF Google
[other][!!!][tuning]
Meta-optimization techniques for optimization algorithms
Schliebs, Stefan 2010 Heterogeneous probabilistic models for optimisation and modelling of evolving spiking neural networks   abstract PDF Google
[app][ext][eda]
Abstract: This thesis proposes a novel feature selection and classification method employing evolving spiking neural networks (eSNN) and evolutionary algorithms (EA). The method is named the Quantum-inspired Spiking Neural Network (QiSNN) framework. QiSNN represents an integrated wrapper approach. An evolutionary process evolves appropriate feature subsets for a given classification task and simultaneously optimises the neural and learning-related parameters of the network. Unlike other methods, the connection weights of this network are determined by a fast one-pass learning algorithm which dramatically reduces the training time. In its core, QiSNN employs the Thorpe neural model that allows the efficient simulation of even large networks. In QiSNN, the presence or absence of features is represented by a string of concatenated bits, while the parameters of the neural network are continuous. For the exploration of these two entirely different search spaces, a novel Estimation of Distribution Algorithm (EDA) is developed. The method maintains a population of probabilistic models specialised for the optimisation of either binary, continuous or heterogeneous search spaces while utilising a small and intuitive set of parameters. The EDA extends the Quantum-inspired Evolutionary Algorithm (QEA) proposed by Han and Kim (2002) and was named the Heterogeneous Hierarchical Model EDA (hHM-EDA). The algorithm is compared to numerous contemporary optimisation methods and studied in terms of convergence speed, solution quality and robustness in noisy search spaces. The thesis investigates the functioning and the characteristics of QiSNN using both synthetic feature selection benchmarks and a real-world case study on ecological modelling. By evolving suitable feature subsets, QiSNN significantly enhances the classification accuracy of eSNN. Compared to numerous other feature selection techniques, like the wrapper-based Multilayer Perceptron (MLP) and the Naive Bayesian Classifier (NBC), QiSNN demonstrates a competitive classification and feature selection performance while requiring comparatively low computational costs.
Analysis of vQEA and QEA as EDA, statistics on CEC'05 benchmark suite
Gawron, P. and Klamka, J. and Miszczak, J.A. and Winiarczyk, R. 2010 Extending scientific computing system with structural quantum programming capabilities   abstract PDF Google
[QB]
Abstract: We present the basic high-level structures used for developing quantum programming languages. The presented structures are commonly used in many existing quantum programming languages and we use quantum pseudo-code based on QCL quantum programming language to describe them. We also present the implementation of introduced structures in GNU Octave language for scientific computing. Procedures used in the implementation are available as a package quantum-octave providing library of functions, which facilitates the simulation of quantum computing. This package allows also to incorporate high-level programming concepts into the simulation in GNU Octave and Matlab. As such it connects features unique for higl-level quantum programming languages, with the full palette of efficient computational routines commonly available in modern scientific computing systems. To present the major features of the described package we provide the implementation of selected quantum algorithms. We also show how quantum errors can be taken into account during the simulation of quantum algorithms using quantum-octave package. This is possible thanks to the ability to operate on density matrices implemented in quantum-octave.
description of quantum-octave library for simulation of true quantum computing
Hu, W. 2010 Cryptanalysis of TEA Using Quantum-Inspired Genetic Algorithms Google
Chen, R.C. and Huang, Y.H. and Lin, M.H. 2010 Solving Unbounded Knapsack Problem Based on Quantum Genetic Algorithms   abstract PDF Google
[app][knapsack]
Abstract: Resource distribution, capital budgeting, investment decision and transportation question could form as knapsack question models. Knapsack problem is one kind of NP-Complete problem and Unbounded Knapsack problems (UKP) are more complex and harder than general Knapsack problems. In this paper, we apply QGAs (Quantum Genetic Algorithms) to solve Unbounded Knapsack Problem. First, present the problem into the mode of QGAs and figure out the corresponding genes types and their fitness functions. Then, find the perfect combination of limitation and largest benefit. Finally, quant bit is updated by adjusting rotation angle and the best solution is found. In addition, we use the strategy of greedy method to arrange the sequence of chromosomes to enhance the effect of executing. Preliminary experiments prove our system is effective. The system also compare with AGAs (Adaptive Genetic Algorithms) to estimate their performances.
Julio Xavier Vianna Neto and Diego Luis de Andrade Bernert and Leandro dos Santos Coelho 2010 Improved quantum-inspired evolutionary algorithm with diversity information applied to economic dispatch problem with prohibited operating zones   abstract PDF Google
[app]
Abstract: The objective of the economic dispatch problem (EDP) of electric power generation, whose characteristics are complex and highly nonlinear, is to schedule the committed generating unit outputs so as to meet the required load demand at minimum operating cost while satisfying all unit and system equality and inequality constraints. Recently, as an alternative to the conventional mathematical approaches, modern meta-heuristic optimization techniques have been given much attention by many researchers due to their ability to find an almost global optimal solution in EDPs. Research on merging evolutionary computation and quantum computation has been started since late 1990. Inspired on the quantum computation, this paper presented an improved quantum-inspired evolutionary algorithm (IQEA) based on diversity information of population. A classical quantum-inspired evolutionary algorithm (QEA) and the IQEA were implemented and validated for a benchmark of EDP with 15 thermal generators with prohibited operating zones. From the results for the benchmark problem, it is observed that the proposed IQEA approach provides promising results when compared to various methods available in the literature.
Teng, Hao and Zhao, Baohua and Cao, Aizeng 2010 Chaos Quantum Genetic Algorithm Based on Henon Map   abstract PDF Google
[operators]
Abstract: Aiming at the trouble of easy getting into local minimum and premature constringency existed in quantum genetic algorithm, this paper presents a new algorithm through analyzing the characteristics of H #x0E9;non map and improving the quantum genetic algorithm using search strategy of mutative scale and chaos optimization method based on H #x0E9;non map. This algorithm carries through global search according to the ergodicity and randomicity of chaos movement, and can help to jump out the local minimum. At the same time, it can avoid the defects in chaos optimization method based on Logistic map or Tent map. The test of typical function shows that the performance of this kind of method is better than quantum genetic algorithm and genetic algorithm.
Wang, Jindong and Zhou, Rigui 2010 A Novel Quantum Genetic Algorithm for PID Controller   abstract PDF Google
[app][representation]
Abstract: Based on subpopulation parallel computing, a novel quantum genetic algorithm (NQGA) is presented. In the algorithm, each axis of solution is divided into k parts, so m dimensional space is partitioned km subspaces, the individual (or chromosome) from different subspace code differently. Finally, NQGA and the classical quantum genetic algorithm (QGA) are applied to parameter optimization of PID controller, simulation results show that NQGA performs better than QGA on running speed and optimizing capability.
Ashish Mani, C. Patvardhan 2010 An Adaptive Quantum Evolutionary Algorithm for Engineering Optimization Problems PDF Google
[representation]
Zhang, Gexiang 2010 Quantum-inspired evolutionary algorithms: a survey and empirical study   abstract PDF Google
[!!!][survey][real]
Abstract: Quantum-inspired evolutionary algorithms, one of the three main research areas related to the complex interaction between quantum computing and evolutionary algorithms, are receiving renewed attention. A quantum-inspired evolutionary algorithm is a new evolutionary algorithm for a classical computer rather than for quantum mechanical hardware. This paper provides a unified framework and a comprehensive survey of recent work in this rapidly growing field. After introducing of the main concepts behind quantum-inspired evolutionary algorithms, we present the key ideas related to the multitude of quantum-inspired evolutionary algorithms, sketch the differences between them, survey theoretical developments and applications that range from combinatorial optimizations to numerical optimizations, and compare the advantages and limitations of these various methods. Finally, a small comparative study is conducted to evaluate the performances of different types of quantum-inspired evolutionary algorithms and conclusions are drawn about some of the most promising future research developments in this area.
VERY COMPREHENSIVE and up to date survey
Ramdane, Chafika and Meshoul, Souham and Batouche, Mohamed and Kholladi, Mohamed-Khireddine 2010 A quantum evolutionary algorithm for data clustering   abstract Google
[app]
Abstract: The emerging field of quantum computing has recently created much interest in the computer science community due to the new concepts it suggests to store and process data. In this paper, we explore some of these concepts to cope with the data clustering problem. Data clustering is a key task for most fields like data mining and pattern recognition. It aims to discover cohesive groups in large datasets. In our work, we cast this problem as an optimisation process and we describe a novel framework, which relies on a quantum representation to encode the search space and a quantum evolutionary search strategy to optimise a quality measure in quest of a good partitioning of the dataset. Results on both synthetic and real data are very promising and show the ability of the method to identify valid clusters and also its effectiveness comparing to other evolutionary algorithms.
Teng Hao and Zhao Bao-hua and Wang Shi-xian 2010 Chaos quantum genetic algorithm based on Tent map   abstract Google
Abstract: Aiming at the trouble of easy getting into local minimum and premature constringency existed in quantum genetic algorithm, this paper presents a new algorithm through analyzing the characteristic of Tent map and improving the quantum genetic algorithm using chaos optimization method based on Tent map. This algorithm carries through global search according to the ergodicity and randomicity of chaos movement, and can help to jump out the local minimum. The test of typical function shows that the performance of this kind of method is better than quantum genetic algorithm and genetic algorithm.
Niu, Qun and zhou, Fang and Zhou, Taijin 2010 Quantum Genetic Algorithm for Hybrid Flow Shop Scheduling Problems to Minimize Total Completion Time   abstract Google
[app]
Abstract: This paper investigates the application of the quantum genetic algorithm (QGA) for Hybrid flow shop problems (HFSP) with the objective to minimize the total completion time. Since HFSP has shown to be NP-hard in a strong sense when the objective is to minimize the makespan in case of two stages, an efficient QGA is proposed to solve the problem. A real number representation is used to convert the Q-bit representation to job permutation for evaluating the solutions and quantum rotation gate is employed to update the population. Two different types of crossover and mutation operators are investigated to enhance the performance of QGA. The experimental results indicate that QGA is capable of producing better solutions in comparison with conventional genetic algorithm (GA) and quantum algorithm (QA).
Hua Zhang and Gexiang Zhang and Haina Rong and Jixiang Cheng 2010 Comparisons of quantum rotation gates in quantum-inspired evolutionary algorithms   abstract Google
[!!!][operators]
Abstract: As a novel evolutionary algorithm, a quantum-inspired evolutionary algorithm (QIEA) is attracting increasing attention, due to its good global search capability and rapid convergence. A quantum rotation gate (QR-gate) is the key operator in a QIEA. In the literature, there are many versions of QR-gates. How to evaluate and choose a QR-gate is very worth discussing. This paper focuses on a comparison and analysis on six QR-gates. The performances of QIEAs with the six QR-gates are tested on a practical problem, image sparse decomposition. Experimental results show that the QR-gate5 is superior to other five versions of QR-gates in terms of the quality of solutions and computing time.
Hongliang Wang and Yangwen Huang and Haifei Ding 2010 Application of support vector machine and quantum genetic algorithm in infrared target recognition Google
[app]
da Cruz, A.V.A. and Vellasco, M.M.B.R. and Pacheco, M.A.C. 2010 Quantum-Inspired Evolutionary Algorithms applied to numerical optimization problems   abstract PDF Google
[representation][real]
Abstract: Since they were proposed as an optimization method, the evolutionary algorithms have been successfully used for solving complex problems in several areas such as, for example, the automatic design of electronic circuits and equipments, task planning and scheduling, software engineering and data mining, among many others. However, some problems are computationally intensive when it concerns the evaluation of solutions during the search process, making the optimization by evolutionary algorithms a slow process for situations where a quick response from the algorithm is desired (for instance, in online optimization problems). Several ways to overcome this problem, by speeding up convergence time, were proposed, including Cultural Algorithms and Coevolutionary Algorithms. However, these algorithms still have the need to evaluate many solutions on each step of the optimization process. In problems where this evaluation is computationally expensive, the optimization can take a prohibitive time to reach optimal solutions. This work presents an evolutionary algorithm for numerical optimization problems (Quantum-Inspired Evolutionary Algorithm for Problems based on Numerical Representation - QIEA-R), inspired in the concept of quantum superposition, which allows the optimization process to be carried on with a smaller number of evaluations. It extends previous works by presenting a broader range of tests and improvements on the algorithm. The results show the good performance of this algorithm in solving numerical problems.
Wenjie Liu and Hanwu Chen and Qiaoqiao Yan and Zhihao Liu and Juan Xu and Yu Zheng 2010 A novel quantum-inspired evolutionary algorithm based on variable angle-distance rotation   abstract Google
[app][operators][knapsack]
Abstract: By reviewing the original INIQGA algorithm, an improved algorithm (IINIQGA) is put forward by revising the lookup table. In addition, By introducing the variable angle-distance rotation method into the update Q(t) procedure, a novel quantum-inspired evolutionary algorithm, QEA-VAR, was proposed. Compared with previous algorithms, our update Q(t) procedure is more simple and feasible. Finally, the corresponding experiments on the 0-1 knapsack problem were carried out, and the results show that our improvement is efficient, and comparing with IINIQGA, QEA, and CGA, QEA-VAR has a faster convergence and better profits than other algorithms.
Popa, R. and Nicolau, V. and Epure, S. 2010 A new Quantum Inspired Genetic Algorithm for Evolvable Hardware   abstract Google
Abstract: 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.
Radha, B. and Rughooputh, H.C.S. 2010 Optimal network reconfiguration of electrical distribution systems using real coded quantum inspired evolutionary algorithm   abstract Google
[app][real]
Abstract: Network reconfiguration is an important tool to optimize the operating conditions of an electrical distribution system. This is accomplished modifying the network structure of distribution feeders by changing the open/close status of sectionalizing switches. This not only reduces the power losses, but also relieves the overloading of the network components. Network reconfiguration belongs to a complex family of problems because of their combinatorial nature and multiple constraints. This paper proposes a solution to this problem, using a Real Coded Quantum Inspired Evolutionary Algorithm (RCQIEA), with a novel codification. In this paper, RCQIEA is tested and compared to an Exhaustive Algorithm (EA), a Heuristic algorithm (HA) and a Genetic Algorithm (GA) on three test systems. Simulation results show that RCQIEA performs better than EA, HA and GA in terms of speed and accuracy. RCQIEA is a highly scalable algorithm as well.
In-Won Park and Bum-Joo Lee and Ye-Hoon Kim and Ji-Hyeong Han and Jong-Hwan Kim 2010 Multi-objective quantum-inspired evolutionary algorithm-based optimal control of two-link inverted pendulum   abstract Google
Abstract: This paper proposes a method to generate an optimal trajectory of nonlinear dynamical system and concurrently optimize multiple performance criteria. As the dimensionality of system increases, it is difficult to find values of cost/reward function of conventional optimal controllers. In order to solve this problem, the proposed method employs iterative linear quadratic regulator and multi-objective quantum-inspired evolutionary algorithm to generate various optimal trajectories that satisfy multiple performance criteria. Fuzzy measure and fuzzy integral are also employed for global evaluation by integrating the partial evaluation of each solution over criteria with respect to user's degree of consideration for each criterion. Effectiveness of the proposed method is verified by computer simulation carried out for the problem of stabilizing two-link inverted pendulum model.
Renjie Liao and Xueyao Wang and Zengchang Qin 2010 A Novel Quantum-Inspired Genetic Algorithm with Expanded Solution Space   abstract Google
Abstract: In this paper, we present a novel quantum-inspired genetic algorithm with expanded solution space. Based on the double chains quantum genetic algorithm (DCQGA), we have expanded the solution space by increasing the number of solution space transformation functions. And we propose a novel method for quantum rotation gate's update by using the sign function and the gradient of objective function. With this method we can automatically determine the direction of quantum rotation gate and adaptively adjust the magnitude of quantum rotation gate. Through experimenting on 2 benchmark problem in the optimization literature: Rosenbrock function and Schaffer's F6 function, we demonstrate that our expanded solution space quantum genetic algorithm (ESSQGA) has achieved more satisfactory results than DCQGA and common genetic algorithm.
Yuyu Wang and Yu Shi 2010 The application of quantum-inspired evolutionary algorithm in analog evolvable hardware   abstract Google
Abstract: This paper proposes the use of quantum-inspired evolutionary algorithm in analog evolvable hardware (EHW). The circuit coding representation, chromosome fitness evaluation method and evolution process of the analog EHW are presented. By the experiments of evolving the circuits of amplifier, full-wave rectifier, integrator and OR-gate on the second generation field programmable transistor array (FPTA-2), the evolutionary performances are demonstrated. Results show that QEA can get better evolutionary results with a higher evolutionary speed than genetic algorithm (GA).
Jung-Chieh Chen 2010 Application of Quantum-Inspired Evolutionary Algorithm to Reduce PAPR of an OFDM Signal Using Partial Transmit Sequences Technique   abstract Google
Abstract: This paper proposes a reduced-complexity partial transmit sequences (PTS) approach based on the quantum-inspired evolutionary algorithm (QEA) for the reduction of peak-to-average power ratio (PAPR) in an orthogonal frequency division multiplexing (OFDM) system. The conventional PTS technique improves the PAPR statistics for OFDM signals, but the considerable computational complexity for an exhaustive search over all combinations of allowed phase factors is a potential problem for practical implementation. To reduce the computational complexity while still obtaining the desirable PAPR reduction, we introduce the QEA, an effective algorithm that solves various combinatorial optimization problems, to search the optimal phase factors. The simulation results show that the proposed QEA achieves significant PAPR reduction with low computational complexity.
Bhattacharyya, S. and Dutta, P. and Chakraborty, S. and Chakraborty, R. and Dey, S. 2010 Determination of optimal threshold of a gray-level image using a quantum inspired genetic algorithm with interference based on a random map model   abstract Google
Abstract: In this article, a variant quantum inspired genetic algorithm for the determination of the optimal threshold of gray-level images is presented. The proposed algorithm initiates with a population of randomly superposed trial solutions in the form of quantum bits. Subsequently, some deterministic nonlinear point transformations are applied on these solutions to generate randomly interfered solutions. Quantum inspired crossover and mutation are then applied on the resultant solution space. Finally, a quantum measurement operation leads to the determination of the optimal solution. Applications of the proposed method for the determination of the optimal thresholds of real life gray-level images are demonstrated.
Zheng, T. and Yamashiro, M. 2010 A novel quantum differential evolutionary algorithm for non-permutation flow shop scheduling problems   abstract Google
Abstract: This paper is the first to propose a novel quantum differential evolutionary algorithm (QDEA) based on the basic quantum-inspired evolutionary algorithm (QEA) for the non-permutation flow-shop scheduling problem (NPFSP). In this QDEA, the quantum chromosomes are encoded by using the quantum rotating angle and a simple converting mechanism for determining job sequence is proposed for the representation of NPFSP firstly. Then we merge the advantages of differential operation, local search and QEA by adopting the differential operation to perform the updating of quantum gate and the local search to perform exploitation in the promising permutative-based solutions. We adopt this approach to minimize the makespan for NPFSP and make the simulation. The comparisons with other state-of-the-art approaches based on well-known benchmarks demonstrate the effectiveness of the proposed QDEA.
Huanlai Xing and Yuefeng Ji and Lin Bai and Yongmei Sun 2010 An improved quantum-inspired evolutionary algorithm for coding resource optimization based network coding multicast scheme   abstract Google
Abstract: This paper investigates how to minimize the required coding resources in network-coding-based multicast scenarios. An evolutionary algorithm (MEQEA) is proposed to address the above problem. Based on quantum-inspired evolutionary algorithm (QEA), MEQEA introduces multi-granularity evolution mechanism which allows different chromosomes, at each generation, to have different rotation angle step values for update. In virtue of this mechanism, MEQEA significantly improves its capability of exploration and exploitation, since its optimization performance is no longer overly dependant upon the single rotation angle step scheme shared by all chromosomes. MEQEA also presents an adaptive quantum mutation operation which is able to prevent local search efficiently. Simulations are carried out over a number of network topologies. The results show that MEQEA outperforms other heuristic algorithms and is characterized by high success ratio, fast convergence, and excellent global-search capability.
Nowotniak, R. and Kucharski, J. 2010 Building blocks propagation in quantum-inspired genetic algorithm Google
R. Nowotniak 2010 Survey of Quantum-Inspired Evolutionary Algorithms Google
Nowotniak, R. and Kucharski, J. 2010 Meta-optimization of Quantum-Inspired Evolutionary Algorithm Google
Je{\.z}ewski, S. and {\L}aski, M. and Nowotniak, R. 2010 Comparison of algorithms for simultaneous localization and mapping problem for mobile robot Google
Russell, S.J. and Norvig, P. and Davis, E. and Russell, S.J. and Russell, S.J. 2010 Artificial intelligence: a modern approach Google
Kusiak, Jan and Danielewska-Tu{\l}ecka, Anna and Oprocha, Piotr 2009 Optymalizacja: wybrane metody z przyk{\l}adami zastosowa{\'n Google
Gwiazda, T 2009 Algorytmy genetyczne Kompendium t. 1 Google
Grygiel, W.P. and Hohol, M. 2009 Rogera Penrose'a kwantowanie umys{\l}u Google
Khan, M.H.A. and Akter, S. 2009 Multiple-case outlier detection in least-squares regression model using quantum-inspired evolutionary algorithm   abstract Google
[app]
Abstract: In ordinary statistical methods, multiple outliers in least-squares regression model are detected sequentially one after another, where smearing and masking effects give misleading results. If the potential multiple outliers can be detected simultaneously, smearing and masking effects can be avoided. Such multiple-case outlier detection is of combinatorial nature and 2N -1 sets of possible outliers need to be tested, where N is the number of data points. This exhaustive search is practically impossible. In this paper, we have used quantum-inspired evolutionary algorithm (QEA) for multiple-case outlier detection in least-squares regression model. An information criterion based fitness function incorporating extra penalty for number of potential outliers has been used for identifying the most appropriate set of potential outliers. Experimental results with four datasets from statistical literature show that the QEA effectively detects the most appropriate set of outliers.
Yu, Y. and Cunhua, LI and Shangce, GAO and Zheng, T. 2009 Quantum interference crossover-based clonal selection algorithm and its application to traveling salesman problem Google
[app][TSP]
Perone, Christian S. 2009 Pyevolve: a Python open-source framework for genetic algorithms   abstract Google
Abstract: Pyevolve is an open-source framework for genetic algorithms. The initial long-term goal of the project was to create a complete and multi-platform framework for genetic algorithms in pure Python. However, the most recent developmental versions currently support also Genetic Programming (GP)[3]; accordingly, Pyevolve now aims at becoming a pure Python framework for evolutionary algorithms.
Hamed, A. and Nuzly, H. and Kasabov, N. and Michlovsk{\`y}, Z. and Shamsuddin, S.M. 2009 String Pattern Recognition Using Evolving Spiking Neural Networks and Quantum Inspired Particle Swarm Optimization   abstract Google
[app][swarm]
Abstract: This paper proposes a novel method for string pattern recognition using an Evolving Spiking Neural Network (ESNN) with Quantum-inspired Particle Swarm Optimization (QiPSO). This study reveals an interesting concept of QiPSO by representing information as binary structures. The mechanism optimizes the ESNN parameters and relevant features using the wrapper approach simultaneously. The N-gram kernel is used to map Reuters string datasets into high dimensional feature matrix which acts as an input to the proposed method. The results show promising string classification results as well as satisfactory QiPSO performance in obtaining the best combination of ESNN parameters and in identifying the most relevant features.
de Pinho, A.G. and Vellasco, M. and da Cruz, A.V.A. 2009 A new model for credit approval problems: A quantum-inspired neuro-evolutionary algorithm with binary-real representation   abstract PDF Google
[app][representation][real]
Abstract: This paper presents a new model for neuro-evolutionary systems. It is a new quantum-inspired evolutionary algorithm with binary-real representation (QIEA-BR) for evolution of a neural network. The proposed model is an extension of the QIEA-R developed for numerical optimization. The Quantum-Inspired Neuro-Evolutionary Computation model (QINEA-BR) is able to completely configure a feed-forward neural network in terms of selecting the relevant input variables, number of neurons in the hidden layer and all existent synaptic weights. QINEA-BR is evaluated in a benchmark problem of financial credit evaluation. The results obtained demonstrate the effectiveness of this new model in comparison with other machine learning and statistical models, providing good accuracy in separating good from bad customers.
Izadinia, H. and Ebadzadeh, M.M. 2009 Quantum-Inspired Evolution Strategy   abstract PDF Google
[!!!][representation][real][operators]
Abstract: Evolution strategy is a suitable method for solving numerical optimization problems whose main characteristic is self adaption of the mutation step size. Finding the promising region in the search space is beneficial in optimization problems. However, in the contemporary ES the next generation is produced in a hyper ellipse and the direction to the optimum is not determined correctly. Therefore it is possible that the mutants are produced in unpromising regions which leads to unsatisfactory convergence. To alleviate this deficiency a novel evolution strategy which is inspired by the quantum computing is proposed in this paper. The proposed algorithm which is called quantum-inspired evolution strategy (QES) can improve the convergence speed and the accuracy by modifying the mutation direction. To demonstrate the effectiveness and applicability of the proposed method, several experiments on a set of numerical optimization problems are carried out. The results show that QES is superior to conventional ES in terms of convergence speed, accuracy and robustness.
quantum-inspired evolution strategy
Chang-Qing Gong and Bing Zhang and Ying Li 2009 Resources Scheduling of TT\&C Network Based on Quantum Genetic Algorithm   abstract PDF Google
[selection][app][operators]
Abstract: Quantum genetic algorithm (QGA) is based on quantum computation and genetic algorithm. QGA introduces quantum bit (qubit) and quantum rotation gate into genetic algorithm (GA). In order to solve the problem of tracking collision in the work of station resources allocation in TT amp;C network, taken the factors of time delay and network bandwidth into consideration, this paper builds a model based on general principle of resource allocation and the rule of optimization, and presents the solutions and steps about QGA. Experimental results show that QGA has more searching efficiency and constringency than GA. Finally, an example is advanced to illustrate the effectiveness of the algorithm.
modified rotation: rotation formula based on generation number
Li, Yangyang and Zhao, Jingjing and Jiao, Licheng and Wu, Qiuyi 2009 Quantum-inspired evolutionary multicast algorithm   abstract Google
[app]
Abstract: As a global optimizing algorithm, genetic algorithm (GA) is applied to solve the problem of multicast more and more. GA has more powerful searching ability than traditional algorithm, however its property of "prematurity" makes it difficult to get a good multicast tree. A quantum-inspired evolutionary algorithm (QEA) to deal with multicast routing problem is presented in this paper, which saliently solves the "prematurity" problem in Genetic based multicast algorithm. Furthermore, in QEA, the individuals in a population are represented by multistate gene quantum bits and this representation has a better characteristic of generating diversity in population than any other representations. In the individual's updating, the quantum rotation gate strategy is applied to accelerate convergence. The algorithm has the property of simple realization and flexible control. The simulation results show that QEA has a better performance than CS and conventional GA.
Zhao, Zhijin and Peng, Zhen and Zheng, Shilian and Shang, Junna 2009 Cognitive radio spectrum allocation using evolutionary algorithms   abstract Google
[app]
Abstract: Cognitive radio has been regarded as a promising technology to improve spectrum utilization significantly. In this letter, spectrum allocation model is presented firstly, and then spectrum allocation methods based on genetic algorithm (GA), quantum genetic algorithm (QGA), and particle swarm optimization (PSO), are proposed. To decrease the search space we propose a mapping process between the channel assignment matrix and the chromosome of GA, QGA, and the position of the particle of PSO, respectively, based on the characteristics of the channel availability matrix and the interference constraints. Results show that our proposed methods greatly outperform the commonly used color sensitive graph coloring algorithm.
Narayan, Apurva and Patvardhan, C. 2009 A novel quantum evolutionary algorithm for quadratic knapsack problem   abstract PDF Google
[knapsack][app][operators]
Abstract: The Quadratic Knapsack Problem (QKP) deals with maximizing a quadratic objective function subject to given constraints on the capacity of the Knapsack. We assume all coefficients to be non-negative and all variables to be binary. Solution to QKP generalizes the problem of finding whether a graph contains a clique of given size. We propose in this paper a Novel Quantum Evolutionary Algorithm (NQEA) for QKPs. These algorithms are general enough and can be used for similar subsection of problems. We report in this paper solutions which lie in less than 1% of the optimal solutions. We also show that our algorithm is scalable to much larger problem sizes and is capable of exploiting the search space to its maximum.
three new quantum operators (NO1, NO2, NO3).
Wei Fang and Jun Sun and Wenbo Xu 2009 A New Mutated Quantum-Behaved Particle Swarm Optimizer for Digital IIR Filter Design   abstract PDF Google
[swarm][app]
Abstract: Adaptive infinite impulse response (IIR) filters have shown their worth in a wide range of practical applications. Because the error surface of IIR filters is multimodal in most cases, global optimization techniques are required for avoiding local minima. In this paper, we employ a global optimization algorithm, Quantum-behaved particle swarm optimization (QPSO) that was proposed by us previously, and its mutated version in the design of digital IIR filter. The mechanism in QPSO is based on the quantum behaviour of particles in a potential well and particle swarm optimization (PSO) algorithm. QPSO is characterized by fast convergence, good search ability, and easy implementation. The mutated QPSO (MuQPSO) is proposed in this paper by using a random vector in QPSO to increase the randomness and to enhance the global search ability. Experimental results on three examples show that QPSO and MuQPSO are superior to genetic algorithm (GA), differential evolution (DE) algorithm, and PSO algorithm in quality, convergence speed, and robustness.
Douglas Mota Dias and Marco Aur\'elio C. Pacheco 2009 Toward a quantum-inspired linear genetic programming model   abstract Google
Abstract: The huge performance superiority of quantum computers for some specific problems lies in their direct use of quantum mechanical phenomena (e.g. superposition of states) to perform computations. This has motivated the creation of quantum-inspired evolutionary algorithms (QIEAs), which successfully use some quantum physics principles to improve the performance of evolutionary algorithms (EAs) for classical computers. This paper proposes a novel QIEA (Quantum-Inspired Linear Genetic Programming - QILGP) for automatic synthesis of machine code (MC) programs and aims to present a preliminary evaluation of applying the quantum-inspiration paradigm to evolve programs by using two symbolic regression problems. QILGP performance is compared to AIMGP model, since it is the most successful genetic programming technique to evolve MC. In the first problem, the hit ratio of QILGP (100%) is greater than the one of AIMGP (77%). In the second problem, QILGP seems to carry on a less greedy search than AIMGP. Since QILGP presents some satisfactory results, this paper shows that the quantum-inspiration paradigm can be a competitive approach to evolve programs more efficiently, which encourages further developments of that first and simplest QILGP model with multiple individuals.
Lin, D.Y. and Waller, S.T. 2009 A quantum-inspired genetic algorithm for dynamic continuous network design problem   abstract Google
[app][representation]
Abstract: The Network Design Problem (NDP), known to be NP-complete, arises in many application contexts. Transportation NDP involves optimizing the network performance under a budget constraint. Due to its non-convex and discontinuous solution space, a majority of the research efforts have been focused on tackling this problem using metaheuristics. Quantum computing is an active research area in which numerous advances have been made since the early 1990s. Quantum algorithms, such as Shor's factorization algorithm and Grover's database search algorithm, have opened up the possibility of solving NP-hard/NP-complete problems in polynomial time with quantum computers. Quantum-inspired genetic algorithms (QGA), as one of the novel meta-heuristics, seek to use insights gained through quantum computing to improve upon the performance of traditional genetic algorithms. By using the qubit as the basic unit of information in QGA, complex search space can be probabilistically characterized by superposition of states. With a suitable QGA updating mechanism, the qubit chromosome gradually converges to a single state as each qubit in the chromosome reaches the stable state of either 0 or 1. Therefore, without an exhaustive search of the qubit states combination, the solution spaces can be effectively explored and a better quality solution can be obtained with the same level of population, generation, and overall computational effort. In this research, we present a floating-point encoded quantum-inspired genetic algorithm to solve the dynamic transportation network design problem. The proposed algorithm is empirically applied to the Sioux-Falls and Monticello networks to test its effectiveness and applicability. Through numerical experiments, the QGA outperforms the conventional genetic algorithm, even with a smaller population size. Technical, computational and practical issues involved in developing and calibrating quantum-inspired genetic algorithm are discussed.
proposal of quantum-inspired floating point coding
Gu, J. and Gu, M. and Cao, C. and Gu, X. 2009 A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem   abstract PDF Google
[app][ext]
Abstract: In this paper, a novel Competitive Co-evolutionary Quantum Genetic Algorithm (CCQGA) is proposed for a Stochastic Job Shop Scheduling Problem (SJSSP) with the objective to minimize the expected value of makespan. Three new strategies named as competitive hunter, cooperative surviving and the big fish eating small fish are developed in population growth process. Based on improved co-evolution idea of multi-population and concepts of quantum theory, this algorithm could not only adjust population size dynamically to increase the diversity of genes and avoid premature convergence, but also accelerate the convergence speed with Q-bit representation and quantum rotation gate. FT benchmark-based problems where the processing times are subjected to independent normal distributions are solved effectively by CCQGA. The experiment results achieved by CCQGA are compared with Quantum-Inspired Genetic Algorithm (QGA) and standard Genetic Algorithm (GA), which shows that CCQGA has better feasibility and effectiveness.
coevolution, dynamic adaptation of population size
Gu, J. and Gu, X. and Gu, M. 2009 A novel parallel quantum genetic algorithm for stochastic job shop scheduling   abstract PDF Google
[app][ext][operators]
Abstract: In this paper, a Novel Parallel Quantum Genetic Algorithm (NPQGA) is proposed for the stochastic Job Shop Scheduling Problem with the objective of minimizing the expected value of makespan, where the processing times are subjected to independent normal distributions. Based on the parallel evolutionary idea and some concepts of quantum theory, we simulate a model of parallel quantum computation. In this frame, there are some demes (sub-populations) and some universes (groups of populations), which are structured in super star-shaped topologies. A new migration scheme based on penetration theory is developed to control migration rate and direction adaptively between demes, and a novel quantum crossover strategy is devised among universes. The quantum evolution is executed in every deme by applying some improvement operators (the coding mechanism aiming at job shop, the new quantum rotation angle and the catastrophe operator). Experiment results show NPQGA's effectiveness and applicability.
catastrophe operator
Jian Guo and Li-juan Sun and Ru-chuan Wang and Zhong-gen Yu 2009 An Improved Quantum Genetic Algorithm   abstract PDF Google
[ext]
Abstract: Abstract-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.
Island model (subpopulations) for quantum-inspired genetic algorithms -- inspired with "Small World Theory
Gu, Jinwei and Cao, Cuiwen and Jiao, Bin and Gu, Xingsheng 2009 An improved quantum genetic algorithm for stochastic flexible scheduling problem with breakdown   abstract PDF Google
[ext][app]
Abstract: A stochastic flexible scheduling problem subject to random breakdowns is studied in this paper, which objective is to minimize the expected value of makespan. We consider a preemptive-resume model of breakdown. The processing times, breakdown intervals and repair times are random variables subjected to independent normal distributions. An expanding method inspired by paper [1] is devised through predicting expected breakdown time of machines. Based on some concepts of quantum evolution, an Improved Quantum Genetic Algorithm (IQGA) is proposed, which is tested on a sampling problem compared with Cooperative Co-evolutionary Genetic Algorithm (CCGA) and Genetic Algorithm (GA). Experiment results show IQGA has better feasibility and effectiveness.
JEONG, Y.U.N.W.O.N. and PARK, J.B.A.E. and SHIN, J.R.I.N. and LEE, K.Y. 2009 A Thermal Unit Commitment Approach Using an Improved Quantum Evolutionary Algorithm   abstract Google
[app][operators]
Abstract: This article presents a new approach for solving unit commitment problems using a quantum-inspired evolutionary algorithm. The unit commitment problem is a complicated non-linear and mixed-integer combinatorial optimization problem with heavy constraints. This article proposes an improved quantum evolutionary algorithm to effectively solve unit commitment problems. The quantum-inspired evolutionary algorithm is considered a novel evolutionary algorithm inspired by quantum computing, which is based on the concept and principles of quantum computing such as the quantum bit and the superposition of states. The proposed improved quantum evolutionary algorithm adopts both the simplified rotation gate and the decreasing rotation angle approach in order to improve the convergence performance of the conventional quantum-inspired evolutionary algorithm. The suggested simplified rotation gate can determine the rotation angle without a lookup table, while the conventional rotation gate requires a predefined lookup table to determine the rotation angle. In addition, the proposed decreasing rotation angle approach provides the linearly decreasing magnitude of rotation angle along the iteration. Furthermore, this article includes heuristic-based constraint treatment techniques to deal with the minimum up/down time and spinning reserve constraints in unit commitment problems. Since the excessive spinning reserve can incur high operation costs, the unit de-commitment strategy is also introduced to improve the solution quality. To demonstrate the performance of the proposed improved quantum evolutionary algorithm, it is applied to the large-scale power systems of up to 100-unit with 24-hr demand horizon.
simplified rotation gate, decreasing rotation angles, removed lookup table
Li, Z. and Rudolph, G. and Li, K. 2009 Convergence performance comparison of quantum-inspired multi-objective evolutionary algorithms   abstract PDF Google
[multiobj][knapsack][!!!]
Abstract: In recent research, we proposed a general framework of quantum-inspired multi-objective evolutionary algorithms (QMOEA) and gave one of its sufficient convergence conditions to the Pareto optimal set. In this paper, two Q-gate operators, H"@e gate and R&N"@e gate, are experimentally validated as two Q-gate paradigms meeting the convergence condition. The former is a modified rotation gate, and the latter is a combination of rotation gate and NOT gate with the specified probability. To investigate their effectiveness and applicability, several experiments on the multi-objective 0/1 knapsack problems are carried out. Compared to two typical evolutionary algorithms and the QMOEA only with rotation gate, the QMOEA with H"@e gate and R&N"@e gate have more powerful convergence ability in high complex instances. Moreover, the QMOEA with R&N"@e gate has the best convergence in almost all of the experimental problems. Furthermore, the appropriate @e value regions for two Q-gates are verified.
Liu, CX and Zhang, GX and Zhu, YH and Fang, C. and Liu, HW 2009 A quantum-inspired evolutionary algorithm based on P systems for radar emitter signals   abstract PDF Google
[app]
Abstract: In this paper, a quantum-inspired evolutionary algorithm based on P systems (QEPS) is used for radar emitter signals to promote the application of membrane computing. QEPS combines the framework and evolution rules of P systems with the chromosome representation and evolutionary mechanism of quantum-inspired evolutionary algorithms (QIEA). With good global search capability and rapid convergence, QEPS can extract specific information from radar emitter signals in a short span of time. Experiments are carried out on linear-frequency modulated radar emitter signals with 10 db signal-to-noise rate to test the effectiveness and practicality of the introduced approach. Experimental results show that QEPS performs better than the greedy algorithm and the counterpart QIEA.
Liu, S. and You, X. 2009 Self-organizing Quantum Evolutionary Algorithm Based on Quantum Dynamic Mechanism   abstract Google
[ext]
Abstract: A novel self-organizing Quantum Evolutionary Algorithm based on quantum Dynamic mechanism for global optimization (DQEA) is proposed. Firstly, population is divided into subpopulations automatically. Secondly, by using co-evolution operator each subpopulation can obtain optimal solutions. Because of the quantum evolutionary algorithm with intrinsic adaptivity it can maintain quite nicely the population diversity than the classical evolutionary algorithm. In addition, it can help to accelerate the convergence speed because of the co-evolution by quantum dynamic mechanism. The searching technique for improving the performance of DQEA has been described; self-organizing algorithm has advantages in terms of the adaptability; reliability and the learning ability over traditional organizing algorithm. Simulation results demonstrate the superiority of DQEA in this paper.
Mahdabi, P. and Abadi, M. and Jalili, S. 2009 A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems   abstract PDF Google
[operators][knapsack][!!!]
Abstract: In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search space. In the operator, first, the Q-bits of each individual in the population are updated based on the personal best measurement of that individual and the best measurement of current generation. Then, a restriction is applied to each Q-bit to prevent the premature convergence of its values. The results of experiments on the 0-1 knapsack and NK-landscapes problems show that NQEA performs better than a classical genetic algorithm, CGA, and two quantum-inspired evolutionary algorithms, QEA and vQEA, in terms of convergence speed and accuracy.
NQEA, a new qubit update operator
Platel, M.D. and Schliebs, S. and Kasabov, N. 2009 Quantum-Inspired Evolutionary Algorithm: A Multimodel EDA   abstract PDF Google
[!!!][eda]
Abstract: The quantum-inspired evolutionary algorithm (QEA) applies several quantum computing principles to solve optimization problems. In QEA, a population of probabilistic models of promising solutions is used to guide further exploration of the search space. This paper clearly establishes that QEA is an original algorithm that belongs to the class of estimation of distribution algorithms (EDAs), while the common points and specifics of QEA compared to other EDAs are highlighted. The behavior of a versatile QEA relatively to three classical EDAs is extensively studied and comparatively good results are reported in terms of loss of diversity, scalability, solution quality, and robustness to fitness noise. To better understand QEA, two main advantages of the multimodel approach are analyzed in details. First, it is shown that QEA can dynamically adapt the learning speed leading to a smooth and robust convergence behavior. Second, we demonstrate that QEA manipulates more complex distributions of solutions than with a single model approach leading to more efficient optimization of problems with interacting variables.
Shu, W. 2009 Quantum-Inspired Genetic Algorithm Based on Simulated Annealing for Combinatorial Optimization Problem   abstract PDF Google
[ext][knapsack]
Abstract: Quantum-inspired genetic algorithm (QGA) is applied to simulated annealing (SA) to develop a class of quantum-inspired simulated annealing genetic algorithm (QSAGA) for combinatorial optimization. With the condition of preserving QGA advantages, QSAGA takes advantage of the SA algorithm so as to avoid premature convergence. To demonstrate its effectiveness and applicability, experiments are carried out on the knapsack problem. The results show that QSAGA performs well, without premature convergence as compared to QGA.
Imabeppu, T. and Ono, S. and Morishige, R. and Kurose, M. and Nakayama, S. 2009 A Comparative Study between Migration and Pair-Swap on Quantum-Inspired Evolutionary Algorithm   abstract PDF Google
[operators][knapsack]
Abstract: Quantum-inspired Evolutionary Algorithm (QEA) has been proposed as one of stochastic algorithms of evolutionary computation instead of a quantum algorithm. The authors have proposed Quantum-inspired Evolutionary Algorithm based on Pair Swap (QEAPS), which uses pair swap operator and does not group individuals in order to simplify QEA and reduce parameters in QEA. QEA and QEAPS imitationally use quantum bits as genes and superposition states in quantum computation. QEAPS has shown better search performance than QEA on knapsack problem, while eliminating parameters about immigration intervals and number of groups. However, QEAPS still has a parameter in common with QEA, a rotation angle unit, which is uncommon among other evolutionary computation algorithms. The rotation angle unit deeply affects exploitation and exploration control in QEA, but it has been unclear how the parameter influences QEAPS to behave. This paper aims to show that QEAPS involves few parameters and even those parameters can be adjusted easily. Experimental results, in knapsack problem and number partitioning problem which have different characteristics, have shown that QEAPS is competitive with other metaheuristics in search performance, and that QEAPS is robust against the parameter configuration and problem characteristics.
pair swap operator
Vlachogiannis, J.G. and {\O}stergaard, J. 2009 Reactive power and voltage control based on general quantum genetic algorithms   abstract PDF Google
[app]
Abstract: This paper presents an improved evolutionary algorithm based on quantum computing for optimal steady-state performance of power systems. However, the proposed general quantum genetic algorithm (GQ-GA) can be applied in various combinatorial optimization problems. In this study the GQ-GA determines the optimal settings of control variables, such as generator voltages, transformer taps and shunt VAR compensation devices for optimal reactive power and voltage control of IEEE 30-bus and 118-bus systems. The results of GQ-GA are compared with those given by the state-of-the-art evolutionary computational techniques such as enhanced GA, multi-objective evolutionary algorithm and particle swarm optimization algorithms, as well as the classical primal-dual interior-point optimal power flow algorithm. The comparison demonstrates the ability of the GQ-GA in reaching more optimal solutions.
Wang, L. and Li, L. 2009 An effective hybrid quantum-inspired evolutionary algorithm for parameter estimation of chaotic systems   abstract PDF Google
Abstract: Parameter estimation of chaotic systems is an important issue and has attracted increasing interest from a variety of research fields. Recently, quantum-inspired evolutionary algorithms have been proposed and applied to some optimization problems. However, to the best of our knowledge, there is no published research work on quantum-inspired evolutionary algorithm (QEA) for estimating parameters of chaotic systems. In this paper, an effective hybrid quantum-inspired evolutionary algorithm with differential evolution (HQEDE) is proposed and applied to estimate the parameters of the Lorenz system. Numerical simulation and comparisons with other methods demonstrate the effectiveness and robustness of the proposed algorithm. In addition, the effects of the parameter settings on HQEDE are investigated.
hybridization of QIEA with Differential Evolution
Wang, L. and Wang, X. and Fei, M. 2009 A novel quantum-inspired pseudorandom proportional evolutionary algorithm for the multidimensional knapsack problem   abstract PDF Google
[ext][app][operators][knapsack]
Abstract: This paper proposes a novel quantum-inspired pseudorandom proportional evolutionary algorithm (QPPEA), whose core is that the pseudorandom proportional operation is introduced in the update strategy. As the traditional quantum evolutionary algorithm (QEA) generates the binary solution completely depending on the probability and the amplitude of rotation angel is small, the efficiency of QEA is low. To make up for it, pseudorandom proportional operation inspired by ant colony algorithm is introduced in QPPEA. Further more, for the sake of the introduction of pseudorandom proportional operation, quantum mutation operator based on quantum NOT gate is used to keep the diversity of population. The simulation results on a class of the multidimensional knapsack problems (MKP) demonstrate that QPPEA can effectively enhance the searching efficiency and improve the optimization performance.
proportional pseudo-random genes update, inspired with ant colony methods
Fu, X. and Ding, M. and Zhou, C. and Sun, Y. 2009 Multi-threshold image segmentation with improved quantum-inspired genetic algorithm   abstract Google
[app][ext][selection][operators]
Abstract: In this paper, a method of multi-threshold image segmentation was proposed using the principle of maximum entropy and an improved quantum-inspired genetic algorithm (IQGA). With the increase number of multi-threshold, it is unrealistic to compute the entropy of all possible combinations and find the maximum entropy in all the multi-threshold combinations for images segmentation. Quantum-inspired genetic algorithm (QGA) has a better characteristic of population diversity, rapid convergence and global search capability than that of the conventional genetic algorithm (CGA). However, the solutions of QGAs may diverge or have a premature convergence to a local optimum due to the selection of the rotation angle in searching the maximum value of a function. Therefore, IQGA is put forward which joins the optimal selection and catastrophe operations, and defines an adaptive rotation angle of quantum gate during quantum chromosomes update procedure. Experimental results demonstrated that the proposed method has a good performance.
catastrophe operator, modified selection, adaptive rotation angles
Guo, X. and Wang, T. and Chen, Z. and Wang, L. and Zhao, W. 2009 Fast FPGA placement algorithm using Quantum Genetic Algorithm with Simulated Annealing   abstract PDF Google
[app][ext][hybrid]
Abstract: Field-programmable gate array (FPGA) attracts more and more attentions in the digital-design field for its excellent features such as reconfiguration and fast time to market. But the implementation of FPGA is restricted by its hardware framework and the CAD software. This paper proposes quantum genetic algorithm with simulated annealing (QGASA) as a hybrid FPGA placement algorithm, which combined the advantage of the fast global search ability of QGA and local adjusting ability of simulated annealing (SA) algorithm. The experimental results are compared with the state-of-the-art placement tool versatile place and route (VPR) by running the MCNC benchmark circuits. The results show that the path-timing driven cost of QGASA is similar to VPR, but the overall CPU time is reduced by 70%.
Xiao, J. and Yan, Y.P. and Zhang, J. and Tang, Y. 2009 A quantum-inspired genetic algorithm for k-means clustering   abstract PDF Google
[app][operators][representation]
Abstract: The number of clusters has to be known in advance for the conventional k-means clustering algorithm and moreover the clustering result is sensitive to the selection of the initial cluster centroids. This sensitivity may make the algorithm converge to the local optima. This paper proposes a quantum-inspired genetic algorithm for k-means clustering (KMQGA). In KMQGA, a Q-bit based representation is employed for exploration and exploitation in discrete 0-1 hyperspace using rotation operation of quantum gate as well as the typical genetic algorithm operations (selection, crossover and mutation) of Q-bits. Different from the typical quantum-inspired genetic algorithms (QGA), the length of a Q-bit in KMQGA is variable during evolution. Without knowing the exact number of clusters beforehand, KMQGA can obtain the optimal number of clusters as well as providing the optimal cluster centroids. Both the simulated datasets and the real datasets are used to validate KMQGA, respectively. The experimental results show that KMQGA is promising and effective.
combination of quantum-inspired operators (rotations in quantum state spaces) with typical genetic operators (classical crossover, mutation, selection); variable length of chromosomes during evolution
Jianhua Xiao and Binglian Liu 2009 Quantum swarm evolutionary algorithm with time-varying acceleration coefficients for partner selection in virtual enterprise   abstract PDF Google
[swarm][app]
Abstract: Partner selection is one of the most critical issue in virtual enterprise, which has been extensively researched in recent years. It is difficult to be solved by the traditional optimization methods for partner selection is a combinatorial optimization problem. In this paper, an improved quantum swarm evolutionary algorithm based on time-varying acceleration coefficients (IQSEA_TVAC) is proposed for partner selection optimization problem. The results of simulation experiments show that the improved algorithm is valid and outperforms the conventional quantum evolutionary algorithm.
Xing, H. and Ji, Y. and Bai, L. and Liu, X. and Qu, Z. and Wang, X. 2009 An adaptive-evolution-based quantum-inspired evolutionary algorithm for QoS multicasting in IP/DWDM networks   abstract PDF Google
[ext][app]
Abstract: This paper investigates least-cost QoS multicast routing problem in IP/DWDM optical networks, and proposes an improved evolutionary algorithm (AEQEA). Based on quantum-inspired evolutionary algorithm (QEA) with quantum rotation gate strategy, AEQEA introduces adaptive evolution mechanism (AEM), which allows each chromosome in a population to update itself to a fitter position according to its own situation. In term of this mechanism, AEQEA can significantly improve its capability of exploration and exploitation, since every chromosome is able to be allocated with suitable evolutionary parameters before each update. A repair method is applied to eliminate illegal graphs as many as possible hence more excellent solutions will appear in each evolutionary generation. Simulations are carried out over a number of network topologies. And the results show that, for the QoS multicasting problem, AEQEA outperforms other existing heuristic algorithms and is characterized by robustness, high success ratio, fast convergence and excellent capability on global searching.
Xing, H. and Liu, X. and Jin, X. and Bai, L. and Ji, Y. 2009 A multi-granularity evolution based Quantum Genetic Algorithm for QoS multicast routing problem in WDM networks   abstract PDF Google
[ext][app][operators]
Abstract: QoS multicast routing problem in WDM networks is investigated, and an improved algorithm Multi-granularity Evolution based Quantum Genetic Algorithm (MEQGA) is proposed to address it. Based on Quantum Genetic Algorithm (QGA) with quantum rotation gate strategy, MEQGA introduces multi-granularity evolution mechanism, which allows different chromosomes of one generation to have different rotation angle step values to update. In term of this mechanism, MEQGA can significantly improve its capability of exploration and exploitation, since its optimization performance does not over-depend on the single rotation angle step scheme shared by all chromosomes any longer. MEQGA also presents an adaptive quantum mutation operation which is able to avoid local search efficiently. A repair method is applied to eliminate illegal graphs as many as possible hence more excellent solutions will appear in each evolutionary generation. Simulation results show that, for the QoS multicast routing problem, MEQGA outperforms other heuristic algorithms and is characterized by robustness, high success ratio, fast convergence and excellent capability on global searching.
,,multi-granular'' evolution mechanism: different rotation angles for each quantum chromosome; a new adaptive quantum mutation operator -- preventing premature convergence; proposal of repair technique for constraint satisfaction
Cao, Maojun and Shang, Fuhua 2009 Training of Process Neural Networks Based on Improved Quantum Genetic Algorithm   abstract Google
[app][representation]
Abstract: For training of process neural networks based on the orthogonal basis expansion, it is difficult to converge for BP algorithm as more parameters. Aiming at the issue, this paper proposes a solution based on quantum genetic algorithm with double chains. Firstly, the number of genes is determined by the number of weight parameters, quantum chromosomes are constructed by qubits, and the current optimal chromosome is obtained with the help of colony assessment. Secondly, taking each qubit in this optimal chromosome as the goal, individuals are updated by quantum rotation gate, and mutated by quantum non-gate to increase the diversity of population. In this method, each chromosome carrying two chains of genes, therefore it can extend ergodicity for solution space and accelerate optimization process. Taking the pattern classification of two groups of two-dimensional trigonometric functions as an example, the simulation results show that the method not only has fast convergence, but also good optimization ability.
Zhao, S. and Xu, G. and Tao, T. and Liang, L. 2009 Real-coded chaotic quantum-inspired genetic algorithm for training of fuzzy neural networks   abstract PDF Google
[app][operators][representation][real]
Abstract: In this paper, a novel approach to adjusting the weightings of fuzzy neural networks using a Real-coded Chaotic Quantum-inspired genetic Algorithm (RCQGA) is proposed. Fuzzy neural networks are traditionally trained by using gradient-based methods, which may fall into local minimum during the learning process. To overcome the problems encountered by the conventional learning methods, RCQGA algorithms are adopted because of their capabilities of directed random search for global optimization. It is well known, however, that the searching speed of the conventional quantum genetic algorithms (QGA) is not satisfactory. In this paper, a real-coded chaotic quantum-inspired genetic algorithm (RCQGA) is proposed based on the chaotic and coherent characters of Q-bits. In this algorithm, real chromosomes are inversely mapped to Q-bits in the solution space. Q-bits probability-guided real cross and chaos mutation are applied to the evolution and searching of real chromosomes. Chromosomes consisting of the weightings of the fuzzy neural network are coded as an adjustable vector with real number components that are searched by the RCQGA. Simulation results have shown that faster convergence of the evolution process in searching for an optimal fuzzy neural network can be achieved. Examples of nonlinear functions approximated by using the fuzzy neural network via the RCQGA are demonstrated to illustrate the effectiveness of the proposed method.
quantum real coding
Birattari, M. 2009 Tuning metaheuristics: a machine learning perspective   abstract PDF Google
[!!!][tuning]
Abstract: The importance of tuning metaheuristics is widely acknowledged in scientific literature. However, there is very little dedicated research on the subject. Typically, scientists and practitioners tune metaheuristics by hand, guided only by their experience and by some rules of thumb. Tuning metaheuristics is often considered to be more of an art than a science. This book lays the foundations for a scientific approach to tuning metaheuristics. The fundamental intuition that underlies Birattari's approach is that the tuning problem has much in common with the problems that are typically faced in machine learning. By adopting a machine learning perspective, the author gives a formal definition of the tuning problem, develops a generic algorithm for tuning metaheuristics, and defines an appropriate experimental methodology for assessing the performance of metaheuristics.
F-Race method for tuning metaheuristics
Huanlai Xing and Yuefeng Ji and Lin Bai and Yongmei Sun 2009 An improved quantum-inspired evolutionary algorithm for coding resource optimization based network coding multicast scheme   abstract Google
[app][operators]
Abstract: This paper investigates how to minimize the required coding resources in network-coding-based multicast scenarios. An evolutionary algorithm (MEQEA) is proposed to address the above problem. Based on quantum-inspired evolutionary algorithm (QEA), MEQEA introduces multi-granularity evolution mechanism which allows different chromosomes, at each generation, to have different rotation angle step values for update. In virtue of this mechanism, MEQEA significantly improves its capability of exploration and exploitation, since its optimization performance is no longer overly dependant upon the single rotation angle step scheme shared by all chromosomes. MEQEA also presents an adaptive quantum mutation operation which is able to prevent local search efficiently. Simulations are carried out over a number of network topologies. The results show that MEQEA outperforms other heuristic algorithms and is characterized by high success ratio, fast convergence, and excellent global-search capability.
Hongxia Miao and Honghua Wang and Zhixiang Deng 2009 Quantum Genetic Algorithm and its Application in Power System Reactive Power Optimization   abstract Google
[app]
Abstract: Quantum Genetic Algorithm (QGA) is a genetic algorithm (GA) based on principles of quantum computing (QC). It uses quantum bit coding, whole interference crossover and quantum gate as update operator to complete evolution search. Compared with conventional GA, QGA is characterized by small population size, rapid convergence and strong global search capability. In this paper, QGA is applied in power system reactive power optimization. Simulation and calculation is carried out in IEEE-6 node test system, and the validity and superiority of the proposed algorithm are proved.
Xiong, Hegen and Xiong, Kai and Tang, Qiuhua 2009 A Novel Variable-Boundary-Coded Quantum Genetic Algorithm for Function Optimization   abstract PDF Google
[representation][operators]
Abstract: 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.
vbQGA algorithm, proposal of a new coding, numerical optimization
Sean Luke 2009 Essentials of Metaheuristics PDF Google
[survey][other]
Impressive and incredibly comprehensive book on variety of metaheuristics
Lili Yan and Henian Chen and Wentian Ji and Yu Lu and Junqing Li 2009 Optimal VSM Model and Multi-Object Quantum-Inspired Genetic Algorithm for Web Information Retrieval   abstract Google
[app]
Abstract: It is becoming an important research issue to search the Web rapidly and effectively from a mass of information. Information retrieval for resolved these problems provide a chance. In this paper, a new adaptive method of information retrieval Web documents is proposed. We give an algorithm QIGA which combines genetic algorithm and quantum computing based on vector space model (VSM). This algorithm avoids the disadvantage of Web documents by using pure genetic algorithm which can not be utilized accurately. Experimental results show that our method can be adopted effectively in practice and is superior to other algorithms.
Jopek, L. and Nowotniak, R. and Postolski, M. and Babout, L. and Janaszewski, M. 2009 Zastosowanie kwantowych algorytmow genetycznych do selekcji cech Google
Seljebotn, Dag Sverre 2009 Fast numerical computations with Cython Google
Hongwen Liu and Gexiang Zhang and Chunxiu Liu and Chun Fang 2008 A novel Memetic Algorithm based on real-observation Quantum-inspired evolutionary algorithms   abstract PDF Google
[!!!][real]
Abstract: To enhance the local search capability of quantum-inspired evolutionary algorithm, a novel memetic algorithm based on real-observation quantum-inspired evolutionary algorithms (MArQ) was proposed. MArQ is a hybrid algorithm combining QIEA with local search techniques. In MArQ, QIEA was used to explore the whole solution space and tabu search was employed to exploit the neighboring domains of the searched best solutions. Several bench complex functions and an application example of reactive power optimization in power systems were applied to test the MArQ performances. Experimental results show that MArQ is superior to the real-observation quantum-inspired evolutionary algorithm and several optimization algorithms reported, in terms of search capability and stability.
rQIEA
Allauddin, R. and Boehmer, S. and Behrman, E. and Gaddam, K. and Steck, J. 2008 Quantum Simulataneous Recurrent Networks for Content Addressable Memory Google
Coelho, L. and Nedjah, N. and Mourelle, L. 2008 Gaussian quantum-behaved particle swarm optimization applied to fuzzy pid controller design Google
Araujo, M.P.M. and Nedjah, N. and De Macedo Mourelle, L. 2008 Designing hardware for finite synchronous state machines using quantum inspired evolution   abstract Google
[app]
Abstract: Synchronous finite state machines are very important for digital sequential systems. Among other important aspects, they represent a powerful way for synchronising hardware components so that these components may cooperate adequately in the fulfilment of the main objective. In this paper, we propose to use an evolutionary methodology inspired from quantum computation to yield a concise and efficient evolvable hardware that implements the state machine control logic. The evolved circuits are promising.
Tayarani, M.H. and Akbarzadeh. T, M.R. 2008 A cellular structure and diversity preserving operator in Quantum Evolutionary Algorithms   abstract PDF Google
Abstract: A diversity preserving cellular quantum evolutionary algorithm (DPCQEA) is proposed in which the quantum individuals are located in a specific topology and interact only with their neighbors. The proposed cellular structure aims to provide a better exploitation of local neighborhoods before moving towards a global best, hence it increases population diversity. This paper also proposes a new operator for diversity preservation in the population. In standard QEA the diversity in the population decreases across the generations. Decreasing the diversity of the population decreases the exploration performance of the algorithm and causes possible algorithm trapping in the local optima. In the proposed algorithm, only the fittest of converged q-individuals from among similar individuals are preserved, while others are reinitialized. A criterion is then proposed to measure convergence and similarity among individuals. Experimental results on knapsack problem, trap problem as well as 14 Numerical benchmark functions show that DPCQEA consistently exceeds the performance of QEA.
Stefan Kotowski 2008 Analiza algorytmów genetycznych jako układów dynamicznych PDF Google
[theoretical][other][!!!]
Shilane, D. and Martikainen, J. and Dudoit, S. and Ovaska, S.J. 2008 A general framework for statistical performance comparison of evolutionary computation algorithms   abstract PDF Google
[other]
Abstract: This paper proposes a statistical methodology for comparing the performance of evolutionary computation algorithms. A two-fold sampling scheme for collecting performance data is introduced, and these data are analyzed using bootstrap-based multiple hypothesis testing procedures. The proposed method is sufficiently flexible to allow the researcher to choose how performance is measured, does not rely upon distributional assumptions, and can be extended to analyze many other randomized numeric optimization routines. As a result, this approach offers a convenient, flexible, and reliable technique for comparing algorithms in a wide variety of applications.
statistical methodology for comparing the performance of evolutionary algorithms
Kai Fan and Conall O'Sullivan and Anthony Brabazon and Michael O'Neill and Sean McGarraghy 2008 Calibration of the VGSSD Option Pricing Model using a Quantum-inspired Evolutionary Algorithm   abstract PDF Google
[app][real][representation][operators]
Abstract: Quantum effects are a natural phenomenon and just like evolution, the brain, or immune systems, can serve as an inspiration for the design of computing algorithms. This chapter illustrates how a quantum-inspired evolutionary algorithm (QIEA) using real number encodings can be constructed and examines the utility of the resulting algorithm on an important real-world problem, namely the calibration of an Option Pricing model. The results from the algorithm are shown to be robust and comparable to those of other algorithms, suggesting that there is useful potential to apply QIEA to this domain.
Kai Fan and Anthony Brabazon and Conall O'Sullivan and Michael O'Neill 2008 Quantum-Inspired Evolutionary Algorithms for Financial Data Analysis   abstract PDF Google
[app][initialization][representation][real][operators][eda]
Abstract: This paper describes a real-valued quantum-inspired evolutionary algorithm (QIEA), a new computational approach which bears similarity with estimation of distribution algorithms (EDAs). The study assesses the performance of the QIEA on a series of benchmark problems and compares the results with those from a canonical genetic algorithm. Furthermore, we apply QIEA to a finance problem, namely non-linear principal component analysis of implied volatilities. The results from the algorithm are shown to be robust and they suggest potential for useful application of the QIEA to high-dimensional optimization problems in finance.
Weise, T. 2008 Global Optimization Algorithms--Theory and Application PDF Google
[other][theoretical][!!!]
Incredible comprehensive study of various global optimization techniques; emphasised on theoretical aspects, applications, mathematical and global optimization fundamentals; Holland's theorem, criticism
Sofge, D.A. 2008 Prospective algorithms for quantum evolutionary computation   abstract PDF Google
[survey][QB][!!!]
Abstract: This effort examines the intersection of the emerging field of quantum computing and the more established field of evolutionary computation. The goal is to understand what benefits quantum computing might offer to computational intelligence and how computational intelligence paradigms might be implemented as quantum programs to be run on a future quantum computer. We critically examine proposed algorithms and methods for implementing computational intelligence paradigms, primarily focused on heuristic optimization methods including and related to evolutionary computation, with particular regard for their potential for eventual implementation on quantum computing hardware.
Zhang, Jing-Ling and Zhao, Yan-Wei and Peng, Dian-Jun and Wang, Wan-Liang 2008 A Hybrid Quantum-Inspired Evolutionary Algorithm for Capacitated Vehicle Routing Problem   abstract Google
[app][representation][operators]
Abstract: A hybrid Quantum-Inspired Evolutionary Algorithm (HQEA) with 2-OPT sub-routes optimization for capacitated vehicle routing problem (CVRP) is proposed. In the HQEA, 2-OPT algorithm is used to optimize sub-routes for convergence acceleration. Moreover, an encoding method of converting Q-bit representation to integer representation is designed. And genetic operators of quantum crossover and quantum variation are applied to enhance exploration. The proposed HQEA is tested based on classical benchmark problems of CVRP. Simulation results and comparisons with genetic algorithm show that the proposed HQEA has much better exploration quality and it is an effective method for CVRP.
Wei, W. and Li, B. and Zou, Y. and Zhang, W. and Zhuang, Z. 2008 A multi-objective HW-SW co-synthesis algorithm based on quantum-inspired evolutionary algorithm   abstract Google
[app][multiobj][operators]
Abstract: Hardware-Software (HW-SW) co-synthesis is one of the key steps in modern embedded system design. Generally, HW-SW co-synthesis is to optimally allocate processors, assign tasks to processors, and schedule the processing of tasks to achieve a good balance among performance, cost, power consumption, etc. Hence, it is a typical multi-objective optimization problem. In this paper, a new multi-objective HW-SW co-synthesis algorithm based on the quantum-inspired evolutionary algorithm (MQEAC) is proposed. MQEAC utilizes multiple quantum probability amplitude vectors to model the promising areas of solution space. Meanwhile, this paper presents a new crossover operator to accelerate the convergence to the Pareto front and introduces a PE slot-filling strategy to improve the efficiency of scheduling. Experimental results show that the proposed algorithm can solve the typical multi-objective co-synthesis problems effectively and efficiently.
Chaoyong Qin and Yongjuan Liu and Jianguo Zheng 2008 A real-coded quantum-inspired evolutionary algorithm for global numerical optimization   abstract PDF Google
[representation][real]
Abstract: In this paper, a novel kind of algorithm, real-coded quantum-inspired evolutionary algorithm (RQEA), is proposed based on evolutionary programming and quantum computation. In RQEA, several real numbers are directly encoded in a chromosome which is usually represented by quantum bits in quantum evolutionary programming. Quantum computation mechanics is employed to accelerate evolution process. The result of experiments shows that RQEA has a strong ability of global optimization and high convergence speed.
Araujo, M.P. and Nedjah, N. and Macedo Mourelle, L. 2008 Optimised State Assignment for {FSMs} Using Quantum Inspired Evolutionary Algorithm   abstract Google
[app]
Abstract: Synchronous finite state machines are very important for digital sequential designs. Among other important aspects, they represent a powerful way for synchronizing hardware components so that these components may cooperate adequately in the fulfillment of the main objective of the hardware design. In this paper, we propose an evolutionary methodology to solve one of the problems related to the design of finite state machines. We solve the state assignment NP-complete problem using a quantum inspired evolutionary algorithm. This is motivated by the fact that with an optimised state assignment one can physically implement the state machine using a minimal hardware area and response time.
Teng, H. and Zhao, B. and Yang, B. 2008 An Improved Mutative Scale Chaos Optimization Quantum Genetic Algorithm   abstract PDF Google
Abstract: The theory of chaos optimization is introduced in this paper; and through improving the constringency strategy of mutative scale chaos optimization method, we can enhance the efficiency and the performance of chaos optimization method; then aiming at the trouble of easy getting into local minimum existed in quantum genetic algorithm, this paper presents a new chaos quantum genetic algorithm. Using the improved mutative scale chaos optimization method, chaotic search for the optimization is implemented to the population which is processed one time with the quantum genetic algorithm, which can lead to the rapid evolution of the population. The test of typical function shows that the performance of this method is better than quantum genetic algorithm and genetic algorithm.
Dai, H. and Li, C. 2008 Improved Quantum Interference Crossover-Based Genetic Algorithm and its Application   abstract PDF Google
[operators][TSP]
Abstract: In this paper, we propose an improved quantum interference crossover-based genetic algorithm. The primary difference between the classical interference crossover and the new one is the chromosome reconstruction process. Unlike the position-based selection approach in classical approach, the novel method selects the city that has a shorter distance with the city selected in the previous chromosome. The new method has been used to solve the traveling salesman problem. Experimental results indicate that the new method is superior to the classical interference crossover-based genetic algorithm.
quantum interference crossover operator
Huo, H. and Xie, Q. and Shen, X. and Stojkovic, V. 2008 A Probabilistic Coding Based Quantum Genetic Algorithm for Multiple Sequence Alignment   abstract PDF Google
[app][representation][operators]
Abstract: This paper presents an original Quantum Genetic algorithm for Multiple sequence ALIGNment (QGMALIGN) that combines a genetic algorithm and a quantum algorithm. A quantum probabilistic coding is designed for representing the multiple sequence alignment. A quantum rotation gate as a mutation operator is used to guide the quantum state evolution. Six genetic operators are designed on the coding basis to improve the solution during the evolutionary process. The features of implicit parallelism and state superposition in quantum mechanics and the global search capability of the genetic algorithm are exploited to get efficient computation. A set of well known test cases from BAliBASE2.0 is used as reference to evaluate the efficiency of the QGMALIGN optimization. The QGMALIGN results have been compared with the most popular methods (CLUSTALX, SAGA, DIALIGN, SB_PIMA, and QGMALIGN) results. The QGMALIGN results show that QGMALIGN performs well on the presenting biological data. The addition of genetic operators to the quantum algorithm lowers the cost of overall running time.
Jiao, L. and Li, Y. and Gong, M. and Zhang, X. 2008 Quantum-inspired immune clonal algorithm for global optimization   abstract PDF Google
Abstract: Based on the concepts and principles of quantum computing, a novel immune clonal algorithm, called a quantum-inspired immune clonal algorithm (QICA), is proposed to deal with the problem of global optimization. In QICA, the antibody is proliferated and divided into a set of subpopulation groups. The antibodies in a subpopulation group are represented by multistate gene quantum bits. In the antibody's updating, the general quantum rotation gate strategy and the dynamic adjusting angle mechanism are applied to accelerate convergence. The quantum NOT gate is used to realize quantum mutation to avoid premature convergences. The proposed quantum recombination realizes the information communication between subpopulation groups to improve the search efficiency. Theoretical analysis proves that QICA converges to the global optimum. In the first part of the experiments, 10 unconstrained and 13 constrained benchmark functions are used to test the performance of QICA. The results show that QICA performs much better than the other improved genetic algorithms in terms of the quality of solution and computational cost. In the second part of the experiments, QICA is applied to a practical problem (i.e., multiuser detection in direct-sequence code-division multiple-access systems) with a satisfying result.
Xiao, J. and Yan, Y.P. and Lin, Y. and Yuan, L. and Zhang, J. 2008 A Quantum-inspired Genetic Algorithm for Data Clustering   abstract PDF Google
[app][operators][representation]
Abstract: The conventional k-means clustering algorithm must know the number of clusters in advance and the clustering result is sensitive to the selection of the initial cluster centroids. The sensitivity may make the algorithm converge to the local optima. This paper proposes an improved k-means clustering algorithm based on quantum-inspired genetic algorithm (KMQGA). In KMQGA, Q-bit based representation is employed for exploration and exploitation in discrete 0-1 hyperspace by using rotation operation of quantum gate as well as three genetic algorithm operations (selection, crossover and mutation) of Q-bit. Without knowing the exact number of clusters beforehand, the KMQGA can get the optimal number of clusters as well as providing the optimal cluster centroids after several iterations of the four operations (selection, crossover, mutation, and rotation). The simulated datasets and the real datasets are used to validate KMQGA and to compare KMQGA with an improved k-means clustering algorithm based on the famous variable string length genetic algorithm (KMVGA) respectively. The experimental results show that KMQGA is promising and the effectiveness and the search quality of KMQGA is better than those of KMVGA.
quantum-inspired genetic operators (rotations) + classical genetic operators (crossover, mutation)
Khosraviani, M. and Pour-Mozafari, S. and Ebadzadeh, M.M. 2008 Convergence analysis of quantum-inspired genetic algorithms with the population of a single individual   abstract PDF Google
[theoretical][!!!]
Abstract: In this paper, the Quantum-inspired Genetic Algorithms with the population of a single individual are formalized by a Markov chain model using a single and the stored best individual. Here, we analyze the convergence property of the Quantum-inspired Genetic Algorithms based on our proposed mathematical model, and with assumption in which its special genetic operation in the generation changes is restricted to a quantum operator; and show by means of the Markov chain analysis that the algorithm with preservation of the best individual in the population and comparison of it with the existing individual, will converge on the global optimal solution.
Analysis of the algorithms as Markov chains
Li, P. and Li, S. 2008 Quantum-inspired evolutionary algorithm for continuous space optimization based on Bloch coordinates of qubits   abstract PDF Google
[representation][operators]
Abstract: A novel quantum-inspired evolutionary algorithm is proposed based on the Bloch coordinates of quantum bits (qubits) in this paper. The chromosome is comprised of qubits whose Bloch coordinates comprise gene chain. The quantum chromosomes are updated by quantum rotation gates, and are mutated by quantum non-gates. For the rotation direction of quantum rotation gates, a simple determining method is proposed. For the rotation and mutation of qubits, two new operators are constructed based on Bloch coordinates of qubits. In this algorithm, the Bloch coordinates of each qubit are regarded as three paratactic genes, each chromosome contains three gene chains, and each gene chain represents an optimization solution, which can accelerate the convergence process for the same number of chromosomes. By two application examples of function extremum and neural network weights optimization, the simulation results show that the approach is superior to common quantum evolutionary algorithm and simple genetic algorithm in both search capability and optimization efficiency.
Z. Luo and P. Wang and Y. Li and W. Zhang and W. Tang and M. Xiang 2008 Quantum-inspired evolutionary tuning of SVM parameters   abstract PDF Google
[app]
Abstract: The most commonly used parameters selection method for support vector machines (SVM) is cross-validation, which needs a long-time complicated calculation. In this paper, a novel regularization parameter and a kernel parameter tuning approach of SVM are presented based on quantum-inspired evolutionary algorithm (QEA). QEA with quantum chromosome and quantum mutation has better global search capacity. The parameters of least squares support vector machines (LS-SVM) can be adjusted using quantum-inspired evolutionary optimization. Classification and function estimation are studied using LS-SVM with wavelet kernel and Gaussian kernel. The simulation results show that the proposed approach can effectively tune the parameters of LS-SVM, and the improved LS-SVM with wavelet kernel can provide better precision.
Wenfeng Zhang and Zhongke Shi and Zhiyong Luo 2008 Prediction of urban passenger transport based-on wavelet SVM with quantum-inspired evolutionary algorithm   abstract PDF Google
[app]
Abstract: Based on least squares wavelet support vector machines (LS-WSVM) with quantum-inspired evolutionary algorithm (QEA), the prediction model of urban passenger transport is proposed , that can provide the theoretical foundation of forecasting passenger volume of urban transport accurately. The prediction model of urban passenger transport is established by using LS-WSVM, whose regularization parameter and kernel parameter are adjusted using quantum-inspired evolutionary algorithm. QEA with quantum chromosome and quantum mutation has better global search capacity. The parameters of LS-WSVM can be adjusted using quantum-inspired evolutionary optimization. Combining with the data of the urban volume of passenger transport of Xipsilaan over years, the prediction model of urban passenger transport is validated, the simulation results indicate that the prediction model is effective, and based on LS-WSVM has more improvement than LS-SVM with Gaussian kernel in predicting precision, and then the improved LS-WSVM with QEA is efficient than with cross-validation method for tuning parameters.
Mahdabi, P. and Jalili, S. and Abadi, M. 2008 A multi-start quantum-inspired evolutionary algorithm for solving combinatorial optimization problems   abstract PDF Google
[ext][operators][knapsack]
Abstract: Quantum-inspired evolutionary algorithms (QIEAs), as a subset of evolutionary computation, are based on the principles of quantum computing such as quantum bits and quantum superposition. In this paper, we propose a multi-start quantum-inspired evolutionary algorithm, called MSQIEA. To improve the performance of the algorithm, a multi-measurement operator and a new strategy for updating the rotation angle is proposed. When Q-bit individuals start to converge to their final states, the best solution is stored and all Q-bits in each Q-bit individual are reinitialized. We compare the effectiveness of MSQIEA with a popular quantum-inspired evolutionary algorithm, called QEA, for solving 0-1 knapsack problem. The experimental results show that MSQIEA outperforms QEA and finds a solution with higher profit.
multi-measurement operator; new strategy for rotation angles update; reinitialization
Malossini, A. and Blanzieri, E. and Calarco, T. 2008 Quantum Genetic Optimization   abstract PDF Google
[QB]
Abstract: The complexity of the selection procedure of a genetic algorithm that requires reordering, if we restrict the class of the possible fitness functions to varying fitness functions, is , where is the size of the population. The quantum genetic optimization algorithm (QGOA) exploits the power of quantum computation in order to speed up genetic procedures. In QGOA, the classical fitness evaluation and selection procedures are replaced by a single quantum procedure. While the quantum and classical genetic algorithms use the same number of generations, the QGOA requires fewer operations to identify the high-fitness subpopulation at each generation. We show that the complexity of our QGOA is in terms of number of oracle calls in the selection procedure. Such theoretical results are confirmed by the simulations of the algorithm.
L. M. Melo and G. A. O. P. Costa and R. Q. Feitosa and A. da Cruz and A. Vargas 2008 Quantum-inspired Evolutionary Algorithm and Differential Evolution Used in The Adaptation of Segmentation Parameters   abstract PDF Google
[app]
Abstract: The key step in object-based image interpretation is segmentation. Frequently the relationship between the segmentation parameter values and the corresponding segmentation outcome is not obvious, and the definition of suitable parameter values is usually a time consuming, trial and error process. In (Costa et al., 2008), a supervised, semi-automatic method for the adaptation of segmentation parameters was proposed. Initially a human operator delineates polygons enclosing a representative set of target image objects. The manually drawn polygons are then used as reference segments by a Genetic Algorithm (GA), which searches the segmentation parameter space for values that produce segments as similar as possible to the reference. Although GA based methods have been successfully applied in many optimization problems, they are characterized by a high computational load, and do not guarantee that optimal values are found. Alternatives to the basic GA model have been proposed in order to accelerate convergence, preventing at the same time convergence to local maxima. In this work two of such alternatives have been investigated: Quantum-Inspired Evolutionary Algorithm (QIEA) (Abs da Cruz, 2007) and Differential Evolution (DE) (Storn and Price, 1997). Those two models were employed in the method proposed in (Costa et al., 2008), substituting the conventional GA originally used. Experiments showed that both models converge significantly faster than the original GA. Additionally, for an equivalent computational load, dissimilarity among the reference segments and the ones generated with the parameter values found by applying QIEA and DE was in average respectively 44% and 50% lower, when compared to the results obtained with the original GA.
Nadia Nedjah and Leandro dos Santos Coelho and Luiza de Macedo Mourelle 2008 Quantum inspired intelligent systems   abstract PDF Google
Abstract: Research on applying principles of quantum computing to improve the engineering of intelligent systems has been launched since late 1990s. This emergent research field concentrates on studying on quantum computing that is characterized by certain principles of quantum mechanics such as standing waves, interference, quantum bits, coherence, superposition of states, and concept of interference, combined with computational intelligence or soft computing approaches, such as artificial neural networks, fuzzy systems, evolutionary computing, swarm intelligence and hybrid soft computing methods. This volume offers a wide spectrum of research work developed using soft computing combined with quantum computing systems.
Shen, S. and Liu, Y. 2008 Probability evolutionary algorithm for functional and combinatorial optimization   abstract PDF Google
[representation][knapsack]
Abstract: A novel evolutionary algorithm called probability evolutionary algorithm (PEA) is proposed, which is inspired by the quantum computation and quantum-inspired evolutionary algorithm (QEA). The individual in PEA is encoded by a probabilistic superposed bit which can represent a linear superposition of the states 0 to k (k ges 1). The observing step is used in PEA to obtain the observed individual, and the update method is used to evolve the population. The function optimization and 0-k knapsack problem experiments show that PEA has apparent superior in application area, searching capability and computation time compared with QEA and canonical genetic algorithm (CGA).
quantum natural coding (inspired by qudits)
Imabeppu, T. and Nakayama, S. and Ono, S. 2008 A study on a quantum-inspired evolutionary algorithm based on pair swap   abstract PDF Google
[ext][knapsack]
Abstract: A quantum-inspired evolutionary algorithm (QEA) is proposed as a stochastic algorithm to perform combinatorial optimization problems. The QEA is evolutionary computation that uses quantum bits and superposition states in quantum computation. Although the QEA is a coarse-grained parallel algorithm, it involves many parameters that must be adjusted manually. This paper proposes a new method, named pair swap, which exchanges each best solution information between two individuals instead of migration in the QEA. Experimental results show that our proposed method is a simpler algorithm and can find a high quality solution in the 0-1 knapsack problem.
a new "pair swap" concept instead of migration
Su, H. and Yang, Y. 2008 Quantum-Inspired Differential Evolution for Binary Optimization   abstract PDF Google
[hybrid]
Abstract: The differential evolution (DE) is usually considered as a robust, fast, powerful optimization approach. DE has been widely applied to solve many optimization problems in the continuous-valued space. However, DE is seldom used in the binary-valued space owing to its particular operators. The paper uses a Q-bit string as a representation, and proposes the quantum-inspired differential evolution algorithm (QDE). The operators of DE are used to be able to drive the individuals to move to better solutions. Numerical experiments are performed to illustrate the performance of QDE compared with three algorithms in the binary-valued space. The results show that QDE generally outperform the other algorithms in the test functions.
Vlachogiannis, J.G. and Lee, K.Y. 2008 Quantum-Inspired Evolutionary Algorithm for Real and Reactive Power Dispatch   abstract PDF Google
[app]
Abstract: This paper presents an evolutionary algorithm based on quantum computation for bid-based optimal real and reactive power (P-Q) dispatch. The proposed quantum-inspired evolutionary algorithm (QEA) has applications in various combinatorial optimization problems in power systems and elsewhere. In this paper, the QEA determines the settings of control variables, such as generator outputs, generator voltages, transformer taps and shunt VAR compensation devices for optimal P-Q dispatch considering the bid-offered cost. The algorithm is tested on the IEEE 30-bus system, and the results obtained by the QEA are compared with those obtained by other modern heuristic techniques: ant colony system (ACS), enhanced GA and simulated annealing (SA) as well as the original QEA. Furthermore, in order to demonstrate the applicability of the proposed QEA, it is also implemented in a different problem, which is to minimize the real power losses in the IEEE 118-bus transmission system. The comparisons demonstrate an improved performance of the proposed QEA.
Lv, Y. and Li, D. 2008 Improved Quantum Genetic Algorithm and Its Application in Nutritional Diet Optimization   abstract PDF Google
[app][ext][initialization]
Abstract: An improved quantum genetic algorithm (IQGA) is proposed to avoid declining of the searching ability for multi-peak function optimization and multi-genes chromosome encoding problem. Improvements include adjusting initialization way of chromosome's genes, changing elitist strategy and introducing partial population disaster strategy. Experimental results on continuous multi-peak function optimization and actual nutritional diet optimization show that IQGA is superior to traditional quantum genetic algorithm on convergence speed and global optimization ability. Even for multi-genes encoding problem, this improved quantum genetic algorithm still has higher searching capability, usability and robustness than traditional quantum genetic algorithm.
modified initialization, elitism, partial replacement of population
Abdesslem Layeb and Djamel Eddine Saidouni 2008 A quantum genetic algorithm with hill climbing algorithm for max 3-SAT problems   abstract PDF Google
[app]
Abstract: In this paper we present a new iterative method to solve the maximum satisfiability problem (MAX SAT). This one aims to find the best assignment for a set of Boolean variables that gives the maximum of verified clauses in a Boolean formula. Unfortunately, It is shown that the MAX SAT problem is NP complete if the number of variable per clause is higher than 3. Our approach called QHILLSAT is a combination of a Quantum Genetic Algorithm QGA and a Hill Climbing Algorithm. The main features of this algorithm consist in the quantum structure used to represent MAX SAT solutions and the quantum operators defining the overall evolutionary dynamic of the genetic algorithm. The Hill Climbing Search procedure is used in order to increase the efficiency of the exploration process. Experiments on wide range of data sets have shown the effectiveness of the proposed framework and its ability to achieve good quality solutions.
Yang, X.S. 2008 Nature-inspired metaheuristic algorithms Google
[other]
Zhang, G.X. and Gheorghe, M. and Wu, C.Z. 2008 A Quantum-Inspired Evolutionary Algorithm Based on P systems for Knapsack Problem   abstract PDF Google
[hybrid][app][ext][knapsack]
Abstract: This paper introduces an evolutionary algorithm which uses the concepts and principles of the quantum-inspired evolutionary approach and the hierarchical arrangement of the compartments of a P system. The P system framework is also used to formally specify this evolutionary algorithm. Extensive experiments are conducted on a well-known combinatorial optimization problem, the knapsack problem, to test the effectiveness of the approach. These experimental results show that this evolutionary algorithm performs better than quantum-inspired evolutionary algorithms, for certain arrangements of the compartments of the P system structure utilized.
Neubauer, A. 2008 Intrinsic System Model of the Genetic Algorithm with $\alpha$-Selection   abstract PDF Google
[other][theoretical][!!!]
Abstract: Genetic algorithms are random heuristic search (RHS) algorithms which can be theoretically described with the help of a dynamical system model. This model characterises the stochastic trajectory of a population using a deterministic heuristic function and its fixed points. For practical problem sizes the determination of the fixed points is unfeasible even for the simple genetic algorithm (SGA). In this paper the novel intrinsic system model is introduced for the genetic algorithm with #-selection and the corresponding unique fixed point is determined. It is shown that this model is compatible with the equivalence relation imposed by schemata. In addition to the theoretical analysis experimental results are presented which confirm the theoretical predictions.
theoretical analysis of GAs in a dynamical system model point of view
Pedersen, Magnus Erik Hvass and Chipperfield, Andrew John 2008 Local unimodal sampling Google
Araujo, Marcos Paulo and Nedjah, Nadia and Macedo Mourelle, Luiza 2008 Logic Synthesis for FSMs Using Quantum Inspired Evolution   abstract Google
[app]
Abstract: Synchronous finite state machines are very important for digital sequential systems. Among other important aspects, they represent a powerful way for synchronising hardware components so that these components may cooperate adequately in the fulfilment of the main objective. In this paper, we propose to use an evolutionary methodology inspired from quantum computation to yield a concise and efficient evolvable hardware that implements the state machine control logic.
Layeb, Abdesslem and Saidouni, Djamel-Eddine 2008 A New Quantum Evolutionary Local Search Algorithm for MAX 3-SAT Problem   abstract PDF Google
[app]
Abstract: The Max Sat problem is very known problem in computer science. It aims to find the best assignment for a set of Boolean variables that gives the maximum of verified clauses in a Boolean formula. Unfortunately, this problem was showed NP-Hard if the number of variable per clause is higher than 3. In this article, we propose a new iterative stochastic approach called QSAT based on a hybrid algorithm of Quantum Evolutionary Algorithm QEA and Local Search Algorithm LSA. QSAT is based on a basic core defined by a suitable quantum representation and an adapted quantum evolutionary dynamic enhanced by Local Search procedure. The obtained results are encouraging and prove the feasibility and the effectiveness of our approach. QSAT is distinguished by a reduced population size and a reasonable number of iterations to find the best assignment, thanks to the principles of quantum computing.
Yu, Hai-Yan and Fan, Jiu-Lun 2008 Three-Level Image Segmentation Based on Maximum Fuzzy Partition Entropy of 2-D Histogram and Quantum Genetic Algorithm   abstract Google
[app]
Abstract: A method is presented for three-level image segmentation through maximizing the fuzzy partition entropy of two-dimensional histogram. Two groups, each including three member functions, namely Z-function, ďžż-function and S-function, are used for fuzzy division of two-dimensional histogram to get nine fuzzy sets. And the nine fuzzy sets are classified to three parts, corresponding to dark, gray and white part of the image, respectively, while a fuzzy partition is obtained for the two-dimensional space. Then a fuzzy partition entropy is defined based on multi-dimensional fuzzy partition and entropy theory. The parameters of the six membership functions can be determined by maximizing fuzzy partition entropy of two-dimensional histogram and the procedure for finding the optimal combination of all the fuzzy parameters is implemented by quantum genetic algorithm with an appropriate coding method. The experiment results show that the proposed method gives better performance than onedimensional three-level thresholding method under noise case.
R. Nowotniak 2008 Wykorzystanie metod ewolucyjnych w projektowaniu algorytmów kwantowych Google
[other]
Petko, Joshua S and Werner, Douglas H 2007 An autopolyploidy-based genetic algorithm for enhanced evolution of linear polyfractal arrays Google
Hawking, S. 2007 Public Lectures: Does God Play Dice? Google
Jolanta Socała and Witold Kosiński 2007 Zastosowanie metody funkcji dolnej do badania zbieżności algorytmów genetycznych   abstract PDF Google
[theoretical][other]
Abstract: W badaniu wielu zjawisk przyrodniczych istotną rolę odgrywają operatory Markowa, nieujemne operatory liniowe oraz ich półgrupy. W szczególności rozważana jest asymptotyczna stabilność. A. Lasota i J. A. Yorke w 1982 r. udowodnili, że warunkiem wystarczającym i koniecznym asymptotycznej stabilności dla operatora Markowa jest istnienie nietrywialnej funkcji dolnej. W niniejszej pracy pokazujemy zastosowanie metody funkcji dolnej do badania zachowania algorytmów genetycznych. Rozpatrywane w pracy algorytmy genetyczne, używane do rozwiązywania niegładkich problemów optymalizacyjnych, są wynikiem złożenia dwóch operatorów losowych: selekcji i mutacji. Złożenie tych operacji jest macierzą Markowa.
P. Arpaia and G. Meccariello and M. Rapone and A. Zanesco 2007 Quantum-Inspired Evolutionary Classification of Driving Sequences in Vehicle Emission Factor Measurement   abstract PDF Google
[app]
Abstract: A heuristic procedure of classification, the quantum-inspired classifier (QIC), exploiting search space exploration and resource exploitation of quantum computing on a software basis is proposed. The application to the problem of speed sequence classification for vehicle emission factor determination based on drive styles is shown. Experimental results are discussed by showing the QIC capability of converging better and faster than classical evolutionary algorithms.
not published, not verified paper
Guo, R. and Li, B. and Zou, Y. and Zhuang, Z. 2007 Hybrid quantum probabilistic coding genetic algorithm for large scale hardware-software co-synthesis of embedded systems   abstract PDF Google
[app]
Abstract: Hardware-software co-synthesis is a key step of future design of embedded systems. It involves three interdependent subproblems: allocation of resources, assignment of tasks to resources, and scheduling the execution of tasks. Both assignment and scheduling are known to be NP-complete. So it is a really hard and challenging task to optimization algorithms. Both heuristic and evolutionary algorithms are commonly used in real world. Heuristic algorithms converge rapidly but often be trapped in local minima and evolutionary algorithms own high exploration capacity but become time-consuming when handling large-scale systems. In this paper, a new hybrid evolutionary algorithm, called Hybrid Quantum probabilistic coding Genetic Algorithm, is proposed to implement the co-synthesis of large scale multiprocessor embedded systems, in which a heuristic algorithm is combined with the Quantum probabilistic coding Genetic Algorithm to enhance the performance on the hard task. The experimental results show that HQGA has better performance than both HA and QGA on large scale HW/SW co-synthesis problems.
Layeb, A. and Saidouni, D.E. 2007 Quantum Genetic Algorithm forBinary Decision Diagram Ordering Problem   abstract PDF Google
[app][representation]
Abstract: The Binary Decision Diagram (BDD) is used to represent in symbolic manner a set of states. It's largely used in the field of formal checking. The variable ordering is a very important step in the BDD optimization process. A good order of variables will reduce considerably the size of a BDD. Unfortunately, the search for the best variables ordering has been showed NP-difficult. In this article, we propose a new iterative approach called QGABDD based on a Quantum Genetic Algorithm. QGABDD is based on a basic core defined by a suitable quantum representation and an adapted quantum evolutionary dynamic. The obtained results are encouraging and attest the feasibility and the effectiveness of our approach. QGABDD is distinguished by a reduced population size and a reasonable number of iterations to find the best order, thanks to the principles of quantum computing
Lv, YJ and Liu, NX 2007 Application of quantum genetic algorithm on finding minimal reduct   abstract PDF Google
[app]
Abstract: Quantum Genetic Algorithm (QGA) is a promising area in the field of computational intelligence nowadays. Although some genetic algorithms to find minimal reduct of attributes have been proposed, most of them have some defects. On the other hand, quantum genetic algorithm has some advantages, such as strong parallelism, rapid good search capability, and small population size. In this paper, we propose a QGA to find minimal reduct based on distinction table. The algorithm can obtain the best solution with one chromosome in a short time. It is testified by two experiments that our algorithm improves the GA from four points of view: population size, parallelism, computing time and search capability.
Patvardhan, C. and Narayan, A. and Srivastav, A. 2007 Enhanced Quantum Evolutionary Algorithms for Difficult Knapsack Problems   abstract Google
[app][knapsack]
Abstract: Difficult knapsack problems are problems that are expressly designed to be difficult. In this paper, enhanced Quantum Evolutionary Algorithms are designed and their application is presented for the solution of the DKPs. The algorithms are general enough and can be used with advantage in other subset selection problems.
Defoin-Platel, M. and Schliebs, S. and Kasabov, N. 2007 A versatile quantum-inspired evolutionary algorithm   abstract PDF Google
[ext][!!!][eda]
Abstract: This study points out some weaknesses of existing quantum-inspired evolutionary algorithms (QEA) and explains in particular how hitchhiking phenomena can slow down the discovery of optimal solutions and encourage premature convergence. A new algorithm, called versatile quantum- inspired evolutionary algorithm (vQEA), is proposed. With vQEA, the attractors moving the population through the search space are replaced at every generation without considering their fitness. The new algorithm is much more reactive. It always adapts the search toward the last promising solution found thus leading to a smoother and more efficient exploration. In this paper, vQEA is tested and compared to a classical genetic algorithm CGA and to a QEA on several benchmark problems. Experiments have shown that vQEA performs better than both CGA and QEA in terms of speed and accuracy. It is a highly scalable algorithm as well. Finally, the properties of the vQEA are discussed and compared to estimation of distribution algorithms (EDA).
vQEA -- attractors of the evolutionary process are modified each generation; comparison with EDA
Yang, Q. and Ding, S. 2007 Methodology and Case Study of Hybrid Quantum-Inspired Evolutionary Algorithm for Numerical Optimization   abstract PDF Google
[operators]
Abstract: This paper proposes a hybrid quantum-inspired evolutionary algorithm which codes individuals with amplitudes. The evolutionary goals are evolved by classical crossover operator. Self-adaptive rotation operator and mutation operator with respect to mutation degree are introduced too. Extensive case studies show that the novel algorithm exceeds other quantum evolutionary algorithms and classical genetic algorithms on the single-objective numerical optimization problems. In addition, novel algorithm with random weighted-sum aggregation strategy performs very well on multi-objective numerical optimization problems.
classical crossover operator, self-adaptation of rotation operator, generalised mutation operator
Talbi, H. and Batouche, M. and Draa, A. 2007 A Quantum-Inspired Evolutionary Algorithm for Multiobjective Image Segmentation   abstract PDF Google
[app][multiobj]
Abstract: In this paper we present a new approach to deal with image segmentation. The fact that a single segmentation result do not generally allow a higher level process to take into account all the elements included in the image has motivated the consideration of image segmentation as a multiobjective optimization problem. The proposed algorithm adopts a split/merge strategy that uses the result of the k-means algorithm as input for a quantum evolutionary algorithm to establish a set of non-dominated solutions. The evaluation is made simultaneously according to two distinct features: intra-region homogeneity and inter-region heterogeneity. The experimentation of the new approach on natural images has proved its efficiency and usefulness.
Wang, Y. and Feng, X.Y. and Huang, Y.X. and Pu, D.B. and Zhou, W.G. and Liang, Y.C. and Zhou, C.G. 2007 A novel quantum swarm evolutionary algorithm and its applications   abstract PDF Google
[swarm][knapsack][TSP]
Abstract: In this paper, a novel quantum swarm evolutionary algorithm (QSE) is presented based on the quantum-inspired evolutionary algorithm (QEA). A new definition of Q-bit expression called quantum angle is proposed, and an improved particle swarm optimization (PSO) is employed to update the quantum angles automatically. The simulated results in solving 0-1 knapsack problem show that QSE is superior to traditional QEA. In addition, the comparison experiments show that QSE is better than many traditional heuristic algorithms, such as climb hill algorithm, simulation anneal algorithm and taboo search algorithm. Meanwhile, the experimental results of 14 cities traveling salesman problem (TSP) show that it is feasible and effective for small-scale TSPs, which indicates a promising novel approach for solving TSPs.
Qin, C. and Zheng, J. and Lai, J. 2007 A Multiagent Quantum Evolutionary Algorithm for Global Numerical Optimization   abstract Google
Abstract: In this paper, a novel kind of algorithm, multiagent quantum evolutionary algorithm(MAQEA), is proposed based on multiagent, evolutionary programming and quantum computation. An agent represents a candidate solution for optimization problem. All agents are presented by quantum chromosome, whose core lies on the concept and principles of quantum computing, live in table environment. Each agent competes and cooperates with its neighbors in order to increase its competitive ability. Quantum computation mechanics is employed to accelerate evolution process. The result of experiments shows that MAQEA has a strong ability of global optimization and high convergence speed.
Fan, Kai and Brabazon, Anthony and O'Sullivan, Conall and O'Neill, Michael 2007 Option pricing model calibration using a real-valued quantum-inspired evolutionary algorithm   abstract PDF Google
[app][representation][real]
Abstract: Quantum effects are a natural phenomenon and just like evolution, or immune processes, can serve as an inspiration for the design of computing algorithms. This study illustrates how a real-valued quantum-inspired evolutionary algorithm(QEA) can be constructed and examines the utility of the resulting algorithm on an important real-world problem, namely the calibration of an Option Pricing model. The results from the algorithm are shown to be robust and sensitivity analysis is carried out on the algorithm parameters, suggesting that there is useful potential to apply QEA to this domain.
Gexiang Zhang and Haina Rong 2007 Parameter Setting of Quantum-Inspired Genetic Algorithm Based on Real Observation   abstract PDF Google
[!!!]
Abstract: Parameter setting, especially the angle of Q-gate, has much effect on the performance of quantum-inspired evolutionary algorithm. This paper investigates how the angle of Q-gate affects the optimization performance of real-observation quantum-inspired genetic algorithm. Four methods, including static adjustment methods, random adjustment methods, dynamic adjustment methods and adaptive adjustment methods, are presented to bring into comparisons to draw some guidelines for setting the angle of Q-gate. Comparative experiments are carried out on some typical numerical optimization problems. Experimental results show that real-observation quantum-inspired genetic algorithm has good performance when the angle of Q-gate is set to lower value.
Analysis of various rotation strategies on efficacy of QGAs
Al-Othman, AK and Al-Fares, FS and EL-Nagger, KM 2007 Power System Security Constrained Economic Dispatch Using Real Coded Quantum Inspired Evolution Algorithm   abstract PDF Google
[app][real]
Abstract: This paper presents a new optimization technique based on quantum computing principles to solve a security constrained power system economic dispatch problem (SCED). The proposed technique is a population-based algorithm, which uses some quantum computing elements in coding and evolving groups of potential solutions to reach the optimum following a partially directed random approach. The SCED problem is formulated as a constrained optimization problem in a way that insures a secureeconomic system operation. Real Coded Quantum-Inspired Evolution Algorithm (RQIEA) is then applied to solve the constrained optimization formulation. Simulation results of the proposed approach are compared with those reported in literature. The outcome is very encouraging and proves that RQIEA is very applicable for solving security constrained power system economic dispatch problem (SCED).
Zhang, Gexiang and Rong, Haina 2007 Real-Observation Quantum-Inspired Evolutionary Algorithm for a Class of Numerical Optimization Problems   abstract PDF Google
[!!!][real]
Abstract: This paper proposes a real-observation quantum-inspired evolutionary algorithm (RQEA) to solve a class of globally numerical optimization problems with continuous variables. By introducing a real observation and an evolutionary strategy, suitable for real optimization problems, based on the concept of Q-bit phase, RQEA uses a Q-gate to drive the individuals toward better solutions and eventually toward a single state corresponding to a real number varying between 0 and 1. Experimental results show that RQEA is able to find optimal or close-to-optimal solutions, and is more powerful than conventional real-coded genetic algorithm in terms of fitness, convergence and robustness.
rQIEA -- very good
Ong, Yew-Soon and Lim, Meng-Hiot and Zhu, Ning and Wong, Kok-Wai 2006 Classification of adaptive memetic algorithms: a comparative study Google
Penrose, Roger 2006 The road to reality: A complete guide to the laws of the universe Google
Hameroff, S. 2006 Consciousness, neurobiology and quantum mechanics: The case for a connection Google
Feng, X.Y. and Wang, Y. and Ge, H.W. and Zhou, C.G. and Liang, Y.C. 2006 Quantum-inspired evolutionary algorithm for travelling salesman problem   abstract Google
[TSP][app]
Abstract: A novel quantum coding mechanism is proposed to solve the travelling salesman problem (TSP) based on the quantum-inspired evolutionary algorithm. It adopts Q-bit individual to encode the visited sequence of the cities and employs the quantum rotation gate to adjust the population dynamically. Experimental results of 14 cities show that the proposed approach is feasible and effective for small-scale TSPs, which indicates a promising novel approach for solving TSPs.
De Jong, K.A. 2006 Evolutionary computation: a unified approach PDF Google
[other][survey]
Layeb, A. and Meshoul, S. and Batouhe, M. 2006 Multiple Sequence Alignment by Quantum Genetic Algorithm   abstract PDF Google
[operators]
Abstract: In this paper we describe a new approach for the well known problem in bioinformatics: multiple sequence alignment (MSA). MSA is fundamental task as it represents an essential platform to conduct other tasks in bioinformatics such as the construction of phylogenetic trees, the structural and functional prediction of new protein sequences. Our approach merges between the classical genetic algorithm and some principles of the quantum computing like interference, measure, superposition, etc. It differs from other genetic methods of the literature by using a small population size and a less iteration required to find good quality alignments thanks to the used quantum principles: state superposition, interference, quantum mutation and quantum crossover. Another attractive feature of this method is its ability to provide an extensible platform for evaluating different objective functions. Experiments on a wide range of data sets have shown the effectiveness of the proposed approach and its ability to achieve good quality solutions comparing to those given by other popular multiple
six new quantum genetic operators for the sequence alignment problem
Alfares, F.S. and Esat, I.I. 2006 Real-Coded Quantum Inspired Evolution Algorithm Applied to Engineering Optimization Problems   abstract PDF Google
[real]
Abstract: A novel evolutionary algorithm based on quantum computing concepts is applied to engineering optimization problems. Quantum computing mimics behavior of atoms in processing information. Quantum inspired algorithm is a concept, which employs certain elements of quantum computing to use in a wider class of search and optimization problems. The main parts of a quantum-inspired algorithm are the qubits (quantum equivalent of bits) and the quantum gates. Qubits hold the information in a superposition of all the states, while the quantum gates evolve the qubit to achieve the desired objective, which is, in optimization the maximum or the minimum. The paper addresses the ability of the Quantum-Inspired Evolution Algorithm (QIEA) to solve practical engineering optimization problems. QIEA, which is developed by authors, is based on their previous work and it is extended to acquire the floating-point representation of the information. The RQIEA is tested on a four benchmark engineering optimization problems. The results showed that the new algorithm has the ability to compete and even overcome other well known methods.
da Cruz, A.V.A. and Vellasco, M.M.B. and Pacheco, M.A.C. 2006 Quantum-Inspired Evolutionary Algorithm for Numerical Optimization   abstract PDF Google
[real][representation][operators][!!!]
Abstract: Since they were proposed as an optimization method, evolutionary algorithms (EA) have been used to solve problems in several research fields. This success is due, besides other things, to the fact that these algorithms do not require previous considerations regarding the problem to be optimized and offers a high degree of parallelism. However, some problems are computationally intensive regarding solution's evaluation, which makes the optimization by EA's slow for some situations. This paper proposes a novel EA for numerical optimization inspired by the multiple universes principle of quantum computing. Results show that this algorithm can find better solutions, with less evaluations, when compared with similar algorithms.
The first clear proposal of quantum real coding, based on CDF, slight inspiration from Evolutionary Strategies
Xiao Wang-xin and Zhang Xue and Yan Xin-ping 2006 QGA based Bandwidth Adaptation Scheme for Wireless/Mobile Networks   abstract PDF Google
[app]
Abstract: Radio resource management plays a major role in QoS provisioning for wireless/mobile networks. The scarcity and fluctuation of wireless link bandwidth, as well as the interconnection of wireless networks and Internet, motivate the research on adaptive multimedia services which have already run in Internet widely. The problem of seeking the optimal solution for revenue maximization is NP-hard, so the optimal bandwidth adaptation algorithm is not practical. In this paper, we propose a QGA (quantum genetic algorithm) based bandwidth adaptation scheme to find the suboptimal solution for such problem. As a general optimization algorithm, QGA is of less searching generations, higher convergence speed, higher searching efficiency, and better global searching ability, when compared with conventional genetic algorithm. Simulation results show that our algorithm works well for such problem, and with much less optimization time compared with the optimal algorithm
Udrescu, Mihai and Prodan, Lucian and Vl\u{a}du\c{t}iu, Mircea 2006 Implementing quantum genetic algorithms: a solution based on Grover's algorithm   abstract PDF Google
[QB]
Abstract: This paper presents a new methodology for running Genetic Algorithms on a Quantum Computer. To the best of our knowledge and according to reference [6]there are no feasible solutions for the implementation of the Quantum Genetic Algorithms (QGAs). We present a new perspective on how to build the corresponding QGA architecture. It turns out that the genetic strategy is not particularly helpful in our quantum computation approach; therefore our solution consists of designing a special-purpose oracle that will work with a modified version of an already known algorithm (maximum finding [1]), in order to reduce the QGAs to a Grover search. Quantum computation offers incentives for this approach, due to the fact that the qubit representation of the chromosome can encode the entire population as a superposition of basis-state values.
Han, K.H. and Kim, J.H. 2006 On the analysis of the quantum-inspired evolutionary algorithm with a single individual   abstract PDF Google
[theoretical][!!!]
Abstract: This paper discusses the reason why QEA works and verifies how QEA works. The theoretical analysis of the simplified model of the segment process of QEA shows that QEA with a single individual for OneMax problem guarantees the global solution in terms of expected running number of generations. The analysis for exploration shows clearly that QEA starts with a global search scheme and changes automatically into a local search scheme as generation advances because of its inherent probabilistic mechanism, which leads to a good balance between exploration and exploitation. For comparison purpose, simulated annealing is considered with three test functions. The results support the conclusions derived from the theoretical analysis of QEA with a single individual.
Kim, Y. and Kim, J.H. and Han, K.H. 2006 Quantum-inspired multiobjective evolutionary algorithm for multiobjective 0/1 knapsack problems   abstract PDF Google
[app][knapsack][multiobj]
Abstract: This paper proposes a multiobjective evolutionary algorithm (MOEA) inspired by quantum computing, which is named quantum-inspired multiobjective evolutionary algorithm (QMEA). In the previous papers, quantum-inspired evolutionary algorithm (QEA) was proved to be better than conventional genetic algorithms for single-objective optimization problems. To improve the quality of the nondominated set as well as the diversity of population in multiobjective problems, QMEA is proposed by employing the concept and principles of quantum computing such as uncertainty, superposition, and interference. Experimental results pertaining to the multiobjective 0/1 knapsack problem show that QMEA finds solutions close to the Pareto-optimal front while maintaining a better spread of nondominated set.
Li, B. and Wang, L. 2006 A hybrid quantum-inspired genetic algorithm for multi-objective scheduling   abstract Google
[app][multiobj][operators]
Abstract: This paper proposes a hybrid quantum-inspired genetic algorithm (HQGA) for multi-objective flow shop scheduling problem. On one hand, a quantum-inspired GA (QGA) based on Q-bit representation is applied for exploration in discrete 0-1 hyperspace by using updating operator of quantum gate and genetic operators of Q-bit. Random key representation is used to convert the Q-bit representation to job permutation. On the other hand, permutation-based GA (PGA) is applied for both performing exploration in permutation-based scheduling space and stressing exploitation for good schedule solutions. To evaluate solutions in multi-objective sense, randomly weighted linear sum function is used in QGA, while non-dominated sorting techniques including classification of Pareto fronts and fitness assignment are applied in PGA regarding to both proximity and diversity of solutions in multi-objective sense. Simulation results and comparisons demonstrate the effectiveness and robustness of the proposed HQGA.
Zhang, G. and Li, N. and Jin, W. and Hu, L. 2006 Novel quantum genetic algorithm and its applications   abstract Google
[app][operators]
Abstract: Abstract By introducing strong parallelism of quantum computing into evolutionary algorithm, a novel quantum genetic algorithm (NQGA) is proposed. In NQGA, a novel approach for updating the rotation angles of quantum logic gates and a strategy for enhancing search capability and avoiding premature convergence are adopted. Several typical complex continuous functions are chosen to test the performance of NQGA. Also, NQGA is applied in selecting the best feature subset from a large number of features in radar emitter signal recognition. The testing and experimental results of feature selection show that NQGA presents good search capability, rapid convergence, short computing time, and ability to avoid premature convergence effectively.
a new method for rotation angles update
W. G. Zhou and C. G. Zhou and G. X. Liu and H. Y. Lv and Y. C. Liang 2006 An Improved Quantum-Inspired Evolutionary Algorithm for Clustering Gene Expression Data   abstract Google
[app][representation][operators]
Abstract: Microarray technologies have made it straightforward to monitor simultaneously the expression pattern of thousands of genes. So an important task is to cluster gene expression data to identify groups of genes with similar patterns and hence similar functions. In this paper, an improved quantum-inspired evolutionary algorithm (IQEA) is first proposed for minimum sum-of-squares clustering. We have suggested a new representation form and added an additional mutation operation in IQEA. Experiment results show that IQEA appears to be much more robust in finding optimum or best-known solutions and be superior to conventional k-means and self-organizing maps clustering algorithms even with a small population. ER -
a new quantum representation for the specific application, a new quantum mutation operator
Shannon, S. 2006 Trends in quantum computing research Google
Rutkowski, L. 2006 Metody i techniki sztucznej inteligencji: inteligencja obliczeniowa Google
Michalewicz, Z. and Fogel, D.B. 2006 Jak to rozwiązać czyli nowoczesna heurystyka Google
Sofge, D.A. 2006 Toward a framework for quantum evolutionary computation PDF Google
[QB]
Eugene Eberbach 2005 Toward a theory of evolutionary computation   abstract PDF Google
[other][theoretical]
Abstract: We outline a theory of evolutionary computation using a formal model of evolutionary computation - the Evolutionary Turing Machine - which is introduced as the extension of the Turing Machine model. Evolutionary Turing Machines provide a better and a more complete model for evolutionary computing than conventional Turing Machines, algorithms, and Markov chains. The convergence and convergence rate are defined and investigated in terms of this new model. The sufficient conditions needed for the completeness and optimality of evolutionary search are investigated. In particular, the notion of the total optimality as an instance of the multiobjective optimization of the Universal Evolutionary Turing Machine is introduced. This provides an automatic way to deal with the intractability of evolutionary search by optimizing the quality of solutions and search costs simultaneously. Based on a new model a very flexible classification of optimization problem hardness for the evolutionary techniques is proposed. The expressiveness of evolutionary computation is investigated. We show that the problem of the best evolutionary algorithm is undecidable independently of whether the fitness function is time dependent or fixed. It is demonstrated that the evolutionary computation paradigm is more expressive than Turing Machines, and thus the conventional computer science based on them. We show that an Evolutionary Turing Machine is able to solve nonalgorithmically the halting problem of the Universal Turing Machine and, asymptotically, the best evolutionary algorithm problem. In other words, the best evolutionary algorithm does not exist, but it can be potentially indefinitely approximated using evolutionary techniques.
Soca{\l}a, J. and Kosi{\'n}ski, W. and Kotowski, S. 2005 O asymptotycznym zachowaniu prostego algorytmu genetycznego   abstract PDF Google
[other][theoretical]
Abstract: W pracy zdefiniowano prosty algorytm genetyczny w terminach skończonego multizbioru potencjalnych rozwiązań (osobników danej populacji), na którym są określone operacje krzyżowania, mutacji i selekcji, każda z pewnym prawdopodobieństwem. Działając złożeniem tych operacji na dowolną populację, tworzymy nową populację. Istnienie funkcji przystosowania (dopasowania), określonej na osobnikach populacji, pozwala powiązać prawdopodobieństwo selekcji osobników do nowej populacji z wartościami, jakie funkcja przystosowania przyjmuje na osobniku. Przejście z jednej generacji do drugiej jest realizowane przez operator działający na wektory probabilistyczne charakteryzujące rozkład prawdopodobieństwa pojawienia się każdej z możliwych populacji. Jest to operator Markowa. W teorii operatorów Markowa oraz operatorów dodatnich znanych jest wiele twierdzeń dotyczących istnienia punktów stałych oraz zbieżności ciągu iteracji operatora (np. [9, 12, 13]). Korzystając z tych wyników, znaleźliśmy warunki wystarczające i konieczne stabilności operatora Markowa związanego z pewną klasą algorytmów
Clear and understandable analysis of SGA as a dynamic system
Paszynska, A. 2005 An extension of vose's markov chain model for genetic algorithms   abstract PDF Google
[other][theoretical]
Abstract: The paper presents an extension of Vose's Markov chain model for genetic algorithm (GA). The model contains not only standard genetic operators such as mutation and crossover but also two new operators - translation to the left/right and permutation of bits. The presented model can be used for finding the transition matrices and for the investigation of asymptotic properties by using Markov transition functions. The ergodity of the Markov chain describing the GA with new operators, translation to the left/right and permutation, is shown. The model is specialized for a case of Bentley's GA. For this GA the ergodity of the Markov chains and the asymptotic correctness in the probabilistic sense are shown. To model other aspects of the Bentley's GA (effective fitness, total transmission probability) the microscopic Exact Poli GP Schema Theory for Subtree-Swapping Crossover is used.
André V. Abs da Cruz and Marco Aurélio Cavalcanti Pacheco and Marley B. R. Vellasco and Carlos R. Hall Barbosa 2005 Cultural Operators for a Quantum-Inspired Evolutionary Algorithm Applied to Numerical Optimization Problems.   abstract PDF Google
[ext][operators][real][representation]
Abstract: This work presents the application of cultural algorithms operators to a new quantum-inspired evolutionary algorithm with numerical representation. These operators (fission, fusion, generalization and specialization) are used in order to provide better control over the quantum-inspired evolutionary algorithm. We also show that the quantum-inspired evolutionary algorithm with numerical representation behaves in a very similar manner to a pure cultural algorithm and we propose further investigations concerning this aspect.
New "cultural" operators for real quantum coding
Wang, L. and Tang, F. and Wu, H. 2005 Hybrid genetic algorithm based on quantum computing for numerical optimization and parameter estimation   abstract PDF Google
Abstract: Quantum computing is applied to genetic algorithm (GA) to develop a class of quantum-inspired genetic algorithm (QGA) characterized by certain principles of quantum mechanisms for numerical optimization. Furthermore, a framework of hybrid QGA, named RQGA, is proposed by reasonably combining the Q-bit search of quantum algorithm in micro-space and classic genetic search of real-coded GA (RGA) in macro-space to achieve better optimization performances. Simulation results based on typical functions demonstrate the effectiveness of the hybridization, especially the superiority of RQGA in terms of optimization quality, efficiency as well as the robustness on parameters and initial conditions. Moreover, simulation results about model parameter estimation also demonstrate the effectiveness and efficiency of the RQGA.
Hybridization of QiGA and GA with real coding
Wang, L. and Wu, H. and Tang, F. and Zheng, D. 2005 A hybrid quantum-inspired genetic algorithm for flow shop scheduling   abstract PDF Google
[app][operators]
Abstract: This paper is the first to propose a hybrid quantum-inspired genetic algorithm (HQGA) for flow shop scheduling problems. In the HQGA, Q-bit based representation is employed for exploration in discrete 0-1 hyperspace by using updating operator of quantum gate as well as genetic operators of Q-bit. Then, the Q-bit representation is converted to random key representation. Furthermore, job permutation is formed according to the random key to construct scheduling solution. Moreover, as a supplementary search, a permutation-based genetic algorithm is applied after the solutions are constructed. The HQGA can be viewed as a fusion of micro-space based search (Q-bit based search) and macro-space based search (permutation based search). Simulation results and comparisons based on benchmarks demonstrate the effectiveness of the HQGA. The search quality of HQGA is much better than that of the pure classic GA, pure QGA and famous NEH heuristic.
Combination of QiGA with operators for permutations
Wang, L. and Wu, H. and Zheng, D. 2005 A quantum-inspired genetic algorithm for scheduling problems   abstract PDF Google
[operators]
Abstract: This paper is the first to propose a quantum-inspired genetic algorithm (QGA) for permutation flow shop scheduling problem to minimize the maximum completion time (makespan). In the QGA, Q-bit based representation is employed for exploration in discrete 0-1 hyperspace by using updating operator of quantum gate as well as genetic operators of Q-bit. Meanwhile, the Q-bit representation is converted to random key representation, which is then transferred to job permutation for objective evaluation. Simulation results and comparisons based on benchmarks demonstrate the effectiveness of the QGA, whose searching quality is much better than that of the famous NEH heuristic.
A new representation of scheduling tasks
Fortuna, Z and Macukow, B and Wasowski, J 2005 Metody numeryczne. WNT. Warszawa Google
Md. Amjad Hossain and Md. Kowsar Hossain and M. M. A Hashem 2005 A generalized hybrid real-coded quantum evolutionary algorithm based on particle swarm theory with arithmetic crossover   abstract PDF Google
[real][operators][hybrid]
Abstract: This paper proposes a generalized Hybrid Real-coded Quantum Evolutionary Algorithm (HRCQEA) for optimizing complex functions as well as combinatorial optimization. The main idea of HRCQEA is to devise a new technique for mutation and crossover operators. Using the evolutionary equation of PSO a Single-Multiple gene Mutation (SMM) is designed and the concept of Arithmetic Crossover (AC) is used in the new Crossover operator. In HRCQEA, each triploid chromosome represents a particle and the position of the particle is updated using SMM and Quantum Rotation Gate (QRG), which can make the balance between exploration and exploitation. Crossover is employed to expand the search space, Hill Climbing Selection (HCS) and elitism help to accelerate the convergence speed. Simulation results on Knapsack Problem and five benchmark complex functions with high dimension show that HRCQEA performs better in terms of ability to discover the global optimum and convergence speed.
Khorsand, A.-R. and Akbarzadeh-T, M.-R. 2005 Quantum gate optimization in a meta-level genetic quantum algorithm   abstract PDF Google
[!!!][tuning]
Abstract: Genetic quantum algorithms (GQA) are population based evolutionary algorithms that imitate quantum physics by introducing quantum bits for a basic probabilistic genotypic representation and hence better population diversity, and quantum gates for evolving the population of solutions. While quantum inspired gates play an important role in the evolutionary process, there is no specific method for their design, i.e. they are mostly developed through ad hoc procedures. Here, we propose a multi-objective meta-level GQA in order to determine parameters of QG which is applicable for a wide variety of optimization problems. Specifically, a two-layer GQA is constructed, in which the lower layer's objective is to optimize the four junction types: Dejong, Peak, Easoms, and Griewank. And the higher layer's objective is to determine optimal parameters for QG that helps the proposed algorithm find best solutions. GQA optimization performance, with optimized parameter of QG is compared with GA on several benchmark problems and the superiority of the proposed method is statistically shown.
Toosi, T.K. and Mashhadi, H.R. 2005 A Modified Genetic Algorithm Comparable to Quantum GA   abstract PDF Google
Abstract: Recently, researchers proposed an evolutionary algorithm, QGA based on quantum concepts .It have shown that QGA's convergence and global search ability are superior to conventional GA's. This paper proposed a modified genetic algorithm that uses genetic operators effectively to have more advantages than QGA without employing any quantum feature.
Riebe, Mark and H{\"a}ffner, H and Roos, CF and H{\"a}nsel, W and Benhelm, J and Lancaster, GPT and K{\"o}rber, TW and Becher, C and Schmidt-Kaler, F and James, DFV and others 2004 Deterministic quantum teleportation with atoms Google
Skolicki, Zbigniew and De Jong, Kenneth 2004 Improving evolutionary algorithms with multi-representation island models Google
Hu, Jianjun and Goodman, Erik 2004 Robust and efficient genetic algorithms with hierarchical niching and a sustainable evolutionary computation model Google
Tu, Zhenguo and Lu, Yong 2004 A robust stochastic genetic algorithm (StGA) for global numerical optimization Google
Hansen, Nikolaus and Kern, Stefan 2004 Evaluating the CMA evolution strategy on multimodal test functions Google
Mika Hirvensalo 2004 Algorytmy kwantowe Google
Liang Ming and Yu-Ping Wang and Yu-ming Cheung 2004 A new schema theorem for uniform crossover based on ternary representation   abstract PDF Google
[other][theoretical]
Abstract: Crossover is a fundamental operator in genetic algorithms, through which not only an existing schema may be either eliminated or survived, but also a new schema is constructed via other existing schemata. Unfortunately the traditional schema theorem (Holland, J.H., 1975) does not take into account the positive effects of a schema construction through crossover operation. Recently, some works have been done by considering the schema construction, but they could not well characterize the evolution of a schema via crossover. We propose a new representation of a schema, called ternary representation, through which the survival and construction probabilities of a schema are given out. Eventually, we present a new improved schema theorem that considers both schema survival and construction in a uniform crossover.
Malossini, A. and Blanzieri, E. and Calarco, T. 2004 QGA, A Quantum Genetic Algorithm   abstract PDF Google
[QB]
Abstract: The complexity of the selection procedure of a genetic algorithm that requires reordering, if we restrict the class of the possible fitness functions to non-local or time-dependent fitness functions, is O(N logN) where N is the size of the population. Quantum Genetic Algorithm (QGA) exploits the power of quantum computation in order to speed up genetic procedures. In QGA the classical fitness evaluation and selection procedures are replaced by a single quantum procedure. QGA outperforms a typical classical genetic algorithm. We show that the complexity of our QGA is O(1) in terms of number of oracle calls in the selection procedure. Such theoretical results are confirmed by the simulations of the algorithm.
Lothar M. Schmitt 2004 Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling   abstract PDF Google
[other][theoretical]
Abstract: We present a theoretical framework for an asymptotically converging, scaled genetic algorithm which uses an arbitrary-size alphabet and common scaled genetic operators. The alphabet can be interpreted as a set of equidistant real numbers and multiple-spot mutation performs a scalable compromise between pure random search and neighborhood-based change on the alphabet level. We discuss several versions of the crossover operator and their interplay with mutation. In particular, we consider uniform crossover and gene-lottery crossover which does not commute with mutation. The Vose-Liepins version of mutation-crossover is also integrated in our approach. In order to achieve convergence to global optima, the mutation rate and the crossover rate have to be annealed to zero in proper fashion, and unbounded, power-law scaled proportional fitness selection is used with logarithmic growth in the exponent. Our analysis shows that using certain types of crossover operators and large population size allows for particularly slow annealing schedules for the crossover rate. In our discussion, we focus on the following three major aspects based upon contraction properties of the mutation and fitness selection operators: (i) the drive towards uniform populations in a genetic algorithm using standard operations, (ii) weak ergodicity of the inhomogeneous Markov chain describing the probabilistic model for the scaled algorithm, (iii) convergence to globally optimal solutions. In particular, we remove two restrictions imposed in Theorem 8.6 and Remark 8.7 of (Theoret. Comput. Sci. 259 (2001) 1) where a similar type of algorithm is considered as described here: mutation need not commute with crossover and the fitness function (which may come from a coevolutionary single species setting) need not have a single maximum.
André V. Abs da Cruz and Carlos R. Hall Barbosa and Marco Aurélio Cavalcanti Pacheco and Marley B. R. Vellasco 2004 Quantum-Inspired Evolutionary Algorithms and Its Application to Numerical Optimization Problems.   abstract PDF Google
[real][representation][operators][!!!]
Abstract: This work proposes a new kind of evolutionary algorithm inspired in the principles of quantum computing. This algorithm is an extension of a proposed model for combinatorial optimization problems which uses a binary representation for the chromosome. This extension uses probability distributions for each free variable of the problem, in order to simulate the superposition of solutions, which is intrinsic in the quantum computing methodology. A set of mathematical operations is used as implicit genetic operators over those probability distributions. The efficiency and the applicability of the algorithm are demonstrated through experimental results using the F6 function.
The first suggestion and mention of quantum real coding
Hui, C. and Jiashu, Z. and Chao, Z. 2004 Chaos updating rotated gates quantum-inspired genetic algorithm   abstract PDF Google
[operators]
Abstract: From the recent research on combinational optimization of the knapsack problem, the quantum-inspired genetic algorithm (QGA) was proved to be better than conventional genetic algorithms. To accelerate the convergence speed of the QGA, the paper proposes research issues on QGA such as Q-gate. A novel Q-gate updating algorithm called chaos updating rotated gates quantum-inspired genetic algorithm (CQGA) is proposed. An analysis of the two main characters of quantum computing and chaos is also presented. This algorithm demonstrates the convergence of the quantum genetic algorithm (QGA). Several experiments are carried out on a class of numerical and combinatorial optimization problems. The results show the updated QGA makes QGA more powerful than the previous QGA in convergence speed.
A new method of rotation in the qubit state space -- "chaos updating rotated gates
Giraldi, G.A. and Portugal, R. and Thess, R.N. 2004 Genetic algorithms and quantum computation   abstract PDF Google
[!!!][survey]
Abstract: Recently, researchers have applied genetic algorithms (GAs) to address some problems in quantum computation. Also, there has been some works in the designing of genetic algorithms based on quantum theoretical concepts and techniques. The so called Quantum Evolutionary Programming has two major sub-areas: Quantum Inspired Genetic Algorithms (QIGAs) and Quantum Genetic Algorithms (QGAs). The former adopts qubit chromosomes as representations and employs quantum gates for the search of the best solution. The later tries to solve a key question in this field: what GAs will look like as an implementation on quantum hardware? As we shall see, there is not a complete answer for this question. An important point for QGAs is to build a quantum algorithm that takes advantage of both the GA and quantum computing parallelism as well as true randomness provided by quantum computers. In the first part of this paper we present a survey of the main works in GAs plus quantum computing including also our works in this area. Henceforth, we review some basic concepts in quantum computation and GAs and emphasize their inherent parallelism. Next, we review the application of GAs for learning quantum operators and circuit design. Then, quantum evolutionary programming is considered. Finally, we present our current research in this field and some perspectives.
a survey from 2004 on quantum and quantum-inspired evolutionary algorithms
Han, K.H. and Kim, J.H. 2004 Quantum-inspired evolutionary algorithms with a new termination criterion, H${}_\epsilon$ Gate, and two-phase scheme   abstract PDF Google
[!!!][operators]
Abstract: 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ε 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.
proposal of a new stop condition, modified rotation gate
Jun-Su Jang and Kuk-Hyun Han and Jong-Hwan Kim 2004 Face detection using quantum-inspired evolutionary algorithm   abstract PDF Google
[app]
Abstract: This work proposes a new face detection system using quantum-inspired evolutionary algorithm (QEA). The proposed detection system is based on elliptical blobs and principal component analysis (PCA). The elliptical blobs in the directional image are used to find the face candidate regions, and then PCA and QEA are employed to verify faces. Although PCA related algorithms have shown outstanding performance, there still exist some problems such as optimal decision boundary or learning capabilities. By PCA, we can obtain the optimal basis but they may not be the optimal ones for discriminating faces from non-faces. Moreover, a threshold value should be selected properly considering the success rate and false alarm rate. To solve these problems, QEA is employed to find out the optimal decision boundary under the predetermined threshold value which distinguishes between face images and non-face images. The proposed system provides learning capability by reconstructing the training database, which means that system performance can be improved as failure trials occur.
Talbi, H. and Draa, A. and Batouche, M. and Abdelkader, U.S.I.E. and Constantine, A. 2004 A new quantum-inspired genetic algorithm for solving the travelling salesman problem   abstract PDF Google
[app][TSP]
Abstract: This paper presents a new algorithm for solving the travelling salesman problem (TSP). The TSP is one of the most known combinatorial optimisation problems. It is about finding the shortest Hamiltonian cycle relating N cities. The algorithm is inspired from both genetic algorithms and quantum computing fields. It extends the standard genetic algorithms by combining them to some concepts and principles provided from quantum computing field such as quantum bit, states superposition and interference. The obtained results from the application of the proposed algorithm on some instances of TSP are significantly better than those provided by standard genetic algorithms.
Talbi, H. and Batouche, M. and Draa, A. 2004 A quantum-inspired genetic algorithm for multi-source affine image registration   abstract Google
[app]
Abstract: In this paper we propose a new algorithm for image registration which is a key stage in almost every computer vision system. The algorithm is inspired from both genetic algorithms and quantum computing fields and uses the mutual information as a measure of similarity. The proposed approach is based on some concepts and principles of quantum computing such as quantum bit and states superposition. So, the definitions of the basic genetic operations have been adapted to use the new concepts. The evaluation of each solution is performed by the computation of mutual information between the reference image and the resulting image. The process aims to maximize this mutual information in order to get the best affine transformation parameters which allow the alignment of the two images.
Li, Y. and Zhang, Y. and Zhao, R. and Jiao, L. 2004 The immune quantum-inspired evolutionary algorithm   abstract PDF Google
Abstract: By leading immune concepts and methods into quantum-inspired evolutionary algorithm (QEA), a novel algorithm, the immune quantum-inspired evolutionary algorithm (IQEA), is proposed. On condition of preserving QEA's advantages, IQEA utilizes some characteristics and knowledge in the pending problems for restraining the repeat and ineffective operations during evolution, so as to improve the algorithm efficiency. The experimental results of the knapsack problem show that the performance of IQEA is superior to the conventional EA (CEA), the immune EA (IEA) and QEA.
Kusztelak, G. and Rudnicki, M. and Wiak, S. 2004 Propagation of Building Blocks in SGA and MPGA   abstract PDF Google
[theoretical][other]
Abstract: The goal of this paper is to demonstrate the rate at which building blocks evolve in time during run of GA. We compare the building block propagation rate for the simple genetic algorithm (SGA) with the building block propagation rate for the migration (island) genetic algorithm (MPGA). The results are checked against the lower bound given by Hollandrsquos schema theorem. Using genetic programming, we made symbolic regression on the number of individuals matching given schema versus generation number. As a result, a new expression describing the propagation rate was found, and its correctness was confirmed in all cases considered in the paper.
Arabas, J 2004 Wyk{\l}ady z algorytm{\'o}w ewolucyjnych Google
Yang, H. and Li, M. 2003 Form invariance of schema and exact schema theorem PDF Google
[other][theoretical]
Bin, L. and Junan, Y. and Zhenquan, Z. 2003 GAQPR and its application in discovering frequent structures in time series   abstract PDF Google
[!!!][app][operators]
Abstract: A new genetic algorithm based on the quantum probability representation (GAQPR) is proposed, in which each individual evolves independently; a new crossover operator is designed to integrate searching processes of multiple individuals into a more efficient global searching process; a new mutation operator is also proposed. The algorithm is used to discover frequent structures in time series, experiment results show that the GAQPR is efficient for the complex multi-peak searching problem.
Yang Haijun and Li Minqiang and Kou Jisong 2003 Exact schema theorem based on the space of schema   abstract PDF Google
[other][theoretical]
Abstract: Holland's schema theorem has several limitations. The first is that it is not an exact equation, and the second is that it only considers schemata as individuals in GA's population. This paper will try to make some novel extensions to overcome these limitations. In the paper, we formulate an exact schema equation based on schema space, and our results are similar to the conclusions of Stephens et al., but they have novel expressions and a larger degree of coarse graining.
Kuk-Hyun Han 2003 Quantum-inspired Evolutionary Algorithm   abstract PDF Google
[!!!][knapsack]
Abstract: This thesis proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, the evaluation function, and the population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. A Q-gate is introduced as a variation operator that drives the individuals toward better solutions. The termination condition of QEA is designed by defining a new measure on the convergence of Q-bit individuals. To analyze the characteristics of QEA, the theoretical analysis of the QEA algorithm as well as the effects of changing parameters of QEA are examined. In particular, some issues of QEA such as the analysis of changing the initial values of Q-bits, a novel variation operatorH# gate, and a two-phase QEA (TPQEA) scheme are addressed to improve the performance of QEA. To demonstrate the effectiveness and applicability of QEA, experiments are carried out on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that QEA performs well, even with a small number of population, without premature convergence as compared to the conventional genetic algorithms. Moreover, through the experiments on numerical optimization problems, the superior performance of QEA is also verified. These results show that QEA can be applied to a class of numerical as well as combinatorial optimization problems.
Han, K.H. and Kim, J.H. 2003 On setting the parameters of quantum-inspired evolutionary algorithm for practical applications   abstract PDF Google
[theoretical][!!!]
Abstract: In this paper, some guidelines for setting the parameters of quantum-inspired evolutionary algorithm (QEA) are presented. QEA is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. However, QEA is not a quantum algorithm, but a novel evolutionary algorithm. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, the evaluation function, and the population dynamics. From recent research on the knapsack problem, the results of QEA are better than those of CGA (conventional GA). Although the performance of QEA is excellent, there is relatively little or no research on the effects of different settings for its parameters. This paper describes some guidelines for setting these parameters. The guidelines are drawn up based on extensive experiments carried out for a class of combinatorial and numerical optimization problems. Through the guidelines, the performance of QEA can be maximized.
Kuk-Hyun Han and Jong-Hwan Kim 2003 On Setting the Parameters of QEA for Practical Applications: Some Guidelines Based on Empirical Evidence   abstract PDF Google
[theoretical][!!!]
Abstract: In this paper, some guidelines for setting the parameters of quantum-inspired evolutionary algorithm (QEA) are presented. Although the performance of QEA is excellent, there is relatively little or no research on the effects of different settings for its parameters. The guidelines are drawn up based on extensive experiments.
Jang, J.S. and Han, K.H. and Kim, J.H. 2003 Quantum-inspired evolutionary algorithm-based face verification   abstract PDF Google
[app]
Abstract: Face verification is considered to be the main part of the face detection system. To detect human faces in images, face candidates are extracted and face verification is performed. This paper proposes a new face verification algorithm using Quantum-inspired Evolutionary Algorithm (QEA). The proposed verification system is based on Principal Components Analysis (PCA). Although PCA related algorithms have shown outstanding performance, the problem lies in the selection of eigenvectors. They may not be the optimal ones for representing the face features. Moreover, a threshold value should be selected properly considering the verification rate and false alarm rate. To solve these problems, QEA is employed to find out the optimal distance measure under the predetermined threshold value which distinguishes between face images and non-face images. The proposed verification system is tested on the AR face database and the results are compared with the previous works to show the improvement in performance.
Kim, K.H. and Hwang, J.Y. and Han, K.H. and Kim, J.H. and Park, K.H. 2003 A quantum-inspired evolutionary computing algorithm for disk allocation method   abstract PDF Google
[app]
Abstract: Based on a Quantum-inspired Evolutionary Algorithm (QEA), a new disk allocation method is proposed for distributing buckets of a binary cartesian product file among unrestricted number of disks to maximize concurrent disk I/O. It manages the probability distribution matrix to represent the qualities of the genes. Determining the excellent genes quickly makes the proposed method have faster convergence than DAGA. It gives better solutions and 3.2-11.3 times faster convergence than DAGA. (author abst.)
Zbigniew Michalewicz 2003 Algorytmy genetyczne + struktury danych = programy ewolucyjne PDF Google
[other]
Zhang, G. and Jin, W. and Li, N. 2003 An improved quantum genetic algorithm and its application   abstract Google
[operators]
Abstract: An improved quantum genetic algorithm (IQGA) is proposed in this paper. In IQGA, the strategies of updating quantum gate by using the best solution and introducing population catastrope are used. The typical function tests show convergent speed of IQGA is faster than that of quantum genetic algorithm(QGA) and other several GAs, and IQGA can also make up for prematureness of QGA. The simulations of FIR filter design demonstrate IQGA is superior to QGA, the methods in reference [5] and traditional method.
population catastrophe operation
Reeves, C.R. and Rowe, J.E. 2003 Genetic algorithms: principles and perspectives: a guide to GA theory PDF Google
[theoretical][other][!!!]
Theory of classical SGAA - schemata, critics, Walsh transforms, deceptive problems, No Free Lunches, Markov chains and other approaches to theoretical analysis
Shuyuan Yang and Licheng Jiao 2003 The quantum evolutionary programming   abstract PDF Google
[operators]
Abstract: Evolutionary programming (EP) is an efficient algorithm in solving optimization problems, but the criterion EP is of torpid convergence. In this paper, a novel kind of algorithm, the quantum evolutionary programming (QEP), is proposed based on the combination of quantum theory with evolutionary theory. It is a kind of evolutionary programming with the form of quantum chromosome, whose core lies on the concept and principles of quantum computing, such as quantum bit and superposition of states. Using quantum mutation, we can make full use of the information of the current best individual to perform the next search, so QEP has rapid convergence and global searching capacity. Some simulation experiments are also given to prove its superiority over its counterpart.
quantum mutation
Streichert, Felix and Stein, Gunnar and Ulmer, Holger and Zell, Andreas 2003 A clustering based niching method for evolutionary algorithms Google
Han, K.H. and Kim, J.H. 2002 Quantum-inspired evolutionary algorithm for a class of combinatorial optimization   abstract PDF Google
[!!!][knapsack]
Abstract: This paper proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, evaluation function, and population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. A Q-gate is introduced as a variation operator to drive the individuals toward better solutions. To demonstrate its effectiveness and applicability, experiments were carried out on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that QEA performs well, even with a small population, without premature convergence as compared to the conventional genetic algorithm.
Han, K.H. and Kim, J.H. 2002 Introduction of Quantum-Inspired Evolutionary Algorithm   abstract PDF Google
[!!!]
Abstract: This paper introduces quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, the evaluation function and the population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits.
Eberhart, R.C. and Shi, Y. and Kennedy, J. 2001 Swarm intelligence Google
K.H. Han and J.H. Kim 2001 Analysis of Quantum-Inspired Evolutionary Algorithm   abstract PDF Google
[theoretical][!!!][knapsack]
Abstract: This paper extends the author's previous works on quantum-inspired evolutionary algorithm (QEA). It investigates the characteristics of QEA which is based on the concept and principles of quantum computing such as quantum bit and linear superposition of states. QEA has many advantages such as automatic balance ability between global search and local search, inclusion of individual's past history, having fewer individuals without degrading performance, less computation time, and clearer termination-condition. The experimental results on the knapsack problem are presented to verify these characteristics of QEA.
Lothar M. Schmitt 2001 Theory of genetic algorithms   abstract PDF Google
[theoretical][other]
Abstract: (i) We investigate spectral and geometric properties of the mutation-crossover operator in a genetic algorithm with general-size alphabet. By computing spectral estimates, we show how the crossover operator enhances the averaging procedure of the mutation operator in the random generator phase of the genetic algorithm. By mapping our model to the multi-set model often investigated in the literature, we compute corresponding spectral estimates for mutation-crossover in the multi-set model. (ii) Various types of unscaled or scaled fitness selection mechanisms are considered such as proportional fitness selection, rank selection, and tournament fitness selection. We allow fitness selection mechanisms where the fitness of an individual or creature depends upon the population it resides in. We investigate contracting properties of these fitness selection mechanisms and combine them with the crossover operator to obtain a model for genetic drift. This has applications to the study of genetic algorithms with zero or extremely low mutation rate. (iii) We discuss a variety of convergent simulated-annealing-type algorithms with mutation-crossover as generator matrix. (iv) The theory includes proof of strong ergodicity for various types of scaled genetic algorithms using common fitness selection methods. If the mutation rate converges to a positive value, and the other operators of the genetic algorithm converge, then the limit probability distribution over populations is fully positive at uniform populations whose members have not necessarily optimal fitness. (v) In what follows, suppose the mutation rate converges to zero sufficiently slow to assure weak ergodicity of the inhomogeneous Markov chain describing the genetic algorithm, unbounded power-law scaling for the fitness selection is used, mutation and crossover commute, and the fitness function is injective which is a minor restriction in regard to function optimization. (va) If a certain integrable convergence condition is satisfied such that the selection pressure increases fast, then there is essentially no other restriction on the crossover operation, and the algorithm asymptotically behaves as the following take-the-best search algorithm: (1) mutate in every step with rate decreasing to zero, and (2) map any population to the uniform population with the best creature. The take-the-best search algorithm is investigated, and its convergence is shown. Depending upon population-size, the take-the-best search algorithm does or does not necessarily converge to the optimal solution. (vb) If population size is larger than length of genome, and a certain logarithmic convergence condition is satisfied such that the selection pressure increases slowly but sufficiently fast, then the algorithm asymptotically converges to the optimal solution.
Han, K.H. and Park, K.H. and Lee, C.H. and Kim, J.H. 2001 Parallel quantum-inspired genetic algorithm for combinatorial optimization problem   abstract PDF Google
[parallel][knapsack]
Abstract: This paper proposes a new parallel evolutionary algorithm called parallel quantum-inspired genetic algorithm (PQGA). Quantum-inspired genetic algorithm (QGA) 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 the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. QGA is suitable for parallel structures because of rapid convergence and good global search capability. That is, QGA is able to possess the two characteristics of exploration and exploitation simultaneously. The effectiveness and the applicability of PQGA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that PQGA is superior to QGA as well as other conventional genetic algorithms
Poli, R. 2001 Exact schema theory for genetic programming and variable-length genetic algorithms with one-point crossover PDF Google
[other][theoretical]
Hoos, H and Stiitzle, Thomas 2000 SATLlB: An Online Resource for Research on SAT Google
Nielsen, Michael A. and Chuang, Isaac L. 2000 Quantum Computation and Quantum Information   abstract Google
[other]
Abstract: In this first comprehensive introduction to the main ideas and techniques of quantum computation and information, Michael Nielsen and Isaac Chuang ask the question: What are the ultimate physical limits to computation and communication? They detail such remarkable effects as fast quantum algorithms, quantum teleportation, quantum cryptography and quantum error correction. A wealth of accompanying figures and exercises illustrate and develop the material in more depth. They describe what a quantum computer is, how it can be used to solve problems faster than familiar "classical" computers, and the real-world implementation of quantum computers. Their book concludes with an explanation of how quantum states can be used to perform remarkable feats of communication, and of how it is possible to protect quantum states against the effects of noise.
Poli, R. 2000 Why the schema theorem is correct also in the presence of stochastic effects   abstract PDF Google
[other][theoretical]
Abstract: J. Holland's (1975) schema theorem has been criticised by D.B. Fogel and A. Ghozeil (1997, 1998, 1999) for not being able to correctly estimate the expected proportion of a schema in the population when fitness-proportionate selection is used in the presence of noise or other stochastic effects. This is incorrect for two reasons. Firstly, the theorem in its original form is not applicable to this case. If the quantities involved in schema theorems are random variables, the theorems must be interpreted as conditional statements. Secondly, the conditional versions of Holland and other researchers' schema theorems are indeed very useful to model the sampling of schemata in the presence of stochasticity. In this paper, I show how one can calculate the correct expected proportion of a schema in the presence of stochastic effects when only selection is present, using a conditional interpretation of Holland's schema theorem. In addition, I generalise this result (again using schema theorems) to the case in which crossover, mutation and selection-with-replacement are used. This can be considered as an exact schema theorem that is applicable both in the presence and in the absence of stochastic effects
Han, K.H. and Kim, J.H. 2000 Genetic quantum algorithm and its application to combinatorial optimization problem   abstract PDF Google
[!!!][knapsack]
Abstract: 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
publikacja, która zapoczątkowała zainteresowanie tym obszarem
Eremeev, A. 2000 Modeling and analysis of genetic algorithm with tournament selection   abstract PDF Google
[other][theoretical][!!!]
Abstract: In this paper we propose a mathematical model of a simplified version of genetic algorithm (GA) based on mutation and tournament selection and obtain upper and lower bounds on expected proportion of the individuals with the fitness above certain threshold. As an illustration we consider a GA optimizing the bit-counting function and a GA for the vertex cover problem on graphs of a special structure. The theoretical estimates obtained are compared with experimental results.
theoretical, mathematical model of a simplified genetic algorithm
Novaes, S.F. 2000 Standard model: An introduction Google
Whitley, Darrell and Rana, Soraya and Heckendorn, Robert B 1999 The island model genetic algorithm: On separability, population size and convergence Google
Poli, Riccardo 1999 Schema theorems without expectations Google
Naudts, Bart and Verschoren, Alain and others 1999 Epistasis and deceptivity Google
Yao, Xin and Liu, Yong and Lin, Guangming 1999 Evolutionary programming made faster Google
Stephens, C. and Waelbroeck, H. 1999 Schemata evolution and building blocks PDF Google
[other][theoretical]
Eiben, A. E. and Rudolph, G. 1999 Theory of evolutionary algorithms: a bird's eye view   abstract PDF Google
[theoretical][other][!!!][survey]
Abstract: In this paper we consider the most important questions, research topics and technical tools used in various branches of evolutionary algorithms. The road map we give is to facilitate the readers' orientation in evolutionary computation theory. In the meanwhile, this survey provides key references for further study and evidence that the field of evolutionary computation is maturing rapidly, having many important results and even more interesting challenges.
Survey of various theoretical analyses of classical GA -- from 1999
Vose, M.D. 1999 The simple genetic algorithm: foundations and theory PDF Google
[theoretical][other][!!!]
Fundamental publication on theoretical analysis of SGA
Matsumoto, Makoto and Nishimura, Takuji 1998 Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator Google
Boschi, Danilo and Branca, Salvatore and De Martini, Francesco and Hardy, Lucien and Popescu, Sandu 1998 Experimental realization of teleporting an unknown pure quantum state via dual classical and Einstein-Podolsky-Rosen channels Google
Pollack, Jordan B and Blair, Alan D 1998 Co-evolution in the successful learning of backgammon strategy Google
Angeline, Peter J 1998 Evolutionary optimization versus particle swarm optimization: Philosophy and performance differences Google
Goldberg, D.E. 1998 Algorytmy genetyczne i ich zastosowania Google
[other]
Vose, Michael D. and Wright, Alden H. 1998 The simple genetic algorithm and the walsh transform: Part I, theory   abstract PDF Google
[other][theoretical]
Abstract: This paper is the first part of a two-part series. It proves a number of direct relationships between the Fourier transform and the simple genetic algorithm. (For a binary representation, the Walsh transform is the Fourier transform.) The results are of a theoretical nature and are based on the analysis of mutation and crossover. The Fourier transform of the mixing matrix is shown to be sparse. An explicit formula is given for the spectrum of the differential of the mixing transformation. By using the Fourier representation and the fast Fourier transform, one generation of the infinite population simple genetic algorithm can be computed in time O(cl log2 3), where c is arity of the alphabet and l is the string length. This is in contrast to the time of O(c3l) for the algorithm as represented in the standard basis. There are two orthogonal decompositions of population space that are invariant under mixing. The sequel to this paper will apply the basic theoretical results obtained here to inverse problems and asymptotic behavior.
Lothar M. Schmitt and Chrystopher L. Nehaniv and Robert H. Fujii 1998 Linear analysis of genetic algorithms   abstract PDF Google
[other][theoretical]
Abstract: We represent simple and fitness-scaled genetic algorithms by Markov chains on probability distributions over the set of all possible populations of a fixed finite size. Analysis of this formulation yields new insight into the geometric properties of the three phase mutation, crossover, and fitness selection of a genetic algorithm by representing them as stochastic matrices acting on the state space. This indicates new methods using mutation and crossover as the proposal scheme for simulated annealing. We show by explicit estimates that for small mutation rates a genetic algorithm asymptotically spends most of its time in uniform populations regardless of crossover rate. The simple genetic algorithm converges in the following sense: there exists a fully positive limit probability distribution over populations. This distribution is independent of the choice of initial population. We establish strong ergodicity of the underlying inhomogeneous Markov chain for genetic algorithms that use any of a large class of fitness scaling methods including linear fitness scaling, sigma-truncation, and power law scaling. Our analysis even allows for variation in mutation and crossover rates according to a pre-determined schedule, where the mutation rate stays bounded away from zero. We show that the limit probability distribution of such a process is fully positive at all populations of uniform fitness. Consequently, genetic algorithms that use the above fitness scalings do not converge to a population containing only optimal members. This answers a question of G. Rudolph (IEEE Trans. on Neural Networks 5 (1994) 96-101). For a large set of fitness scaling methods, the limit distribution depends on the pre-order induced by the fitness function f, i.e. c [greater-or-equal, slanted] c' |-> f(c) [greater-or-equal, slanted] f(c') on possible creatures c and c', and not on the particular values assumed by the fitness function.
Vose, Michael D. and Wright, Alden H. 1998 The simple genetic algorithm and the walsh transform: Part II, the inverse   abstract PDF Google
[other][theoretical]
Abstract: This paper continues the development, begun in Part I, of the relationship between the simple genetic algorithm and the Walsh transform. The mixing scheme (comprised of crossover and mutation) is essentially "triangularized" when expressed in terms of the Walsh basis. This leads to a formulation of the inverse of the expected next generation operator. The fixed points of the mixing scheme are also determined, and a formula is obtained giving the fixed point corresponding to any starting population. Geiringer's theorem follows from these results in the special case corresponding to zero mutation.
Hadad, Ben S and Eick, Christoph F 1997 Supporting polyploidy in genetic algorithms using dominance vectors Google
Obuchowicz, A 1997 The evolutionary search with soft selection and deterioration of the objective function Google
Penrose, R. and Cartwright, N. and Hawking, S.W. and Shimony, A. 1997 The Large, the Small, and the Human Mind Google
Yao, X. and Liu, Y. and Lin, G.M. 1997 Quantum gate optimization in a meta-level genetic quantum algorithm Google
Wolpert, D.H. and Macready, W.G. 1997 No free lunch theorems for optimization   abstract PDF Google
[other]
Abstract: A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving. A number of "no free lunch" (NFL) theorems are presented which establish that for any algorithm, any elevated performance over one class of problems is offset by performance over another class. These theorems result in a geometric interpretation of what it means for an algorithm to be well suited to an optimization problem. Applications of the NFL theorems to information-theoretic aspects of optimization and benchmark measures of performance are also presented. Other issues addressed include time-varying optimization problems and a priori "head-to-head" minimax distinctions between optimization algorithms, distinctions that result despite the NFL theorems' enforcing of a type of uniformity over all algorithms
Chaiyaratana, N. and Zalzala, AMS 1997 Recent developments in evolutionary and genetic algorithms: theory and applications   abstract PDF Google
[other][app][survey][theoretical]
Abstract: This paper provides a review on current developments in genetic algorithms. The discussion includes theoretical aspects of genetic algorithms and genetic algorithm applications. Theoretical topics under review include genetic algorithm techniques, genetic operator technique, niching techniques, genetic drift, method of benchmarking genetic algorithm performances, measurement of difficulty level of a test-bed function, population genetics and developmental mechanism in genetic algorithms. Examples of genetic algorithm application in this review are pattern recognition, robotics, artificial life, expert system, electronic circuit design, cellular automata, and biological applications. While the paper covers many works on the theory and application of genetic algorithms, not much details are reported on genetic programming, parallel genetic algorithms, in addition to more advanced techniques e.g. micro-genetic algorithms and multiobjective optimisation
review on developments in genetic algorithms for late 1990s, methods of benchmarking, theoretical approaches
Hansen, N. and Ostermeier, A. 1996 Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation Google
Petrowski, Alain 1996 A clearing procedure as a niching method for genetic algorithms Google
Richard P. Feynman 1996 Wykłady o obliczeniach Google
Narayanan, A. and Moore, M. 1996 Quantum-inspired genetic algorithms   abstract PDF Google
[!!!][TSP]
Abstract: A novel evolutionary computing method-quantum inspired genetic algorithms-is introduced, where concepts and principles of quantum mechanics are used to inform and inspire more efficient evolutionary computing methods. The basic terminology of quantum mechanics is introduced before a comparison is made between a classical genetic algorithm and a quantum inspired method for the travelling salesperson problem. It is informally shown that the quantum inspired genetic algorithm performs better than the classical counterpart for a small domain. The paper concludes with some speculative comments concerning the relationship between quantum inspired genetic algorithms and various complexity classes
The first proposal ever of quantum-inspired genetic algorithm
Grover, Lov K. 1996 A fast quantum mechanical algorithm for database search Google
B\"{a}ck, Thomas 1996 Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms PDF Google
[!!!][theoretical][other]
A survey of various Evolutionary Algorithms (GA,ES,EP). Theoretical foundations, FORMAL MODEL OF EA (8 tuple)
Dorigo, Marco and Maniezzo, Vittorio and Colorni, Alberto 1996 Ant system: optimization by a colony of cooperating agents Google
Michalewicz, Zbigniew and Nazhiyath, Girish 1995 Genocop III: A co-evolutionary algorithm for numerical optimization problems with nonlinear constraints Google
Moore, M. and Narayanan, A. 1995 Quantum-inspired computing Google
Menneer, T. and Narayanan, A. 1995 Quantum-inspired neural networks Google
Kennedy, J. and Eberhart, R. 1995 Particle swarm optimization Google
[other]
Peter W.~Shor 1994 Algorithms for Quantum Computation: Discrete Log and Factoring Google
Vaidman, Lev 1994 Teleportation of quantum states Google
Darrell Whitley 1994 A genetic algorithm tutorial   abstract PDF Google
[other][theoretical]
Abstract: This tutorial covers the canonical genetic algorithm as well as more experimental forms of genetic algorithms, including parallel island models and parallel cellular genetic algorithms. The tutorial also illustrates genetic search by hyperplane sampling. The theoretical foundations of genetic algorithms are reviewed, include the schema theorem as well as recently developed exact models of the canonical genetic algorithm.
Comprehensive study on theoretical aspects of SGA: schemata, building blocks, linkage problem, O(n^3) approximation, Holland's theorem criticism
Penrose, R. 1994 Shadows of the mind: an approach to the missing science of consciousness Google
Rudolph, G. 1994 Convergence analysis of canonical genetic algorithms   abstract PDF Google
[theoretical][other]
Abstract: This paper analyzes the convergence properties of the canonical genetic algorithm (CGA) with mutation, crossover and proportional reproduction applied to static optimization problems. It is proved by means of homogeneous finite Markov chain analysis that a CGA will never converge to the global optimum regardless of the initialization, crossover, operator and objective function. But variants of CGA's that always maintain the best solution in the population, either before or after selection, are shown to converge to the global optimum due to the irreducibility property of the underlying original nonconvergent CGA. These results are discussed with respect to the schema theorem
convergence analysis of classical GA by means of Markov chains
Tadeusiewicz, Ryszard 1993 Sieci neuronowe Google
Brassard, Gilles and Cr{\'e}peau, Claude and Jozsa, Richard and Langlois, Denis 1993 A quantum bit commitment scheme provably unbreakable by both parties Google
Bennett, Charles H and Brassard, Gilles and Cr{\'e}peau, Claude and Jozsa, Richard and Peres, Asher and Wootters, William K 1993 Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels Google
De Jong, K.A. 1993 Genetic algorithms are NOT function optimizers   abstract PDF Google
[other]
Abstract: Genetic Algorithms (GAs) have received a great deal of attention regarding their potential as optimization techniques for complex functions. The level of interest and success in this area has led to a number of improvements to GA-based function optimizers and a good deal of progress in characterizing the kinds of functions that are easy/hard for GAs to optimize. With all this activity, there has been a natural tendency to equate GAs with function optimization. However, the motivating context of Holland's initial GA work was the design and implementation of robust adaptive systems. In this paper we argue that a proper understanding of GAs in this broader adaptive systems context is a necessary prerequisite for understanding their potential application to any problem domain. We then use these insights to better understand the strengths and limitations of GAs as function optimizers.
Yager, Ronald R and Zadeh, Lotfi A 1992 An introduction to fuzzy logic applications in intelligent systems Google
Koza, John R 1992 Genetic programming: on the programming of computers by means of natural selection (complex adaptive systems) Google
Colorni, A. and Dorigo, M. and Maniezzo, V. and others 1991 Distributed optimization by ant colonies Google
[other]
Koza, John R 1991 Evolution and co-evolution of computer programs to control independently-acting agents Google
Davidor, Yuval 1990 Epistasis variance: Suitability of a representation to genetic algorithms Google
Penrose, R. 1989 The Emperor's New Mind: Concerning Computers Google
Moscato, Pablo and others 1989 On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms Google
Goldberg, D.E. 1989 Genetic algorithms in search, optimization, and machine learning Google
[other]
Moravec, H. 1988 Mind children: The future of human and robot intelligence Google
Minsky, M. 1988 Society of mind Google
Metropolis, Nicholas 1987 The beginning of the Monte Carlo method Google
Grefenstette, John J 1986 Optimization of control parameters for genetic algorithms Google
Kirkpatrick, Scott and Gelatt, C Daniel and Vecchi, Mario P and others 1983 Optimization by simmulated annealing Google
Feynman, R.P. 1982 Simulating physics with computers Google
Bekenstein, Jacob D 1981 Universal upper bound on the entropy-to-energy ratio for bounded systems Google
Salam, A. 1980 Gauge unification of fundamental forces Google
Mercer, Robert E and Sampson, JR 1978 Adaptive search using a reproductive meta-plan Google
Buras, A.J. and Ellis, J. and Gaillard, M.K. and Nanopoulos, D.V. 1978 Aspects of the grand unification of strong, weak and electromagnetic interactions Google
De Jong, Kenneth Alan 1975 An analysis of the behavior of a class of genetic adaptive systems. PDF Google
[other]
Holland, J.H. 1975 Adaptation in natural and artificial system: an introduction with application to biology, control and artificial intelligence PDF Google
[other]
Rechenberg, Ingo 1973 Evolutionsstrategie--Optimierung technisher Systeme nach Prinzipien der biologischen Evolution Google
Weinberg, Roger 1970 Computer simulation of a living cell, University of Michigan Google
Broyden, CG 1967 Quasi-Newton methods and their application to function minimisation Google
Samuel, Arthur L 1967 Some studies in machine learning using the game of checkers. Google
Marvin Minsky 1967 Computation: Finite and Infinite Machines Google
Fogel, Lawrence J and Owens, Alvin J and Walsh, Michael J 1966 Artificial intelligence through simulated evolution Google
Zadeh, Lotfi A 1965 Fuzzy sets Google
Nelder, John A and Mead, Roger 1965 A simplex method for function minimization Google
Fletcher, Reeves and Reeves, Colin M 1964 Function minimization by conjugate gradients Google
Bell, John S and others 1964 On the einstein-podolsky-rosen paradox Google
Higgs, P.W. 1964 Broken symmetries and the masses of gauge bosons Google
Lucas, J.R. 1961 Minds, machines and G{\"o}del Google
Hooke, Robert and Jeeves, To A 1961 ``Direct Search''Solution of Numerical and Statistical Problems Google
Einstein, Albert and Podolsky, Boris and Rosen, Nathan 1935 Can quantum-mechanical description of physical reality be considered complete? Google
G{\"o}del, K. 1931 \"U}ber formal unentscheidbare S{\"a}tze der Principia Mathematica und verwandter Systeme I Google
Compton, A.H. 1923 A quantum theory of the scattering of X-rays by light elements Google
Einstein, A. 1905 \"U}ber einen die Erzeugung und Verwandlung des Lichtes betreffenden heuristischen Gesichtspunkt Google
Planck, M. 1901 On the law of distribution of energy in the normal spectrum Google
Pierre-Simon Laplace 1814 A Philosophical Essay on Probabilities Google


Total: 363 entries
Last update: 2021-01-24 22:03 CET