《分层元胞遗传算法研究》由会员分享，可在线阅读，更多相关《分层元胞遗传算法研究（65页珍藏版）》请在金锄头文库上搜索。
1、Research on Hierarchical Cellular AlogorithmA DissertationSubmitted for the Degree of MasterOn signal and information processingbyCai YeUnder the Supervision ofProf. Li Ming, Lu Yu-MingCollege of Information and EnginneringNanchang Hangkong University, Nanchang, ChinaMay, 2012摘要进化算法作为一种智能搜索算法将种群中的个体
2、当作待解决问题的潜在解，采用类似于自然界进化过程中的选择和进化机制来指导最优解的搜索方向。这种解决问题的办法已经成功地应用于解决一些复杂度高的传统算法难以处理的工程问题。进化算法中普遍存在的一个问题是如何在种群多样性和种群收敛速度之间找到平衡，即如何快速捕获全局最优，这是当前进化算法研究的热点，也是本文对分层元胞遗传算法研究的意义所在。针对元胞遗传算法（CGA）求解速度慢的特点，分层元胞遗传算法（HCGA）在求解过程中采用一种分层操作，让种群中的个体在进化过程中往元胞空间中心迁移。这种分层操作强化了种群中优秀个体的聚集，能有效提高元胞遗传算法的运算速度。在进化算法中，算法的运算速度与追踪种群最
3、优解的能力有关，算法跳出局部最优的能力与种群个体的多样性密切相关。分层元胞遗传算法的分层操作中元胞个体的移动局限于简单地与周围邻居元胞进行比较，这样使得算法的求解速度没有得到更大的提高。另一方面，分层元胞遗传算法元胞空间中的元胞个体仅往单一的元胞空间中心移动，这样使得种群的整体多样性不能得到更好的保持。为了更进一步提高分层元胞遗传算法的性能，本文从提高种群追踪最优解的能力和种群的整体多样性着手展开研究。本文对分层元胞遗传算法的研究内容主要包括以下几个方面的工作：1）研究了一种 HCGA和 PSO的混合算法这种改进的算法将粒子群优化算法（PSO）与分层元胞遗传算法相结合，利用粒子群算法中粒子运动
4、的位置和速度随当前最优解不断更新的特点，使得种群中个体进行分层操作后优秀个体聚集的趋势更加明显，分层元胞遗传算法中个体在进化时能更快速地捕获种群全局最优解从而提高算法的运算速度。文中研究了这种混合算法在不同优化强度下的算法性能并通过实验将改进算法与其他同类型算法进行了比较，实验结果表明，这种将粒子群优化算法与分层元胞遗传算法相结合的混合算法跟分层元胞遗传算法相比在计算速度上有较大的提高。2）研究了基于多中心城市策略的分层元胞遗传算法在进化算法运算的过程中，随着选择和遗传进化机制的不断进行，种群中个体间的多样性逐渐消失，进化个体之间的趋同性变强，这种情况会阻碍种群进化的持续进行。因此如何保持种群
5、的多样性是关系到算法性能的一个很重要的因I素。针对分层元胞遗传算法中种群个体往单一的元胞空间中心区域移动的特点，改进的算法在整个种群中选取多个优秀个体作为进化过程中的中心城市，在种群进化过程中元胞个体往不同的中心城市迁移。这种多中心城市策略在保持原有算法寻优速度的同时能够较好保持种群整体的多样性。实验结果表明改进的算法能够很好提高分层元胞遗传算法跳出局部最优的能力。关键词：元胞遗传算法，分层元胞遗传算法，粒子群，中心城市IIAbstractIn evolutionary algorithm, each individual in the population represent a poten
6、tialsolutions of the problems to be resolved. Mechanism similar to the selection andevolution in nature is used to guide the search direction of the optimal solution. Thiskind of solution has been used successfully in solve those engineering problem withhigh complexity. The common problem exist in E
7、volutionary algorithm is the balancebetween exploration and exploitation. Research on improve the efficiency of thealgorithm to find the global optimum is nowadays highly on the rise, and that is alsothe purpose of this study.By adding layered operation, computation speed of Cellular Genetic Algorit
8、hmhas been improved greatly in Hierarchical Cellular Genetic Algorithm (HCGA).In theevolutionary algorithm, calculation speed is related to the ability of tracking theoptimal solution, the escape ability from the local optimal is closely related to thediversity of the population. In Hierarchical Cel
9、lular Genetic Algorithm, the move ruleof cellular individuals is limited to neighbors and individuals in cellular space aremove to the single center. In order to further improve the performance of HCGA, thetrace ability of optimal solution and the diversity of the population were studied inthis pape
10、r.The main works of this paper research on Hierarchical Cellular Algorithm is asfollows:1) A Hybrid Algorithm Based on HCGA and PSOThis improved algorithm mixed the two algorithms together. In particle swarmalgorithms, position and movement speed of each particle in population is updatedwith the cur
11、rent optimal solution continuously. The advantages of PSO can makebetter result of layered operation in HCGA. The improved algorithm can trace theglobal optimal solution effectively and so as to improve calculation speed ofpopulation. Research on algorithms performance under the different optimizati
12、onstrength and comparison among algorithms with the same type has been done in thispaper. The experimental results show that Hybrid Algorithm Based on HCGA andPSO could capture the global optimal solution rapidly in the evolution process.III2) Research on Polycentric Hierarchical Cellular Genetic Al
13、gorithmsIn many case, the increase of the convergence speed is on the cost of thediversity lost in population. With The process of evolution, the species diversity lostgradually and the algorithms fall into the local optimum. Therefore, how to keep thediversity of population is the key problem to en
14、sure algorithm iterative operation. Inthis paper, a new polycentric Hierarchical Cellular Genetic algorithm on the basis ofHierarchical Cellular Genetic Algorithm and central city theory of western economicsis proposed .The characteristic feature of new algorithms is choosing a few individualwith high fitness in population as the center city. Individuals around the center citymoved towards the center, the optimal solution produced in those central cities. Thenew algorithm greatly improves population is diversity and the searching efficiency.The numerical simulations show th
