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