EVOLVINGBUILDINGBLOCKSFORDESIGNUSINGGENETIC ENGINEERING A FO

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:AFORMALAPPROACH.

JOHNS.GEROANDVLADIMIRA.KAZAKOV

KeyCentreofDesignComputing,

DepartmentofArchitecturalandDesignScience,

TheUniversityofSydney,NSW2006Australia.

e-mail:john,kaz@arch.su.edu.au

Abstract.Thispaperpresentsaformalapproachtotheevolutionofarepresentationforuseinadesignprocess.Theapproachadoptedisbasedonconceptsassociatedwithgeneticengineering.Aninitialsetofgenesrepresentingelementarybuildingblocksisevolvedintoasetofcomplexgenesrepresentingtargetedbuildingblocks.Thesetargetedbuild-ingblockshavebeenevolvedbecausetheyaremorelikelytoproducedesignswhichex-hibitdesiredcharacteristicsthanthecommencingelementarybuildingblocks.Thetar-getedbuildingblockscanthenbeusedinadesignprocess.Thepaperpresentsaformalevolutionarymodelofdesignrepresentationsbasedongeneticalgorithmsandusespatternrecognitiontechniquestoexecuteaspectsofthegeneticengineering.Thepaperdescribeshowthestatespaceofpossibledesignschangesovertimeandillustratesthemodelwithanexamplefromthedomainoftwo-dimensionallayouts.Itconcludeswithadiscussionofstyleindesign.

1.Introduction

Thereisanincreasingunderstandingoftherolethatadesignlanguageanditsrep-resentationplayintheef ciencyandef cacyofanydesignprocesswhichusesthatlanguage(Coyneetal.,1990;Geroetal.,1994).Arecurringissueiswhatistheappropriategranularityofalanguage.Ifbuildingblockswhichconstitutetheelementsofadesignmapontoadesignlanguagethenthequestionbecomeswhatisanappropriatescaleforthosebuildingblocksintermsofthe naldesign.Atoneextremewehaveparameterisedrepresentationswherethestructureofadesignis xed,allthevariableswhichgotode neadesignareprede nedandwhatisleftistodeterminethevaluesofthosevariables.Thisde nesaverysmalldesignspace,smallintermsofallthepossibledesignswhichmightbeabletobeproducedforthatdesignsituation.Attheotherextremewehaveelementarybuild-ingblockswhichcanbecombinedinaverylargevarietyofwaysandwhich,asa

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

2JohnS.GeroANDVladimirA.

Kazakov

Se

Figure1.

ingblocks,

variables,isthedesignspaceproducedbyallthepossiblecombinationsoftheelementarybuild-isthedesignspaceproducedbyallthecombinationsofthevaluesoftheparameterisedisthedesignspaceofinterestingdesignsforthedesignsituation.

consequencede neaverylargedesignspace,thevastpartofwhichcoversdesignswhicharelikelytobeuninterestingintermsofthecurrentdesignsituation.Thedesignsproducedbytheparameteriseddesignrepresentationsareasubsetofthosecapableofbeingproducedbytheelementarybuildingblockrepresentation,Fig-ure1.Examplesofbuildingblockrepresentationsincludeconstructivesystemssuchasdesigngrammarsasexempli edbyshapegrammars(Stiny,1980b).Ex-amplesofparameterisedvariablerepresentationsincludeawidevarietyofdesignoptimizationformulations(Gero,1985).

Theadvantageoftheuseoftheelementarybuildingblocksrepresentationisthecoverageoftheentiredesignspacetheyprovide,whereastheadvantageoftheparameterisedvariablerepresentationistheef ciencywithwhichasolutioncanbereached.

Wepresenthereaformalapproachwhichgeneratesatargetedrepresentationofadesignproblem.Atargetedrepresentationistheonewhichcloselymapsontotheproblemathand.Asanexampleconsideralayoutplanningprobleminarchi-tecturaldesign.Onerepresentationmaybeatthematerialmolecularlevel,wheremoleculescanbecombinedtomakeavarietyofmaterialsandparticularcombina-tionsinspaceproducephysicalobjects;herethepotentialsolutionspaceincludesdesignswhichbearnorelationstoarchitecture.Atargetedrepresentationsmaybetorepresentroomssuchthatthepotentialsolutionspaceprimarilyincludesdesignswhichareallrecognizablyarchitecturallayouts.

