Parallel Problem Solving from Nature — PPSN IV

In recent years computer viruses have grown to be of great concern. They have also been proposed as prototypical artificial life, but the possibility of their evolution has been dismissed due to modern computer programs being computationally brittle (i.e. a random change to a functional program will almost certainly render it non-functional) and the series of steps required for the evolution of a new virus being improbable. These allegations are examined by studying homology between functional program sequences. It is concluded that programs are far less brittle than expected. While the evolution of viruses de novo is still unlikely, evolution of pre-existing viruses and programs is feasible. This has significant implications for computer security and evolutionary computation.

In this paper we introduce two macro-level operators to enhance the use of population-based evolutionary computing techniques in multiagent environments: speciation and symbiogenesis. We describe their use in conjunction with the genetic algorithm to evolve Pittsburgh-style classifier systems, where each classifier system represents an agent in a cooperative multi-agent system. The reasons for implementing these kinds of operators are discussed and we then examine their performance in developing a controller for the gait of a wall-climbing quadrupedal robot, where each leg of the quadruped is controlled by a classifier system. We find that the use of such operators can give improved performance over static population/agent configurations.

Evolution strategies with subjective selection of the offspring can be applied to optimization problems, when no objective evaluation of the offspring is possible. For this class of optimization problems, strategies with insensitivity towards incorrect selection decisions are necessary. With subjective selection, incorrect decisions are unavoidable and have the effect of noise being overlaid onto the fitness value. Three examples of different evolution strategies (ES) are presented which are resistant against wrong selection decisions.The convergence of an ES with manually controlled stepsize for the adaptation of a mixture of colored liquid components towards a target color is shown. This first example can be regarded as a real world experiment. In two computer experiments an ES with automatically adapted stepsize has been applied for the first time to this type of optimization problems. The color and shape of a rectangle will be adapted towards a target rectangle, and the adaptation of the shape of a polygon towards a symmetric dodecagon will be shown. With these two test problems the convergence of different strategy variants with and without recombination is examined.

This paper presents the emergence of the cooperative behavior for the multiple agents by means of Genetic Programming (GP). Our experimental domain is the Tile World, a multi-agent test bed [Pollack90]. The world consists of a simulated robot agent and a simulated environment which is both dynamic and unpredictable. For the purpose of evolving the cooperative behavior, we propose three types of strategies, i.e, homogeneous breeding, heterogeneous breeding, and co-evolutionary breeding. The effectiveness of these three types of GP-based multi-agent learning is discussed with comparative experiments.

Growth grammars in the form of parallel rewrite systems (L-systems) are used to model morphogenetic processes of plant structures. With the help of evolutionary programming techniques developmental programs are bred which encode plants that exhibit characteristic growth patterns advantageous in competitive environments.Program evolution is demonstrated on the basis of extended genetic programming on symbolic expressions with genetic operators and expression generation strongly relying on templates and pattern matching.

This paper examines the ways in which the encoding scheme that governs how phenotypes develop from genotypes may be used to improve the performance of open-ended artificial evolution for design. If an open-ended framework involving variable complexity genetic algorithms is adopted, then the vast majority of the evolutionary effort is spent exploring neutral flat areas of the search space. Domain-specific heuristics may be employed to reduce the time spent on searching these neutral areas, however, and the ways in which domain knowledge may be incorporated into the encoding scheme are examined. Experiments are reported in which different categories of scheme were tested against each other, and conclusions are offered as to the most promising type of encoding scheme for a viable open-ended artificial evolution.

This paper describes a function-level Evolvable Hardware (EHW). EHW is hardware which is built on programmable logic devices (e.g. PLD and FPGA) and whose architecture can be reconfigured by using a genetic learning to adapt to new unknown environments in real time. It is demonstrated that the function-level hardware evolution can attain much higher performances than the gate-level evolution, in neural network applications (e.g. two-spiral). VLSI architecture of the functionbased FPGA dedicated to function level evolution is also described.

This work studies the interaction of evolution and learning. It starts from the coevolutionary genetic algorithm (CGA) introduced earlier. Two techniques — life-time fitness evaluation (LTFE) and predator-prey coevolution — boost the genetic search of a CGA. The partial but continuous nature of LTFE allows for an elegant incorporation of life-time learning (LTL) within CGAs. This way, not only the genetic search but also the LTL component focuses on “not yet solved” problems. The performance of the new algorithm is compared with various other algorithms.

A co-evolutionary approach for developing programs for controlling a very simple “robot-like” simulated vehicle is presented. The main goal is to find programs that can generalize and solve other similar problems. Good results are achieved by coevolving the test cases and the simulated vehicles and using locality in both the reproduction and evaluation phases. The fitness of a controller is determined by its performance in competition with its neighbours in the test case population. The fitness of a test case is similarly determined through competition with its neighbours in the controller population. The co-evolved controllers are more robust and general than a simple hand-designed algorithm or controllers evolved using a fixed training set.

The fundamental dynamical processes of evolution are connected to processes based on sequences — the genetic messages coded by DNA. In biological evolution we can discover stages of the emergence of novel features. Nature apparently explores some unknown mechanisms of complexification of nets of replicating strings.It is known that genetic changes are not directly manifested in phenotypic changes. Rather, a complex developmental machinery mediates between genetic information and phenotypic characteristics. It provides a certain robustness by filtering out genetic changes.Such degree of freedom allows the species to accumulate appropriate mutations without interruption of the development. When the volume of heritable changes achieving critical threshold, this can force out the development to a new higher-level trajectory.I intend to overview here some findings on the way of searching and exploitation of the rules for evolutionary complexification. I hope these algorithms could find applications in the presentation problem of evolutionary computations.

A brief survey of biological research on non-coding DNA is presented here. There has been growing interest in the effects of non-coding segments in evolutionary algorithms (EAs). To better understand and conduct research on non-coding segments and EAs, it is important to understand the biological background of such work. This paper begins with a review of basic genetics and terminology, describes the different types of non-coding DNA, and then surveys recent intron research.

We investigate the biologically motivated selfreproduction strategies by numerical and analytical calculations. In the analytical part we show that each of these strategies can be reduced to an eigenvalue problem of Sturm-Liouville-type. The properties of the landscape and the dynamics of the optimization are encoded in the spectrum of the Hamiltonian, which is different in both cases. We discuss some model cases with exact solutions and compare them with simulations.

The performance of (Μ/Μ, λ)-ESs (Evolution Strategies) in the asymptotic limit for N→∞ and λ→∞ is investigated. The conjecture made by Schwefel that the maximum performance of such strategies scales like Μ In(λ/Μ) will be proved. Furthermore, it will be shown that an optimally tuned Μ/Μ, λ)-ES performs exactly λ times faster than an optimally tuned (1+1)-ES, if the hyper-sphere is taken as the fitness model (using the number of generations as the performance measure). The notion of fitness efficiency will be introduced and will be used to derive the ES time complexity. The results are compared to the non-recombinant (Μ, λ)-ES.

