基于强化型精英保存遗传策略的聚类方法研究

陈磊+普运伟

摘要：遗传算法是一种随机搜索算法，适用于解决许多复杂的智能优化问题。然而，经典遗传算法具有收敛速度慢和易早熟缺陷。为了找到一种普适性高且效果好的改进遗传算法，解决数据聚类问题，提出一种新的遗传算法改进策略。该策略同时保留父代及交叉产生的个体中的绝大部分精英，用来替换掉变异后同等数量的最差个体，并且将交叉与变异概率提高到1，这样不仅能很好地保留住已产生的精英个体，引导算法稳定地向最优解进化，还可最大限度地使算法获得开拓新的解空间能力。实验结果表明，该方法具有较高的聚类准确性和收敛率，平均收敛准确率为94.67%，平均收敛率为100%，且收敛速度较快，是一种适合解决数据聚类问题的可行方案。

关键词：改进遗传算法；精英保存策略；数据聚类

DOIDOI：10.11907/rjdk.171997

中图分类号：TP301

文獻标识码：A 文章编号：1672-7800（2017）012-0015-04

Abstract：Genetic algorithm is a stochastic search algorithm， which is applied to solving many complex intelligent optimization problems. However， the classical genetic algorithm has disadvantages of slow convergence speed and easy prematurity. In order to find an improved genetic algorithm with high universality and good effect to solve general data clustering problems， this paper proposes a new revised strategy about GA， which retains parts of the elites in the parents and in the individuals after crossover and increases the probability of cross and mutation to 1. Through these strategies， the novel improved GA makes the algorithm maximize the ability of exploiting new solution spaces， and retains the generated elites well. The experimental results show that， the proposed method has higher clustering accuracy and rate of convergence than two recent improved genetic strategies， whose average accuracy rate achieves 94.67% and average rate of convergence is 100%. In addition， the convergence speed of the proposed method is so fast that it can be as a feasible solution to solve data clustering problems.

Key Words：improved genetic algorithm；elitism strategy；data clustering

0 引言

遗传算法是一种随机搜索算法，其基本思想源于生物进化论和群体遗传学，是模拟自然界生物进化过程与机制，求解极值问题的一类自组织、自适应人工智能技术[1-2]。遗传算法对各种优化问题通用性很强，特别是在解决一些传统数学方法难以解决的复杂非线性问题时具有明显优势。因此，在复杂函数优化、组合优化、生产调度、图像识别和机器学习等众多领域都获得了成功[3-4]。但是，在实际应用中，传统遗传算法显现出诸多缺点。针对这些问题，学者们提出了许多新的改进方法。如文献[5]构建了一种小生境遗传算法，运用分裂型社区结构发现算法划分超级个体关系网来获得生境，同时提取生境中的共有模式以改善算法效果；文献[6]则将小生境技术和Nelder-Mead的单一方法有机融合，增强了算法的全局搜索能力。此外，文献[7]采用基因空间均匀分布策略、自适应交叉和变异算子以及淘汰算子等多种改进策略，构建了一种基于多样化策略的基因表达式编程算法DS-GEP，提高了种群多样性，加快了算法收敛速度；文献[8]将反向传播神经网络融合进遗传算法，大大提高了算法搜索到全局最优解的概率；文献[9]提出了一种基于智能体的多目标社会进化算法，结合了遗传算法与关系网模型优点，专门用于解决多目标优化问题；文献[10]提出了一种M精英协同进化算法，利用遗传算法中的精英保存思想来增强算法的搜索能力；文献[11]则设计了一种智能仿生遗传算法，可以有效改善3种遗传算子的不足。总的来说，上述改进遗传算法主要应用在函数优化、自动控制和图像处理等方面，专门针对数据分类问题的研究则相对较少。

如何从大型数据库中提取出人们感兴趣的知识是数据挖掘的一个重要内容。将与现实情况相关的各种混乱无序的数据变成搜索空间，利用改进遗传算法随机、非线性和混沌的特点，在大量的数据规则中去完成搜索，得到需要的数据，是数据挖掘领域重要的研究方向[12]。聚类是一种无监督分类，其本质是在没有先验知识的前提下，仅根据数据的相似性将数据分成不同类别，是数据挖掘技术的一种重要手段[13]。遗传聚类算法可较好地解决数据聚类时的优化问题，满足优化目标的多样性需求[14]。但是，现有的聚类算法存在稳定性差、收敛速度慢以及算法设计复杂等问题，无法充分满足实际应用需求。为了找到一种普适性高且聚类效果好的改进遗传算法，本文构建了一种新的遗传算法改进策略。本文方法同时保留父代中的部分精英个体与交叉产生的绝大部分精英个体，将交叉概率与变异概率增加到最大值，以较好地平衡精英保存与解空间开拓能力之间的矛盾。为了验证算法的可行性和有效性，将所提方法用于5均匀分布数据集和IRIS数据集聚类，并和新近提出的两种改进遗传策略进行对比实验。结果表明，所提方法与其它两种方法相比具有较高的聚类准确性和收敛率，且算法收敛速度较快、适应能力强，是一种适合解决数据聚类问题的可行方案。

