EVOLVINGBUILDINGBLOCKSFORDESIGNUSINGGENETIC ENGINEERING A FO(2)

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”samplingsetconvergestoth …… 此处隐藏：6062字，全部文档内容请下载后查看。喜欢就下载吧 ……