Inordertosimplifyouranalysisweconsiderdesignswhichareassembledfrom

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

3

Figure2.ThesetofbuildingblocksforFroebel’skindergartengifts(Stiny,1980b).

some nitecollectionofspatialelements(wecallthembuildingblocksorcompon-ents)alongwithassemblyrules.Itisassumedthattheassemblyrulesdonotaffectthecomponents-thedesignobjectisaunionofnon-overlappingbuildingblocks.Westartwithsomesetofbuildingblockswhichwecallelementarycomponents.Itisassumedthattheycannotbedecomposedintoanysmallerones.Wecallasetofbuildingcomponentsandassemblyrulesarepresentationofthedesignproblemandthesetofelementarycomponentsandcorrespondingrulesthebasicrepresent-ation.Wecallitarepresentationbecauseitimplicitlyde nesthesetofalldesigns(designstatespace)whichcanbeproducedusingthissetofbuildingblocksandassemblyrules.

ThekindergartengiftsofFroebel(Stiny,1980b)isatypicalexampleofsuchtypesofdesignproblem.Oneofmanypossibleelementaryrepresentationsandas-semblyrulesforitisshowninFigures2and3.Onecaneasilyextenditbyaddingfurtherelementarybuildingblocksand/orfurtherassemblyrules.

Targetedrepresentations

uallythedesignerisinterestedinsomeparticularclassofdesigns.Assumewehavesomeadditionalsetofcompositebuildingblocksandanadditionalsetofassemblyrulestohandlethem.Wecancalculatethenumberofthesecompositebuildingblockswhichcanbefoundinallpossibledesignsinthatparticularclassandthenumberofelementarybuildingblocksusedtobuildtherestofthesedesigns(eachelementarybuildingblockshouldbecountedonlyonceasamemberofcompositebuildingorelementarybuildingblock,thelargestcompositeblocksarecounted rstandtheelementaryblocksarecountedlast).Thenwecancalculatethefrequencyofusageofthesecompositebuildingblocksandelementarybuildingblocksintheentiredesignspace.Thesamevaluescanbecalculatedforalldesignswhichhavethepropertyorpropertiesweareinterestedin.Ifthefrequencyoftheusageofthecompositebuildingblocksismuchhigherforthedesignsofinterestthanforalldesignsbuiltfromtheelementarybuildingblockandthefrequencyofelementarycomponentsusageismuchlowerthanthatofthecompositebuildingblocksforthedesignspaceofinterestthenwecanusethecompositebuildingblocksinstead

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

4JohnS.GeroANDVladimirA.

Kazakov

Figure3.ThesetofsixassemblyrulesforFroebel’skindergartengifts.

ofelementaryonetoproducedesignsofinterestwithmuchhigherprobability.Inotherwordsarepresentationexistswhichmapsintotheareaofinterestoftheentiredesignspace.Letuscallitthetargetedrepresentationfortheparticularclassofdesigns.Obviouslydifferenttargetedrepresentationscanbeproducedwhichcor-respondtodifferentsetsofcompositebuildingblocks.Wecharacterizetheserep-resentationsbytheir“complexity”whichisde nedrecursivelyas:0-complexityforthebasicrepresentation,1-complexityfortherepresentationwhosebuildingblocksareassembledfromelementarybuildingblocks,2-complexityfortherep-resentationwhosebuildingblocksareassembledfromthebuildingblocksof0-complexityand1-complexity,etc.Assumeanevolutionoccursinanabstractspaceofcomplexrepresentations:initiallyonlyelementarybuildingblocksexistthenacycleproceedswhenanewsetofcompositebuildingblocksisproducedfromtheoneswhicharecurrentlyavailable.Thenarepresentationofi-complexity(andbuildingblocksofi-complexity)simplymeansthatcompositebuildingblocksofthisrepresentationhavebeenproducedduring-thstepofthisevolution.

Differentcompositebuildingblocksofthesame-complexitymaycontaindif-ferentnumbersofelementarybuildingblocks:forexample,assumesomebuild-ingblockof3-complexitycontains3elementarybuildingblocksandoneofthecompositebuildingblocksof4-complexityisassembledfrom2buildingblocksof3-complexityandthuscontains6elementarycomponentsandanotheroneisas-sembledfromoneblockof3-complexityandoneblockof0-complexityandthuscontains4elementarycomponents.Itisalsoclearthatbecausetherearedifferentwaystoassemblethesamecompositebuildingblockitmaybeproducedmultiple

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