1 实验方案设计

经典遗传算法步骤[15]：①设置种群数量N，交叉概率Pc，变异概率Pm；②问题域编码。将实际问题编码成解空间，可采用二进制编码、实数编码和符号编码等；③初始化种群，计算种群内个体相应的适应度值；④执行选择、交叉和变异策略，进行精英保存，得到子代个体；⑤迭代终止条件检测。若满足迭代终止条件，输出结果，否则转步骤④。

在上述经典遗传算法基础上，本文构建了一种改进遗传策略——基于强化型精英保存策略的遗传算法（方案三），并和基于选择算子的遗传算法改进（方案一）和基于改进锦标赛选择算子的遗传算法（方案二）进行对比，实验方案比较如表1所示。

由表1可以看出，方案一在进化初期，采用宽松的选择机制，因为此时个体分布较为分散，优良个体比重相对较小；在进化后期，采用严格的选择机制，以适应此时个体分布比较集中与优良个体比重较大的情形。方案二改进了传统锦标赛选择算子，使竞赛规模的大小在种群规模的60%～80%之间，以改善算法效果。

本文提出的方案三改进了传统的精英保存策略。在该方案中首先设置交叉概率Pc与变异概率Pm为1，采用符号编码初始化N个个体作为原始父代，并计算每个个体的适应度值，然后执行方案二中改进的锦标赛选择策略与随机单点交叉操作，将原始父代加上交叉操作后的子代共2N个个体中的1/4优秀个体保留下来。最后对交叉操作后N个个体进行随机单点变异操作，用上一步保留的优秀个体替换掉變异后等量的最差个体，完成一次迭代进化过程，得到第一代的子代种群n。以n作为下一代的父代种群，重复执行上述操作，迭代到规定次数后得到最终进化后的种群n′，找到其中的最优个体，解码输出结果。

该方案能最大限度地保留住父代与交叉产生的个体中已存在的优秀个体，以避免因为将交叉概率与变异概率提高到最大而使算法变成纯随机搜索，并指导算法向最优解的进化方向进行，使算法可以稳定地收敛到最优解附近。同时，将交叉概率与变异概率提高到1，使子代具有较强的开拓解空间能力，加快算法收敛速度，较好地防止了算法因保留过多的精英个体而陷入局部最优的情况。

2 实验结果与数据分析

2.1 实验一：5均匀分布数据集

以（150，150）、（650，150）、（850，350）、（650，650）和（250，650）为中心点，在每个中心点附近随机均匀地生成10个点，每个数据包含X与Y两个坐标值。

采用表1的3种方案对上述5均匀分布数据集进行聚类，每一种方案独立运行100次。种群规模为50，最大迭代次数为500。在方案一和方案二中，交叉概率设置为0.9，变异概率设置为0.1，方案二与方案三的竞赛规模设置为种群规模的60%。在方案三中，交叉概率与变异概率均设置为1，从父代及交叉产生的个体中保留最优的个体数量为25。

表2给出了3种方案的收敛率、收敛准确率和平均收敛代数的结果对比。其中，收敛率是指成功收敛次数所占的百分比，收敛准确率是指方案成功收敛时，被准确聚类数据占全部测试数据的百分比，平均收敛代数是100次随机实验收敛代数的平均值。同时，某次采用本文方案对5均匀分布数据集的聚类结果如图1所示，某次三种方案的平均收敛代数对比结果如图2所示。

由表2可以看出，方案三与方案二的收敛率最高，达到100%，方案一略低，这显示出基于锦标赛选择策略的遗传算法比基于轮盘赌选择策略的遗传算法具有更好的稳定性。在收敛准确率方面，3种方案的实验结果分别为99.74%、99.80%和100%，可见，本文提出的方案三具有一定优势。这是因为在本文的设计方案中，强化型精英保留策略能留住进化过程中的大多数精英个体，使得算法在绝大多数情况下均能寻找到最优解。此外，从图1可以看出，所有测试数据均被正确聚类，显示出本文方法良好的聚类准确性。在收敛速度上，方案三的平均收敛代数为41代，比方案一的354代提高了8.63倍，比方案二的203代提高了4.95倍，说明在本文方法中较高的交叉与变异概率使算法能够更快速地收敛到最优解。从图2的收敛代数对比情况不难发现，方案三的收敛曲线较为陡峭，较少出现方案一和方案二中的局部“小平台”，表明本文方法在保证较快的收敛速度的同时，还具有较强的逃逸局部最优能力。

