Homogeneous genetic algorithms

A new type of genetic algorithm (GA) is developed to mitigate one or both of the following two major difficulties that traditional GAs may suffer: (1) when the number of ‘active genes’ needs to be held constant or kept within some prescribed range, and (2) when the set of genes is much larger than the set of active genes of feasible solutions under consideration. These homogeneous GAs use (unordered) sets to represent ‘active genes’ in chromosomes rather than strings, and a correspondingly natural crossover operator is introduced. ‘Homogeneous’ refers to the fact that, in contrast to traditional GAs where pairs of genes that are ‘close’ have better chances of being preserved under crossover, there is no notion of proximity between pairs of genes. Examples are provided that will demonstrate superior performance of these new GAs for some typical problems in which these difficulties arise.     

Leveraging saving-based algorithms by master-slave genetic algorithms

Saving-based algorithms are commonly used as inner mechanisms of efficient heuristic construction procedures. We present a general mechanism for enhancing the effectiveness of such heuristics based on a two-level genetic algorithm. The higher-level algorithm searches in the space of possible merge lists which are then used by the lower-level saving-based algorithm to build the solution. We describe the general framework and we illustrate its application to three hard combinatorial problems. Experimental results on three hard combinatorial optimization problems show that the approach is very effective and it enables considerable enhancement of the performance of saving-based algorithms.     

Integrating adaptive mutations and family competition into genetic algorithms as function optimizer

 In this paper, we propose a robust evolutionary algorithm, called adaptive mutations genetic algorithm, for function optimization problems. Our main contribution is robustly optimizing problems whose number of variables from 2 to 200. In order to have a fair comparison, we propose the criteria for constructing a testing bed and for classifying these problems into different complexity degrees. The proposed approach, based on the family competition and multiple adaptive rules, successfully integrates the decreasing-based Gaussian mutation and self-adaptive Cauchy mutation to balance the exploitation and exploration. It is implemented and applied to widely used test functions and several nonseparable multimodal functions. Experimental results indicate that our approach is more robust than ten evolutionary algorithms.     

Putting risk management into practice

The authors use an SEI designed road map as a guide to discussing effective and ineffective risk management methods based on six years' experience with software intensive DoD programs. These programs followed the SEI approach of continuous and team risk management, selecting processes and methods that would best fit their work cultures     

Convergence of genetic algorithms

The mean convergence of various versions of a genetic algorithm are considered. A number of convergence statements are formulated and relevant estimates are obtained. A hypothesis concerning the form of these estimates under variation of the structure of a genetic algorithm is put forward. Roman Riviyanovich Sharapov. Born 1981. Graduated from the Faculty of Mechanics and Mathematics, Ural State University, in 2003. Presently, a postgraduate at the Department of Mathematical Economics at the same university. Scientific interests: genetic algorithms, neural networks, and financial mathematics. Aleksandr Vyacheslavovich Lapshin. Born 1980. Graduated from the Faculty of Mechanics and Mathematics, Ural State University, in 2003. Presently, a postgraduate at the Department of Mathematical Economics at the same university. Scientific interests: financial mathematics, genetic algorithms, and neural networks.     

遗传算法中的联结关系

进化计算领域的一个根本问题是哪些问题适合遗传算法求解,为此需要研究问题的结构对算法性能的影响.变量之间的联结关系是问题的本质属性,决定了遗传算法求解问题的难度.如果某个变量对函数值的影响非线性依赖于其他变量,则认为这些变量之间存的联结关系不,对遗传算法的联结关系这一理论问题进行了深入研究,给出了分析一般离散问题联结结构的理论基础,通过分析傅里叶系数与函数子空间的关系,提出了检测黑箱问题联结结构的确定性和随机性算法,通过试验分析说明了算法的正确性和有效性.     

Elitism-based compact genetic algorithms

This paper describes two elitism-based compact genetic algorithms (cGAs)-persistent elitist compact genetic algorithm (pe-cGA), and nonpersistent elitist compact genetic algorithm (ne-cGA). The aim is to design efficient cGAs by treating them as estimation of distribution algorithms (EDAs) for solving difficult optimization problems without compromising on memory and computation costs. The idea is to deal with issues connected with lack of memory by allowing a selection pressure that is high enough to offset the disruptive effect of uniform crossover. The pe-cGA finds a near optimal solution (i.e., a winner) that is maintained as long as other solutions generated from probability vectors are no better. The ne-cGA further improves the performance of the pe-cGA by avoiding strong elitism that may lead to premature convergence. It also maintains genetic diversity. This paper also proposes an analytic model for investigating convergence enhancement.     

