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.