EVOLVINGBUILDINGBLOCKSFORDESIGNUSINGGENETIC ENGINEERING A FO(4)

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.

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