Long path problems have been introduced into GA literature as problems that are hard for hill-climbers but empirical results suggest they can easily be solved by GAs. However, no formal analysis has been carried out which would explain this apparent success. The paper shows that the Root2path problem resembles a Royal Road function which allows the GA to exploit short cuts in the crossover landscape.To fully understand the GA behaviour the original problem as introduced by Horn et. al. has been decomposed into its components: the Root2path and the slope function. Although both functions may be classified as GA-easy, they impose different requirements on the constitution of the population. These requirements are shown to be incompatible, so that the combination of Root2path and slope function results in a problem that is hard for a GA.

This paper introduces a random tree generation algorithm for GP (Genetic Programming). Generating random trees is an essential part of GP. However, the recursive method commonly used in GP does not necessarily generate random trees, i.e the standard GP initialization procedure does not sample the space of possible initial trees uniformly. This paper proposes a truly random tree generation procedure for GP. Our approach is grounded upon a bijection method, i.e., a 1–1 correspondence between a tree with n nodes and some simple word composed by letters x and y. We show how to use this correspondence to generate a GP tree and how GP search is improved by using this “randomness”.

This paper discusses the term implicit forma, which is useful for explaining the behaviour of genetic algorithms. Implicit formae are predicates over the chromosome space that are not strongly connected to the representation at hand but are capable of directing the search. After a short theoretical discussion, three examples are given for illustration, including the subset sum problem which is NP-complete.

This paper takes a fresh look at some of the key ideas of genetic algorithms, using concepts drawn from the theory of majorization and probabilistic databases. We show the intimate relationships between GAs and the theory of probabilistic databases. We show how deception is well described using Saari's theorem, and its relationships with the Simpson and other paradoxes in decision theory. Reconstructability, a concept of fundamental importance in databases, is proposed as a useful substitute for deception. The database projection operator is connected with hyperplane partitions, and is used to show the nexus between point crossover operators and the join operator. Using results from probabilistic databases, we show that crossover may be considered as a majorization operator.

A simple model of biological evolution based on q-tournament selection and uniform random mutations is presented and its time dependent behaviour analysed.

The Breeder Genetic Algorithm (BGA) is based on the equation for the response to selection. In order to use this equation for prediction, the variance of the fitness of the population has to be estimated. For the usual sexual recombination the computation can be difficult. In this paper we shortly state the problem and investigate several modifications of sexual recombination. The first method is gene pool recombination, which leads to marginal distribution algorithms. In the last part of the paper we discuss more sophisticated methods, based on estimating the distribution of promising points.

The Breeder Genetic Algorithm (BGA) is based on the equation for the response to selection. In order to use this equation for prediction, the variance of the fitness of the population has to be estimated. For the usual sexual recombination this can be difficult. In this paper the new points (offspring) are generated from distributions, a uniform distribution and a distribution generated by univariate marginal distributions. For a class of unimodal fitness functions the performance of the BGA is analytically computed. The results are compared to gene recombination methods. The uniform distribution is approximately generated by line recombination; recombination methods acting independently on each gene approximate the second distribution.

In this paper, we examine the effects of noise on both local search and genetic search. Understanding the potential effects of noise on a search space may explain why some search techniques fail and why others succeed in the presence of noise. We discuss two effects that are the result of adding noise to a search space: the annealing of peaks in the search space and the introduction of false local optima.

We introduce a classifying measure of fitness landscapes — the density of states — for continuous and discrete problems, especially optimisation of sequences and graphs. By means of the Boltzmann strategy we obtain a simple algorithm to calculate the density of states for a given problem. Knowing the density of states we are able to approximate the optimal fitness value of the problem which makes it feasible to assess the effectivity of practical optimisations.

Interactive evolutionary algorithms (IEAs) are special cases of interactive optimization methods. Potential applications range from multicriteria optimization to the support of rapid prototyping in the field of design. In order to provide a theoretical framework to analyze such evolutionary methods, the IEAs are formalized as stochastic Mealy automata. The potential impacts of such a formalization are discussed.

Function optimization is a typical application domain for genetic algorithms (GAs). Traditionally, GAs work on bit strings of fixed total length l. Significant research has been done on designing and analyzing different coding schemes, of which Gray coding is one of the most used forms. Surprisingly little attention has been devoted to directly encoding the parameters by floating-point values provided by the programming language. This form of coding has been in favor in evolution strategy. This paper discusses several coding schemes and derives the resulting complexity when optimizing functions with n independent continuous parameters. It turns out that the direct use of real-valued parameters has certain advantages. First of all, it speeds up convergence by a factor of up to lq−1, where q denotes the number of bits per parameter. Furthermore, the use of real-valued parameters allows for more flexibility in designing the mutation operator and eases many implementation issues. The theoretical analysis presented here strongly suggests that real-valued parameters (implemented by floating point values provided by the programming language) should be the best choice when applying a GA in the field of function optimization.

The increasing availability of finely-grained parallel architectures has resulted in a variety of evolutionary algorithms (EAs) in which the population is spatially distributed and local selection algorithms operate in parallel on small, overlapping neighborhoods. The effects of design choices regarding the particular type of local selection algorithm as well as the size and shape of the neighborhood are not particularly well understood and are generally tested empirically. In this paper we extend the techniques used to more formally analyze selection methods for sequential EAs and apply them to local neighborhood models, resulting in a much clearer understanding of the effects of neighborhood size and shape.

Numerical optimization problems enjoy a significant popularity in evolutionary computation community; all major evolutionary techniques use such problems for various tests and experiments. However, many of these techniques (as well as other, classical optimization methods) encounter difficulties in solving some real-world problems which include non-trivial constraints. This paper discusses a new development which is based on the observation that very often the global solution lies on the boundary of the feasible region. Thus, for many constrained numerical optimization problems it might be beneficial to limit the search to that boundary, using problem-specific operators. Two test cases illustrate this approach: specific operators are designed from the simple analytical expression of the constraints. Some possible generalizations to larger classes of constraints are discussed as well.

This paper revisits an important, yet poorly understood, phenomenon of genetic optimisation, namely the mixing or juxtapositioning capacity of recombination, and its relation to selection. Mixing is a key factor in order to determine when a genetic algorithm will converge to the global optimum, or when it will prematurely converge to a suboptimal solution. It is argued that from a dynamical point of view, selection and recombination are involved in a kind of race against time: the number of instances of good building blocks is quickly increased from generation to generation by the selection phase, but in order to create optimal solutions these building blocks have to be juxtaposed by the crossover operator and this also takes some time to occur. If the selection of building blocks goes too fast — relative to the rate at which crossover can juxtapose or mix them — then the population will prematurely converge to a suboptimal solution. Previous work (Goldberg, Deb & Thierens, 1993) made a first step toward a better understanding of mixing in genetic algorithms, and also introduced the use of dimensional analysis in GA modelling. In this paper we extend this work by integrating some of the insights gained from the modelling of the dynamic behaviour of GAs on infinite populations (Mühlenbein & Schlierkamp-Voosen, 1993; Thierens & Goldberg, 1994; Bäck, 1995; Miller & Goldberg, 1995). The resulting dimensional model quantifies the allele-wise mixing process: it specifies the boundary in the GA parameter space between the region of reliable convergence at one side, and the region of premature convergence at the other. Although the model is limited to simple bit-wise mixing, the lessons learned from it are quite general and are also valid for more difficult, building-block based problems.

