7 NEG UY yn ar retapons ue er aig v7 Ya A elated [lal hitedPublished by World Scientific Publishing Co, Pte. Ltd. POBox 128, Farrer Road, Singapore 912805 USA office: Suite 1B, 1060 Main Street, River Edge, NJ 07661 UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE. British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. EVOLUTIONARY COMPUTATION: THEORY AND APPLICATIONS Copyright © 1999 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher. For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc.,222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher. ISBN 981.02-2306-4 Printed in Singapore.Contents PHC ..0 orien eceneieniieeniecomeineniesieiiuntieie castes aininaneinn nneeienieeceietie v Acknowledgements ............... secs eee eeee cece eee eee ee eee ee vii List of Contributors .. 1 Introduction X_Yao 1 2 Evolutionary Computation in Behavior Engineering MM. Colombetts anil: Mo Dong sis asicciwsxvansistonissiniewinsiaiaiisicind 37 3_A General Method for Incremental Self-improvement and Multi-agent Learning _ Schmit wae 4 Teacher: A Genetics-Based System for Learning and for Gen- eralizing Heuristics B. W. Wah and A. Ieumwananonthachai ............... 646+ 124xiv Contents 5 Automatic Discovery of Protein Motifs Using Genetic Pro- 6 The Role of Self Organization in Evolutionary Computations Ae CVG GIES SROO eqpecapemgcemcavexmensmoaves onary 198 7 Virus-Evolutionary Genetic Algorithm and Its Application to Traveling Salesman Problem T. Fukuda, N. Kubota, and K. Shimojima .........+..000005 235 8 Hybrid Evolutionary Optimization Algorithm for Constrained Problems STi eas Grd EA . a ccnctas sin este iniauee sm meannenae ie 256 9 CAM-BRAIN — The Evolutionary Engineering of a Billion Neuron Artificial Brain BGO GOS cmos nsonnunesassempnenssinionssiamamecenasienesnins 296 10 An Evolutionary Approach to the N-Player Iterated Pris- oner’s Dilemma Game X. Yao and P. Darwen ......:cceecesecsssscevsccsssveeseces 331 Index 359Chapter 1 Introduction X. Yao 1.1. What Is Evolutionary Computation Evolutionary computation is the study of computational systems which use ideas and get inspiration from natural evolution and adaptation. It aims at understanding such computational systems and developing more robust and efficient ones for solving complex real-world problems. The problems dealt with by such computational systems are usually highly nonlinear and contain inaccurate and noisy data. Traditional computational systems are good at accurate and exact computation but brittle. They are not designed for processing inac- curate, noisy and complex data although they might excel at dealing with complicated data. For example, the classical simplex method is an invaluable mathematical programming technique which has been ap- plied to numerous practical problems successfully. However, it requires a problem to be formulated in exact and accurate mathematical forms. It does not work well for problems where the objective function cannot be expressed mathematically, is noisy, and changes with time. Evolu- tionary computation is a field where such problems will be studied in depth. It complements the study of traditional computational systems. Many evolutionary computation techniques get their ideas and inspi- rations from molecular evolution, population genetics, immunology, etc. 12 X. Yao Some of the terminologies used in evolutionary computation have been borrowed from these fields to reflect their connections, such as genetic algorithms, genotypes, phenotypes, species, etc. Although the research in evolutionary computation could help us understand some biological phenomena better, its primary aim is not to build biologically plausible models. There is no requirement in evolutionary computation that a technique developed must be biologically plausible. The primary aim is to study and develop robust and efficient computational systems for solving complex real-world problems. Evolutionary computation is an emerging field which has grown rapidly in recent years. There are at least two international journals which are dedicated to this field: IEEE Transactions on Evolutionary Computation and Evolutionary Computation (MIT Press). Other jour- nals which have a large evolutionary computation component include IEEE Transactions on Systems, Man, and Cybernetics and BioSystems (Elsevier). There are also many international conferences on evolution- ary computation held each year, such as the annual JEEE International Conference on Evolutionary Computation, Evolutionary Programming Conference and Genetic Programming Conference, and bi-annual Inter- national Conference on Genetic Algorithms, International Conference on Parallel Problem Solving from Nature, and Asia-Pacific Conference on Simulated Evolution and Learning. 1.1.1. A Brief History Evolutionary computation encompasses several major branches, i.e., evolution strategies, evolutionary programming, genetic algorithms and genetic programming, due largely to historical reasons. At the philo- sophical level, they differ mainly in the level at which they simulate evolution. At the algorithmic level, they differ mainly in their rep- resentations of potential solutions and their operators used to modify the solutions, From a computational point of view, representation and search are two key issues. This book will look at their differences more at the algorithmic level than at the philosophical level. Evolution strategies were first proposed by Rechenberg and Schwefel in 1965 as a numerical optimisation technique. The original evolution strategy did not use populations. A population was introduced intoChapter 1. Introduction 3 evolution strategies later [1, 2]. Evolutionary programming was first proposed by Fogel et al. in mid 1960’s as one way to achieve artificial intelligence [3]. Several exam- ples of evolving finite state machines were demonstrated [3]. Since late 1980’s, evolutionary programming was also applied to various combina torial and numerical optimisation problems. The current framework of genetic algorithms was first proposed by Holland [4] and his students [5] in 1975 although some of the ideas ap- peared as early as 1957 in the context of simulating genetic systems [6]. Genetic algorithms were first proposed as adaptive search algorithms, although they have mostly been used as a global optimisation algorithm for either combinatorial or numerical problems. They are probably the most well-known branch of evolutionary computation. A special sub-branch of genetic algorithms is genetic programming. Genetic programming can be regarded as an application of genetic algo- rithms to evolve tree-structured chromosomes. Historically, those trees represent LISP programs. The term of genetic programming was first used by Koza in the above sense [7, 8]. de Garis used the term of ge- netic programming to mean a quite different thing. He regarded genetic programming as the genetic evolution of artificial neural networks [9]. This book will follow Koza’s explanation of genetic programming since de Garis is no longer using the term. In recent years, a general term of evolutionary algorithms has been used by more and more researchers to include all three major algo- rithms, i.e., evolution strategies, evolutionary programming and genetic algorithms, since they use almost the same computational framework. This is the view taken by this book. 1.1.2 A General Framework of Evolutionary Algorithms All evolutionary algorithms have two prominent features which dis- tinguish themselves from other search algorithms. First, they are all population-based. Second, there is communications and information exchange among individuals in a population. Such communications and information exchange are the result of selection and/or recombination in evolutionary algorithms. A general framework of evolutionary algo- rithms can be summarised by Figure 1.1, where the search operators are4 X. Yao also called genetic operators for genetic algorithms. They are used to generate offspring (new individuals) from parents (existing individuals). 1. Set i = 0; 2. Generate the initial population P(i) at random; 3. REPEAT (a) Bvaluate the fitness of each individual in P(i); (b) Select parents from P(i) based on their fitness; (c) Apply search operators to the parents and produce gen- eration P(i + 1); 4. UNTIL the population converges or the maximum time is reached Figure 1.1: A General Framework of Evolutionary Algorithms. Obviously Figure 1.1 specifies a whole class of algorithms, not any particular ones. Different representations of individuals and different schemes for implementing fitness evaluation, selection and search oper- ators define different algorithms. 1.1.3 Evolution Strategies For evolution strategies [2, 10], the representation of individuals is often very close to a problem's natural representation. It does not emphasise the genetic representation of individuals. For example, an individual is represented as a vector of real numbers rather than a binary string for numerical optimisation problems. Evolution strategies usually use a deterministic selection scheme, Gaussian mutation, and discrete or intermediate recombination. The term crossover is seldom used in the context of evolution strategies because evolution strategies do not sim- ulate evolution at the genetic level.on Chapter 1. Introduction There are two major deterministic selection schemes in evolution strategies [1, 2], i.c., (A+) and (4,4) where y is the population size (which is the same as the number of parents) and \ the number of offspring generated from all parents. In (\ + ;4) evolution strategies, ) offspring will be generated from p parents. The p fittest individuals from + js candidates will be selected to form the next generation. In (A, 4) evolution strategies, the p fittest individuals from \ offspring only will be selected to form the next generation. As a result, A > p is required. Mutation in evolution strategies is often implemented by adding a Gaussian random number to a parent. Assume x = (2), 22,...,Zn) isa parent (individual), then an offspring will be generated by mutation as follows: i+ N;(0,0;) (1.1) where N,(0,0;) is a normally distributed random number with mean 0 and standard deviation o;. The n random numbers are generated independently. One important parameter in the Gaussian mutation is the standard deviation, o;. Its selection is quite important in determining the per- formance of evolution strategies. Unfortunately, its optimal value is problem dependent as well as dimension dependent. Schwefel [1] pro- posed to include o;’s as part of an individual so that it can be evolved automatically. This is often called self-adaptation in evolution strate- gies. It is one of the major differences between evolution strategies and genetic algorithms. In many implementations, o;’s will be mutated first, and then 2; is mutated using the new oj. Mutating different components of an vector independently may not be appropriate for some problems because those components may not be independent at all. To address this issue, co-variance has been intro- duced as another additional part of an individual. It is unclear at this stage whether such self-adaptation is beneficial for most problem as the search space will be increased exponentially as we triple (at least) the individual size. Further work will be necessary in this area. Recombination in evolution strategies takes two major forms, i.e., discrete and intermediate recombinations. Discrete recombination mixes components of two parent vectors. For example, given two parents x = (21,22,...,2n) and y = (yi,Y2,-.-,Yn). The offspring x’ =6 X. Yao (24, 25,...,2,) and y’ = (yj,4y5,-.-,y)) can be generated as follows: vl =) ti with probability Precombination * yi otherwise y’ will be the complement of x’. Intermediate recombination is usually based on some kind of aver- aging. For example, given two parents x = (21,22,...,2,) and y = (y1,¥25-+-, Ym). The offspring x” = (x1, 23,...,2),) and y! = (yf, vp --) Yn) can be generated as follows: a= ai talyi — 2) where a is a weighting parameter in (0,1). It is traditionally set to 0.5. It can also be generated at random. y’ can be generated similarly. According to the description by Back and Schwefel [11], a (j,) evolution strategy can be implemented as follows: 1. Generate the initial population of y individuals, and set k = 1. Each individual is taken as a pair of real-valued vectors, (x;, 7), Vi € {1,-+-,}, where 7 plays the role of o (i.e, the standard deviation). 2. Evaluate the fitness value for each individual (x;,;), Vie {1,--- 2}, of the population. 3. Each parent (x,,7;),i = 1,---,, creates \/ offspring on average, so that a total of A offspring are generated: for i = 1,---,p, J=1,--+,n, and k=1,---,A, ne(3) exp(7N(0,1) + 7N;(0, 1)) (1.2) xi(9) + ni'(9)Nj(0, 1) (1.3) where x,(j), xx'(j), ni(j) and m'(j) denote the j-th component of the vectors x;, x;’, 7 and n,’, respectively. N(0,1) denotes a normally distributed one-dimensional random number with mean zero and standard deviation one. Nj(0,1) indicates that the ran- dom number is generated anew for each value of j. The factors T -T 7: and 7’ are usually set to ( a) and (v3n) 7 (11). I m' (3) xx'()Chapter 1. Introduction 7 4, Evaluate the fitness of each offspring (xi’, ni’), Vie {1,--- A}. 5. Sort offspring (x;', 7’), Vi € {1,---, A} into a non-descending order according to their fitness values, and select the best offspring out of d to be parents of the next generation. 6. Stop if the stopping criterion is satisfied; otherwise, k = k +1 and go to Step 3. 1.1.4 Evolutionary Programming When used for numerical optimisation, evolutionary programming [3, 12, 13] is very similar to evolution strategies in terms of algorithm. It uses vectors of real numbers as individuals, Gaussian mutation and self- adaptation as described above. The most noticeable differences between evolutionary programming and evolution strategies are recombination and selection. Evolutionary programming does not use any recombi- nation or crossover, but uses a probabilistic competition (i.e., a kind of tournament selection) as the selection mechanism. Of course, there is no reason why evolutionary programming cannot have recombination and why evolution strategies cannot have a probabilistic selection scheme from the algorithmic point of view. The origins of evolutionary programming and evolution strategies are quite different. Evolutionary programming was first proposed to simulate intelligence by evolving finite state machines, while evolution strategies were proposed to optimise numerical parameters. It was un- clear how recombination could be usefully applied to finite state ma- chines. According to the description by Back and Schwefel [11], evolutionary programming can be implemented as follows: 1. Generate the initial population of » individuals, and set k = 1. Each individual is taken as a pair of real-valued vectors, (x;,7), Vi € {1,---,p}, where x;’s are objective variables and 7,’s are standard deviations for Gaussian mutations. 2. Evaluate the fitness score for each individual (xj, ni), Wie {1,--> ye}, of the population.8 X. Yao 3. Each parent (x;, nj), i = 1,-++, 2, creates a single offspring (x;',7;’) by: for j =1,---,n, ni) = m(j)exp(r'N(O, 1) + 7N;(0,1)) (1.4) (5) e4(3) + m'(3)Nj(0, 1), (1.5) where 2;(j), 2i'(7), ni(j) and m!(j) denote the j-th component of the vectors x;, x;', m and 7’, respectively. N(0,1) denotes a normally distributed one-dimensional random number with mean 0 and standard deviation 1. N;(0,1) indicates that the random number is generated anew for each value of j. The factors 7 and i ne 7! have commonly set to ( avn) and (Vn) (11, 14). 4. Calculate the fitness of each offspring (x,’,7;’), Vi € {1,--+, 4}. . Conduct pairwise comparison over the union of parents (x;, 7) and offspring (x;',7'), Vi € {1,--+,}- For each individual, q opponents are chosen uniformly at random from all the parents and offspring. For each comparison, if the individual’s fitness is no smaller than the opponent’s, it receives a “win.” a 6. Select the yz individuals out of (x;,7j) and (x;', i’), Vi € {1,---, 2}, that have the most wins to be parents of the next generation. 7. Stop if the halting criterion is satisfied; otherwise, k = k +1 and go to Step 3, 1.1.5 Genetic Algorithms Genetic algorithms [4, 15, 16] are quite different from evolution strate- gies and evolutionary programming in terms of individual representation and search operators. Genetic algorithms emphasise genetic encoding of potential solutions into chromosomes and apply genetic operators to these chromosomes. This is equivalent to transforming the original problem from one space to another space. It is obvious that the genetic representation will be crucial to the success of genetic algorithms. A good representation will make a problem easier to solve. A poor repre- sentation will do the opposite. The issues faced by genetic algorithmsChapter 1. Introduction 9 in general are the same as those which have haunted many artificial intelligence problems for years, i.e., representation and search. In other words, a crucial issue in applying genetic algorithms to a problem is how to find a representation which can be searched efficiently. A canonical genetic algorithm (also called simple genetic algorithm sometimes) [15] is the one which uses binary representation, one point crossover and bit-flipping mutation. Binary representation means that each individual will be represented by a number of binary bits, 0 or 1. One point crossover is carried out as follows: Given two binary strings, x and y, of length n. Generate a crossover point between 1 and n-—1 (inclusively) uniformly at random, say r. Then the first offspring consists of the first r bits of x and the last n — r bits of y. The second offspring consists of the first r bits of y and the last n — r bits of z. Mutation is carried out bit-wise. That is, every bit of an individual has certain probability of being flipped from 0 to 1 or from 1 to 0. A canonical genetic algorithm can be implemented as follows: 1. Generate the initial population P(0) at random and set i = 0; 2. REPEAT (a) Evaluate the fitness of each individual in P(i). (b) Select parents from P(i) based on their fitness as follows: Given the fitness of n individuals as f1, fo,..., fn. Then se- lect individual i with probability __fi SG This is often called roulette wheel selection of fitness propor- tional selection. (c) Apply crossover to selected parents; (d) Apply mutation to crossed-over new individuals; (e) Replace parents by the offspring to produce generation P(i+ 1) 3, UNTIL the halting criterion is satisfied10 X. Yao 1.1.6 Other Topics in Evolutionary Computation There are numerous variants of classical evolution strategies, evolution- ary programming and genetic algorithms described above. Some of the evolutionary algorithms can hardly be classified into any of these three categories. Evolutionary computation includes much more than just three kinds of algorithms. It also covers topics such as artificial immune systems, artificial ecological systems, co-evolutionary systems, evolvable hardware, self-adaptive systems, etc. 1.2 A Brief Overview of Evolutionary Compu- tation The current research and development in evolutionary computation can be classified into three major areas, i.e., evolutionary computation the- ory, evolutionary optimisation and evolutionary learning. There are, of course, overlaps among these areas. 1.2.1 Evolutionary Computation Theory The theoretical work in evolutionary computation has concentrated on three main topics. The first one is the theoretical analysis of conver- gence and convergence rate of evolutionary algorithms. There has been some work on the convergence and convergence rate of evolution strate- gies (1, 2, 17], evolutionary programming [18, 13] and genetic algorithms [19, 20, 21, 22, 23, 24, 25]. They are very general results which describe the asymptotic behaviour of certain class of evolutionary algorithms un- der different conditions. However, few of them studied the relationship between the convergence rate and the problem size. The second main topic in evolutionary computation theory is the study of problem hardness with respect to evolutionary algorithms. That is, the aim is to investigate what kind of problems is hard for evolutionary algorithms and what is easy for them. If we knew the characteristics of a problem which make evolutionary algorithms hard or easy to solve, we would be able to better understand how and when evolutionary algorithms would work. This will be of enormous practi- cal value in addition to of theoretical interest. Centered around thisChapter 1. Introduction u topic, there was some work on genetic algorithm deceptive problems (15, 26, 27]. Such work tried to characterise problems that are hard for genetic algorithms to solve as deceptive. It has been pointed out that this approach is rather problematic [28]. There have been other approaches to the understanding of what make a problem hard for ge- netic algorithms, such as building block and schema analysis [4, 15, 29], Walsh analysi based on Walsh functions (30], fitness landscape analysis (31, 32] and fitness distance correlation [33], etc. All these approaches have made certain progress towards a better understanding of how ge- netic algorithms work, but there is still a long way to go to gain a full understanding of how and when a genetic algorithm would work. The third main topic in evolutionary computation theory is compu- tational complexity of evolutionary algorithms. This is one of the most important research topics where little progress has been made. Evo- lutionary algorithms have been used extensively in both combinatorial and numerical optimisation in spite of the original emphasis on search and adaptation [3, 4, 34, 35]. There are established algorithms and their complexity results for many of these optimisation problems. However, it is unclear whether evolutionary algorithms can perform any better than other approximate or heuristic algorithms in terms of worst or av- erage time complexity. There has not been any concrete result on the computational complexity of an evolutionary algorithm on a nontrivial problem, especially a combinatorial problem, although the complexity theory is well established for combinatorial decision and optimisation problems [36]. 1.2.2. Evolutionary Optimisation Evolutionary optimisation is probably the most active and productive area in evolutionary computation measured by the number of papers published and the number of successful applications reported. Although neither evolutionary programming nor genetic algorithms were first pro- posed as optimisation algorithms, people had quickly realised they could adapt these algorithms to carry out combinatorial and function optimi- sation. Hence a flood of variants of classical algorithms were proposed and applied to different optimisation problems. So far most of the evolutionary optimisation work belongs to numer-12 X. Yao ical optimisation. Both constrained (37, 38] and unconstrained [39, 40] numerical optimisation has been studied. There has also been research on multiobjective optimisation by evolutionary algorithms [41, 42, 43]. When genetic algorithms are applied to numerical function optimisa- tion, vectors of real numbers are usually encoded into binary bit strings. Different binary encoding methods have been proposed, such as Gray coding [15] and delta coding [44]. Delta coding actually changes the representation during search. In spite of all these efforts in finding the best encoding method for real numbers, it is still unclear whether it is necessary to transform real numbers into binery strings. Evolution strategies and evolutionary programming use vectors of real numbers directly as individuals and thus avoid the burden of find- ing a suitable encoding method for individuals. There have been some comparative studies between the binary representation used by genetic algorithms and the real representation used by evolutionary program- ming [45, 46]. However, more extensive comparisons need to be carried out to test the performance of different algorithms and find out why an algorithm performs well (or poorly) for certain problems. In addition to numerical optimisation, evolutionary algorithms have also been used to tackle various combinatorial optimisation problems, such as the travelling salesman problem [47, 48, 49], transportation problem {50, 51), switchbox routing in integrated circuits [52], cutting stock problem [53, 54], lecture room assignment problem [55], etc. Some of these results are quite competitive in comparison with more tradi- tional approaches. In particular, hybrid algorithms which combine evo- lutionary algorithms with others (such as simulated annealing [56] and local search methods [57]) have shown a lot of promises in dealing with hard combinatorial optimisation problems. 1.2.3 Evolutionary Learning Evolutionary learning includes many topics, such as learning classifier systems, evolutionary artificial neural networks, co-evolutionary learn- ing, self-adaptive systems, etc. The primary goal of evolutionary learn- ing is the same as that of machine learning in general. Evolutionary learning can be regarded as the evolutionary approach to machine learn- ing. It has been used in the framework of supervised learning, reinforce-Chapter 1. Introduction 13 ment learning and unsupervised learning, although it appears to be most promising as a reinforcement learning method. Learning Classifier Systems Learning classifier systems [58, 59], also known as classifier systems, are probably the oldest and best known evolutionary learning systems, although they did not work very well in their classical form {60]. Some of the recent systems have improved this situation (61, 62]. Due to its historical importance, a brief introduction to the classical learning classifier system [58, 59] will be presented here. Learning classifier systems are a particular class of message-passing, rule-based systems [59]. They can also be regarded as a type of adaptive expert system that uses a knowledge base of production rules in a low- level syntax that can be manipulated by a genetic algorithm [63]. In a classifier system, each low-level rule is called a classifier. A classifier system proposed by Holland can be described by Figure 1.2 [59]. The general operational cycle for the classifier system is as follows: 1. Allow the detectors (input interface) to code the current environ- ment status and place the resulting messages on the message list. 2. Determine the set of classifiers that are matched by the current messages. 3. Resolve conflicts caused by limited message list size or contradic- tory actions. 4. Remove those messages which match the conditions of firing clas- sifiers from the message list. 5. Add the messages suggested by firing messages to the list 6. Allow the effectors (output interface) that are matched by the current message list to take actions in the environment. 7. If a payoff signal is received from the environment, assign credit to classifiers. 8. Goto Step 1.14 X. Yao Message List Rule List match ———— ee | output post Message Bucket brigade V Input interface (adjusts rule strengths) ‘Output interface detectors Genetic algorithm effectors (generates new rules) K Payoff Environment ——— Figure 1.2: An overview of a classifier system [59].Chapter 1. Introduction 15 Each rule is a simple message processor: Conditions look for certain kinds of messages and, when the conditions are satisfied, the action specifies a message to be sent. Messages are normally coded by symbolic strings. The alphabet of the symbols is {0,1, #}, where # is a “don’t care” symbol which matches cither 1 or 0. For example, 144 matches any length 4 messages starting with 1. An example of classifier can be described as: condition-1, condition-2 / action (message) [strength] lls 10010010 = / 00101101 (56) One message is more specific than another if its condition is more specific than another’s. One condition is more specific than another if the set of messages that satisfy the one is smaller than the set of messages that satisfy the other. The usefulness of a classifier is determined by its strength and up- dated by the credit assignment scheme, which is based on its average usefulness in the contexts in which it has been tried previously. All classifiers whose conditions are satisfied have to compete for the right to post their messages. Competition provides a simple, situation- dependent means of resolving conflicts between classifiers. The actual competition is based on a bidding process. The bid can be treated as some proportion of the classifier’s strength. The bid ratio is determined by the number of specific bits divided by the total number of bits in a message. That is, the competition favours more specific classifiers. An important feature of classifier systems is the possible adaptive formation of default hierarchies, i.e., layered sets of default and excep- tion rules. A classifier system organises default hierarchies by favouring exception rules over defaults in its conflict resolution and credit assign- ment schemes. The simplest example of a classifier hierarchy consists of only two classifiers: 1. The first (“default”) one has a relatively unspecific condition and provides action that is correct in most cases and incorrect some- times. 2. The second (“exception”) one is satisfied only by a subset of the messages satisfying the first classifier and its action generally cor- rects errors committed by the first classifier.16 X. Yao The specific classifier both provides the correct action and saves the general classifier from a mistake when it prevents the general classifier from winning. The exception classifier may in tu make mistakes that can be corrected by even more specific classifiers, and so on. Such default hierarchies can be learned by the classifier system. Credit assignment is a very difficult task because credit must be assigned to early-acting classifiers that set the stage for a sequence of actions leading to a favourable situation. The most famous credit as- signment algorithm is bucket brigade algorithm which uses metaphors from economics [59]. For a classifier called middleman, its suppliers are those classifiers that have sent messages satisfying its conditions, and its consumers are those classifiers that both have conditions satisfied by its message and have won their competition in turn. When a classifier wins in competition, its bid is actually apportioned to its suppliers, increasing their strengths by the amounts apportioned to them. At the same time, because the bid is treated as a payment for the right to post a message, the strength of the winning classifier is reduced by the amount of its bid. Should the classifier bid but not win, its strength remains unchanged and its suppliers receive no payment. Winning classifiers can recoup their payments from either wining consumers or the environment payoff. A genetic algorithm is used in classifier systems to discover new clas- sifiers by crossover and mutation. The strength of a classifier is used as its fitness. The genetic algorithm is only applied to the classifiers after certain number of operational cycles in order to approximate strengths better. There are two approaches to classifier systems; the Michigan approach and the Pitts approach. For the Michigan approach, each in- dividual in a population is a classifier. The whole population represents a complete classifier system. For the Pitts approach, each individual in a population represents a complete classifier system. The whole popu- lation includes a number of competing classifier systems. Evolutionary Artificial Neural Networks Evolutionary artificial neural networks can be considered as a combina- tion of artificial neural networks and evolutionary algorithms (64, 65, 66}. Evolutionary algorithms have been introduced into artificial neural net-Chapter 1. Introduction 17 works at three different levels: the evolution of connection weights, architectures, and learning rules [65, 66]. At present, most work on evolutionary artificial neural networks concentrates on the evolution of architectures, i.e., connectivities of ANNs [67, 68, 69, 70]. Very good results have been achieved for some artificial and real-world benchmark problems. One of the most important benefits of evolutionary artificial neural networks is that a near optimal (in terms of generalisation) artificial neural network with both structure and weights can be evolve automat- ically without going through a tedious trial-and-error manual design process. The results obtained so far have demonstrated that very com- pact artificial neural networks with good generalisation can be evolved [69]. Co-evolutionary Learning “Coevolution refers to the simultaneous evolution of two or more species with coupled fitness.” [71] Co-evolutionary learning has two different forms. In the first form, two or more populations are evolved at the same time [72]. ‘The fitness of an individual in one population depends on the individuals in another population. There is no crossover or other information exchange between two populations. This can be regarded as co-evolution at the population level. The second form of co-evolution is at the individual level. There is only one population involved. The fitness of an individual in the population depends on other individuals in the same population [73, 74, 75, 76, 7]. For example, the same strategy for playing an iterated prisoner’s dilemma game may get quite different fitness values depending on what other strategies are in the same population. Both forms of co- evolution have a dynamic environment and a dynamic fitness function. This is an active area of research. 1.3. Evolutionary Algorithm and Generate-and- Test Search Algorithm Although evolutionary algorithms are often introduced from the point of view of survival of the fittest and from the analogy to natural evolution,18 X. Yao they can also be understood through the framework of generate-and- test search. The advantage of introducing evolutionary algorithms as a type of generate-and-test search algorithms is that the relationships between evolutionary algorithms and other search algorithms, such as simulated annealing [78, 79, 80, 81], tabu search [82, 83], etc., can be made clearer and thus easier to explore. Under the framework of generate-and-test search, different search algorithms investigated in ar- tificial intelligence, operations research, computer science, and evolu- tionary computation can be unified together. Such interdisciplinary studies are expected to generate more insights into search algorithms in general. A general framework of generate-and-test search can be described by Figure 1.3. 1. Generate the initial solution at random and denote it as the current solution; 2. Generate the next solution from the current one by perturba- tion, 3. Test whether the newly generated solution is acceptable; (a) Accepted it as the current solution if yes; (b) Keep the current solution unchanged otherwise. 4. Goto Step 2 if the current solution is not satisfactory, stop oth- erwise. Figure 1.3: A General Framework of Generate-and-Test. It is quite clear that various hill-climbing algorithms can be de- scribed by Figure 1.3 with different strategies for perturbation. They all require the new solution to be no worse than the current one to be acceptable. simulated annealing does not have such a requirement. It regards a worse solution to be acceptable with certain probability. The difference among classical simulated annealing [78], fast simulated an-Chapter 1. Introduction 19 nealing [79], very fast simulated annealing [84], and a new simulated annealing [81] lies in the difference in their perturbations, i.e., methods of generating the next solution. Evolutionary algorithms can be regarded as a population-based ver- sion of generate-and-test search. They use search operators like crossover and mutation to generate new solutions, and use selection to test which solutions are fitter than others. From this point of view, it is clear that we do not have to limit ourselves to crossover and mutation in an evo- lutionary algorithm. In principle, we can use any search operators to generate new solutions (i.e., offspring). A good search operator should always increase the probability of finding a global optimum. This is also true for selection. 1.4 Search Operators There are many search operators that have been used in various evolu- tionary algorithms. Some of them are specialised in solving a particular class of problems. This section describes some search operators and se- lection schemes! commonly used. They do not represent a complete set of all search operators. 1.4.1. Recombination Operators The essence of any recombination (crossover) operator is the inheritance of information (genes) from two or more parents by offspring. Although most recombination operator uses two parents, multiple parents may be useful in some cases. Two offspring are often produced by a recombina- tion operator, but, again, other numbers might be appropriate for some problems. Recombination for Real-Valued Vectors These operators are mostly proposed for evolution strategies. They are used to process vectors of real numbers. In evolution strategies, ‘Usually selection is not regarded as a search operator. It is included in this section for ease of discussions.20 X. Yao recombination is done independently for objective variables and strat- egy parameters (i.e., variance, etc.). It can be different for objective variables and strategy parameters. Discrete Recombination In this case, an offspring vector will have components coming from two or more parent vectors. There is no change to any component itself. For example, given two par- ents x = (2,22,.--,2,) and y = (y1,4y2,-.-,Yn)- The offspring x! = (x},25,...,2},) and y’ = (y},y),-.-,yh) can be generated as follows: gi = ti With probability Precombination + yi otherwise y’ will be the complement of x’. A global version of this recom- bination is that y; will be taken from a randomly generated y for each i value. That is, for each i value, a y is generated uniformly at random in the whole population. Then its ith component will be used for recombination. Basically the number of parents is the same as the population size. Intermediate Recombination In this case, a component of an off- spring vector is a linear combination (average) of parent’s corre- sponding components. For example, given two parents x = (x1, ©, ..., Zn) and y = (x1, ya, --+5 Yn). The offspring x’ = (24, 2, ¥ and y’ = (yj, >, --», Y) can be generated as follows: 2, = 2; + a(y — zi) where « is a weighting parameter in (0,1). It is traditionally set to 0.5. It can also be generated at random. y’ can be generated similarly. A global version of this recombination is that y; will be taken from a randomly generated y for each i value. @ can also be different for each i. Recombination for Binary Strings Common recombination operators for binary strings include k-point crossover (K > 1) and uniform crossover, although there are many other variants.Chapter 1. Introduction 21 k-point crossover This crossover can actually be applied to strings of any alphabet. Given two parents of length n. k random numbers, 11,72,---,7k, between 1 and n — 1 will be generated uniformly (without repetition). Then an offspring is produced by taking segments (separated by r1,r2,-..,r) of parent strings alternately, i.e, the first segment from the first parent, the second from the second parent, the third from the first parent, and so on. For example, a 3-point crossover at 1,4,6 of two parents 00000000 and 11111111 will produce two offspring 01110011 and 10001100. uniform crossover This crossover is also applicable to strings of any alphabet. An offspring is generated by taking its each bit or char- acter from the corresponding bit or character in one of the two parents. The parent that the bit or character is to be taken from is chosen uniformly at random. Other crossover operators include segmented crossover and shuffle crossover [85]. They are not widely used in genetic algorithm applica- tions. Specialised Recombination There are numerous recombination operators which have been proposed for different problems, especially combinatorial optimisation problems, such as matrix-based crossover [51, 55], permutation-based crossover (86, 49], tree-based crossover (87, 88], etc. 1.4.2 Mutation Operators Mutation operators used for vectors of real values are usually based on certain probability distributions, such as uniform, lognormal, Gauss (normal) and Cauchy distributions. Mutation for binary strings is a lot simpler. It is usually a bit-fliping operation. Mutation for Real-Valued Vectors Gaussian Mutation In this case, an offspring is produced by adding a Gaussian random number with mean 0 and standard deviation22 X. Yao go to the parent. For example, given x = (21,22,...,2,) as the parent, an offspring is produced as follows: x = 2 + N,(0,0;) where Nj(0,0;) is a normally distributed random number with mean 0 and standard deviation oj. The n random numbers are generated independently for each dimension (thus the subscription i in N;,(0,0;). For self-adaptive evolutionary algorithms, such as evolution strategies and evolutionary programming, o;’s are usu- ally mutated independently using a lognormal distribution. More details are given by Eqs. 1.2 and 1.3 in Section 1.1.3. Cauchy Mutation Cauchy mutation differs from Gaussian mutation in the probability distribution used to generate the random num- ber. The use of Cauchy mutation in evolutionary algorithms was inspired by fast simulated annealing [79, 81] and proposed indepe- dently by several researchers [39, 89]. A detailed study of Cauchy mutation will be presented later in this chapter. Other Mutations Mutations based on other probability distributions, such as the t-distribution, may be introduced into evolutionary algorithms. An important question to ask when introducing a new operator is when the new operator will be most efficient for what kind of problems. Mutation for Binary Strings Bit-Fliping Bit-flipping mutation simply flips a bit from 0 to 1 or from 1 to 0 with certain probability. This probability is often called the mutation probability or mutation rate. Bit-flipping mutation can be generalised to mutate strings of any alphabet. The generalised mutation works as follows: for cach character (allele) in a string, replace it with another randomly chosen character (not the same as the one to be replaced) in the alphabet with certain mutation probability. Random Bit This mutation does not flip a bit. It replaces a bit by 0 or 1 with equal probability (i.e., 0.5 respectively). The gener- alised version of this mutation works as follows: for each characterChapter 1. Introduction 23 (allele) in a string, replace it with a randomly chosen character (could be the same as the one to be replaced) in the alphabet with certain mutation probability. Specialised Mutations Similar to the situation for crossover, there are many other specialised mutation operators designed for various combinatorial problems, such as the operators for mutate finite state machines [3], artificial neural networks [69] and cutting stock problems [54]. 1.4.3 Selection A selection scheme determines the probability of an individual being se- lected for producing offspring by recombination and/or mutation. In order to search for increasingly better individuals, fitter individuals should have higher probabilities of being selected while unfit individ- uals should be selected only with small probabilities. Different selection schemes have different methods of calculating selection probability. The selection pressure has sometimes been used to indicate how large the selection probability should be for a fit individual in comparison with that for an unfit individual. The larger the probability, the stronger the selection pressure. There are three major types of selection schemes, roulette wheel selection (also known as the fitness proportional selection), rank-based selection and tournament selection. Roulette Wheel Selection Let fi, fa;--+sfn be fitness values of individuals 1,2,---,n. Then the selection probability for individual 7 is _ _fi Cha fy Roulette wheel selection calculates the selection probability directly from individual’s fitness values. This method may cause problems in some cases. For example, if an initial population contains one or two very fit but not the best individu- als and the rest of the population are not good, then these fit individuals Pi24 X. Yao will quickly dominate the whole population (due to their very large se- lection probabilities) and prevent the population from exploring other potentially better individuals. On the other hand, if individuals in a population have very similar fitness values, it will be very difficult for the population to move towards a better one since selection probabili- ties for fit and unfit individuals are very similar. To get around these two problems, various fitness scaling methods have been proposed [15]. These fitness scaling methods are used to scale fitness values before they are used in calculating selection probabilities. Rank-Based Selection Rank-based selection does not calculate selection probabilities from fit- ness values directly. It sorts all individuals according to their fitness values first and then computes selection probabilities according to their ranks rather than their fitness values. Hence rank-based selection can maintain a constant selection pressure in the evolutionary search and avoid some of the problems encountered by roulette wheel selection. There are many different rank-based selection schemes. Two are introduced here. Assume the best individual in a population ranks the first. The probability of selecting individual i can be calculated linearly as follows [90]: 1 i-l Pi= = (Nmax — (max — min) -— where n is the population size, Mmax and tmin are two parameters. Nmaz = Nin 2 0 Taz + min = 2 The recommended value for Nmaz is 1.1. A rank-based selection scheme with a stronger selection pressure is the following nonlinear ranking scheme [49]:Chapter 1. Introduction 25 Tournament Selection Both roulette wheel selection and rank-based selection are based on the global information in the whole population. This increases communica- tions overheads if we want to parallelise an evolutionary algorithms on a parallel machine. Tournament selection only needs part of the whole population to calculate an individual’s selection probability. Different individuals can also calculate their selection probabilities in parallel. One of the often used tournament selection schemes is that used in evolutionary programming, which was described in Section 1.1.4. An- other one is Boltzmann tournament selection (91], described as follows: 1. For tournament size 3, first select an individual i; at random. Then select ig also at random but must differ from i; by a fitness amount of ©. Randomly selected i3 must also differ from 4,, and half the time differ from i2 as well, all by 9. 2. i2 competes with ig first. Then the winner competes with i). The winner is identified by the Boltzmann acceptance probability. The probability of individual c wining over y is: 1 1 +exp((fy — fz)/T) where T is the temperature. (Note that we are maximising fit- ness.) P(a,y) = Elitist Selection Elitist selection is also known as elitism and elitist strategy. It always copy the best individual to the next generation without any modifica- tion. More than one individual may be copied, i.e., the best, second best, etc., may be copied to the next generation without any modifica- tion. Elitism is usually used in addition to other selection schemes. 1.5 Summary This chapter introduces the basic concept and major areas of evolu- tionary computation. It presents a brief history of three major types26 X. Yao of evolutionary algorithms, i.e., evolution strategies, evolutionary pro- gramming and genetic algorithms, and points out similarities and differ- ences among them. It is also pointed out that the field of evolutionary computation is much more than just three types of algorithms. The field includes many other topics. The chapter gives a quick overview of evolutionary computation without diving into too much detail. Three main areas of the field have been discussed: evolutionary computation theory, evolutionary optimi- sation and evolutionary learning. It is argued that much work on the computational complexity of evolutionary algorithms is needed among other things in order to better understand the computational power of these algorithms.Bibliography 1] H.-P. Schwefel, Numerical Optimization of Computer Models. Chichester: John Wiley & Sons, 1981. 2] H.-P. Schwefel, Evolution and Optimum Seeking. New York: John Wiley & Sons, 1995. 3] L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence Through Simulated Evolution. New York, NY: John Wiley & Sons, 1966. J. H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, MI: The University of Michigan Press, 1975. 5] K. A. D. Jong, An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan, Ann Arbor, 1975. 6] A. S. Fraser, “Simulation of genetic systems by automatic digital computers. I. Introduction,” Australian Journal of Biological Sciences, vol. 10, pp. 484-491, 1957. 7] J. R. Koza, “Evolving programs using symbolic expressions,” in Proc. of the 11th Int’l Joint Conf. on Artificial Intelligence (N. S. Sridharan, ed.), (San Mateo, CA), pp. 768-774, Mor- gan Kaufmann, 1989. 4] 8] J. R. Koza, “Genetic programming: a paradigm for genetically breeding populations of computer programs to solve problems,” Tech. Rep. STAN-CS-90-1314, Department of Computer Sci- ence, Stanford University, June 1990. 9] H. de Garis, “Genetic programming: modular evolution for Darwin machines,” in Proc. of Int’l Joint Conf. on Neural Networks, 2728 11 12] 13] 14] 15] 16 17] 18 19] (20 X. Yao Vol. I, (Washington, DC), pp. 194-197, Lawrence Erlbaum As- sociates, Hillsdale, NJ, 1990. T. Back, Evolutionary Algorithms in Theory and Practice. New York: Oxford University Press, 1996. T. Back and H.-P. Schwefel, “An overview of evolutionary algo- rithms for parameter optimization,” Evolutionary Computation, vol. 1, no. 1, pp. 1-23, 1993. D. B. Fogel, System Identification Through Simulated Evolution: A Machine Learning Approach to Modeling. Needham Heights, MA 02194: Ginn Press, 1991. D. B. Fogel, Evolutionary Computation: Towards a New Philosophy of Machine Intelligence. New York, NY: IEEE Press, 1995. D. B. Fogel, “An introduction to simulated evolutionary optimisa- tion,” IEEE Trans. on Neural Networks, vol. 5, no. 1, pp. 3-14, 1994. D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989. Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs (3rd edition). Berlin, Germany: Springer-Verlag, 1996. H.-G. Beyer, “Towards a theory of evolution strategies: the (44, A) theory,” Evolutionary Computation, vol. 2, no. 4, pp. 381-407, 1994. D. B. Fogel, Evolving Artificial Intelligence. PhD thesis, University of California, San Diego, CA, 1992. A. E. Eiben, E. H. L. Aarts, and K. M. van Hee, “Global conver- gence of genetic algorithms: a markov chain analysis,” in Paral- lel Problem Solving from Nature (H.-P. Schwefel and R. Manner, eds.), pp. 4-12, Springer-Verlag, Heidelberg, 1991. G. Rudolph, “Convergence properties of canonical genetic algo- rithms,” IEEE Trans. on Neural Networks, vol. 5, no. 1, pp. 96- 101, 1994.Chapter 1. Introduction 29 21) 22) 23) (24) 25) [26 27, 28) [29 30) G. Rudolph, “Convergence analysis of evolutionary algorithms in general search spaces,” in Proc. of the 1996 IEEE Int'l Conf. on Evolutionary Computation (ICEC’96), (New York, NY), pp. 50-54, IEEE Press, 1996. D. Reynolds and J. Gomatam, “Stochastic modelling of genetic algorithms,” Artificial Intelligence, vol. 82, no. 1-2, pp. 303- 330, 1996. J. Suzuki, “A markov chain analysis on a genetic algorithm,” in Proc. of the Fifth Int'l Conf. on Genetic Algorithms (S. Forrest, ed.), pp. 146-153, Morgan Kaufmann, San Mateo, CA, 1993. J. Suzuki, “A markov chain analysis on a simple genetic al- gorithm,” IEEE Trans. on Systems, Man, and Cybernetics, vol. 25, pp. 655-659, 1995. G. Rudolph, “Convergence of non-elitist strategies,” in Proc. of the 1994 IEEE Int'l Conf. on Evolutionary Computation (ICEC’94) (Z. M. et al., ed.), pp. 63-66, IEEE Press, New York, NY 10017- 2394, 1994. G. E. Liepins and M. D. Vose, “Deceptiveness and genetic al- gorithm dynamics,” in Foundations of Genetic Algorithms (G. J. E. Rawlins, ed.), vol. 1, (San Mateo, CA), pp. 36-50, Morgan Kaufmann, 1991. K. Deb and D. E. Goldberg, “Analyzing deception in trap func- tions,” in Foundations of Genetic Algorithms 2 (L. D. Whitley, ed.), (San Mateo, CA), pp. 93-108, Morgan Kaufmann, 1993. J. J. Grefenstette, “Deception considered harmful,” in Foundations of Genetic Algorithms 2(L. D. Whitley, ed.), (San Mateo, CA), pp. 75-91, Morgan Kaufmann, 1993. YY. Davidor, “Epistasis variance: a viewpoint on GA-hardness,” in Foundations of Genetic Algorithms (G. J. E. Rawlins, ed.), pp. 23-35, Morgan Kaufmann, San Mateo, CA, 1991. R. B. Heckendorn and D. Whitley, “A Walsh analysis of NK- landscapes,” in Proc. of the 7th Int'l Conf. on Genetic Algo- rithms (T. Back, ed.), (San Francisco, CA), pp. 41-48, Morgan Kaufmann, 1997.30 31 32) 33) 34) (35) 36 37 38) 39 40] X. Yao B. Manderick, M. de Weger, and P. Spiessens, “The genetic al- gorithm and the structure of the fitness landscape,” in Proc. of the Fourth Intl Conf. on Genetic Algorithms (R. K. Belew and L. B. Booker, eds.), pp. 143-150, Morgan Kaufmann, San Mateo, CA, 1991. W. Hordijk, “A measure of landscapes,” Evolutionary Computa- tion, vol. 4, no. 4, pp. 335-360, 1996. T. Jones, Evolutionary Algorithms, Fitness Landscapes and Search. PhD thesis, The University of New Mexico, Albuquerque, New Mexico, May 1995. J. H. Holland, Adaptation in Natural and Artificial Systems (1st MIT Press Edn). Cambridge, MA: The MIT Press, 1992. K. A. DeJong, “Genetic algorithms are NOT function optimizers,” in Foundations of Genetic Algorithms 2 (L. D. Whitley, ed.), (San Mateo, CA), pp. 5-17, Morgan Kaufmann, 1993. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness San Francisco: W. H. Freeman Co., 1979. Z. Michalewicz and M. Schoenauer, “Evolutionary algorithms for constrained parameter optimization problems,” Evolutionary Computation, vol. 4, no. 1, pp. 1-32, 1996. J.-H. Kim and H. Myung, “Evolutionary programming techniques for constrained optimization problems,” JEEE Transactions on Evolutionary Computation, vol. 1, no. 2, pp. 129-140, 1997. X. Yao and Y. Liu, “Fast evolutionary programming,” in Evolu- tionary Programming V: Proc. of the Fifth Annual Conference on Evolutionary Programming (L. J. Fogel, P. J. Angeline, and T. Bick, eds.), (Cambridge, MA), pp. 451-460, The MIT Press, 1996. X. Yao and Y. Liu, “Fast evolution strategies,” Control and Cyber- netics, vol. 26, no. 3, pp. 467-496, 1997.Chapter 1. Introduction 31 (41 (42] 43} 44 45) 46 47| 48} 49) 50) C. M. Fonseca and P. J. Fleming, “An overview of evolutionary algorithms in multiobjective optimization,” Evolutionary Com- putation, vol. 3, no. 1, pp. 1-16, 1995. C. M. Fonseca and P. J. Fleming, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms — part i: A unified formulation,” [EEE Trans. on Systems, Man, and Cybernetics, Part A: Systems and Humans, vol. 28, no. 1, pp. 26-37, 1998. C. M. Fonseca and P. J. Fleming, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms — part ii: Application example,” JEEE Trans. on Systems, Man, and Cybernetics, Part A: Systems and Humans, vol. 28, no. 1, pp. 38-47, 1998. K. E. Mathias and D. Whitley, “Changing representations during search: A comparative study of delta coding,” Evolutionary Computation, vol. 2, no. 3, pp. 249-278, 1994. D. B. Fogel and J. W. Atmar, “Comparing genetic operators with Gaussian mutations in simulated evolutionary process using lin- ear systems,” Biological Cybernetics, vol. 63, no. 2, pp. 111-114, 1990. D. B. Fogel, “A comparison of evolutionary programming and genetic algorithms on selected constrained optimization prob- lems,” Simulation, vol. 64, no. 6, pp. 399-406, 1995. J. J. Grefenstette, R. Gopal, B. J. Rosmaita, and D. van Gucht, “Genetic algorithms for the traveling salesman problem,” in Proc. of the First Int’l Conf. on Genetic Algorithms and Their Applications (J. J. Grefenstette, ed.), pp. 160-168, Carnegie- Mellon University, 1985. D. B. Fogel, “An evolutionary approach to the traveling salesman problem,” Biological Cybernetics, vol. 60, pp. 139-144, 1988. X. Yao, “An empirical study of genetic operators in genetic al- gorithms,” Microprocessing and Microprogramming, vol. 38, pp. 707-714, 1993. Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs.32 X. Yao Berlin, Germany: Springer-Verlag, 1992. [51] G. A. Vignaux and Z. Michalewicz, “A genetic algorithm for the linear transportation problem,” IEEE Trans. on Systems, Man, and Cybernetics, vol. 21, no. 2, pp. 445-452, 1991. (52] J. Lienig and K. Thulasiraman, “GASBOR: A genetic algorithm for switchbox routing in integrated circuits,” in Progress in Evolu- tionary Computation, Lecture Notes in Artificial Intelligence, Vol. 956 (X. Yao, ed.), (Heidelberg, Germany), pp. 187-200, Springer-Verlag, 1995. [53] R. Hinterding and L. Khan, “Genetic algorithms for cutting stock problems: with and without contiguity,” in Progress in Evolu- tionary Computation, Lecture Notes in Artificial Intelligence, Vol. 956 (X. Yao, ed.), (Heidelberg, Germany), pp. 166-186, Springer-Verlag, 1995. [54] K.-H. Liang, X. Yao, C. Newton, and D. Hoffman, “Solving cutting stock problems by evolutionary programming,” in Evolutionary Programming VII: Proc. of the 7th Annual Conference on Evo- lutionary Programming (V. W. Porto, N. Saravanan, D. Waa- gen, and A. E. Eiben, eds.), vol. 1447 of Lecture Notes in Com- puter Science, (Berlin), pp. 291-300, Springer-Verlag, 1998. [55] F. Luan and X. Yao, “Solving real-world lecture room assign- ment problems by genetic algorithms,” in Complex Systems — From Local Interactions to Global Phenomena, pp. 148-160, IOS Press, Amsterdam, 1994. [56] X. Yao, “Optimization by genetic annealing,” in Proc. of Second Australian Conf. on Neural Networks (M. Jabri, ed.), (Sydney, Australia), pp. 94-97, 1991. [57] T. Kido, K. Takagi, and M. Nakanishi, “Analysis and compar- isons of genetic algorithm, simulated annealing, tabu search, and evolutionary combination algorithm,” Informatica, vol. 18, pp. 399-410, 1994. [58] J. H. Holland, K. J. Holyoak, R. E. Nisbett, and P. R. Thagard, Induction: Processes of Inference, Learning, and Discovery. Cambridge, MA: The MIT Press, 1986.Chapter 1. Introduction 33 59] (60) 61 62] 63) 64] 65} 66 67 68) J. H. Holland, “Using classifier systems to study adaptive nonlin- ear networks,” in Lectures in the Sciences of Complexity (D. L. Stein, ed.), pp. 463-499, Redwood City, CA: Addison-Wesley, 1988. T. H. Westerdale, “Classifier systems — no wonder they don’t work,” in Proc. of the 2nd Annual Conf. on Genetic Program- ming (J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, and R. L. Riolo, eds.), (San Francisco, CA), pp. 529-537, Morgan Kaufmann, 1997. S. W. Wilson, “Classifier fitness based on accuracy,” Evolutionary Computation, vol. 3, no. 2, pp. 149-175, 1995. M. Colombetti and M. Dorigo, “Evolutionary computation in be- havior engineering,” in this volume, World Scientific Publ. Co. R. E. Smith and D. E. Goldberg, “Reinforcement learning with classifier systems: adaptive default hierarchy formation,” Ap- plied Artificial Intelligence, vol. 6, pp. 79-102, 1992. X. Yao, “Evolution of connectionist networks,” in Preprints of the Int'l Symp. on Al, Reasoning & Creativity (T. Dartnall, ed.), (Queensland, Australia), pp. 49-52, Griffith University, 1991. X. Yao, “A review of evolutionary artificial neural networks,” Inter- national Journal of Intelligent Systems, vol. 8, no. 4, pp. 539- 567, 1993. X. Yao, “Evolutionary artificial neural networks,” in Encyclope- dia of Computer Science and Technology (A. Kent and J. G. Williams, eds.), vol. 33, pp. 137-170, New York, NY 10016: Marcel Dekker Inc., 1995. X. Yao and Y. Shi, “A preliminary study on designing artificial neural networks using co-evolution,” in Proc. of the IEEE Sin- gapore Intl Conf on Intelligent Control and Instrumentation, (Singapore), pp. 149-154, IEEE Singapore Section, June 1995. Y. Liu and X. Yao, “A population-based learning algorithm which learns both architectures and weights of neural networks,” Chi- nese Journal of Advanced Software Research (Allerton Press, Inc., New York, NY 10011), vol. 3, no. 1, pp. 54-65, 1996.34 69 70) 7] 72! 73 74) 76 77) 78) X. Yao X. Yao and Y. Liu, “A new evolutionary system for evolving artifi- cial neural networks,” [EEE Transactions on Neural Networks, vol. 8, no. 3, pp. 694-713, 1997. X. Yao and Y. Liu, “Making use of population information in evolutionary artificial neural networks,” IEEE Trans. on Sys- tems, Man, and Cybernetics, Part B: Cybernetics, vol. 28, no. 3, pp. 417-425, 1998. C. D. Rosin and R. K. Belew, “New methods for competitive co- evolution,” Evolutionary Computation, vol. 5, no. 1, pp. 1-29, 1997. W. D. Hillis, “Co-evolving parasites improve simulated evolution as an optimization procedure,” in Santa Fe Institute Studies in the Sciences of Complexity, Volume 10, pp. 313-323, Addison- Wesley, 1991. R. Axelrod, “The evolution of strategies in the iterated pris- oner’s dilemma,” in Genetic Algorithms and Simulated Anneal- ing (L. Davis, ed.), ch. 3, pp. 32-41, San Mateo, CA: Morgan Kaufmann, 1987. X. Yao and P. Darwen, “An experimental study of N-person iter- ated prisoner’s dilemma games,” Informatica, vol. 18, pp. 435- 450, 1994. P. J. Darwen and X. Yao, “On evolving robust strategies for iter- ated prisoner’s dilemma,” in Progress in Evolutionary Compu- tation, Lecture Notes in Artificial Intelligence, Vol. 956 (X. Yao, ed.), (Heidelberg, Germany), pp. 276-292, Springer-Verlag, 1995. P. Darwen and X. Yao, “Automatic modularization by speciation,” in Proc. of the 1996 IEEE Int’l Conf. on Evolutionary Compu- tation (ICEC’96), Nagoya, Japan, pp. 88-93, IEEE Press, New York, NY 10017-2394, 1996. P. J. Darwen and X. Yao, “Speciation as automatic categorical modularization,” IEEE Transactions on Evolutionary Compu- tation, vol. 1, no. 2, pp. 101-108, 1997. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, pp. 671-680, 1983.Chapter 1. Introduction 35 [79 (80 [81 (82 83) 84] [85 86 87, 88) i) 90) H. H. Szu and R. L. Hartley, “Fast simulated annealing,” Physics Letters A, vol. 122, pp. 157-162, 1987. X. Yao, “Simulated annealing with extended neighbourhood,” Int. J. of Computer Math., vol. 40, pp. 169-189, 1991. X. Yao, “A new simulated annealing algorithm,” Int. J. of Com- puter Math., vol. 56, pp. 161-168, 1995. F. Glover, “Tabu search — part I,” ORSA J. on Computing, vol. 1, pp. 190-206, 1989. F. Glover, “Tabu search — part II,” ORSA J. on Computing, vol. 2, pp. 4-32, 1990. L. Ingber, “Very fast simulated re-annealing,” Mathl. Comput. Modelling, vol. 12, no. 8, pp. 967-973, 1989. L. Eshelman, R. Caruana, and J. D. Schaffer, “Biases in the crossover landscape,” in Proc. of the Third Int’l Conf. on Ge- netic Algorithms and Their Applications (J. D. Schaffer, ed.), pp. 10-19, Morgan Kaufmann, San Mateo, CA, 1989. D. Whitley, T. Starkweather, and D. Shaner, “The traveling salesman and sequence scheduling: quality solutions using ge- netic edge recombination,” in Handbook of Genetic Algorithms (L. Davis, ed.), ch. 22, pp. 350-372, New York, NY: Van Nos- trand Reinhold, 1991. J. R. Koza, Genetic Programming. Cambridge, Mass.: The MIT Press, 1992. J. Koza and D. Andre, “Automatic discovery of protein motifs using genetic programming,” in this volume, World Scientific Publ. Co. C. Kappler, “Are evolutionary algorithms improved by large mu- tations?,” in Parallel Problem Solving from Nature (PPSN) IV (H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, eds.), vol. 1141 of Lecture Notes in Computer Science, (Berlin), pp. 346-355, Springer-Verlag, 1996. J. E. Baker, “Adaptive selection methods for genetic algorithms,” in Proc. of an Int'l Conf. on Genetic Algorithms and Their Applications (J. J. Grefenstette, ed.), pp. 101-111, 1985.36 X. Yao {91] D. E. Goldberg, “A note on Bltzmann tournament selection for ge- netic algorithms and population-oriented simulated annealing,” Compler Systems, vol. 4, pp. 445-460, 1990.Chapter 2 Evolutionary Computation in Behavior Engineering Marco Colombetti and Marco Dorigo In the last few years we have used ALECSYS, a parallel learning classifier system based on the genetic algorithm, to develop behavioral modules for mobile robots, both simulated and real. In this paper we briefly report on our experience, and then reflect on various concepts stemming from the application of evolutionary computation to agent building. We propose a definition of agent, analyze the relationships holding between an agent and its external environment, and discuss some important similarities and differences between natural and artificial systems; in particular, we compare the concept of fitness of an organism with that of quality of an artifact. We then concentrate on adaptation, regarded as a basic process for the development of both biological organisms and artificial agents. We carry on our analysis trying to understand where and how Behavior Engineering (i.c., the discipline concerned with the development of artificial agents) might profit from the use of evolutionary strategies. We argue that an evolutionary approach might allow us to search the space of nonrational design, thus opening a whole new world of possibilities for the implementation of artificial systems. 3738 M. Colombetti and M. Dorigo 2.1 Introduction In the late fifties, computer scientists started to work on the project — known as Artificial Intelligence (AI) — of building intelligent computational systems. The basic assumption underlying most work in AI is that intelligence, either natural or artificial, intrinsically is a computational phenomenon, and therefore can be studied in disembodied systems, that is, in systems that have a “mind” but no “body” (with the exception of their computing “brain”). Forty years later, it is widely believed that — in spite of impressive local successes — AI will find it very difficult to reach its ultimate goal. Feeling unable to implement disembodied minds, several AI scientists tured to an apparently harder task, namely, to build intelligent robots endowed with a body and acting in the physical world. Such systems we shall simply call agents. In fact, the very term “intelligent”, which has been adopted copiously not only in AI, but in various areas of Computer Science, will be used very sparingly in this paper. Later on we shall discuss other laudatory terms, like autonomous and adaptive, that seem to be more suitable, in that they are both easier to define rigorously and relevant to the analysis of agency. The main motivation for turning one’s interest to embodied agents is that intelligence — whatever it is — is a natural phenomenon, which appeared in animals in the course of biological evolution. Darwinian considerations suggest that intelligence must have adaptive value, that is, it must be relevant to the reproductive success of animals in the terrestrial environment. Therefore, directing one’s attention to agents (i.e., to autonomous systems interacting with their environments) appears to be a sensible approach to understanding intelligence. There is no need to stress that any important breakthrough in understanding agency would be relevant to many practical applications. Robotics is the most obvious example of a discipline that would profit from a better comprehension of how artificial agents behave in the physical world. But probably, the notion of agent is more general than the one of robot; for example, an industrial plant of high complexity can also be viewed as an agent of some sort. There is however much work to be done ata You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.a You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Chapter 2, Behavior Engineering 41 rooms and corridors, containing various kinds of obstacles, preys (light sources or colored objects), areas designated as nests, etc. The AutonoMice are small mobile robots built for experimental purposes at our research Lab. AutonoMouse II (Figure 2.2.1) has four directional eyes and two motors. Each directional eye can sense a light source within a cone of about 60 degrees. Each motor can stay still or move the connected wheel one or two steps forwards, or one step backwards. The robot is connected to a transputer board on a PC via a 9600-baud RS-232 link. Only a small amount of processing is done on-board (i.e., the collection of data from sensors and to actuators and the management of communications with the PC); learning algorithms run on the transputer board. Figure 2.2.1 AutonoMouse II.