基于聚类划分子种群的多种群遗传算法.pdf

《基于聚类划分子种群的多种群遗传算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第27卷第3期四川理工学院学报(自然科学版)Vo1．27No．32014年6月JournalofSichuanUniversityofScience＆Engineering(NaturalScienceEdition)Jun．2014文章编号：1673·1549(2014)03-0046-04DOI：10．11863／j．suse．2014．03．11基于聚类划分子种群的多种群遗传算法丁若冰，邹书蓉(成都信息工程学院计算机学院，成都610000)摘要：标准遗传算法存在易于早熟，容易陷入局部最优的缺点，同时标准多种群遗传算法存在进化后期种群同质化严重的缺陷。针对这一问题，将聚类思想引

2、入到多种群遗传算法的子种群划分中，提出了一种使用聚类方式划分子种群的多种群遗传算法，使得种群划分不再只是单纯的随机行为，而是将满足约束条件的个体根据其特征划分到不同子种群中，从而解决种群同质化问题，避免所有子种群陷入局部最优。最后，通过测试两个典型函数，验证了该算法的有效性，为多种群遗传算法提供了一种新的研究方向。关键词：遗传算法；种群同质化；聚类；种群划分中图分类号：TB115文献标志码：A主种群没有任何规律地划分成多个子种群，所以算法引言仍存在许多不足之处，如进化后期种群同质化现象严美国的Holland教授在20世纪七十年代首次提出重、种群陷入局部最优等问题。本文提出了一种基于

3、了一种模拟达尔文进化论的自然选择机制的优化算法，聚类划分子种群的多种群遗传算法(MultiplePopula—是最早的遗传算法起源。遗传算法⋯同其它优化算法tionGeneticAlgorithmBasedonClusteringDividingPopu-相比较拥有隐含的并行性、寻优过程快速、本身的自适lations，MPGA—BC)，使得子种群划分不再是一种随机应性及其鲁棒性等优点，此外还具有搜索不依赖于问题行为，而是将满足约束条件的个体根据其特征划分到的梯度信息、模型特征的优点，使其在传统搜索方法难不同子种群中，从而解决种群同质化问题，避免所有子以解决的复杂和非线性问题上有很好

4、的效果，近年越来种群陷入局部最优，从而提高算法性能和算法搜寻全越多的国内外学者致力于遗传算法的研究，特别是多种局最优解的能力。群遗传算法的研究。多种群遗传算法(Multi—Population多种群遗传算法后期子种群同质化严重一直是一GeneticAlgorithm，MPGA)是在遗传算法并行运算的基个重要缺陷，因为同质化会导致种群陷入局部最优，从础上，通过多种群并行进化的思想，将遗传算法中单种而不能获得全局最优，尽管变异算子能在一定程度上打群进化过程分解为多个子种群并行进行的过程，每个子破这种状况，但其几率比变异操作的概率还要小得多，种群单独完成选择、交叉、变异操作，这样不仅可以

5、加快本文提出的基于聚类划分的多种群遗传算法从根本上算法的收敛速度，而且避免了单个种群进化过程中出现解决种群同质化问题，从而使得算法能最大程度地获得的过早收敛现象。全局最优解。实验结果表明改进的算法有较好的寻优但是，由于传统的多种群遗传算法只是简单地将能力和收敛能力。收稿日期：2013—12—13基金项目：四川省科学技术厅重点科技自筹项目(2012SZZ029)作者简介：丁若冰(1987·)，男，河南驻马店人，硕士生，主要从事计算智能方面的研究，(E—mail)158070976@qq．corn第27鲞第3期丁若冰等：基于聚类划分子种群的多种群遗传算法47的聚类中心；1聚类的定义和数

6、学模型(4)如果在第(2)步某一样本的类别发生改变，则1．1聚类的定义转第(2)步；聚类就是按照一定的要求和规律对事物进行区(5)返回聚类核心和各个样本类别，聚类终止。分和分类的过程，在这一过程中没有任何关于分类的先2聚类划分子种群的多种群遗传算法验知识，仅靠事物间的相似性作为类属划分的准则，因此属于无监督分类的范畴。“人以群分，物以类聚”，聚2．1引入聚类方式划分子种群优势类是一个古老的问题，它伴随着人类社会的产生和发展传统的多种群遗传算法虽然能够将种群分割，从而加而不断深化，人类要认识世界就必须区别不同的事物并快种群收敛速度，但是传统的划分子种群的方法只是如图认识事物间的相似性

7、。1所示，简单随机的将种群初始化为A、B和c几个子种1．2聚类的数学模型群，并没有按个体本身特性分配到不同种群中去。这样会从数学的角度来刻画聚类划分可以得出以下模型：导致种群同质化严重，最终收敛向同一个最优解。设X={。，⋯．，}是待聚类分析的对象的全体，本文提出引人聚类的思想如图2所示，将特性相似中的每个对象(称为样本)(i=1，2⋯．，m)常用有的个体划分到相同的子种群里，这样可以克服基本多种限个参数值来刻画，每个参数值刻画的某个特征。于群遗传算法的缺陷，避免种群