We present a central limit theorem for the population process of a simple genetic algorithm. This theory approximates the discrete population process with finite population size by a continuous Gaussian — process. As a special application we consider a search space with only two elements. For this case we present a complete solution of the differential equation arising in the calculation of the Gaussian — process. This analysis gives first insight into the theory of the general case. Some applications of the theory and extensions to the general case are mentioned, too.

Based on experiences from livestock breeding we introduce erroneous truncation selection for the Breeder Genetic Algorithm (BGA). The decision behavior of the breeder is given by a simple model. It is shown that there is no benefit to the BGA by using erroneous selection though the variance of the parent population is increased by increasing the decision error variance.

In this paper we present two new crossover operators that make use of macro-order information and neighborhood information in sequencing problems. None of them needs local information, thus making them usable for a wide area of applications, e.g., optimal variable orders for binary decision diagrams, scheduling problems, seriation in archeology. The experimental results are promising. Especially they show that macro-order and neighborhood information is very important.

Ordinarily, Genetic Programming uses little or no mutation. Crossover is the predominant operator. This study tests the effect of a very aggressive use of the mutation operator on the generalization performance of our Compiling Genetic Programming System (‘CPGS’). We ran our tests on two benchmark classification problems on very sparse training sets. In all, we performed 240 complete runs of population 3000 for each of the problems, varying mutation rate between 5% and 80%. We found that increasing the mutation rate can significantly improve the generalization capabilities of GP. The mechanism by which mutation affects the generalization capability of GP is not entirely clear. What is clear is that changing the balance between mutation and crossover effects the course of GP training substantially — for example, increasing mutation greatly extends the number of generations for which the GP system can train before the population converges.

In this paper we concentrate on job shop scheduling as a representative of constrained combinatorial problems. We introduce a new permutation representation for this problem. Three crossover operators, different in tending to preserve the relative order, the absolute order, and the position in the permutation, are defined. By experiment we observe the strongest phenotypical correlation between parents and offspring when respecting the absolute order. It is shown that a genetic algorithm using an operator which preserves the absolute order also obtains a superior solution quality.

Using the multi-parent diagonal and scanning crossover in GAs reproduction operators obtain an adjustable arity. Hereby sexuality becomes a graded feature instead of a Boolean one. Our main objective is to relate the performance of GAs to the extent of sexuality used for reproduction on less arbitrary functions then those reported in the current literature. We investigate GA behaviour on Kauffman's NK-landscapes that allow for systematic characterization and user control of ruggedness of the fitness landscape. We test GAs with a varying extent of sexuality, ranging from asexual to ’very sexual’. Our tests were performed on two types of NK-landscapes: landscapes with random and landscapes with nearest neighbour epistasis. For both landscape types we selected landscapes from a range of ruggednesses. The results confirm the superiority of (very) sexual recombination on mildly epistatic problems.

The traditional mutation operator within evolution strategies and evolutionary programming relies on adding a multivariate zero mean Gaussian random vector to each parent solution. An alternative method is proposed that allows for optimizing the direction of such mutations. The notion of mutation in polar coordinates is adopted such that parents generate offspring in a selected direction with a random step size. Experiments on four functions suggest that the independent adjustment of direction of travel and step size can produce improvements in rate of convergence on some functions.

A problem in the use of genetic algorithms is the premature convergence in a local optimum. Its main cause is the lack of diversity in the population due to a disproportionate relationship between exploitation and exploration. In this paper, we present heuristic crossover operators for real-coded genetic algorithms, which use the adaptation of the parents for generating the offspring. With these operators, diversity and convergence in the population may be modeled in order to avoid the premature convergence problem and to introduce good final behaviour.

When optimizing with evolutionary algorithms in a continuous search space, mutations usually are distributed according to a Gaussian. A Gaussian distribution decays exponentially, i. e. very large mutations are highly unlikely. This bears the risk of the optimization getting caught in local extrema. A more slowly decaying distribution, e. g. a Cauchy distribution, may circumvent this problem. A Cauchy distribution allows for rare large mutations. In this paper the performance of Gaussian and Cauchy distributed mutations, in particular their robustness and rate of progress, are compared analytically and numerically in a number of examples. It turns out that, in one dimension, an algorithm working with Cauchy distributed mutations is both more robust and faster. This result cannot easily be generalized to higher dimensions, where the additional problem of finding the right direction for leaving a saddle point appears. The analysis of a simple two dimensional problem does not yet allow to draw final conclusions concerning which kind of mutations, if any, is preferable in higher dimensions.

Adaptive heuristics have been developed in the Evolution Strategy (ES) frame regarding the mutation of real-valued variables. But these heuristics poorly extend to discrete variables: when the rate or variance of mutation gets too small, mutation has no effect any more. To overcome this problem, we propose two mutation operators, that use the worst individuals of the current population as beacons indicating the limits of the current promising region:Mutation by differentiation drives individuals away from the beacon individuals. Mutation by imitation inversely assumes that beacon-individuals still contain relevant informations, and aims at moving the indiidual at hand nearer to the beacons. Mutation by imitation produces offspring that share the features of several “parents”; but in contrast with classical crossover, it allows one to control the distance between the offspring and the main parent, by fixing the number of bits to mutate. Mutation by imitation thus permits a tunable exchange of informations among individuals.Both operators have been implemented in a boolean (Μ + λ) ES framework, and experimented on four problems: the Royal Road problem, a GA-deceptive problem, the combinatorial multiple knapsack optimization problem and the Long Path problem. Comparative validation is presented and discussed.

Most evolutionary algorithms use a fixed representation space. This complicates their application to many problem domains, especially when there are dependencies between problem variables (e.g. problems naturally defined over permutations). This paper presents a method for specifying algorithms with respect to abstract representations, making them completely independent of any actual representation or problem domain. It also defines a procedure for generating a concrete representation from an explicit characterisation of a problem domain which captures beliefs about its structure. This allows arbitrary algorithms to be applied to arbitrary problems yielding well-specified search strategies suitable for implementation. The process is illustrated by showing how identical algorithms can be applied to both the TSP and real parameter optimisation to yield familiar (but superficially very different) concrete search strategies.

In this paper we examine a modification to the genetic algorithm — a new adaptive operator was developed for two industrial applications using genetic algorithm based on-line control systems. The aim is to enable the control systems to track optima of a time-varying dynamic system whilst not being detrimental to its ability to provide sound results for the stationary environments. When compared with the hypermutation operator, the new operator matched the level of diversity introduced into the population with the “degree” of the environmental changes better because it increases population diversity only gradually. Although the new technique was developed for the control application domain where real variables are mostly used, a possible generalization of the method is also suggested. It is believed that the technique has the potential to be a further contribution in making genetic algorithm based techniques more readily usable in industrial control applications.

In this paper we extend the classical Evolution Strategies by a new mechanism to adjust the step sizes. We propose an Evolution Strategy with Variance Function (ESV). The ESV can generate local and global random search procedures depending on the task.The idea of the variance function approach is presented. A performance comparison of the ESV with other published Evolutionary Algorithms for global optimization problems is made. We report about some aspects of the analysis of the used multimodal test functions which concern the complexity of the fitness landscape.