Hierarchical distributed genetic algorithms

Genetic algorithm behavior is determined by the exploration/exploitation balance kept throughout the run. When this balance is disproportionate, the premature convergence problem will probably appear, causing a drop in the genetic algorithm's efficacy. One approach presented for dealing with this problem is the distributed genetic algorithm model. Its basic idea is to keep, in parallel, several subpopulations that are processed by genetic algorithms, with each one being independent from the others. Furthermore, a migration operator produces a chromosome exchange between the subpopulations. Making distinctions between the subpopulations of a distributed genetic algorithm by applying genetic algorithms with different configurations, we obtain the so-called heterogeneous distributed genetic algorithms. In this paper, we present a hierarchical model of distributed genetic algorithms in which a higher level distributed genetic algorithm joins different simple distributed genetic algorithms. Furthermore, with the union of the hierarchical structure presented and the idea of the heterogeneous distributed genetic algorithms, we propose a type of heterogeneous hierarchical distributed genetic algorithms, the hierarchical gradual distributed genetic algorithms. Experimental results show that the proposals consistently outperform equivalent sequential genetic algorithms and simple distributed genetic algorithms. ©1999 John Wiley & Sons, Inc.     

Where genetic algorithms excel

We analyze the performance of a genetic algorithm (GA) we call Culling, and a variety of other algorithms, on a problem we refer to as the Additive Search Problem (ASP). We show that the problem of learning the Ising perceptron is reducible to a noisy version of ASP. Noisy ASP is the first problem we are aware of where a genetic-type algorithm bests all known competitors. We generalize ASP to k-ASP to study whether GAs will achieve "implicit parallelism" in a problem with many more schemata. GAs fail to achieve this implicit parallelism, but we describe an algorithm we call Explicitly Parallel Search that succeeds. We also compute the optimal culling point for selective breeding, which turns out to be independent of the fitness function or the population distribution. We also analyze a mean field theoretic algorithm performing similarly to Culling on many problems. These results provide insight into when and how GAs can beat competing methods.     

General cardinality genetic algorithms

A complete generalization of the Vose genetic algorithm model from the binary to higher cardinality case is provided. Boolean AND and EXCLUSIVE-OR operators are replaced by multiplication and addition over rings of integers. Walsh matrices are generalized with finite Fourier transforms for higher cardinality usage. Comparison of results to the binary case are provided.     

On coevolutionary genetic algorithms

 The use of evolutionary computing techniques in coevolutionary/multi-agent systems is becoming increasingly popular. This paper presents simple models of the genetic algorithm in such systems, with the aim of examining the effects of different types of interdependence between individuals. Using the model it is shown that, for a fixed amount of interdependence between coevolving individuals, the existence of partner gene variance and the level at which fitness is applied can have significant effects, as does the evaluation partnering strategy used.     

A genetic engineering approach to genetic algorithms

We present an extension to the standard genetic algorithm (GA), which is based on concepts of genetic engineering. The motivation is to discover useful and harmful genetic materials and then execute an evolutionary process in such a way that the population becomes increasingly composed of useful genetic material and increasingly free of the harmful genetic material. Compared to the standard GA, it provides some computational advantages as well as a tool for automatic generation of hierarchical genetic representations specifically tailored to suit certain classes of problems.     

Acceleration of cellular automata algorithms using genetic algorithms

The following problem is solved: Given a Cellular Automaton with continuous state space which simulates a physical system or process, use a Genetic Algorithm in order to find a Cellular Automaton with discrete state space, having the smallest possible lattice size and the smallest possible number of discrete states, the results of which are as close as possible to the results of the Cellular Automaton with continuous state space. The Cellular Automaton with discrete state space evolves much faster than the Cellular Automaton with continuous state space. The state spaces of two Cellular Automata have been discretized using a Genetic Algorithm. The first Cellular Automaton simulates the two-dimensional photoresist etching process in integrated circuit fabrication and the second is used to predict forest fire spreading. A general method for the discretization of the state space of Cellular Automata using a Genetic Algorithm is also presented. The aim of this work is to provide a method for accelerating the execution of algorithms based on Cellular Automata (Cellular Automata algorithms) and to build a bridge between Cellular Automata as models for physical systems and processes and Cellular Automata as a VLSI architecture.     

基于改进遗传算法的最小生成树算法

以图论和改进遗传算法为基础,提出了一种求最小生成树的遗传算法。该算法采用二进制表示最小树问题,并设计出相应的适应度函数、算子以及几种控制策略,以提高执行速度和进化效率。传统算法一次只能得到一个候选解。用该算法对其求解,可以在较短的时间内以较高的概率获得多个候选解。应用实例表明该算法优于传统算法。     

