New Trends in Evolutionary ComputationP. J. Bentley, T. Gordon, J. Kim and S. KumarDepartment of Computer ScienceUniversity College London, Gower St., London, UKP.Bentley@cs.ucl.ac.ukAbstract- In the last five years, the field of evolutionarycomputation (EC) has seen a resurgence of new ideas,many stemming from new biological inspirations. Thispaper outlines four of these new branches of research:CreativeEvolutionarySystems,ComputationalEmbryology, Evolvable Hardware and ArtificialImmune Systems, showing how they aim to extend thecapabilities of EC. Recent, unpublished results byresearchers in each area at the Department ofComputer Science, UCL are provided.1 IntroductionThis paper describes four recent branches in evolutionarycomputation (EC) that take us a few steps closer to thetarget of a mature technology based on evolutionaryprocesses. We show how these new ideas are based on abetter understanding of the capabilities of evolutionarysearch. Instead of forcing evolution to do what we think itshould by adding heuristics or local searches, we areharnessing the innate abilities of evolution for exploration,innovation, adaptability and distributed search, oftenidentified through new biological inspirations (Bentley,2001). Examples and results are provided by researchersfrom each area, based at the Department of ComputerScience, University College London.We begin by examining how evolutionary algorithmsare being extended and employed for unconventionalapplications, enabling the development of creativeevolutionary systems. We then show how new advances inevolutionary design of electronic circuits are possible,using similar ideas in evolvable hardware. Next, wedescribe how computational embryology is opening up newpossibilities of scalability and adaptability. Finally, wepresent one of the latest major types of evolutionaryalgorithm: an artifical immune system and show its abilitiesfor machine learning. The paper concludes with a briefsummary and discussion.2 Creative ComputationThe techniques of evolutionary computation have longbeen used for optimisation, with some considerablesuccess. But some researchers are beginning to argue thatevolution is not a natural optimiser. In nature, evolutionpropagates change through populations that exist indynamic, interacting and ever-changing environments.Concepts of optima are meaningless in such naturalsystems ? at most we can talk of ‘better’ or ‘worse’solutions to the day-to-day problems faced by organisms.Evolution works very well with such undefined andchanging problems. It may not be the best optimiser, butwhen optima are irrelevant, its abilities to explorepossibilities and find creative (if transitory) solutionsseems unsurpassed (Bentley and Corne, 2001).Recent research is focussing on these abilties ofevolution more and more. Rather than attempt to optimisestatic and simplified functions, embedding knowledge (andconstraints) into the search, new work applies evolutionaryalgorithms to dynamic and ill-defined problems. Suchresearch ‘traditionally’ took place only in the field ofartificial life, but researchers now investigate howevolution can generate novelty for unconventionalapplications such as music composition, art, conceptualdesign and even novel fighter pilot strategies (Bentley andCorne, 2001).Previous and forthcoming work (Bentley, 2000; Bentleyand Corne, 2001) has explored the huge variety of new,creative applications being tackled by evolutionarypractitioners today. But how do we enable evolution tohandle creativity? One common definition of creativity isremoval of constraints. It is no coincidence, then, thatwhen we examine how creative evolutionary systems differfrom more traditional evolutionary systems, we see thatconstraints of one form or another have been relaxed orremoved. Some researchers do this quite explicitly ? forexample the recent work of Ian Parmee concentrates on thedevelopment of interactive evolutionary systems that allowusers to relax functional constraints for engineering designproblems (Parmee & Bonham, 2000). But there are other,more important constraints that must be considered if weare to enable creative evolutionary systems to generatenovelty.Traditional implementations of evolutionary searchsuffer from the same fundamental drawbacks as allconventional search algorithms. They rely on a goodparameterisation to permit them to find a good solution. Ifwe are optimising a propeller blade, but theparameterisation does not permit the width of the blade to
--------------------------------------------------------------------------------
Page 2 
vary, then the computer will never be able to find solutionswith different widths. Evolution, like all search algorithms,is limited and constrained by the representation it canmodify. While relaxing functional and parameterconstraints will permit evolution to arrive at a largerdiversity of solutions, only by modification of therepresentation can we enable evolution to innovate. Itseems that the remarkable results obtained by creativeevolutionary systems require the removal of constraintswithin the representations, and not only the fitnessfunctions. And by using a different type of representation,we can cause this to happen automatically.When the parameters of our representation do notdefine the solution directly, when they define a set ofcomponents from which the solution is constructed, wepermit far greater freedom for evolutionary search(Bentley, 2000). Now evolution explores new ways ofconstructing the solution by changing the relationshipsbetween components. It can vary the dimensionality of thespace by adding or removing elements. It can explorealternatives instead of optimising a single option.But while component-based representations enableevolution to discover novel solutions, they do not allow ustackle unevaluatable or ill-defined problems. To do this weoften need to add human interaction to the evolutionaryprocess. Our judgement must contribute to or replace thefitness functions (or any other part of the evolutionaryalgorithm that helps generate selection pressure). When wemodify EAs in this way, we call them interactiveevolutionary algorithms, or collaborative evolutionaryalgorithms (Bentley and Corne, 2001).There are a large number of different approaches usedin this area. For example, Furuta et al (1995) allowed usersto judge the aesthetics of evolving bridges in addition totheir structural evaluation, and employed ‘psychovectors’to quantify aesthetic factors. Others use multiobjectiveoptimisation methods to combine user input and fitnessfunctions (Bentley, 1999), some use fuzzy logic to aid theinput of knowledge into the search (Parmee & Bonham,2000). Most evolutionary art systems will present userswith some or all of the evolving population, and allowthem to rank or vote on the quality of the images(Rowbottom, 1999). Some, like the system described inAdrian Thompson’s recent work (Ch. 9 in Bentley andCorne, 2001), even allow users to ‘vote with their feet’ andphysically move themselves towards evolving solutionsthat they prefer.2.1 Interactive Genetic Algorithm DesignerThe addition of user input into an evolutionary algorithm isso easy, and the results often so good, that it is surprisinghow few researchers actually permit it. To provide anexample of such a system in operation, Bentley’s geneticalgorithm designer, GADES (Bentley, 1999) was modified.Figure 1 The generic evolutionary design system.The system comprises four main elements (fig. 1):? A low-parameter spatial-partitioning representation,used to define the shape of solid-object designs byshaping and combining separate solid ‘blocks’.? Hierarchically structured genotypes combined with ahierarchical crossover operator, which allow childdesigns to be efficiently generated from parent designswith different sized genotypes without loss of meaning.? A steady-state multiobjective genetic algorithm, usingan explicit mapping stage between genotypes andphenotypes, preferential selection of parents and a life-span operator, which forms the main search-engine atthe core of the system.? Modular evaluation software, which is used to guideevolution to functionally acceptable designs, with newdesign tasks being quickly specified by the user pickingcombinations of existing evaluation modules from alibrary.“dragonfly”evolved with human guidance only“airplane”evolved using human guidance andobjective functionsFigure 2 Shapes evolved by the interactive GADES.A new evaluation module was added which simplydisplayed a 3D rendered image of each member of theevolving population to the user in turn, and asked for afitness score to be input (a number between 0 and 9). Witha reduced population size of ten individuals, slightly highermutation rates than normal (to slow convergence) andabout 30 or 40 generations, a wide variety of ‘interestingsolutions’ were evolved. Because of the time needed tojudge the solutions, each took around half an hour. Figure2 shows how creative the results of evolution were, when
--------------------------------------------------------------------------------
Page 3 
combined with human guidance. The left image illustratesa shape evolved with human guidance alone, the rightimage shows a shape evolved with human guidance as oneobjective, and two other objectives (to ensure the shapewas not fragmented and also to reduce ‘wind resistance’ byensuring a streamlined shape). Other results are provided in(Bentley and Corne, 2001).3 Evolvable HardwareThere are of course more significant applications thanevolving shapes that look like dragonflies or airplanes(however streamlined they may be). One important newarea is evolvable hardware: the automatic design andsynthesis of electronic circuits. The most exciting areawithin this field is that of intrinsic hardware evolution,where evolved designs are tested for fitness in vivo on fieldprogrammable gate arrays (FPGAs).Modern circuits can contain a large number ofcomponents. Human designers need to reduce the searchspace of all functions of these components to a manageablesize. To do this, they tend to work in a space of lowerdimensionality in which they are expert. For instance,some designers treat all components as perfect digitalgates, when in fact the components are physical devicesthat behave as high gain analogue amplifiers.In order for this digital design abstraction to be realisedin hardware, we have to restrict the temporal behaviour ofthe physical circuit, imposing set-up and hold times onsections of the circuit. This allows the analogue circuit toappear to behave as digital gates. Restrictions on timingsuch as these not only prevent us from taking advantage ofa huge amount of potentially useful gate behaviour, butalso force us to spend a great deal of the design effortensuring that the phase rules are adhered to throughout thecircuit.Evolutionary search works best without adding suchconstraints. Indeed, by allowing evolution to use theanalogue behaviour abstracted away by digital designers,we can enable the generation of more efficient circuits, andperhaps even aid the evolutionary process throughimproved evolvability.Thompson’s(1996) tonediscriminator is an example of such work. Parts of thiscircuit behave digitally, as specified by the FPGA vendor.However, the overall behaviour is far from digital,resulting in highly original and non-human electroniccircuit designs.3.1 Evolving AddersAn intrinsic evolvable hardware platform has beendeveloped to further research at UCL. We selected theXilinx Virtex FPGA for our experiments1.1Virtex 2.5V Field Programmable Gate Arrays Databook V2.4available at: http://www.xilinx.com/partinfo/ds003.pdf.Although the Virtex architecture is course-grained it canbe configured using JBits (the Java configuration API fromXilinx) at a fine level of detail. However to allow thegenetic algorithm to manipulate the configuration at suchfine granularity that JBits allows, a directly mapped binaryrepresentation could not be easily used. To avoid unknownand unwanted biases in the encoding, each resource thatcould be modified by JBits was encoded as a separateinteger gene. The exceptions to this were the lookup table(LUT) configuration, which were each sixteen bits.Routing representation was also an issue. Eachconfigurable logic block (the Virtex is arranged as an arrayof CLBs) is driven independently, so it is possible forcontention to arise between two drivers if two outputmultiplexers from two different CLBs drive the same line.Previously reported intrinsic evolution using Virtex FPGAshas either worked with fixed routing (Hollingworth et al,2000), or the method of contention avoidance has not beenreported (Levi, 2000).To avoid contention we modified the representation. Itwas noted that although CLB input multiplexers canconnect to many nearest neighbour routing lines (singles),the connections between the output multiplexers andsingles are sparse, and few can connect to any that theirneighbours can. In fact, only eight of the possible forty-eight connections had to be prohibited to prevent anypossible contention arising. Only singles were encoded onthe chromosome, and connection points between singleswere not evolved. Although the representation wasnecessarily restricted with the human design principle ofcontention avoidance, it allows the genetic algorithmaccess to manipulate almost all other configurable featureson the FPGA. Searching this unconstrained design spaceoffers the opportunity to find innovative circuits designedexpressly for the Virtex architecture. An overview of thechromosome structure for one CLB and its associatedrouting is shown in table 1.Number of Genes Type of GeneNo. of Values16LUT Input MUXes272Clock Input MUXes112SR Input MUXes102Clock Enable Input MUXes114Other Input MUXes464LUT Configuration248Other CLB Logic1-38Output signal MUX1340Output MUX to single switches 2Table 1 Overview of the genotype for one CLB.A small rectangle of the chip was selected for evolution.The cells on the edges of this area only allowed to use therouting connections to the rest of the evolved area, and not
--------------------------------------------------------------------------------
Page 4 
outside. For instance the cell on the northeast corner wasrestricted to use only output multiplexer connections tosingle lines travelling south and west.3.2 ExperimentsA genetic algorithm was developed to evolve this structure.In addition to the behaviour of standard integer geneticalgorithms, it was also required that the number of allelesthat each gene can assume can be set independently of theothers. We chose to validate this genetic algorithm byevolving in simulation a circuit representation that Milleret al (1997) had examined, the two-bit adder.The circuit is represented by an indexed rectangle ofcells. They are indexed from the top left cell, row-wisethen column-wise. Each cell has two inputs and one logicfunction. The function may either be a two input logic gateor a two data input multiplexer. Inputs to a cell can beeither from other cells, or the circuit inputs. The circuitinputs are the test input vector, the inverted test inputvector, logic 0 or logic 1. To avoid feedback, each inputmust be from a cell with a lower number than the cellitself. The circuit outputs required are restricted to the topand right hand side of the cell array.The circuit is encoded as an integer string. There is atriplet of integers for each cell, representing the sources ofthe two cell inputs and the cell function, with the tripletlocus mapping to the cell index. If the cell function is alogic gate, the function allele represents a specific logicgate. If the cell function is a multiplexer, then the allelerepresents the multiplexer control signal source, which canbe either the output of another cell or a circuit input. Table2 shows the list of functions used. Cell outputs arerepresented by an integer each, the allele referring to theoutput cell index.Fitness was measured by subjecting each candidatecircuit to a test vector containing the complete two-bitadder truth table. One fitness point was awarded for eachcorrect input/output sequence, giving a total of 96 formaximum fitness. The circuit inputs were therefore A0,A1, B0, B1, Carry In, !A0, !A1, !B0, !B1, !Carry In, 0, and1. The outputs were S0, S1, and Carry Out.AlleleFunctionAlleleFunction0A . B7!A1A . !B8!A +B2!A . B9!B3A ? B10!A + B4A + B11!A + !B5!A . !B12....!C . A + C . B, C =circuit input 06!A ? B...(n)!C . A + C . B, C = input(n-12)Table 2 List of function to allele mappings used.Uniform crossover was used with two-member tournamentselection (the winner of each tournament was selected with70% probability). The mutation rate was set to 5% of allgenes in the population. The population size was set to 30.20,000 generations (unlike Miller et al’s 40,000-80,000)seemed sufficient to produce good results.3.3 Results10 runs were each made for cell array sizes of 3x3, 3x4,and 4x4. Table 3 shows overall results. Fitnesses anddeviations have been scaled to 100.ArraySizeMean fitness ofBest SolutionsStd. Dev. OfBest Solutions% of Runs withPerfect Solutions3x396.254.9950%4x396.883.7150%4x497.504.0360%Table 3 Results from 10 runs of 2 bit adder evolution across arange of array sizesThe results achieved from these experiments agree wellwith Miller's results (Miller et al, 1997). For example, for a3x3 array, Miller reported a mean fitness of 96.14 with astandard deviation of 4.52, and 50% of cases perfect.Figure 3 shows an example of a two-bit adder evolved onthe 3x3 array. This is a variation on a traditional two-bitripple-carry adder, using the same number and types ofgates, but in a slightly different configuration. As discussedin (Miller and Thompson, 1998), this illustrates the abilityof evolution to discover novel digital circuit designs. Byusing representations that allow evolution to explore agreater space of circuits than human designers wouldconsider, we enable the generation of innovation.B0C InA0B1A1S1C OutS0Figure 3 Example of an adder evolved on a 3x3 grid.4 Computational EmbryologyAllowing evolution greater freedom by modifyingrepresentations is just the first step towards achieving thediversity and scalability of solutions created by naturalevolution. In nature, ‘representations’ are much morecomplicated: there is not a one-to-one mapping from geneto phenotypic effect. Organisms develop from a set ofgenetic instructions. The new fields of embryonics,artificial morphogenesis and computational embryologyattempt to harness the power of such developmentalprocesses.
--------------------------------------------------------------------------------
Page 5 
Researchers have been using very simple computationalembryogenies of various guises for over a decade. Currentcomputational embryogenies can be classified into threedifferent types: external, explicit, and implicit (Bentley &Kumar, 1999).External embryogenies are typically, hand-designed andare defined globally and externally to genotypes. They arecharacterised by their fixed, non-evolvable structures. Forexample, Evolutionary Art systems often use externalembryogenies which specify how phenotypes should beconstructed using the genes in the genotypes. Similarly,Richard Dawkins’ Blind Watchmaker program (Dawkins,1987), employs a simple external embryogeny to createbiomorphs, using ‘eye-of-the-beholder’ to provide a fitnessmeasure, and mutation to vary the evolving shapes.An explicit embryogeny specifies each step of thegrowth process in the form of explicit and evolvablegenetic instructions. In computer science, an explicitembryogeny can be viewed as a tree containing a singlegrowth instruction at each node. Genetic Programming(GP) uses tree structures to represent its genotypes. GPtherefore, offers a simple and concise way to evolveexplicit embryogenies. Typically, the genotype and theembryogeny are combined and both are allowed to evolvesimultaneously. Perhaps most famous example is the workby Koza et al (1999) who used Gruau’s cellular encodingfor the evolution of analogue circuits. Also, Sims (1999)used an explicit embryogeny with the idea of directedgraphs to specify the nervous systems (neural networks),and morphologies of virtual creatures.An implicit embryogeny does not explicitly specifyeach step of the growth process. Instead, the growthprocess is implicitly specified by a set of genetic rules orinstructions, similar to a ‘recipe’ that govern the growth ofa shape. For example, de Garis (1999) describes an implicitembryogeny to evolve convex and concave shapes using acellular automata approach. Jakobi (1996) devised animplicit embryogeny based system that employed celldivision, cell movement, and diffusable proteins, in orderto evolve neural net robot control architectures. Table 4summarises the three categories of computationalembrogeny.Outside genotypes(Non-evolvable)Inside Genotypes(Evolvable)Timing and action ofevery growth stepis providedEXPLICITEMBRYOGENYTiming and action ofgrowth emergesEXTERNALEMBRYOGENYIMPLICITEMBRYOGENYTable 4 External, explicit and implicit embrogenies.4.1.1ExperimentsPrevious work (Bentley & Kumar, 1999; Kumar andBentley, 2000), compared the performance and scalabilityof different evolved computational embryogenies for thegeneration of tessellating tiles and letters of the alphabet.The results showed impressive scalability by an implicitembryogeny, which maintained constant genotype sizesdespite evolving tessellating tiles in finer resolutions. Forexample, fig. 4 shows the six letters of the alphabet used astargets for evolution. Presented as 4x4, 8x8 (as shown) and16x16 targets, they provided an assessment of the ability ofevolution to produce accurate and scalable developmentalprocesses, capable of ‘growing’ the desired letter.Figure 4 The pre-defined six target shapesIn these tests, two embryogenies were evolved andcompared. The first was an explicit embryogeny, using GPtrees to direct paths of growing cells in a phenotype grid.The second was an implicit embryogeny, which iterativelyused CA-like rules to enable shapes to emerge in aphenotype grid. For full details, refer to (Kumar andBentley, 2000). Table 5 gives the results of theexperiments.Perhaps the most significant results shown in Table 5are the solution sizes. It is clear that the explicitembryogeny required ever-increasing tree sizes as the scaleof the target shapes were increased. However, the reverseseems to be true for the implicit embryogeny, where thenumber of rules actually appears to decrease as theproblems are scaled up. This lack of increase of solutionsize corroborates and confirms the results obtained inprevious work which reported similar findings (Bentley &Kumar, 1999).4x48x816x16Shape MeanSoln.SizeMeanFitnessMeanSoln.SizeMeanFitnessMeanSoln.SizeMeanFitnessC14.2812.700.921.6457.7011.4713.2012.82309.4010.0084.153.7E24.2211.421.280.32168.4411.969.545.89693.586.70081.4049.40G18.8813.861.20.7859.5210.9812.7212.84302.126.00076.3452.90L9.5211.220.260.5871.049.023.566.38235.468.20039.4638.40O20.2011.601.310.1881.2913.2915.769.00293.006.400104.3348.70R18.7812.981.350.60121.5312.337.889.92513.436.90076.1655.80Table 5 Results for the target shapes. Values in italics denote theresults for the implicit embryogeny. Solution sizes are measuredin tree nodes for the explicit, and rules for the implicitembryogeny.
--------------------------------------------------------------------------------
Page 6 
4.1.2Biologically plausible implicit embryogenyWith the results of this experiment in mind, a new implicitmodel is now under development by the authors. Thecurrent system has been extended from the two-dimensional cellular automata, to an isospatial gridsystem. The isospatial grid, is a three dimensionalcoordinate system, developed by (Frazer, 1995), it uses sixaxis to define a point in space, yielding twelve equidistantneighbours for each point.The system uses spheres to represent cells and buildsthree-dimensional morphologies by carefully placing andorganising a colony of cells using a growth process. Thisprocess will use the concept of freely diffusingmorphogens to allow cells to acquire positional-information. In addition, key embryological processes suchas differentiation and pattern formation shall beinvestigated to grow morphologies. Although heavilyinspired by biology, this system is not intended as a modelof biological development. Instead, the work is aimed atextending the capabilities and scalability of evolutionaryalgorithms.An implicit embryogeny based system is used toevolve rules that are able to grow designs in complex ways.A chromosome comprises a series of rules (genes). A ruleconsists of a precondition field and an action field. Eachcell has a copy of the chromosome. The rules are applied(expressed) by matching the preconditions to a cell’s state.If the preconditions are satisfied the rule is expressed. Inthis way, rules expressed earlier on in the development canaffect other rules by switching them on or off.Figure 5 illustrates six morphologies grown fromrandom genomes using the new system. It should be clearthat the isospatial grid enables surprisingly organic formsto emerge.Figure 5 Six example random morphologies grown by the newsystem without any morphogens in the environment.5 Artificial Immune SystemsSo the use of processes that have been inspired bydevelopment in nature can increase the scalability ofevolutionary algorithms. But this is not the only naturalevolutionary process that researchers have recently ‘stolen’from biology. Our own immune systems use evolution,enabling highly robust, adaptive and distributed detectionof a vast variety of foreign pathogens. And a growingnumber of computer scientists have carefully studied thesuccess of this competent natural mechanism and proposedcomputer immune models for solving various problemsincluding fault diagnosis, virus detection, and mortgagefraud detection (Dasgupta, 1998).Among these various areas, intrusion detection is avigorous research area where the employment of anartificial immune system (AIS) has been examined(Dasgupta, 1998). The main goal of intrusion detection isto detect unauthorised use, misuse and abuse of computersystems by both system insiders and external intruders.Currently many network-based intrusion detection systems(IDS’s) have been developed using diverse approaches.Nevertheless, there still remain unresolved problems tobuild an effective network-based IDS. As one approach ofproviding the solutions of these problems, previous work(Kim and Bentley, 1999a) identified a set of generalrequirements for a successful network-based IDS and threedesign goals to satisfy these requirements: beingdistributed, self-organising and lightweight. In addition,Kim and Bentley (1999a) introduced a number ofremarkable features of human immune systems that satisfythese three design goals. It is anticipated that the adoptionof these features should help the construction of aneffective network-based IDS.Previous work (Kim and Bentley, 1999a) introduced thesalient functions of the human immune system with respectto network intrusion detection. In this work, we view thenormal activities of monitored networks as self and theirabnormal activities as non-self and design an AIS fordistinguishing normal network activities from abnormalnetwork activities.Based on this view, we proposed a novel AIS fornetwork intrusion detection (Kim and Bentley, 1999b), seefigure 6. The AIS for network intrusion detection consistsof a primary IDS and secondary IDS’s. For the AIS, theprimary IDS, which we view as being equivalent to thebone marrow and thymus within the human body,generates numerous detector sets. Each individual detectorset describes abnormal patterns of network traffic packetsand common patterns of network traffic packets whennetwork intrusion occurs. This unique detector set istransferred to a monitored single local host. We view localhosts as secondary lymph nodes, detectors as antibodiesand network intrusions as antigens. At the local hosts(secondary IDS’s), detectors are background processeswhich monitor whether non-self network traffic patternsare observed from network traffic patterns profiled at themonitored local host. The primary IDS and each secondaryIDS have communicators to allow the transfer ofinformation between each other, see figure 6.
--------------------------------------------------------------------------------
Page 7 
Prim ary ID SSecondary ID SN etw ork p acketsR outerC om m u nicatorC om m unication flowDetectorsFigure 6 Architecture of the AIS for network intrusiondetection.5.1.1ExperimentsFor the proposed AIS, several sophisticated mechanisms ofthe human immune system are embedded in threeevolutionary stages: gene library evolution, negativeselection and clonal selection. These processes allow theAIS to satisfy the identified goals for designing effectivenetwork-based IDS’s (Kim and Bentley, 1999a). They alsoexploit key features of natural immune systems such asdistributed detection, adaptation to new antigens anddiscovery of new patterns in data.Recent work has investigated the combination of clonalselection with negative selection in the AIS. Detectors (inthe form of classification rules) are evolved using theclonal selection algorithm: parent detectors compete ingroups, with only the rule that matches a non-self antigenhaving its fitness increased. The fittest parents arerandomly picked for reproduction, and if child detectorsmatch any ‘self’ antigens, they are removed (negativeselection), with parents generating new children. Thecombination of these two processes results in the evolutionof a population of detectors that are clustered into niches,and that can together distinguish between ‘self’ and ‘non-self’ data. For full details, refer to (Kim and Bentley,2001).Three different data sets from the UCI repository2formachine learning algorithm benchmark work were used totest the system: Wisconsin breast cancer data (241examples belong to ‘Malignant’ class and 458 examplesbelong to ‘Benign’), the ‘vote’ data set (267 ‘democrat’and 168 ‘republican’ examples) and the iris data set (50examples each of ‘setosa’, ‘virginia’ and ‘versicolour’). Atenfold cross-validation method was employed to preparetraining sets for the AIS to evolve and test sets to evaluatedetection of previously unseen non-self patterns. A detectorpopulation size of 300 was used. Each experiment was runfor a maximum 50 generations.2ftp:// ftp.ics.uci.edu/pub/machine-learning-databasesTPFPCancer Data95.65 %5.41 %Vote Data92.49 %3.57 %IRIS Setosa99.8 %1.2 %IRIS Versicolor95 %5 %IRIS Virginia95.6 %1 %Table 6 The mean of TP and FP rates. IRIS class label in eachrow indicates the assigned self class.Table 6 presents the results of the experiment, wherethe detector sample size was 10 and the antigen samplesize was 1 (groups of ten detectors competed to detect oneantigen). The detection rate of the system is described by aTrue Positive (TP) rate and a False Positive (FP) rate. TheTP is “non-self” detection rate and the FP is the rate atwhich “self” is mistakenly detected by a generated detectorset. The desired system will have a high TP and a low FP.The table shows the means of 10 experiments.The results show good accuracy rates, with evolveddetectors correctly identifying between 92.5 and 99.8% ofnon-self antigens in the test data. Equally, false-positiverates were low, with detectors mistakenly matchingbetween 1 and 5.4% of self antigens. Further results can befound in (Kim and Bentley, 2001). Like the previous threeexamples, these results illustrate the benefits of exploitingthe natural capabilities of evolution. The combination ofimmune processes produced niches of distributed detectors,which together discovered patterns in data thatdistinguished 'self' from 'non-self'.6 Summary and DiscussionThe four branches of evolutionary computation that wehave briefly examined here form part of a new vision ofEC that is now being shared by many researchers. Theseapproaches do not force evolution to do what we think itshould do by adding constraints, problem heuristics, andill-conceived hybridisations. Instead, they all pay attentionto the strengths and weaknesses of evolution. By designingsystems that take full advantage of the special capabilitiesof evolutionary search, we are beginning to harness thepower of evolution for new and more difficult problems.The first example: creative evolutionary systems,illustrated these ideas. In order to enable evolution togenerate a huge diversity of original solutions, knowledgeand constraints were removed, not added. By usingcomponent-based representations, evolution is free to dowhat it does best: explore the search space for novelty, notfind a single, global optimum. And by also allowing humaninteraction, evolution is able to produce good solutions toproblems that cannot be encompassed in fitness functions.The second example: evolvable hardware, also showedthe creative potential of evolution in what looks set to be avery significant application for evolution in the future. By
--------------------------------------------------------------------------------
Page 8 
allowing evolution to consider a larger space of solutions,it is able to find innovative new circuit designs that humandesigners might not think of. The results for this sectionincluded an example of such novelty: a two-bit adderevolved with a non-traditional gate configuration.The third example illustrated some of the lessons we arecontinuing to learn from biology. Natural evolution is ableto generate diversity and complexity in living organismsbecause it uses developmental processes. Like theinnovations by creative evolutionary systems and evolvablehardware, evolution can generate novel developmentalprograms, which enable increased scalability, as wasshown in the results.Finally, the fourth example shows another way thatresearchers are beginning to use the natural abilities ofevolution observed in biology. Our immune systems arerobust, adaptive and distributed because they employ someclever evolutionary tricks. By using ideas inspired by theseprocesses within our computers, we are able to createrobust, adaptive and distributed tools, capable ofdiscovering novel patterns that distinguish betweendifferent types of data such as normal traffic and intrudersin a network.In summary, this paper has described the evolution of"dragonflies", adders, programs of development andimmune system detectors. Although diverse, these newtrends in EC have something important in common: inthem we are exploiting the innate abilities of evolution forexploration, innovation, adaptability and distributed search.Together, all of these new approaches will increase ourabilities to harness the power of natural processes in ourfuture technology.BibliographyBentley, P. J. (2001). Digital Biology: how nature is transformingour technology. Hodder Headline Press, London (to appear).Bentley,P.J.(2000).ExploringComponent-BasedRepresentations - The Secret of Creativity by Evolution? InACDM 2000, April 26th - 28th, 2000, University of Plymouth.Bentley, P. J. (Contributing Editor), (1999). Evolutionary Designby Computers. Morgan Kaufman Publishers Inc., San Fran, CA.Bentley, P. J. and Corne, D. W. (Eds) (2001) CreativeEvolutionary Systems. Morgan Kaufmann Pub (to appear).Bentley, P.J. & Kumar, S. (1999). Three Ways to Grow Designs:A Comparison of Embryogenies for an Evolutionary DesignProblem. In Genetic and Evolutionary Computation Conference(GECCO) Orlando, Florida, USA.Dasgupta, D., (1998), “An Overview of Artificial ImmuneSystems and Their Applications”, In Dasgupta, D. (editor).Artificial Immune Systems and Their Applications, Berlin:Springer-Verlag, pp.3-21.Dawkins, R. (1987). The Evolution of Evolvability. Proceedingsof Artificial Life VI. Langton (Ed.) USA.de Garis, H. (1999) Artificial Embryology and CellularDifferentiation. Ch. 12 in Bentley, P. J. (Ed.) EvolutionaryDesign by Computers. Morgan Kaufman Pub.Frazer, J. (1995). An Evolutionary Architecture. ArchitectureAssociation, London.Furuta, H., Maeda, K. & Watanabe, W. (1995). Apllication ofGenetic Algorithm to Aesthetic Design of Bridge Structures. InMicrocomputers in Civil Engineering v10:6. BlackwellPublishers, MA, USA, 415-421.Hollingworth, G., Smith, S., and Tyrell, A. (2000) The IntrinsicEvolution of Virtex Devices Through Internet ReconfigurableLogic. In Proceedings of the Third Int. Conf. on EvolvableSystems, Springer, pp. 72-79.Jakobi, N. (1996) Harnessing Morphogenesis. University ofSussex, Cognitive Science Research Report #429, Brighton, UK.Kim, J. and Bentley, P., (1999a), “The Human Immune Systemand Network Intrusion Detection”, 7th European Conference onIntelligent Techniques and Soft Computing (EUFIT '99), Aachen,Germany.Kim, J. and Bentley, P., (1999b), “The Artificial Immune Modelfor Network Intrusion Detection, 7th European Conference onIntelligent Techniques and Soft Computing (EUFIT’99), Aachen,Germany.Kim, J. and Bentley, P. J. (2001), The Artificial Immune Systemfor Network Intrusion Detection: An Investigation of ClonalSelection with a Negative Selection Operator. Submitted toCEC2001, the Congress on Evolutionary Computation.Koza, J.R., Bennett III, Forrest H, Andre, David, and Keane,Martin A. (1999). Genetic Programming III. San Francisco, CA:Morgan Kaufmann.Kumar and Bentley (2000). Computational Embryology: Past,Present and Future. To be published as an invited chapter inGhosh and Tsutsui (Eds) Theory and Application of EvolutionaryComputation: Recent Trends. Springer Verlag (UK).Levi, D. (2000) "HereBoy: a fast evolutionary algorithm." InProceedings of the Second NASA/DoD Workshop on EvolvableHardware, IEEE, pp. 17-24.Miller, J. F., Thompson, P., and Fogarty, T. (1997) DesigningElectronic Circuits Using Evolutionary Algorithms. ArithmeticCircuits: A Case Study. In Genetic Algorithms and EvolutionStrategies in Engineering and Computer Science: RecentAdvancements and Industrial Applications, Wiley, Chapter 6.Miller, J. F., Thompson, P. (1998) Discovering Novel DigitalCircuits using Evolutionary Techniques. In IEE Colloquium onEvolvable Systems, IEE.Rowbottom, A. (1999). Evolutionary Art and Form. In Bentley, P.J. (Ed.) Evolutionary Design by Computers. Morgan KaufmanPublishers Inc., San Francisco, CA.Sims, K. (1999). Evolving three-dimensional Morphology andBehaviour. Ch. 13 in Bentley, P. J. (Ed.) Evolutionary Design byComputers. Morgan Kaufman Pub.Thompson, A. (1996) Silicon Evolution. In Proceedings ofGenetic Programming 1996, MIT Press, pp. 444-452.