EVOLVINGBUILDINGBLOCKSFORDESIGNUSINGGENETIC ENGINEERING A FORMAL APPROACH.
更新时间:2023-07-29 10:14:01 阅读量: 实用文档 文档下载
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-
正在阅读:
EVOLVINGBUILDINGBLOCKSFORDESIGNUSINGGENETIC ENGINEERING A FORMAL APPROACH.07-29
2013最新人教版新目标八年级英语上课文翻译二单元08-13
Content and context aware networking using semantic tagging07-27
医书推荐下载05-02
中华民国宪法《完整》01-30
会计实务试题及答案05-02
- 1Computer Methods in Applied Mechanics and Engineering
- 2Disordes of Fluids and Electrolytes--Physiological Approach
- 3A Novel Approach for Automatic Palmprint Recognition
- 4The use of formal models in the design of interactive case m
- 5A Unifying Conformal Field Theory Approach to the Quantum Hall Effect
- 6An Implementable Formal Language for Hard Real-Time Systems
- 7交通工程课后题答案—Traffic Engineering
- 8ENGINEERING, PROCUREMENT AND CONSTRUCTION AGREEMENT合同范本
- 9Open Framework for Collaborative Model Based Engineering
- 10An Evolutionary Multiobjective Approach for Community Discov
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- EVOLVINGBUILDING
- BLOCKSFORDESIGNU
- SINGGENETIC
- ENGINEERING
- APPROACH
- FORMAL
- 2015四川农村信用社招聘考试每日一练答案(4月8日)
- 电大合同法最新案例分析小抄集锦
- 华北水利水电大学2014年就业质量年度报告
- 投资理财综合实训报告总结
- 慢性乙型肝炎患者外周血CD4+CD25+、CD8+CD28+淋巴细胞的变化及与病毒载量的关系
- 传承--DIY陶艺店创业计划书
- 对电气工程及其自动化专业职业岗位环境认知调查
- 论舒曼《幻想曲集》OP.12的创作及演奏
- 惊恐障碍临床路径
- 2015安徽公务员考试公共基础知识_政治常识11
- 房地产项目成本控制限额指标
- 十一. 实验:把电流表改装为电压表
- 日媒称歼-20堪比零式战机 若东海空战美日必胜
- 论文关键词:少数民族音乐 兴趣
- 华中科技大学标准C语言程序设计及应用习题答案
- 可调谐激光吸收光谱法与气相色谱法监测甲烷的对比研究
- 基于城市道路功能划分的交叉口指路标志信息分级体系(1)
- 2013江苏小高考生物试卷
- 2014年联考言语理解主旨概括题主体排除技巧分析
- 湘教版气温和降水说课稿