Various extensions to the Genetic Algorithm (GA) attempt to find all or most optima in a search space containing several optima. Many of these emulate natural speciation. For co-evolutionary learning to succeed in a range of management and control problems, such as learning game strategies, such methods must find all or most optima. However, suitable comparison studies are rare. We compare two similar GA speciation methods, fitness sharing and implicit sharing. Using a realistic letter classification problem, we find they have advantages under different circumstances. Implicit sharing covers optima more comprehensively, when the population is large enough for a species to form at each optimum. With a population not large enough to do this, fitness sharing can find the optima with larger basins of attraction, and ignore the peaks with narrow bases, while implicit sharing is more easily distracted. This indicates that for a speciated GA trying to find as many near-global optima as possible, implicit sharing works well only if the population is large enough. This requires prior knowledge of how many peaks exist.

An investigation is reported into the effects of isolation within a population upon its evolution under a genetic algorithm. The effects of varying population size were compared between a panmictic and a continuously distributed population, each offered an identical environment. Theoretical analysis predicted a logarithmic variation of performance with population size alone. Experiment confirmed such a variation in both populations. Although the distributed population always obtained superior peak fitness, no improvement in the ability to discover optima could be attributed to isolation. However, the distributed population was clearly observed to better maintain allelic diversity. Evidence was also found for the emergence of meta-stable geographical boundaries. Possible explanations are offered.

Self-adaption is one of the most promising areas of research in evolutionary computation as it adapts the algorithm to the problem while solving the problem. In this paper we extend self-adaption to operate on more than one aspect of evolutionary computation and at more than one level of adaption. We developed a genetic algorithm which selfadapts both mutation strength and population size; the results indicate that the approach works quite well.

In this paper we describe niche search, a genetic-based optimisation approach which is characterised by an evolutionary search on two layers: the individual layer (which is comparable to search described in other genetic algorithms), and the niche layer.Neither of these searches is directed: both individuals and niches evolve based on the selection of the fittest.The numerical results obtained by niche search are quite promising, as our implementation has successfully handled all the tests carried out. The computational performance is considerably better than that of other algorithms of the same family analysed in the literature.

It has long been recognised that the choice of recombination and mutation operators and the rates at which they are applied to a Genetic Algorithm will have a significant effect on the outcome of the evolutionary search, with sub-optimal values often leading to poor performance. In this paper an evolutionary algorithm (APES) is presented within which both the units of heredity and the probability that those units will subject to mutation are learnt via self adaptation of the genetic material. Using Kaufmann's NK model, this algorithm is compared to a number of combinations of frequently used crossover operators with “standard” mutation rates. The results demonstrate competitive times to find maxima on simple problems, and (on the most complex problems) results which are significantly better than the majority of other algorithms tested. This algorithm represents a robust adaptive search method which is not dependant on expert knowledge of genetic algorithm theory or practice in order to perform effectively.

This paper proposes a new technique for improving the number of usefully distinct solutions produced by a Genetic Algorithm (GA) when applied to multimodal problems. The tribes method builds on the spatial selection methods proposed by Collins and Jefferson [1]. We compare the technique with two well-known niching methods (crowding and sharing), spatial selection alone, and a simple control GA method, in the domain of simple timetabling problems. We demonstrate that the tribes technique can greatly improve the efficiency with which a GA can obtain multiple distinct solutions to a problem.

In the vast majority of genetic algorithm implementations, the operator probabilities are fixed throughout a given run. However, it may be useful to adjust these probabilities during the run, according to the ability of the operators to produce children of increased fitness. Cost Based Operator Rate Adaptation (COBRA) periodically re-ranks operator probabilities according to a measure of operator performance. The effect upon genetic algorithm performance of COBRA upon both well-studied theoretical and practical problems is examined.

A DGA is a genetic algorithm with novel features: relational schemata. These structures allow a more natural expression of relations existing between loci. Indeed, schemata in standard genetic algorithms can only specify values for each locus. Relational schemata are based on the notion of duality: a schema can be represented by two strings. The intent of this paper is to show the superiority of DGAs over conventional genetic algorithms in two general areas: efficiency and reliability. Thus, we show with theoretical and experimental results, that our algorithm is faster and perform consistently. The application chosen for test DGAs is the optimization of an extension of Royal Road functions we call relational landscapes.

Instance-based methods of classification are easy to implement, easy to explain and relatively robust. Furthermore, they have often been found in empirical studies to be competitive in accuracy with more sophisticated classification techniques (Aha et al., 1991; Weiss & Kulikowski, 1991; Fogarty, 1992; Michie et al., 1994). However, a twofold drawback of the simplest instance-based classification method (1-NNC) is that it requires the storage of all training instances and the use of all attributes or features on which those instances are measured — thus failing to exhibit the cognitive economy which is the hallmark of successful learning (Wolff, 1991). Previous researchers have proposed ways of adapting the basic 1-NNC algorithm either to select only a subset of training cases (‘prototypes’) or to discard redundant and/or ‘noisy’ attributes, but not to do both at once. The present paper describes a program (IOGA) that uses an evolutionary algorithm to select prototypical cases and relevant attributes simultaneously, and evaluates it empirically by application to a set of test problems from a variety of fields. These trials show that very considerable economization of storage can be achieved, coupled with a modest gain in accuracy.

Genetic algorithms are often applied to building block problems. We have developed a simple filtering algorithm that can locate building blocks within a bit-string, and does not make assumptions regarding the linkage of the bits. A comparison between the filtering algorithm and genetic algorithms reveals some interesting insights, and we discus how the filtering algorithm can be used to build a powerful hybrid genetic algorithm.

Recently, multi-objective optimization by use of the genetic algorithms (GAs) is getting a growing interest as a novel approach to this problem. Population based search of GA is expected to find the Pareto optimal solutions of the multi-objective optimization problems in parallel. To achieve this goal, it is an intrinsic requirement that the evolution process of GA maintains well the diversity of the population in the Pareto optimality set. In this paper, the authors propose to utilize the Thermodynamical Genetic Algorithm (TDGA), a genetic algorithm that uses the concepts of the entropy and the temperature in the selection operation, for multi-objective optimization. Combined with the Pareto-based ranking technique, the computer simulation shows that TDGA can find a variety of Pareto optimal solutions.

In the genetic algorithm (GA), maintenance of the diversity of the population is an important issue to enhance its optimization and adaptation ability. The authors have proposed the thermodynamical genetic algorithm (TDGA), which can maintain the diversity explicitly and systematically by evaluating the entropy and the free energy of the population. In adaptation to changing environment, the maintenance of the diversity is quite essential because it is a key factor of generating novel search points. This paper discusses adaptation to changing environment by means of TDGA by taking a time-varying knapsack problem as an example.

Evolutionary and adaptive search (AS) strategies for diverse multi-level search across a preliminary, whole-system design hierarchy defined by both discrete and continuous variable parameters is described. Such strategies provide high-level decision support when integrated with preliminary design software describing the major elements of an engineering system. Initial work has involved a Structured Genetic Algorithm (stGA) with appropriate mutation regimes to encourage search diversity. The shortcomings of the stGA approach are identified and a dual agent strategy is introduced (GAANT). Results are compared to those of the stGA. Appropriate communication between search agents concurrently manipulating the discrete and continuous variable parameter sets results in a more efficient search across the hierarchy than that achieved by the stGA whilst also simplifying the chromosomal representation. This simplification allows the further development of the preliminary design hierarchy in terms of complexity. The technique therefore represents a significant contribution to preliminary design where multi-level, mixed discrete/continuous parameter problems can be prevalent.

