GEP综述：Gene Expression Programming A New Adaptive A

11.IntroductionGeneexpressionprogramming(GEP)is,likegeneticalgo-rithms(GAs)andgeneticprogramming(GP),agenetical-gorithmasitusespopulationsofindividuals,selectsthemaccordingtofitness,andintroducesgeneticvariationusingoneormoregeneticoperators[1].Thefundamentaldiffer-encebetweenthethreealgorithmsresidesinthenatureoftheindividuals:inGAstheindividualsarelinearstringsoffixedlength(chromosomes);inGPtheindividualsarenonlinearentitiesofdifferentsizesandshapes(parsetrees);andinGEPtheindividualsareencodedaslinearstringsoffixedlength(thegenomeorchromosomes)whichareafter-wardsexpressedasnonlinearentitiesofdifferentsizesandshapes(i.e.,simplediagramrepresentationsorexpressiontrees).IfwehaveinmindthehistoryoflifeonEarth(e.g.,[2]),wecanseethatthedifferencebetweenGAsandGPisonlysuperficial:bothsystemsuseonlyonekindofentitywhichfunctionsbothasgenomeandbody(phenome).Thesekindsofsystemsarecondemnedtohaveoneoftwolimitations:iftheyareeasytomanipulategenetically,theyloseinfunc-tionalcomplexity(thecaseofGAs);iftheyexhibitacertainGeneExpressionProgramming:ANewAdaptiveAlgorithmforSolvingProblemsCândidaFerreira†DepartamentodeCiênciasAgráriasUniversidadedosAçores9701-851Terra-ChãAngradoHeroísmo,PortugalGeneexpressionprogramming,agenotype/phenotypegeneticalgorithm(linearandramified),ispresentedhereforthefirsttimeasanewtechniqueforthecreationofcomputerprograms.Geneexpressionprogram-mingusescharacterlinearchromosomescomposedofgenesstructurallyorganizedinaheadandatail.Thechromosomesfunctionasagenomeandaresubjectedtomodificationbymeansofmutation,transposition,roottransposition,genetransposition,generecombination,andone-andtwo-pointrecombination.Thechro-mosomesencodeexpressiontreeswhicharetheobjectofselection.Thecreationoftheseseparateentities(genomeandexpressiontree)withdistinctfunctionsallowsthealgorithmtoperformwithhighefficiencythatgreatlysurpassesexistingadaptivetechniques.Thesuiteofproblemschosentoillustratethepowerandversatilityofgeneexpressionprogrammingincludessymbolicregression,sequenceinductionwithandwith-outconstantcreation,blockstacking,cellularautomatarulesforthedensity-classificationproblem,andtwoproblemsofbooleanconceptlearning:the11-multiplexerandtheGPruleproblem.amountoffunctionalcomplexity,theyareextremelydifficulttoreproducewithmodification(thecaseofGP).Inhisbook,RiverOutofEden[3],R.Dawkinsgivesalistofthresholdsofanylifeexplosion.Thefirstisthereplicatorthresholdwhichconsistsofaself-copyingsysteminwhichthereishereditaryvariation.Alsoimportantisthatreplicatorssurvivebyvirtueoftheirownproperties.Thesecondthresh-oldisthephenotypethresholdinwhichreplicatorssurvivebyvirtueofcausaleffectsonsomethingelse-thepheno-type.Asimpleexampleofareplicator/phenotypesystemistheDNA/proteinsystemoflifeonEarth.Forlifetomovebeyondaveryrudimentarystage,thephenotypethresholdshouldbecrossed[2,3].Similarly,theentitiesofbothGAsandGP(simplereplicators)survivebyvirtueoftheirownproperties.Under-standingly,therehasbeenaneffortinrecentyearsbythescientificcommunitytocrossthephenotypethresholdinevo-lutionarycomputation.Themostprominenteffortisdevelop-mentalgeneticprogramming(DGP)[4]wherebinarystringsareusedtoencodemathematicalexpressions.Theexpres-sionsaredecodedusingafive-bitbinarycode,calledgeneticcode.Contrarytoitsanalogousnaturalgeneticcode,this“ge-neticcode”,whenappliedtobinarystrings,frequentlypro-ducesinvalidexpressions(innaturethereisnosuchthingasaninvalidprotein).Thereforeahugeamountofcomputationalresourcesgoestowardeditingtheseillegalstructures,whichlimitsthissystemconsiderably.Notsurprisingly,thegaininperformanceofDGPoverGPisminimal[4,5].________________________†Electronicmailandwebaddresses:[e-mail];:87-129,20012CreateChromosomesofInitialPopulationEndExpressChromosomesExecuteEachProgramEvaluateFitnessReplicationPrepareNewProgramsofNextGenerationKeepBestProgramSelectProgramsMutationIStranspositionRIStranspositionGeneTransposition1-PointRecombination2-PointRecombinationGeneRecombinationIterateorTerminate?TerminateIterateReproductionFigure1.Theflowchartofageneexpressionalgorithm.Theinterplayofchromosomes(replicators)andexpressiontrees(phenotype)inGEPimpliesanunequivocaltranslationsystemfortranslatingthelanguageofchromosomesintothelanguageofexpressiontrees(ETs).Thestructuralor-ganizationofGEPchromosomespresentedinthisworkal-lowsatrulyfunctionalgenotype/phenotyperelationship,asanymodificationmadeinthegenomealwaysresultsinsyn-tacticallycorrectETsorprograms.Indeed,thevariedsetofgeneticoperatorsdevelopedtointroducegeneticdiversityinGEPpopulationsalwaysproducesvalidETs.Thus,GEPisanartificiallifesystem,wellestablishedbeyondthereplicatorthreshold,capableofadaptationandevolution.TheadvantagesofasystemlikeGEPareclearfromna-ture,butthemostimportantshouldbeemphasized.First,thechromosomesaresimpleentities:linear,compact,relativelysmall,easytomanipulategenetically(replicate,mutate,re-combine,transpose,etc.).