EVOLVINGBUILDINGBLOCKSFORDESIGNUSINGGENETIC ENGINEERING A FO(3)

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

i …… 此处隐藏：5964字，全部文档内容请下载后查看。喜欢就下载吧 ……