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.