资源描述:
《一种协调勘探和开采的遗传算法_收敛性及性能分析》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第24卷第12期计算机学报Vol.24No.122001年12月CHINESEJ.COMPUTERSDec.2001一种协调勘探和开采的遗传算法:收敛性及性能分析1)1)1)2)江瑞罗予频胡东成司徒国业1)(清华大学自动化系北京100084)2)(香港科技大学物理系香港)摘要提出了一种新的遗传算法结构.在该结构中,每一代的新种群由保留种群、繁殖种群和随机种群三部分组成,而它们的相对数量则由不同的参数进行控制,这体现了该算法在运行过程中对搜索空间勘探和开采操作的协调和权衡.通过把该算法建模为齐次的有限Markov链,该文
2、证明了该算法具有全局收敛性.对试验数据的分析表明,该算法能够有效协调算法对问题解空间的勘探和开采操作,因而在处理复杂问题时表现出较高的性能.关键词遗传算法,勘探,开采,有限Markov链中图法分类号:TP18AGeneticAlgorithmbyCoordinatingExplorationandExploitation——ConvergencePropertiesandPerformanceAnalyses1)1)1)2)JIANGRuiLUOYu-PinHUDong-ChengSZETOKwok-Yip1)(Dep
3、artmentofAutomation,TsinghuaUniversity,Beijing100084)2)(DepartmentofPhysics,HongKongUniversityofScienceandTechnology,HongKong)AbstractAnewkindofgeneticalgorithmarchitectureisbroughtforwardinthispaper.Thesimplephilosophyunderlyingthenewalgorithmistodividethepopul
4、ationofageneticalgorithmintodifferentpartsandattachmeaningtoeachsub-populationtoenableefficienttuningoftheim-portanceofexplorationandexploitationduringevolutionbycontrollingthesizesofthesub-popu-lations.Inthealgorithmarchitecture,thenewpopulationineachgeneration
5、iscreatedandcon-stitutedbythreesub-populations:apreservedpart,areproducedpartandarandomizedpart.Thenumberofthepreservedindividualsmeasurestheattentiontoexploitation;thenumberofthereproducedindividualsmeasurestheattentiontotheeffectofvariousgeneticoperationswhile
6、exploringthesolutionspaceofthegivenproblem;thenumberofrandomlygeneratedindividualsmeasurestheattentionpaidtotheeffectofgettingtrappedinlocaloptima.Correspondingparam-etersareintroducedintothearchitecturetocontroltherelativeamountofeachsub-populationandthroughthi
7、sway,thealgorithmcanachievethecoordinationandbalancebetweentheexplo-rationofthesolutionspaceofgivenproblemandtheexploitationoftheinformationinpastsearch,thusgettinghighperformanceswhileoptimizingcomplexmulti-modalfunctions.Bytreatingthecollectionofindividualsine
8、achgenerationasastateandmodelingthealgorithmasahomogeneousfiniteMarkovchain,itisproventhatthenewalgorithmcanguaranteetheconver-gencetowardstheglobaloptimumoftheproble