EvolvingBuildingBlocksforDesignUsingGeneticEngineering5

(a)

(b)(c)

Figure4.Thesetofcompositebuildingblocksofdifferentcomplexityforbuildingastaircase;(a)1-complexity,(b)and(c)2-complexity.

timesinrepresentationsofdifferentcomplexitylevelduringtheevolution.

Thesearchforareasonablygooddesignusingthebasicrepresentationisverydif cultbecausesigni cantpartofthesearcheffortiswastedinthesearchofun-usefulpartsofthedesignspace.Ifthetargetedrepresentationisusedinsteadofele-mentaryonetheprobabilityofproducingdesignsofinterestbecomesmuchhigher,thedesignspacebecomessmallerandthedesignproblemlesscomplicatedandeasiertodealwith.Theapproachpresentedinthisarticleautomaticallygeneratesthehierarchyofmoreandmorecomplexbuildingblocks(ingeneral);oneswhicharemoreandmoreclosetothetargetedrepresentationswhicharecapableofpro-ducingbetterandbetterdesigns.

AssumeweworkwiththerepresentationofthekindergartenblocksshowninFigures2and3andaretryingtodesignatwo-levelbuildingwithwalkingac-cessfromone oortothenext.Thesearchforadesignwiththispropertyisquitedif cultbecauseonlyaverysmallfractionofallfeasibleobjectsexhibitsitandtheprobabilityofdiscoveringthecombinationofbuildingblockswhichmakesastaircaseduringthesearchislow.However,ifweaddacompositeobjectof1-complexity(Figure4)andcorrespondingassemblyrulesFigure5totherepres-entationweincreasethisprobability,andifweaddacompositebuildingblockwith2-complexity(Figure4)thenthisprobabilityincreasesfurther.

Geneticengineering

Geneticengineering,asusedinthispaper,isderivedfromgeneticengineeringno-tionsrelatedtohumaninterventioninthegeneticsofnaturalorganisms.Inthege-neticsofnaturalorganismswedistinguishthreeclasses:thegeneswhichgotomakethegenotype,thephenotypewhichistheorganicexpressionofgenotype,andthe tnessofthephenotypeinitsenvironment.Whenthereisauniqueidenti- able tnesswhichisperformingparticularlywellorparticularlybadlyamongstallthe tnessofinterestwecanhypothesizethatthereisauniquecauseforitand

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

6JohnS.GeroANDVladimirA.

Kazakov

Figure5.Thesetofadditionalassemblyrulesforhandlingcompositebuildingblocks.thatthisuniquecausecanbedirectlyrelatedtotheorganism’sgeneswhichap-pearinastructuredforminitsgenotype.Geneticengineeringinconcernedwithlocatingthosegeneswhichproducethe tnessunderconsiderationandinmodify-ingthosegenesinsomeappropriatemanner.Thisisnormallydoneinastochasticprocesswhereweconcentrateonpopulationsratherthanonindividuals.

Organismswhichperformwell(orbadly)inthe tnessofinterestaresegreg-atedfromtheseorganismswhichdonotexhibitthat tnessordosoonlyinamin-imalsense.Thisbifurcatesthepopulationintotwogroups.Thegenotypesoftheformerorganismsareanalysedtodeterminewhethertheyexhibitcommonchar-acteristicswhicharenotexhibitedbytheorganismsinthelattergroup(Figure6).Iftheyaredisjunctive,thesegenesareisolatedonthebasisthattheyarerespons-iblefortheperformanceofthe tnessofinterest.Innaturalgeneticengineeringtheseisolatedgenesareeithertheputativecauseofpositiveornegative tness.Ifnegativethentheyaresubstitutedforby“good”geneswhichdonotgeneratethenegative tness.Iftheyareassociatedwithpositive tnesstheyarereusedinotherorganisms.Itisthislaterpurposewhichmapsontoourareaofinterest.

Onecaninterprettheproblemof ndingthetargetedsetofbuildingblocksasananalogofthegeneticengineeringproblem: ndingtheparticularcombin-ationsofgenes(representingelementarybuildingblocks)ingenotypeswhichareresponsibleforthepropertiesofinterestofthedesignsandregularusageofthesegeneclusterstoproducedesignswithdesiredfeatures.

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

