【作者】 祝希路；

【导师】 李智勇；

【作者基本信息】 湖南大学 ， 计算机应用技术， 2007， 硕士

【摘要】 遗传算法作为一种基于生物界自然选择和遗传原理的高效的搜索技术,已成功的应用于工程设计,工商管理,科学实验等领域中的复杂优化问题的求解。然而,GA在进化寻优的过程中将不可避免地使种群的多样性渐失,可能使种群收敛于局部极值,形成“早熟”收敛。当前对此问题所作的大量研究工作,其解决方法大致可为分为三类:1)增加群体规模;2)静态或动态调整交叉和变异概率;3)加入其他算子。本文分析和研究几种常用的维持种群多样性的遗传算法,在此基础上提出了两种新的遗传算法,给出了理论分析,并进行了仿真实验。本文的主要工作如下:1)深入研究小生境算法,变异算子和并行遗传算法的基本理论及其进化机理以及如何有效的维持种群多样性,克服“早熟”收敛的原理。2)根据共享小生境遗传和变异算子能增强和保持生物种群的多样性的特点,提出一种共享变异算子,该算子有效的维持种群的多样性,防止“早熟”收敛,同时确定变异的方向,确保好的模式被保存下来,提高算法搜索性能。在求多极值进化算法中,引人一种半径判别方法,从而不需要小生境半径的先验知识。该策略有利于维护种群多样性,提高收敛速度。3)针对并行GA能降低早收敛的可能性,提出一种基于建筑块迁移策略模拟退火并行遗传算法。算法根据种群的收敛情况,从其它种群中获取非重叠的建筑块。采用模拟退火思想防止优良模式的浓度过快地增大引起早熟。理论分析和对多峰函数的仿真结果均表明,该算法减少了无效迁移次数,降低通信开销。而且发生成熟前收敛的概率明显下降,保证遗传算法的全局收敛性。更多还原

【Abstract】 Genetic algorithm based on the principle of efficient search and genetic technology has been successfully applied in engineering design, business management and other areas of scientific experiments to solve complex optimization problems. However, in the process of search of global solution, the diversity gradually diminishes to zero. Convergence, more often, divert to the local solution, causing premature convergence. In fact, lots of works in genetic algorithm solve the problem of premature convergence. The solution could be broadly divided into three categories: 1) increasing the population size, 2) static or dynamic adjustment of crossover and mutation probability, 3) adding other operator. In this paper, several genetic algorithms efficiently maintaining diversity are analyzed. Two new kinds of genetic algorithm is given out, and the experimental testing is carried out. The main important work of this paper includes:(1) Deeply study the basic theory of niche, mutation operator, parallel genetic algorithm, how to efficiently maintain the diversity of genetic algorithm and premature convergence.(2) Basing on the characteristic of enhancing population diversity of niche and mutation operator, a sharing mutation algorithm is proposed, the algorithm efficiently maintains population diversity, prevent premature, and guide the mutation course, accelerate convergence. Applying a new method avoid the hard problem that determine the radius of niche. Simulation on benchmark function shows that the algorithm greatly improves the global efficiency.(3) Considering the possibility of inhabiting the premature convergence, a parallel genetic algorithms based on building block migration is proposed. Relying on convergence situation, get unlapped building block from other population. Using simulated annealing method prevent the density of good schema increase greatly resulting in premature convergence. Theory analysis and experimental results show that the method not only reduce ineffective migration and decrease communication costs, but also lower the possibility of occurring premature and assure the capability of global convergence.更多还原