快速有效收敛遗传算法的研究

摘要

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