7

‘‘good’’ genotypes‘‘bad’’ genotypes

Figure6.Thegenotypesofthe“good”membersofpopulationallexhibitgenecombinations,X,whicharenotexhibitedbythegenotypesofthe“bad”members.Thesegenecombinationsaretheonesofinterestingeneticengineering.

2.Buildingblocks

Thus,weestablishthatdifferentbuildingblocksde nedifferentdesignstatespaces(whichare,intheirturn,thesubsetsoftheentirebasicdesignspace).Moreform-allyweassumethatforthedesignspaceofinterestasetofcompositebuildingblocksexistswhichissuf cienttobuildanydesignofinterestfromit(orwhicharesuf cienttobuildasigni cantpartofanyofthesedesignsofinterest).

Wesearchforthesebuildingblocksusingtheconsequenceoftheassumptionmadeintheintroductionaboutfrequenciesofcompositecomponentsusage:onav-eragethesamplingsetofdesignswiththedesiredcharacteristics(the“good”ones)containsmoreofsuchcompositebuildingblocksthanthesamplingsetofdesignsthatdonothavethesecharacteristics(the“bad”ones).Insomecasesitiseventrueinadeterministicsense-thatonlythedesignswhichcanbebuiltcompletelyfromsomesetofcompositebuildingblockspossesstheobjectivecharacteristics,alltherestoftheentirebasicstatespacedoesnothavethem.Onecaneasilycomeupwithcorrespondingexamples.

Inthenextsectionwedescribeanevolutionaryalgorithmwhichgenerates“good”and“bad”samplingsetsusingthecurrentsetofbuildingblock(setofelementaryblockatthebeginning)andusegeneticengineeringconceptstodeterminenewcompositeblockswhichareclosertothe“targeted”onesthanthecurrentsetofbuildingblocks.Thesetwostepsproceedincyclewhilethe“good”samplingsetconvergestothesamplingsetfromthedesireddesignstatespaceandthesetof

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

8

JohnS.GeroANDVladimirA.

Kazakova

bFigure7.Theassembly(transformation)rulesusedintheexample.

complexbuildingblockscomescloserandclosertothetargetedset.

Ifthebasicassumptionaboutmorefrequentuseofsomecompositebuildingblockstogeneratetheparticularclassofdesignsisnottrueforsomeproblemthenthetargetedrepresentationforthisproblemdoesnotexistandthealgorithmwhichisproposedbelowwillnotgenerateanimprovedrepresentationbutwillbeequi-valenttothealgorithmforsolvingtheroutinedesignproblem(GeroandKazakov,1995)andwillsimplygeneratetheimproveddesigns.

Ifthesequenceofassemblyactionsiscodedasarealvectorthentheproblemof ndingthecomplexbuildingblocksbecomestheproblemof ndingthekeypatternsinthecodingvector-thecombinationsofcodeswithinitwhicharelikelytobeassociatedwiththepropertyofinterestinthedesigns.Thevastarsenalofpatternrecognitionmethodscanbeusedtosolvethisproblem.Essentiallytheyarejustsearchmethodsforsubsetsinacodingsequencewhichonaveragearemorefrequentlyobservedinobjectswithdesiredcharacteristicsthanintherestofthepopulation.

Letusillustratetheexecutionofthecyclejustoutlinedusingasimple2-dimensionalgraphicalexample.Wewilldescribeitinmoredetaillaterbutfornowonitissuf- cienttosaythatthereisonlyoneelementaryblockhere-thesquareandthatadesignisassembledfromcubesusingthe8rulesshowninFigure7.Anydesigncanbecodedasasequenceoftheserulesusedtoassembleit.Assumewearetryingtoproduceadesignwhichhasthemaximumnumberofholesinitandthateachdesigncontainsnotmorethan20squares.WestartthecyclebygeneratingasetofcodingsequencesandcorrespondingdesignsFigure8.Thenwenoticethatanum-ber(4)ofthedesignshavethemaximalnumberofholes(designs1,2,4,and7-the“good”samplingset)containthecompositebuildingblockandthatforthreeofthemtheircodingsequencescontainthepattern.Wealsonoticethatonlyafew(noneinthiscase)ofthedesignswithoutholes(designs3,5,8and10-the“bad”samplingset)containthisblockandnonecontainthispatternintheircodingsequence.Thenwecangeneratethenextpopulationofcodingsequencesusingthe

