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.