In this paper we will formulate a framework for a parallel population based search process: an Abstract Cellular Genetic Algorithm (ACGA). Using the ACGA as a template, various parallel search algorithms can be formulated, e.g. parallel Genetic Algorithms and parallel Simulated Annealing. As a case study we will investigate the influence of locality on the behaviour of a Cellular Genetic Algorithm (CGA), that is constructed according to this framework. A neighbourhood structure is imposed upon the population, which results in overlapping local cell-populations. Using varying neighbourhood sizes, we will discuss experiments with CGAs ranging from maximally local to effectively global. The CGA has been applied to a load balancing problem: the NP-hard problem of mapping a process graph onto a processor topology in parallel finite element simulations.

Many of the studies on GAs give emphasis on finding the global optimal solution. In this paper, we propose a new method which extend the application of GAs to domains that require detection of robust solutions. If a global optimal solution found is on a sharp-pointed location, there may be cases where it is not good to use this solution. In nature, the phenotypic feature of an organism is determined from the genotypic code of genes in the chromosome. During this process, there may be some perturbations. Let X be the phenotypic parameter vector, f(X) a fitness function and δ a noise vector. As can be easily understood from the analogy of nature, actual fitness function should be of the form f(X+δ). We use this analogy for the present work. Simulation results confirm the utility of this approach in finding robust solutions.

MasterMind is a game in which the player must find out, by making guesses, a hidden combination of colors set by the opponent. The player lays a combination of colors, and the opponent points out the number of positions the player has found out (black tokens) and the number of colors that are in a different place from the hidden combination (white tokens). This problem can be formulated in the following way: the target of the game is to find a string composed of l symbols, drawn from an alphabet of cardinality c, using as constraints hints that restrict the search space. The partial objective of the search is to find a string that meets all the constraints made so far the final objective being to find the hidden string.This problem can also be located within the class of constrained optimization, although in this case not all the constraints are known in advance; hence its dynamic nature.Three algorithms playing MasterMind have been evaluated with respect to the number of guesses made by each one and the number of combinations examined before finding the solution: a random-search-with-constraints algorithm, simulated annealing, and a genetic algorithm. The random search and genetic algorithm at each step plays the optimal solution i.e., the one that is consistent with the constraints made so far, while simulated annealing plays the best found within certain time constraints. This paper proves that the algorithms that follow the optimal strategy behave similarly, getting the correct combination in more or less the same number of guesses; between them, GA is better with respect to the number of combinations examined, and this difference increases with the size of the search space, while SA is much faster (around 2 orders of magnitude) and gives a good enough answer.

Genetic programming (GP) is a variant of genetic algorithms where the data structures handled are trees. This makes GP especially useful for evolving functional relationships or computer programs, as both can be represented as trees. Symbolic regression is the determination of a function dependence y=g(x) that approximates a set of data points (x_i, y_i). In this paper the feasibility of symbolic regression with GP is demonstrated on two examples taken from different domains. Furthermore several suggested methods from literature are compared that are intended to improve GP performance and the readability of solutions by taking into account introns or redundancy that occurs in the trees and keeping the size of the trees small. The experiments show that GP is an elegant and useful tool to derive complex functional dependencies on numerical data.

Evolutionary algorithms are sophisticated hill-climbers. In this paper, we discuss the ability of this class of local search algorithms to provide useful and efficient heuristics to solve NP-hard problems. Our discussion is illustrated on experiments aiming at solving the job-shop-scheduling problem. We focus on the components of the EA, pointing out the importance of the objective function as well as the manner the operators are applied. Experiments clearly show the efficiency of local search methods in this context, the trade-off between “pure” and hybrid algorithms, as well as the very good performance obtained by simple hill-climbing algorithms. This work has to be regarded as a step towards a better understanding of the way search algorithms wander in a fitness landscape.

This work proposes a quantitative, non-parametric interpretation of statistical performance of stochastic multiobjective optimizers, including, but not limited to, genetic algorithms. It is shown that, according to this interpretation, typical performance can be defined in terms analogous to the notion of median for ordinal data, as can other measures analogous to other quantiles.Non-parametric statistical test procedures are then shown to be useful in deciding the relative performance of different multiobjective optimizers on a given problem. Illustrative experimental results are provided to support the discussion.

We consider the problem of placing ready-made boxes (containing e.g. articles) on the pages of a generalized newspaper. Three methods — one utilizing heuristic search, and two utilizing simulated annealing — are presented and compared. The second simulated annealing implementation emerged as the best method. It uses only one simple but powerful state transformation. In our view its success is due to clever use of domain knowledge in the design of the model.

We describe a comparison between Simulated Annealing (SA), Dispatch Rules (DR), and a Coevolutionary Distributed Genetic Algorithm (DGA) solving a random sample of integrated planning and scheduling (IPS) problems. We found that for a wide range of optimization criteria the DGA consistently outperformed SA and DR. The DGA finds 8–9 unique high quality solutions per run, whereas the other techniques find only one. On average, each DGA solution is 10–15% better than SA solutions and 30–35% better than DR solutions.

This paper describes a thorough comparison of ten different search techniques applied to a wing-box design optimisation problem. The techniques used vary from deterministic gradient descent to stochastic Simulated Annealing (SA) and Genetic Algorithms (GAs). The stochastic techniques produced as good solutions as the best found by the deterministic techniques. However, only the stochastic techniques consistently produced very good solutions every run. Significantly, only a distributed genetic algorithm (DGA) and hybrid methods (SA with gradient descent, DGA with gradient descent) had a reliable fast decent to good regions of solution space. Of these the hybrid DGA was significantly better than anything else. The issue of generating solutions stable to perturbations of the problem variables, without greatly increasing the runtime of the objective function, is also discussed. We describe a method for producing highly stable solutions with the DGA while increasing the run time of the objective function by a factor of only 4. No explicit term dealing with stability was added to the objective function.

Adaptive filters are systems in digital signal processing designed to work in environments with unknown or time-varying statistical characteristics — according to non-stationary stochastic signals. In order to achieve this capability the adaptive filter's adaptation algorithm has to be able to adapt the filter to a time-dependent error criterion. I.e., given a filter topology, the filter parameters have to be estimated on-line. In this paper, a comparative study of several evolutionary algorithms — evolution strategies (ES), genetic algorithms (GA) and micro-genetic algorithms (ΜGA) — is presented for the on-line adaptation of adaptive filters. The adaptive filter's task is to predict a time-discrete and non-stationary stochastic signal. This important problem arises in a variety of applications, e.g. stochastic signal estimation, system identification and echo cancellation. The evolutionary algorithms optimize the adaptive filter's parameters on-line, with one generation corresponding to one time step of the stochastic signal. Hence, the evolutionary algorithms' ability to adapt to rapidly changing and noisy environments and to track time-varying parameters is of special interest in this study.