asanewrulewhichusesthecompositebuildingblockidenti edsequence

inthedesign.Assumingthatweemploysomeoptimizationmethodtogeneratethisnewpopulationwecanexpectthatthe“good”samplingsetfromthenewpop-

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

design 2design 39

good{3,2,2,6,5,8,2,1,4,4,3,1}design 6

{2,3,2,3,4,3,5,6,5,1,6,2}design 9

neutral{6,4,1,2,3,4,5,2,1,7,4}

Figure8.Theidenti cationofthepattern

inthegenotypesof“good”designs.andcorrespondingcompositebuildingblock

ulationisbetterthanthepreviousone(thatis,thedesignswhichbelongtoithaveonaveragemoreholesthantheonesfromtheprevious“good”samplingset).Thenweagaintrytoidentifythepatternswhicharemorelikelytobefoundindesignsfromthis“good”samplingsetthanfromthe“bad”one.Thistimethesepatternsmaycontainthepreviouslyidenti edpattersasacomponent.Thenwegenerateanewpopulationofdesignsusingtheseadditionalpatternsequencesofrulesasanadditionalassemblyruleandsoon.

Thesizesofthesamplingsetsinrealisticsystemsislikelytobemuchlarger

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

10JohnS.GeroANDVladimirA.Kazakov

thantheonesinthisexampleandmuchmoresophisticatedtechniques(PearsonandMiller,1992)shouldbeemployedtosingleoutthesekeypatterns.

3.Evolvingbuildingblocks

Foramoreformalanalysisoftheevolutionofthebuildingblocksweusetheshapegrammarformalism(Stiny,1980a).Itconsistsofanorderedsetofinitialshapesandanorderedsetofshapetransformationruleswhichareappliedrecursively.Aparticulardesignwithinthegivengrammariscompletelyde nedbyacontrolvectorwhichde nestheinitialshapeandtransformationrulesappliedateachstageofrecursiveshapegeneration.AccordingtothediscussionintheIntroduc-tionweconsideraparticularclassofshapegrammarsimilartothekindergartengrammar(Stiny,1980b),whereanyshapeisanon-overlappingunionofbuildingblocksandfeasibleshapetransformationsareaddition,replacementordeletionofthebuildingblocks.

beasetofcurrentlyavailablebuildingblocks,andbeasetofassemblyrulesapplicabletotheseblocks.,,,,Thenthecontrolvector

de nesthepopulationofdesigns,.,isavariable.Thelengthofthecontrolvector

Ifweaddnewcomplexbuildingblock

andnewassemblyrulesforitshandlingthenwegetanewextendedsetofrules,,and.

whichcorrespondstothevectorwhoseNowwecanproducethedesign

componentsbelongtotheextendedand.Notethattheadditionalbuildingblocksandassemblyrulesaregeneratedrecursively:theyarecompletelyde nedintermsofthepreviousand.

Weassumethatthedesignproblemhasaquanti ableobjectivevector-function,andcanbeformulatedasoptimizationproblemLet

(1)

Theproblem(1)overtherepresentationwitha xedsetofbuildingcompon-entsandassemblerulescanbesolvedusinganyofoptimizationmethods(GeroandKazakov,1995)butthestochasticalgorithmslikegeneticalgorithms(Hol-land,1975)andsimulatedannealing(Kirkpatricketal.,1983)lookmostprom-isingatthemoment.Wehavechosenthegeneticalgorithm.

Theevolutionarymethodhasthefollowingstructure:

Algorithm

.Takethesetofelementarybuild-(0).Initialization.Setcounterofiteration

andcorrespondingassemblyrules.Generatesomeingblocks

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

EvolvingBuildingBlocksforDesignUsingGeneticEngineering11

randompopulationof,calculateand.Settherelativethresholds;theyareusedduringanevolutionforthedesign’sranking

stagetodividethedesigninto“good”,“bad”and“neutral”samplingsets,thatis,thepartsofpopulationwhichexhibit()best,()worseandintermediaterel-ative tnesslevel.

