分层元胞遗传算法研究

《分层元胞遗传算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ResearchonHierarchicalCellularAlogorithmADissertationSubmittedfortheDegreeofMasterOnsignalandinformationprocessingbyCaiYeUndertheSupervisionofProf.LiMing,LuYu-MingCollegeofInformationandEnginneringNanchangHangkongUniversity,Nanchang,ChinaMay,2012摘要进化算法作为一种智能搜索算法将种群中的个体当作待解决问题的潜在解，采用类似于自然界进化过程中的选

2、择和进化机制来指导最优解的搜索方向。这种解决问题的办法已经成功地应用于解决一些复杂度高的传统算法难以处理的工程问题。进化算法中普遍存在的一个问题是如何在种群多样性和种群收敛速度之间找到平衡，即如何快速捕获全局最优，这是当前进化算法研究的热点，也是本文对分层元胞遗传算法研究的意义所在。针对元胞遗传算法（CGA）求解速度慢的特点，分层元胞遗传算法（HCGA）在求解过程中采用一种分层操作，让种群中的个体在进化过程中往元胞空间中心迁移。这种分层操作强化了种群中优秀个体的聚集，能有效提高元胞遗传算法的运算速度。在进化算法中，算法的运算速度与追踪种群最优解的能力有关，算法跳出局部最优的能力与种群个

3、体的多样性密切相关。分层元胞遗传算法的分层操作中元胞个体的移动局限于简单地与周围邻居元胞进行比较，这样使得算法的求解速度没有得到更大的提高。另一方面，分层元胞遗传算法元胞空间中的元胞个体仅往单一的元胞空间中心移动，这样使得种群的整体多样性不能得到更好的保持。为了更进一步提高分层元胞遗传算法的性能，本文从提高种群追踪最优解的能力和种群的整体多样性着手展开研究。本文对分层元胞遗传算法的研究内容主要包括以下几个方面的工作：1）研究了一种HCGA和PSO的混合算法这种改进的算法将粒子群优化算法（PSO）与分层元胞遗传算法相结合，利用粒子群算法中粒子运动的位置和速度随当前最优解不断更新的特点，使

4、得种群中个体进行分层操作后优秀个体聚集的趋势更加明显，分层元胞遗传算法中个体在进化时能更快速地捕获种群全局最优解从而提高算法的运算速度。文中研究了这种混合算法在不同优化强度下的算法性能并通过实验将改进算法与其他同类型算法进行了比较，实验结果表明，这种将粒子群优化算法与分层元胞遗传算法相结合的混合算法跟分层元胞遗传算法相比在计算速度上有较大的提高。2）研究了基于多中心城市策略的分层元胞遗传算法在进化算法运算的过程中，随着选择和遗传进化机制的不断进行，种群中个体间的多样性逐渐消失，进化个体之间的趋同性变强，这种情况会阻碍种群进化的持续进行。因此如何保持种群的多样性是关系到算法性能的一个很重

5、要的因I素。针对分层元胞遗传算法中种群个体往单一的元胞空间中心区域移动的特点，改进的算法在整个种群中选取多个优秀个体作为进化过程中的中心城市，在种群进化过程中元胞个体往不同的中心城市迁移。这种多中心城市策略在保持原有算法寻优速度的同时能够较好保持种群整体的多样性。实验结果表明改进的算法能够很好提高分层元胞遗传算法跳出局部最优的能力。关键词：元胞遗传算法，分层元胞遗传算法，粒子群，中心城市IIAbstractInevolutionaryalgorithm,eachindividualinthepopulationrepresentapotentialsolutionsoftheprobl

6、emstoberesolved.Mechanismsimilartotheselectionandevolutioninnatureisusedtoguidethesearchdirectionoftheoptimalsolution.Thiskindofsolutionhasbeenusedsuccessfullyinsolvethoseengineeringproblemwithhighcomplexity.ThecommonproblemexistinEvolutionaryalgorithmisthebalancebetweenexplorationandexploitatio

7、n.Researchonimprovetheefficiencyofthealgorithmtofindtheglobaloptimumisnowadayshighlyontherise,andthatisalsothepurposeofthisstudy.Byaddinglayeredoperation,computationspeedofCellularGeneticAlgorithmhasbeenimprovedgreatlyinHier