2.2 实验二：IRIS数据集

IRIS数据集是由3种不同种类的鸢尾花的各50个样本组成，每个样本共4种属性，分别代表花萼长度、花萼宽度、花瓣长度和花瓣宽度。

该实验中除了最大迭代次数调整为900以外，其它参数均与实验一相同。表3给出了3种方案在收敛率、收敛准确率和平均收敛代数上的结果对比，图3为某次本文方案对IRIS数据集的聚类结果，图4为某次3种方案的平均收敛代数对比结果。

由表3可以看出，3种方案全部成功收敛，显示出基于遗传机制的聚类方法在数据聚类问题上的有效性。但在收敛准确率和平均收敛代数方面，本文提出的方案三效果更好。从图3可以看出，尽管IRIS数据集内部较复杂，但本文方法依然能对绝大部分数据进行有效聚类，只有极少数的几个数据没有被正确分开。图4的3种方案平均收敛代数对比中，方案三具有较为明显的优势，平均收敛代数仅为110代，比方案一和方案二分别提高6.71倍和3.58倍，且在进化过程中较少陷入局部最优。可见，本文方法具有较好的稳健性、较高的准确率和较强的收敛能力。

3 结语

为解决数据的自动聚类问题，本文构建了一种基于强化型精英保存策略的改进遗传算法。该算法能够保留住算法进化过程中的绝大多数精英个体，有效指导了算法的进化方向，增强了算法稳定性，使得算法收敛到最优解的概率显著提高。本文方案将交叉概率和变异概率提高到最大，最大限度地增强了算法的收敛速度，防止了算法因保留过多精英个体而陷入局部最优的情况。实验结果对比表明，本文方法具有收敛速度快、平均收敛率高和准确性好等优点，是一种解决数据聚类问题的可行方案。如何进一步增强算法的通用性并用于更复杂的数据聚类问题，将是下一步的研究重点。

参考文献：

[1] 王福林，朱会霞，王吉权，等.遗传算法的一种改进进化策略[J].生物数学学报，2015，30（1）：69-74.

[2] 葛继科，邱玉辉，吴春明，等.遗传算法研究综述[J].计算机应用研究，2008，25（10）：2911-2916.

[3] MANTSWY A H，ABDEL-MAGID Y L，SELIM S Z.Integration genetic algorithm，tabu search，and simulated annealing for the unit commitment problem [J].IEEE Transactions on Power Systems，1999，14（3）：829-836.

[4] MCHALEWICZ Z.Genetic algorithm +data structure=evolution programs[M].New York：Spring-Verlag，1994.

[5] 祝希路，王伯.一種基于社团划分的小生境遗传算法[J].控制与决策，2010，25（7）：1113-1116.

[6] WEI LING YUN，ZHAO MEI.A niche hybrid genetic algorithm for global optimization of continuous multimodal functions[J].Applied Mathematics and Computation，2005，160（3）：649-661.

[7] 吴江，李太勇，姜玥，等.基于多样化进化策略的基因表达式编程算法[J].吉林大学学报：信息科学版，2010，28（4）：396-403.

[8] JAVADI A A，FARMANI R，TAN T P.A hybrid intelligent genetic algorithm[J].Advanced Engineering Informmatics，2005，19（4）：255-262.

[9] 潘晓英，刘芳，焦李成.基于智能体的多目标社会进化算法[J].软件学报，2009，20（7）：1703-1713.

[10] 慕彩红，焦李成，刘逸.求解约束优化问题M-精英协同进化算法[J].西安电子科技大学学报：自然科学版，2010，37（5）：852-861.

[11] LI FA-CHAO，XU LI-DA，JIN CHEN-XIA，et al.Intelligent bionic genetic algotithm （IB-GA） and its convergence[J].Expert Systems with Applications，2011，38（7）：8804-8811.

[12] 陈晶晶.遗传算法在数据挖掘中的应用[J].信息通信，2015（11）：120-121.

[13] 戴阳阳，李朝锋，徐华.初始点优化与参数自适应的密度聚类算法[J].计算机工程，2016，42（1）：203-209.

[14] 冯少荣，潘炜炜，林子雨.基于改进k-medoids算法的XML文档聚类[J].计算机工程，2015，41（9），57-62.

[15] 郭广颂，王燕芳.包含交叉和变异操作的交互式遗传算法[J].计算机工程，2015，41（3），183-185.

[16] 董妍汝.基于选择算子的遗传算法改进[J].办公自动化，2015 （8）：59-61.

[17] 张琛，詹志辉.遗传算法选择策略比较[J].计算机工程与设计，2009，30（23）：5471-5474.

（责任编辑：杜能钢）