The structural development of human settlements can be characterized as a complex highly feedbacketed process. The assumption that this process is governed by rather few fundamental laws stimulated a considerable research in the field of urban growth during the last decade. Aiming at the comprehension of the basic underlying dynamics different approaches from the field of self-organizing systems have been proposed. In this paper we present a “cellular model” of urban growth dynamics based on the work of White, Engelen and Uljee. As a starting point this model throws some light on the mechanism of urban growth. But even more important, it raises a lot of questions concerning the requirements for a sound modeling technique. One of these questions is how to assess the complex patterns produced by single simulation runs. Here we make especially use of fractal measures reducing the contained information to a manageable size. No doubt, this field of research is still in its infant state, and we are far from being able to hand a reliable tool to the decision maker. But promising results will stimulate future investigations which we hope will lead to a deeper insight into the nature of cities to improve the living conditions of their inhabitants.

A novel strategy for finding optimal solutions to complex problems with many competing requirements is proposed. It consists in a simultaneous optimization of the energy, cost or fitness function of the system itself, and of sub-systems of all sizes with an appropriate weight function. For various travelling salesman problems and spin glasses as well as for an example of a continuous-valued system (the optical multilayer problem) the corresponding Monte Carlo algorithm is shown to yield results superior to those obtained by previous optimization techniques.

Ant-Q is an algorithm belonging to the class of ant colony based methods, that is, of combinatorial optimization methods in which a set of simple agents, called ants, cooperate to find good solutions to combinatorial optimization problems. The main focus of this article is on the experimental study of the sensitivity of the Ant-Q algorithm to its parameters and on the investigation of synergistic effects when using more than a single ant. We conclude comparing Ant-Q with its ancestor Ant System, and with other heuristic algorithms.

Conventional artificial intelligent (AI) system have been criticized for its brittleness under hostile/dynamic changing environments. Therefore, recently much attention has been focused on the reactive planning systems such as behavior-based AI. However, in the behavior-based AI approaches, how to construct a mechanism that realizes adequate arbitration among competence modules is still an open question. In this paper, we propose a new decentralized consensus-making system inspired from the biological immune system. And we apply our proposed method to behavior arbitration of an autonomous mobile robot as a practical example. To verify the feasibility of our method, we carry out some experiments. In addition, we propose an adaptation mechanism, and try to construct a suitable immune network for adequate action selection.

An algorithm for approximately solving the maximum clique is presented which uses relaxation labeling neural network techniques, focusing on the continuous problem formulation: maximize a quadratic form over the standard simplex. We employ somewhat surprising connections of the latter problem with dynamic principles of evolutionary game theory, and give a detailed report on our numerical experiences with the method proposed.

This paper presents the results of a parameter study of the Grand Deluge Evolutionary Algorithm, whose special features consist of local interactions between individuals within a spatially structured population and a self-adjusting control mechanism of the selection pressure. Since both ingredients are parametrizable this study aims at the identification of the significance and sensitivity of the parameter settings with regard to the performance of the algorithm, especially under the transition from one- to two-dimensional neighborhood patterns.

A DNA-based biomolecular string processing scheme demonstrated by Adleman has attracted wide attention. While it is not known to what degree the scheme can scale up, it nevertheless introduces a new and interesting concept which seems so far to have been overlooked. The key point is that the Adleman scheme involves building specific hardware for a single problem instance. This opens a design degree of freedom that is not limited to biomolecular architectures.

Radial Basis Function (RBF) neural networks offer the possibility of faster gradient-based learning of neuron weights compared with Multi-Layer Perceptron (MLP) networks. This apparent advantage of RBF networks is bought at the expense of requiring a large number of hidden layer nodes, particularly in high dimensional spaces (the “curse of dimensionality”). This paper proposes a representation and associated genetic operators which are capable of evolving RBF networks with relatively small numbers of hidden layer nodes and good generalisation properties. The genetic operators employed also overcome the “competing conventions” problem, for RBF networks at least, which has been a reported stumbling block in the application of crossover operators in evolutionary learning of directly encoded neural network architectures.

In this paper, we present a three step method for designing Genetic Fuzzy Systems combining an iterative and increasing rule derivation stage and two genetic-based simplification and tuning processes. The performance of the method proposed is shown by measuring the accuracy of the Fuzzy Logic Controllers designed in the fuzzy modeling of two three-dimensional control surfaces and comparing them with others generated by using Wang and Mendel's method, one of the most widely known iterative rule derivation processes.

Ordered Binary Decision Diagrams (OBDDs) are the state-of-the-art data structure in CAD for ICs. OBDDs are very sensitive to the chosen variable ordering, i.e. the size may vary from linear to exponential.In this paper we present an Evolutionary Algorithm (EA) that learns good heuristics for OBDD minimization starting from a given set of basic operations. The difference to other previous approaches to OBDD minimization is that the EA does not solve the problem directly. Rather, it developes strategies for solving the problem.To demonstrate the efficiency of our approach experimental results are given. The newly developed heuristics are more efficient than other previously presented methods.

Based on Population-Based Incremental Learning (PBIL) we present a new approach for the evolution of neural network architectures and their corresponding weights. The main idea is to use a probability vector rather than bit strings to represent a population of networks in each generation. We show that crucial issues of neural network training can effectively be integrated into the PBIL framework. First, a Quasi-Newton method for local weight optimization is integrated and the moving average update rule of the PBIL is extended to continuous parameters in order to transmit the best network to the next generation. Second, and more important, we incorporate cross-validation to focus the evolution towards networks with optimal generalization performance. A comparison with standard pruning and stopped-training algorithms shows that our approach effectively finds small networks with increased generalization ability.

This paper presents a new approach to Genetic Programming (i.e. GP). Our goal is to realize robustness by means of the automatic discovery of functions. In traditional GP, techniques have been proposed which attempt to discover certain subroutines for the sake of improved efficiency. So far, however, the robustness of GP has not yet been discussed in terms of knowledge acquisition. We propose an approach for robustness named COAST, which has a library for storing certain subroutines for reuse. We make use of the Wall Following Problem to illustrate the efficiency of this method.

We describe a high-speed pattern recognition system using Evolvable Hardware (EHW), which can change its own hardware structure by genetic learning in order to adapt best to the environment. The purpose of the system is to show that EHW can work as a recognition device with such robustness for the noise as seen in the recognition systems based on neural networks. The advantage of EHW compared with a neural network is the high processing speed and the readability of the learned result. The readability means that the result is understandable in terms of Boolean functions. In this paper, we describe the architecture, the learning algorithm and the experiment on the pattern recognition system using EHW.

For many applications feedforward neural networks have proved to be a valuable tool. Although the basic principles of employing such networks are quite straightforward, the problem of tuning their architectures to achieve near optimal performance still remains a very challenging task. Genetic algorithms may be used to solve this problem, since they have a number of distinct features that are useful in this context. First, the approach is quite universal and can be applied to many different types of neural networks or training criteria. It also allows network topologies to be optimized at various level of detail and can be used with many types of energy function, even those that are discontinuous or non-differentiable. Finally, a genetic algorithm need not be limited to simply adjusting patterns of connections, but, for example, can be utilized to select node transfer functions, weight values or to find architectures that perform best under certain simulated working conditions. In this paper we have investigated an application of genetic algorithms to feedforward neural network architecture design. These neural networks are used to model a nonlinear, discrete SISO system when only noisy training data are available. Additionally, some incidental but nonetheless important aspects of neural network optimization, such as complexity penalties or automatic topology simplification are discussed.

