EVOLVINGBUILDINGBLOCKSFORDESIGNUSINGGENETIC ENGINEERING A FO(2)

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说公务员考试EVOLVINGBUILDINGBLOCKSFORDESIGNUSINGGENETIC ENGINEERING A FO(2)在线全文阅读。