基于聚类思想的改进混合遗传算法

现代科学理论研究和实践中存在着大量优化及自适应问题。在大规模的复杂多模态优化问题上，一般的计算方法无能为力。遗传算法是一种模拟生物遗传进化过程的自适应全局优化概率搜索算法。它依据概率对各代种群施加选择、交叉和变异等遗传操作，使种群逐步进化到包含或接近最优解的状态，是解决各类复杂优化问题的一种有效算法。 早熟收敛和收敛速度之间的平衡一直是遗传算法研究的焦点。如何有效平衡这一冲突，是改善算法在复杂多模态优化问题上性能的关键。早熟收敛的主要成因是优良个体间的近亲繁殖，导致种群多样性过早丧失。针对以上问题，本文先后将K均值,层次聚类以及最小生成树等聚类方法和最优代表思想加入遗传算法中，提出了对应的改进遗传算法；并在此基础之上，又将正交实验设计方法和局部搜索技术引入其中，提出了一种混合种群分化遗传算法，并在高维，复杂和多模态函数优化问题上验证了新方法的有效性。本文的主要研究工作如下： (1)为解决早熟收敛问题，在对聚类算法和改进遗传算法进行了深入研究与实现验证基础上，提出了一种基于聚类的改进遗传算法(CGA)。该方法通过聚类操作对种群进行子种群划分，禁止同一子种群内的相似个体进行遗传操作，从而可有效抑制早熟收敛。本文还从理论上分析出CGA算法相对于标准遗传算法(SGA)能更好地克服无效交叉操作。 (2)针对CGA算法在抑制早熟收敛中造成的收敛速度降低问题，在其基础之上，又提出了一种基于聚类的最优代表改进遗传算法(OCGA)。新方法通过选择子类内最优个体代替子类内其它个体进行交叉操作，加快了算法的搜索效率。 (3)本文采用K均值,层次聚类以及最小生成树等聚类方法实现了相应的CGA和OCGA算法，并在基准函数优化问题进行了相关的对比数值实验。实验结果表明，与SGA相比，CGA和OCGA确实能够从一定程度上有效抑制早熟收敛现象，OCGA还能够加快算法搜索效率。 (4)在OCGA基础之上，提出了一种混合种群分化遗传算法(HPDGA)。新方法提出了一种适用于局部搜索的方向单形交叉算子，能够根据父代个体的适应度有方向性的产生若干个较优子代个体；并且结合方向交叉算子，提出了一种可调控局部搜索策略，根据当代子种群数目以及子种群中的个体数目采取相应的局部操作算子，加速种群进化。 (5)在14个高维基准函数优化问题上对HPDGA进行了对比测试，测试结果表明，与多种已有算法相比，新算法明显优于其它算法的性能。