We review recent research in Evolution Strategy (ES) operators with particular emphasis on improving convergence within small populations. We then report on the results of applying some of these operators in a problem domain where performance is critically dependent on population size and where the objective function is dynamic, i.e. changing shape as optimization proceeds. The ES must operate quickly and efficiently, acting as the exploration component of a larger on-line learning architecture. We found that the use of a derandomised mutation operator and intermediate recombination resulted in a considerable performance improvement.

The paper describes the application of a Parallel Genetic Algorithm to Automatic Test Pattern Generation (ATPG) for digital circuits. Genetic Algorithms have been already proposed to solve this industrially critical problem, both on mono- and multi-processor architectures. Although preliminary results are very encouraging, there are some obstacles which limit their use: in particular, GAs are often unable to detect some hard to test faults, and require a careful tuning of the algorithm parameters. In this paper, we describe a new parallel version of an existing GA-based ATPG, which exploits competing sub-populations to overcome these problems. The new approach has been implemented in the PVM environment and has been evaluated on a workstation network using standard benchmark circuits. Preliminary results show that it is able to improve the results quality (by testing additional critical faults) at the expense of increased CPU time requirements.

In this paper, we present the constraint handling techniques developed to tackle a real world optimization application: the frequency assignment problem (FAP) in cellular radio networks. The main goal of this application consists in finding assignments which minimize electromagnetic interference due to frequency reuse and minimize the number of frequencies used. An acceptable assignment of the FAP must satisfy a set of multiple constraints such as traffic constraints and interference constraints. We present how each type of constraint can play a different role in EAs. In particular, we show how co-station constraints can be used to reduce the search space efficiently. The effectiveness of the constraint handling techniques combined with a regeneration technique is tested on big and hard FAP instances. Results show that limiting the degree of unfeasible solutions is beneficial for this application.

This paper presents an effective strategy to schedule fossilfuel power plant systems with so-called power-heat coupling. Due to the simultaneous production of electricity, heat and steam such systems reach a higher efficiency than pure electric power plants. The goal is to minimize the total costs for the production of the predicted load demand of the next day. We employ a genetic algorithm to determine the unit commitment, while the economically optimal load distribution among the operating units is performed by a conventional constraint optimization method. Our approach is based on exact thermodynamic simulations of the unit efficiency, taking into account the current plant state and environmental conditions. In order to make this high modeling precision available within short computation times we employ neural networks for the storage and interpolation of simulation data.

The prediction of electron distributions in semiconductor devices is compulsory for the design of modern computer chips. In spite of increasing computation facilities the calculation of electron distributions at high energies is difficult resulting in significant deviations between theoretical predictions and measurement results. With evolutionary algorithms, however, it is possible to search for electron distributions which fit to experimental results and in this way backward calculate the distribution from measurements. Hereby the possibility to support the optimization of the evolutionary algorithm by a physical mutation operator which modifies individuals due to physical rules is important. This new approach was applied to the calculation of electron distributions and gate currents in Si-MOSFETS. The results demonstrate that the combination of physical model and evolutionary optimization is an interesting tool to compare theoretical models with experimental results.

An evolutionary algorithm is applied to the refueling of a nuclear power plant. Refueling plans so far are designed by experts on the basis of the experience and intuition. An automatization of this process is desirable because of its high commercial and scientific interest. We develop an appropriate fitness function and parallelize the optimization process. The focal point of this paper is the comparison of two mutation operators: a naive operator, and one in which more problem specific knowledge, in particular knowledge about the symmetry of the problem, is incorporated. The latter operator reduces the search space considerably. This specialization involves the risk of excluding the best solutions from consideration. We expound a method by which to acquire some certainty that this is not the case. The method also shows how the specialized mutation operator smoothes the search space. Finally, it allows a rough estimate of the best fitness value. At this time, refueling plans found by the algorithm compare favorably with those developed by experts, but they do not yet reach the estimated optimal fitness.

Electronic design automation is concerned with the design and production of VLSI systems. One of the important steps in creating a VLSI circuit is its physical design. The input to the physical design step is a logical representation of the system under design. The output of this step is the layout of a physical package that optimally or near-optimally realizes the logical representation. Physical design problems are generally combinatorial in nature and have very large problem sizes. In this paper we review genetic algorithms for physical design and observe and analyze the common traits of the superior contributions. For example, many of these investigations use genetic operators that incorporate expert knowledge. We believe this review can stimulate and steer further applications.

The performance of a CMOS circuit depends heavily on its transistor sizes. We have tested a standard optimizer, a Monte Carlo scheme and a method based on Genetic Algorithms combined with very accurate SPICE simulations to automatically optimize transistor sizes of three different digital CMOS circuits. While the standard optimizer and the Monte Carlo scheme are advantageous for small circuits, the method based on Genetic Algorithms was found to be more stable for larger circuits.

The generation of a high quality layout during the design of a VLSI microchip is a very complex combinatorial optimization problem. Components of a circuit have to be placed, and signal nets have to be routed on an overall minimal area. In this paper a parallel Genetic Algorithm for the combined optimization of placement and routing is presented. The main focus is on the self-adaptation of the search process: Several islands execute a sequential GA with different strategies. At fixed intervals these strategies are ranked and each strategy is adjusted to the next better one by assimilating its characteristical parameters.

We present a first attempt in applying a genetic algorithm for checking the correctness of communication protocols (expressed as a pair of communicating FSMs). The GA measures the fitness of a given string by making use of a protocol simulator. Every string in the population is a trace of the execution of the protocol. The simulator evaluates the trace by running it, provoking changes and messages exchanges in the states of every FSM. The fitness of a string (trace) is high if the string detects a deadlock or if useless states or transitions are encountered. We are interested in testing the suitness of the GA search in such a domain. We have tested this genetic validation on a hand-made protocol and on the Transmission Control Protocol (TCP).

Real world problems quite often are constrained and their successful solution requires the application of an appropriate constraint handling technique. The lack of a uniform methodology for handling nonfeasible points largely predetermines the current best practice — the investigation of some problem-specific operators which search (within) the feasibility boundary in an efficient way. In this paper we apply this approach to a real world problem provided by Rolls Royce and Associates Ltd., and show how to design feasibility preserving operators that map the feasibility region onto itself. Some of our results provoke new ideas of how to modify real-time test and monitoring systems so as to increase their reliability.

In this paper, an approach is presented to incorporate problem specific knowledge into a genetic algorithm which is used to compute near-optimum solutions to traveling salesman problems (TSP). The approach is based on using a tour construction heuristic for generating the initial population, a tour improvement heuristic for finding local optima in a given TSP search space, and new genetic operators for effectively searching the space of local optima in order to find the global optimum. The quality and efficiency of solutions obtained for a set of TSP instances containing between 318 and 1400 cities are presented.

