资源描述：
《标准遗传算法收敛性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、SIAMJ.COMPUT.c2000SocietyforIndustrialandAppliedMathematicsVol.30,No.1,pp.269–282CONVERGENCECRITERIAFORGENETICALGORITHMS∗DAVIDGREENHALGH†ANDSTEPHENMARSHALL‡Abstract.Inthispaperwediscussconvergencepropertiesforgeneticalgorithms.Bylookingattheeffectofmutationonconvergence,weshowthatbyrunnin
2、gthegeneticalgorithmforasufficientlylongtimewecanguaranteeconvergencetoaglobaloptimumwithanyspecifiedlevelofconfidence.Weobtainanupperboundforthenumberofiterationsnecessarytoensurethis,whichimprovespreviousresults.Ourupperbounddecreasesasthepopulationsizeincreases.Weproduceexamplestoshowthati
3、nsomecasesthisupperboundisasymptoticallyoptimalforlargepopulationsizes.Thefinalsectiondiscussesimplicationsoftheseresultsforoptimalcodingofgeneticalgorithms.Keywords.geneticalgorithms,convergencecriteria,upperbounds,probability,optimalcodingAMSsubjectclassifications.68A10,68A20,60G35PII.S00
4、9753979732565X1.Introduction.Geneticalgorithmsarerobustsearchmechanismsbasedonunderlyinggeneticbiologicalprinciples.Havingbeenestablishedasavalidapproachtoproblemsrequiringefficientandeffectivesearch,geneticalgorithmsareincreasinglyfindingwidespreadapplicationinbusiness,scientific,andengineeri
5、ngcircles(Gold-berg(1989)).Thesealgorithmsarecomputationallysimpleyetpowerfulintheirsearchforimprovement.Theyworkonawiderangeofdiscretesearchspacesandareveryversatile,asfewassumptionsareneededaboutthesespaces.However,perhapsbecauseofthisversatility,relativelylittlemathematicaltheoryisavai
6、lableconcerningtheperformanceofthesealgorithms.Geneticalgorithmscomprisethreebasicmechanisms:reproduction,crossover,andmutation.Typicallythediscretespacetobesearchediscodedasasetofbinarystringsoflengthγ.Thesestringsareanalogoustochromosomes.Aninitialpopulationofnstringsischosen.Forsimplic
7、itynistakentobeeven.Thegoalofthegeneticalgorithmistofindthemaximumofsomeobjectivefunctionf(calledthefitnessfunction)definedonthesearchspace.AsimplegeneticalgorithmisdescribedinGoldberg(1989).Startingwiththeoriginalpopulation,anewpopulationofnstringsisselectedinthreesta
