(1)Evolutionofcomplexbuildingblocks.Foreverycomponentoftheobjective
dividethepopulationinto3groups:function
,“good”(
“bad”(,and“neutral”(therestofpopulation).
Determinecombinations,ofthecurrentbuildingblockswhichdistinguishthe“good”samplingsetfromthe“bad”onestatisticallysigni cantlyusinganyoneofthepatternrecognitionalgorithms.
.Addcorres-Addittothecurrentsetofbuildingblocks
pondingnewassemblyrulesto.
(2)putenewpopulationusingavailablein-formationaboutcurrentpopulation.Thecom-ponentsofbelongtothenewextendedand.Thedependsontheop-timizationmethodemployed.Ifthegeneticalgorithmhasbeenchosenthen
istobecalculatedusingstandardcrossoverandmutationoperations.Becausetheupdatedgrammarincludesthegrammarfromthepreviousgenerationthesearchmethodguaranteesthatthenewpopulationisbetterthanthepreviousone(atleastnoworse)andthenew“good”samplingsetisclosertosamplingsetofthedesignstatespaceofinterest.
(3)Repeatsteps(1)and(2)untilthestopconditionsaremet.
Thestopconditionsusuallyaretheterminationorslowingdownoftheim-provementinand/ortheendofnewbuildingblocksgeneration.
4.Example
Evolvingthetargetedrepresentation
Asanexamplewetaketheproblemofthegenerationofa2-dimensionalblockdesignonauniformplanargrid(derivedfrom(GeroandKazakov,1995)).Thereisjustoneelementarycomponenthere-asquareandtheeightassemblyrules(trans-formationrulesintermsofashapegrammar)whichareshowninFigure7.Ifthepositionwherethecurrentassemblyruletriestoplacethenextsquareisalreadytakenthenallthesquaresalongthisdirectionareshiftedtoallowtheplacementofnewsquare.Itisassumedthatthetransformationruleatthe-thassemblingstageis
-thstage.Thecharacterist-appliedtotheelementaryblockaddedduringthe
icsofinterestaregeometricpropertiesofthegenerateddesign.Inordertodemon-stratetheidea,assumethatthegenerateddesigncannotconsistofmorethan32
Abstract. This paper presents a formal approach to the evolution of a representation for use in a design process. The approach adopted is based on concepts associated with genetic engineering. An initial set of genes representing elementary building blocks
12
0.9JohnS.GeroANDVladimirA.Kazakov0.8
TOTAL FRACTION OF COMPLEX GENES 0.70.60.50.40.3
0.2
0.1020406080100GENERATIONS120140160180
Figure9.Thefractionofcompositebuildingblocksinthetotalpoolofbuildingblocksusedtoassemblethepopulationvs.generationnumber.Theobjectivefunctionhastwocomponents:theareaofclosedholesandthenumberofconnectionsbetweenholesandtheoutsidespace.Theinitialsetofbuildingblockscontainsonlyelementarybuildingblocks.Evolutionproceedsuntilitnaturallydiesoff.
elementarycomponents.Wegenerateanewpopulationduringthestage(2)oftheAlgorithmusingthemodi cationofthesimplegeneticalgorithmtailoredtohandlemultidimensionalobjectivefunctions(GeroandKazakov,1995).Weimplementaverysimplepatternrecognitionalgorithmbasedonthestatisticalfrequencyana-lysesofdoubleandtripleelementbuildingblockswithahighcut-offthresholdfortheacceptanceofthepatterns.Formorecomplexsystemsmoresophisticatedtechniqueisneeded.
Duringthe rstiterationwebeginwiththesetofbuildingblockswhichcon-tainsonlytheelementaryonesandsearchforthedesignswithmaximalareaofen-closedholesandmaximalnumberofconnectionsbetweentheholesandoutsidespace.Theevolutionwasallowedtoproceeduntilastableconditionwasreached.TheresultareshowninFigures9and10.Byplottingthefractionofthecomplexbuildingblocksinthetotalpoolofbuildingblocksusedtoassemblethepopula-tionatdifferentgenerationsFigure9,onecanseehowcomplexbuildingblocksbecomedominantandhowitsfractionreachesastablelevelafter110-120itera-tions.ThefractionsofbuildingblocksofdifferentcomplexityinthetotalpoolatdifferentgenerationareshowninFigure10.Onecanseethatduringthe rst40generationsthetotalfractionofcompositebuildingblocksarisesmonotonically.Forthe rst10generationsthisriseiscompletelyprovidedbytheincreasingnum-berof1-complexitycompositebuildingblocksinthepopulation.Then(from15to30generations)thefractionof1-complexityblocksremainsstablebutthenum-berof2-complexitybuildingblocksincreasesandprovidesthecontinuingincrease
Abstract. This paper presents a formal approach to the evolution of a representation for use in a design process. The approach adopted is based on concepts associated with genetic engineering. An initial set of genes representing elementary building blocks
EvolvingBuildingBlocksforDesignUsingGeneticEngineering
0.8
1-COMPLEXITY2-COMPLEXITY3-COMPLEXITY4-COMPLEXITY5-COMPLEXITY6-COMPLEXITY7-COMPLEXITY8-COMPLEXITY130.7
FRACTION OF COMPLEX GENES 0.60.50.40.30.2
0.1
0020406080100GENERATIONS120140160180
Figure10.Thefractionofcompositebuildingblockswithdifferentcomplexitiesinthetotalpoolofthebuildingblocksusedtoassemblethepopulationvs.generationnumber.This gureshowsthebuildingblocksofdifferentcomplexitieswhicharesummedtoproducethetotalfractionshowninFigure9.
inthetotalfractionofcompositebuildingblocks.Fromgenerations40to70thistotalfractionisstablewithapproximatelyhalfofbuildingblocksof1-complexityandhalfof2,3and4-complexities.Thenthenumberof1-complexityblocksandtotalnumberofcomplexblocksdeclinessharplyandfrom70until110generationatransitionalprocessoccurswithacomplexredistributionofpopulationsbetweenrepresentationswithdifferentcomplexities.Attheendofthisperiodthebuildingblocksof8-complexitysaturatethepopulationwhenthefractionsoftheothercom-plexbuildingblocksareshiftedtowardsanoiselevelonly.OneoftheevolutionpathsinthespaceofcomplexbuildingblocksisshowninFigure11(a).SomeofthedesignsproducedareshowninFigure11(b).Herearrowsshowwhichpre-viouslyevolvedcompositebuildingblocksareusedtoassemblethenewbuildingblock.The0-complexityblockanditscontributionsareomitted.Aswealreadynotedcompositeblocksofthesamecomplexitylevelsometimeshavedifferentnumbersofelementarycomponents.Coincidently,the5-complexityblockisre-producedagainintherepresentationsof6-,7-and8-complexitiesandisoneofthedominantblocksattheendoftheevolutionaryprocess.