In this paper, we present an approach to hardware/software codesign of real-time embedded systems. Two of the difficulties associated with codesign are handling tradeoffs among multiple attributes and exploring a large design space. We use a combination of techniques from the evolutionary computation and utility theory fields to address these problem areas. A real-time microcontroller-based design example is presented to illustrate our approach.

We present an evolutionary tool to solve free-route Air Traffic Flow Management problems within a three-dimensional air space [4]. This is the first evolutionary tool which solves free-route planning problems involving a few hundred aircraft. We observe that the importance of the recombination operator increases as we scale to larger problem instances. The evolutionary algorithm is based on a variant of the elitist recombination algorithm. We show a theoretical analysis of the problem, and present the results of experiments.

This paper presents an adaptive dynamic load balancing scheme employing a genetic algorithm which includes an evaluation mechanism of fitness values in stochastic environments. A sender-initiative task migration algorithm continues to send unnecessary requests for a task migration while the system load is heavy, which brings much overhead before the migration finishes. In a genetic-based dynamic load balancing scheme we propose, a small subset of computers to which the requests are sent off is adaptively determined by a learning procedure to reduce unnecessary requests. The learning procedure consists of stochastic learning automata and genetic operators applied to a population of strings each of which stands for a subset of computers to which task migration requests are sent off. We implement the proposed algorithm on an actual distributed system which consists of UNIX workstations. We show the effectiveness of our approach through empirical investigations on the distributed system.

A real-world application which develops daily production plans for a large manufacturing company is presented. It is a hybrid system, which combines a genetic algorithm with simulation. Because of the time constraints involved when generating daily schedules, a number of modifications to the standard genetic algorithm were required. A real-valued chromosome representation stored in a hierarchical, dynamic data structure is proposed. Steady-state, rank-based selection, a two-point order crossover and a simple, order-based mutation were implemented. An adaptive feedback controller was introduced to vary the mutation rate as a function of population convergence. Integration of a tabu list minimizes time wasted reevaluating known solutions. A rank-based fitness function is proposed to handle multiple, competing objectives.

Network optimization which has to consider both the connection distance (detour) between different nodes and the total length (costs) of the network, belongs to the class of frustrated optimization problems. Here, evolutionary strategies which include both thermodynamic and biological elements, are used to find different optimized solutions (graphs of varying density) for the network in dependence on the degree of frustration. We show, that the optimization process occurs on two different time scales, and that in the asymptotic limit a a fixed relation between the mean connection distance (detour) and the total lenght (costs) of the network exist.

Random numbers are needed in a variety of applications, yet finding good random number generators is a difficult task. In the last decade cellular automata (CA) have been used to generate random numbers. In this paper non-uniform CAs are studied, where each cell may contain a different rule, in contrast to the original, uniform model. We present the cellular programming algorithm for co-evolving non-uniform CAs to perform computations, and apply it to the evolution of random number generators. Our results suggest that good generators can be evolved; these exhibit behavior at least as good as that of previously described CAs, with notable advantages arising from the existence of a “tunable” algorithm for obtaining random number generators.

In this paper, multi-step crossover (MSX) and a local search method are unified as a single operator called MSXF. MSX and MSXF utilize a neighborhood structure and a distance measure in the search space. In MSXF, a solution, initially set to be one of the parents, is stochastically replaced by a relatively good solution in the neighborhood, where the replacement is biased toward the other parent. After a certain number of iterations of this process, the best solution from those generated is selected as an offspring. Using job-shop scheduling problem benchmarks, MSXF was evaluated in a GA framework as a high-level crossover working on the critical path of a schedule. Experiments showed promising performance for the proposed method.

Finding the optimal conformation for fluorescent labeled nucleosides is difficult for standard GAs. We investigated the structure of molecule and of the resulting search space itself and concluded that the problem is of the “needle in the haystack” type.Using niching and island models and a crossover operator adapted to the underlying problem, the GA was able to find the global optimum. Each of these improvements increased the probability to find the global optimum from 0% (standard GA) to ∼30%. The combination of either niching + island model, or graph crossover + island model, increased the probability up to 80%; the combination of all three methods up to 90%.

Breeder Genetic Algorithms represent a class of random optimisation techniques gleaned from the science of population genetics, which have proved their ability to solve hard optimisation problems with continuous parameters. In this paper we test a parallel version of this technique against a sequential Breeder Genetic Algorithm on a typical inverse design problem in Aerodynamics, the problem of an aerofoil geometry recover starting from a target pressure distribution. Our results show that Parallel Breeder Genetic Algorithms are well suited for applications in Aerodynamics.

In this paper, we tried evolutionary designs of f-θ lenses for a laser printer or a digital copier with a real-valued GA (NDX: Normal Distributed Crossover) and a genotype GA with high mutation. The f-θ lens represented by a B-Spline curve refract a laser beam reflected from rotating mirror to scan a photo sensitive drum with a constant velocity. Fitness is evaluated by accumulated errors between destinations of ray traces and given targets. We compared the performances of two evolutionary methods. Empirical results show that the real-valued GA has converged faster with better accuracy than the genotype GA for the f-θ lens design problem with strong epistasis.

This paper describes the adaptation of Evolution Strategies (ESs) for simulation based heat exchanger network synthesis. Due to space limitations the presentation is restricted to a brief overview of the application domain, the problems and pitfalls we encountered during the project and hints to solutions. Some of these problems are of general relevance for the application of Evolutionary Algorithms in cases where the objective function is based on a simulation model and are therefore discussed in more detail. The emphasis lies on the design of a suitable genetic representation.

The pipe-route design problem for heavy industrial plant concerns minimising pipe material cost while satisfying constraints on required interconnections and obstacle avoidance. This process is invariably done by human experts, but modern stochastic iterative search techniques allow the opportunity to automate this process. This study explores the possibility of automated industrial pipe-route design on three test problems, using stochastic hillclimbing, simulated annealing, and genetic algorithms. The representation strategy is explained and discussed, and results are presented which show great promise for genetic algorithms in particular in this application area.

The concept of an evolutionary algorithm for improving the design optimization process is presented. A first application, the design optimization of a micropump, is used for both, the description of the concept being especially tailored for multicriteria applications and the presentation of very promising results.The behavior of the micropump is formulated as an analog model including the various domains as there are electrical, thermal, and pneumatic phenomena. The parameters of this model are modified with the proposed evolutionary algorithm until a satisfactory behavior of the system is reached. The quality of the optimization depends highly on the quality of the simulation model at hand, therefore we give in addition an outlook of an evolutionary algorithm for improving the analog simulation model by using FEM results.

A learning classifier system complex is developed in order to accomplish the broader goal of developing a methodology to perform generalized zeroth-order two- and three-dimensional shape optimization. Specifically, the methodology has the objective of determining the optimal boundary to minimize mass while satisfying constraints on stress and geometry. Even with the enormous advances in shape optimization no method has proven to be satisfactory across the broad spectrum of optimization problems facing the modern engineer. Similarly the available software in the field of learning classifier systems is so embryonic that a new software package had to be developed for this application. The shape optimization via hypothesizing inductive classifier system complex (SPHINcsX) instantiates the methodology in a software package overcoming many of the limitations of today's conventional shape optimization techniques, while advancing the state-of-the-art in classifier system software tools.