丁若冰，邹书蓉

(成都信息工程学院计算机学院，成都 610000)

引 言

美国的Holland教授在20世纪七十年代首次提出了一种模拟达尔文进化论的自然选择机制的优化算法，是最早的遗传算法起源。遗传算法［1］同其它优化算法相比较拥有隐含的并行性、寻优过程快速、本身的自适应性及其鲁棒性等优点，此外还具有搜索不依赖于问题的梯度信息、模型特征的优点，使其在传统搜索方法难以解决的复杂和非线性问题上有很好的效果，近年越来越多的国内外学者致力于遗传算法的研究，特别是多种群遗传算法的研究。多种群遗传算法(Multi-Population Genetic Algorithm，MPGA)是在遗传算法并行运算的基础上，通过多种群并行进化的思想，将遗传算法中单种群进化过程分解为多个子种群并行进行的过程，每个子种群单独完成选择、交叉、变异操作，这样不仅可以加快算法的收敛速度，而且避免了单个种群进化过程中出现的过早收敛现象［2-6］。

但是，由于传统的多种群遗传算法只是简单地将主种群没有任何规律地划分成多个子种群，所以算法仍存在许多不足之处，如进化后期种群同质化现象严重、种群陷入局部最优等问题。本文提出了一种基于聚类划分子种群的多种群遗传算法(Multiple Population Genetic Algorithm Based on Clustering Dividing Populations，MPGA_BC)，使得子种群划分不再是一种随机行为，而是将满足约束条件的个体根据其特征划分到不同子种群中，从而解决种群同质化问题，避免所有子种群陷入局部最优，从而提高算法性能和算法搜寻全局最优解的能力。……