(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.

Usingtargetedrepresentation.

Thesetoftargetedbuildingblocksevolvedduringthisprocessisthenusedasaninitialsetofbuildingblocksduringthesecondexperimentwhenweproducethedesignswithmaximaltotalareaofholesinsideandmaximalnumberofconnec-tionsbetweentheseholesinsidethestructure.Herethe tnessesareclosetobut

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

14JohnS.GeroANDVladimirA.

Kazakov

Figure11.(a)Anexampleoftheevolutionarypathsintheevolutionofacomplexbuildingblock,(b)someofthedesignsproducedusingthesetofevolvedcomplexblocks.

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

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

015TOTAL FRACTION OF COMPLEX GENES020406080100GENERATIONS120140160180

Figure12.Thefractionofcompositebuildingblockinthetotalpoolofbuildingblockusedtoas-semblethepopulationvs.generationnumber.Inthisexperimenttheobjectivefunctionisthenum-berofclosedholesandthenumberofconnectionbetweentheclosedholesinsidethestructure.Theinitialsetofbuildingblocksisinheritedfromthe rstexperimentandisthetargetedrepresentation.notthesameasthoseusedtoevolvethetargetedrepresentation.Thisexperimentisusedtotestwhetherthetargetedrepresentationislikelytobeusedmorethantheoriginal,elementarybuildingblocks.Ifthetargetedrepresentationisusedratherthantheelementarybuildingblocksthenwehaveachievedourgoalofevolvingarepresentationcanbeusedtoproducedesignswhichexhibitdesiredcharacterist-icsmorereadily.TheresultsareshowninFigures12and13.Onecanseethatthefractionofthecompositebuildingblocksusedtoproducethesedesignsreachesthesaturationlevelduringthe rstfewiterations.Thevisibleredistributionsofthepopulationbetweenthecompositebuildingblocksof5,6and7-complexitiesarepurelysuper cial-thisredistributionoccursbetweenthesamecompositebuildingblockswhicharepresentinalltheserepresentations.Evolutionoftherepresenta-tiondoesnotoccurduringthisexperiment-nonewcomplexbuildingblockwereevolved.Thiscanbeinterpretedasanindicationofclosenessofthetargetedrep-resentationsforbothproblems.Soifthetargetedrepresentationisevolvedforonesetofobjectivesthenitcanbeusefullyappliedtoanyoftheobjectivesetswhichareonlyslightlydifferenttoit.

Effectsofincompleteevolution

Inthisexperimentwerepeatthe rstiterationbutstoptheevolutionprematurelyafteronly60generations.Afterthiswerepeattheseconditerationusingtheevolvedincompletesetofcompositebuildingblocks.TheresultsareshowninFigures14

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

16

0.9JohnS.GeroANDVladimirA.Kazakov0.8

0.7

FRACTION OF COMPLEX GENES 0.60.51-COMPLEXITY2-COMPLEXITY3-COMPLEXITY4-COMPLEXITY5-COMPLEXITY6-COMPLEXITY7-COMPLEXITY8-COMPLEXITY0.40.3

0.2

0.1

0020406080100GENERATIONS120140160180

Figure13.Thefractionofcompositebuildingblockswithdifferentcomplexitiesinthetotalpoolofthebuildingblockusedtoassemblethepopulationvs.generationnumberintheexperiment.

1

0.9

TOTAL FRACTION OF COMPLEX GENES 0.80.7 0.60.50.40.3

0.2

0.10102030GENERATIONS405060

Figure14.Thefractionofcompositebuildingblockinthetotalpoolofbuildingblockusedtoas-semblethepopulationvs.generationnumber.Inthisexperimenttheobjectivefunctionisthenumberofclosedholesandthenumberofconnectionsbetweentheclosedholesinsidethestructure.Theini-tialsetofbuildingblocksisinheritedfrom rstiterationwhichhasbeenprematurelyterminatedatgeneration60.

and15.Inthiscasetheevolutionoftherepresentationcontinuesforaboutafur-ther10generationsandweendupwiththesamesetofevolvedcompositebuildingblocks.Thesaturationofthepopulationwiththecompositebuildingblocksisalsocompletedafterthese10generations.Thus,onecanstarttoevolvearepresenta-

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.9170.8

0.7

FRACTION OF COMPLEX GENES 0.60.51-COMPLEXITY2-COMPLEXITY3-COMPLEXITY4-COMPLEXITY5-COMPLEXITY6-COMPLEXITY7-COMPLEXITY8-COMPLEXITY0.40.3

0.2

0.1

00102030GENERATIONS405060

Figure15.Thefractionofcompositebuildingblockswithdifferentcomplexitiesinthetotalpoolofthebuildingblockusedtoassemblethepopulationvs.generationnumberinthethirdexperiment.tionforonesetofobjectivesandthencontinueitforanothercloselyrelatedsetofobjectives.

Ifwecommencebytreatingtheproblemasoneof ndingimproveddesignsthenfromacomputationalviewpointthisformofevolutionspeedsuptheconver-

(intermsofthenumberofgenerationsgencetoimproveddesignsbyupto

required)whencomparedwithstandardgeneticalgorithms.Itappearsthattheuseofatargetedrepresentationcanleadtotheproductionofdesignswhicharelocallyoptimal.

However,ifweusethecompletionevolutionapproachpresentedinthesecondexperimentwegetfurtherimprovementsinperformance.WewillleavetotheDis-cussionsectionfurtherdiscussionoftheotheradvantagesoftheapproachpresen-ted.

5.Discussion

Theanalysisjustpresentedcanbeeasilyextendedtoincludegeneralobjectgram-marsoftypesdifferenttothekindergartengrammar.Theproposedapproachcanbeconsideredasanimplementationofthesimplestversionofthegeneticengin-eeringapproachtothegenericdesignproblem.Fromthetechnicalpointofviewthealgorithmpresentedisamixtureofastochasticsearchmethod(whichmaybeageneticalgorithm)andapatternrecognitiontechnique.

Thegeneticengineeringapproachcanbeappliedinasimilarfashiontotheproblemofthegenerationofa“suitable”shapegrammar(GeroandKazakov,1995)wherethecomplexbuildingblockscorrespondtotheevolvedgrammarrules.

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

18JohnS.GeroANDVladimirA.Kazakov

Asalreadymentionedintheanalysisofthenumericalexperiment,theevolvedrepresentationsarehighlyredundant-thesamecompositebuildingblocksareevolvedmanytimesalongthedifferentbranchesoftheevolutionarytrees.Theredundancylevelofthecurrentsetofcompositebuildingblockscanbereducedinanumberofdifferentways.Thesimplestisjusttodeletealltheredundantcopiesfromthecurrentset.Inthegeneralcase,wehaveto ndtheminimalrepresentationofthesubspacewhichcanbegeneratedusingthecurrentsetofcomplexbuildingblocks.Theintroductionofideasandmethodsfromgeneticengineeringintodesignsystemsbasedongeneticalgorithmsopensupanumberofavenuesforresearchintobothevolutionary-baseddesignsynthesisandintomodi edgeneticalgorithms.Indesignsystemsbasedonsuchmodi edgeneticalgorithmsitispossibletocon-sidertwodirections.

The rstistotreatthesequenceofthegeneswhichresultsincertainbehavioursor tnessperformancesasaformof‘emergence’,emergenceoftheschemarepres-entedbythatgenesequence.Theuseofthegeneticallyengineeredcomplexgeneschangesthepropertiesovertimeofthestatespaceswhicharebeingsearched.Thisallowsustoconsidertheprocessasbeingrelatedtodesignexplorationmodelledinaclosedworld.Theprecisemannerinwhichtheprobabilitiesassociatedwithstatesinthestatespacechangeisnotyetknown.Clearly,thisisalsoafunctionofwhethera xedlengthgenotypeencodingisusedornot.Ifavariablelengthgenotypeencodingisusedwiththegeneticallyengineeredcomplexgenesthentheshapeofthestatespaceremains xedbuttheprobabilitiesassociatedwiththestateswithinitchange.Ifa xedlengthgenotypeencodingisusedwiththege-neticallyengineeredcomplexgenesthentheshapeofthestatespacechangesinadditiontotheprobabilitiesassociatedwithstatesinthestatespace.

Thesecondistotreatthegeneticallyengineeredcomplexgenesasameansofdevelopingarepresentationforpotentialdesigns.Afundamentalpartofdesign-ingisthedeterminationofanappropriaterepresentationofthecomponentswhichareusedinthestructure(Gero,1990)ofthedesign.Thisispartofthataspectofdesigningcalled‘formulation’,iethedeterminationofthevariables,theirre-lationshipsandthecriteriabywhichresultingdesignswillbeevaluated.Inmostcomputer-aideddesignsystemsthecomponentsmapdirectlyontovariables.Fur-ther,insuchsystemsthevariablesarespeci edattheoutset,asaconsequencethereisanunspeci edmappingbetweenthesolutionscapableofbeingproducedandthevariableschosentorepresenttheideaswhicharetobecontainedintheresultingdesigns.Thegeneticengineeringapproachdescribedprovidesameansofautomat-ingtherepresentationpartoftheformulationprocess.Thelevelofgranularityisdeterminedbythestabilityconditionoftheevolutionaryprocessorcanbedeterm-inedbytheuser.Thetargetedbuildingblocksprovideahigh-levelstartingpointforalllaterdesignswhicharetoexhibittherequiredcharacteristicsasevidencedintheearlierdesigns.Itisthislatterrequirementwhichismetbythisformalmethod.Thefollowingsimplepicturecanbeusedtosummarizethemodeldescribedin

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

EvolvingBuildingBlocksforDesignUsingGeneticEngineering19thispaper.Agroupofchildrenareplayingwiththe“Lego”gameusingnotmorethan50squares.Theyjointhemtogetherandwanttobuildtheobjectwiththelargestnumberofclosedspacesinside.Aftereachchildhasbuilthisorherob-jectthesupervisortriesto ndacombinationofsquareswhichispresentinmanyofthebestdesignsbutispresentinnoneoronlyinafewofunsatisfactorydesigns.Thenhemakesthiscombinationpermanentbygluingitscomponentstogetherandaddsabunchofsuchpermanentcombinationstothepoolofbuildingelementsavailabletothechildren.Thenthechildrenmakeanothersetofobjectsusingthesenewbuildingblocksaswellasanoldones.Thesupervisortriesto ndanother“good”compositeblockandtheprocessisrepeated.Thus,twostepsoccurineachcycle: rstchildrenmakeasetofnewdesignsfromcurrentlyavailableblocksandcombinationofblocksandsecondthesupervisortriestosingleouttheadditionalcombinationofblocksthatshouldbeemployed.Iftherearenosuchcombinationswhichdistinguish“good”designfromthe“bad”onesthenwewillnotgetnewcombinationsbutonlytheimproveddesigns.

Style

Thechoiceofparticularvariablesandcon gurationsofvariablesisadetermin-antofthestyleofthedesign(Simon,1975).Thelabel‘style’canbeusedinatleasttwoways:eithertodescribeaparticularprocessofdesigningorasameansofdescribingarecognizablesetofcharacteristicsofadesign.Thus,itispossibletotalkaboutthe‘Gothic’styleinbuildingsorthe‘hightech”styleofconsumergoods.Preciselywhatgoestomakeupeachofthesestylesisextremelydif culttoarticulateeventhoughweabletorecognizeeachofthesestyleswithverylittledif culty.Anappropriatequestiontoposeis:howcanweunderstandwhatpro-ducesastyleduringtheformulationstageofadesigningprocess?Thisbringsusbacktotheconceptsdescribedinthispaper.

‘Thehistoryoftasteandfashionisthehistoryofpreferences,ofvariousactsofchoicebetweendifferentalternatives......[But]anactofchoiceisonlyofsymptomaticsigni cance,isexpressiveofsomethingonlyifwecanreallywanttotreatstylesassymptomaticofsomethingelse,wecannotdowithoutsometheoryofthealternatives’(Gombrich,quotedfrom(Simon,1975)).Ifweuseaparticularstyleasthe tnessofinterestthenitshouldbepossibletoutilisethegeneticengineeringapproachdescribedinthispapertodetermineifthereisauniquesetofgenesorgenecombinationswhichiscapableofbeingtheprogenitorsofthatstyle.Forthistooccursatisfactorilyaricherformofpatternrecognitionwillbeneededthanthatalludedtohere.Wewillneedtobeabletodetermineawidervarietyofgeneschemasinthegenotypesofthosedesignswhichexhibitthedesiredstyle.

Theuseofgeneticengineeringinevolvingschemasofinterestopensupapo-tentialsubsymbolicmodelofemergenceincludingtheemergenceofdomainse-