The algebra of genetic algorithms

A rigorous formulation of the generalisation of schema analysis known as forma analysis is presented. This is shown to provide a direct mechanism for harnessing knowledge about a search space, codified through the imposition of equivalence relations over that space, to generate a genetic representation and operators. It is shown that a single characterisation of a space leads to a unique genetic representation, and the kinds of representations that are possible are classified and discussed. A relatively new operator, calledrandom assorting recombination (RAR _w ), is defined rigorously and is shown to be, in an important sense, a universal recombination operator.     

Improving swarming using genetic algorithms

The verification of temporal properties against a given system may require the exploration of its full state space. In explicit model checking, this exploration uses a depth-first search and can be achieved with multiple randomized threads to increase performance. Nonetheless, the topology of the state space and the exploration order can cap the speedup up to a certain number of threads. This paper proposes a new technique that aims to tackle this limitation by generating artificial initial states, using genetic algorithms. Threads are then launched from these states and thus explore different parts of the state space. Our prototype implementation is 10% faster than state-of-the-art algorithms on a general benchmark and 40% on a specialized benchmark. Even if we expected a decrease in an order of magnitude, these results are still encouraging since they suggest a new way to handle existing limitations. Empirically, our technique seems well suited for “linear” topology, i.e., the one we can obtain when combining model checking algorithms with partial-order reduction techniques.

     

遗传算法研究综述

介绍了遗传算法的基本工作原理和主要特点 ,讨论了遗传算法的理论、技术、存在问题及改进方法 ,概述了遗传算法的常见应用领域 ,分析了近五年国内对遗传算法的研究现状。最后 ,进一步探讨了遗传算法的未来研究方向。     

Camera calibration with genetic algorithms

We present an approach based on genetic algorithms for performing camera calibration. Contrary to the classical nonlinear photogrammetric approach, the proposed technique can correctly find the near-optimal solution without the need of initial guesses (with only very loose parameter bounds) and with a minimum number of control points (7 points). Results from our extensive study using both synthetic and real image data as well as performance comparison with Tsai's procedure (1987) demonstrate the excellent performance of the proposed technique in terms of convergence, accuracy, and robustness     

Learning with case-injected genetic algorithms

This paper presents a new approach to acquiring and using problem specific knowledge during a genetic algorithm (GA) search. A GA augmented with a case-based memory of past problem solving attempts learns to obtain better performance over time on sets of similar problems. Rather than starting anew on each problem, we periodically inject a GA's population with appropriate intermediate solutions to similar previously solved problems. Perhaps, counterintuitively, simply injecting solutions to previously solved problems does not produce very good results. We provide a framework for evaluating this GA-based machine-learning system and show experimental results on a set of design and optimization problems. These results demonstrate the performance gains from our approach and indicate that our system learns to take less time to provide quality solutions to a new problem as it gains experience from solving other similar problems in design and optimization.     

Chaotic populations in genetic algorithms

We set two objectives for this study: one is to emulate chaotic natural populations in GA (Genetic Algorithms) populations by utilizing the Logistic Chaos map model, and the other is to analyze the population fitness distribution by utilizing insect spatial distribution theory. Natural populations are so dynamic that one of the first experimental evidences of Chaos in nature was discovered by a theoretical ecologist, May (1976, Nature, 261,459–467)[30], in his analysis of insect population dynamics. In evolutionary computing, perhaps influenced by the stable or infinite population concepts in population genetics, the status quo of population settings has dominantly been the fixed-size populations. In this paper, we propose to introduce dynamic populations controlled by the Logistic Chaos map model to Genetic Algorithms (GA), and test the hypothesis – whether or not the dynamic populations that emulate chaotic populations in nature will have an advantage over traditional fixed-size populations.The Logistic Chaos map model, arguably the simplest nonlinear dynamics model, has surprisingly rich dynamic behaviors, ranging from exponential, sigmoid growth, periodic oscillations, and aperiodic oscillations, to complete Chaos. What is even more favorable is that, unlike many other population dynamics models, this model can be expressed as a single parameter recursion equation, which makes it very convenient to control the dynamic behaviors and therefore easy to apply to evolutionary computing. The experiments show result values in terms of the fitness evaluations and memory storage requirements. We further conjecture that Chaos may be helpful in breaking neutral space in the fitness landscape, similar to the argument in ecology that Chaos may help the exploration and/or exploitation of environment heterogeneity and therefore enhance a species’ survival or fitness.