一种改进的遗传聚类算法

摘要

本发明公开了一种改进的遗传聚类算法，包括：对数据进行编码，得染色体种群；计算适应度数值，并进行排序，获得适应度数组；以贪婪法为基准，根据适应度值将每两个染色体不重复的做交叉操作；根据适应值做选择操作；做模拟退火选择；计算剩余染色体适应值排序，并用当前最好染色体替换最差染色体；如果循环次数大于规定的最大循环次数，则运算结束，将数据解码得到最终聚类结果。本发明不仅执行的收敛速度加快，且在保证多样性的同时，将适应度值以最大限度的提高，时间及空间资源的消耗减少，迭代次数降低，实现了对遗传聚类中遗传方法进行优化。

说明书

技术领域

本发明属于遗传聚类算法的技术领域，尤其涉及一种改进的遗传聚类算法。

背景技术

聚类算法作为一种无监督学习方法，广泛应用于图像分析、模式识别等领域，优化聚类算法有多种方式，如Jaspreet Kaur等人通过利用模糊C均值和人工蜂群算法对聚类算法进行改进，Yuefeng Tang等人利用萤火虫算法对聚类优化。

其中遗传聚类作为处理高维数据集的有效方法，已成为生物信息和医学分析等领域的研究热点，于金霞和蔡自兴等人通过加权的模糊聚类做特征提取，改进遗传算子以加快收敛速度，且避免了局部最优，但时间复杂度高，Faliang Huang和Xuelong Li等人提出一种和谐遗传聚类算法(HGCA)，对数据样本聚类时，可自动确定聚类的数量，但算法计算复杂程度大，占用较多的搜索空间，同样为确定聚类的数量，Bin Zhang和Zhichun Gan等人通过变长染色体的遗传运算得到最优解的方法，从而自动确定合适的聚类数目，且不受初始聚类中心的影响，而缺点是算法的空间复杂度大，算法效率降低，Md.Touhidul Islam和Pappu Kumar Basak等人提出一种混合遗传算法(HGA)，使启发式聚类算法避免陷入局部最优的状态，但时间复杂度大，算法执行速度慢。

综上所述，目前的研究大多在于对染色体优化或是将遗传算法与其余算法结合，而对遗传聚类中遗传方法的优化较少。

因此，发明一种改进的遗传聚类算法来解决上述问题很有必要。

发明内容

基于以上现有技术的不足，本发明所解决的技术问题在于提供一种改进的遗传聚类算法，不仅执行的收敛速度加快，且在保证多样性的同时，将适应度值以最大限度的提高，时间及空间资源的消耗减少，迭代次数降低，实现了对遗传聚类中遗传方法进行优化。

本发明的改进的遗传聚类算法，包括以下步骤：

S1、对数据进行编码，得染色体种群；

S2、计算适应度数值，并进行排序，获得适应度数组；

S3、以贪婪法为基准，根据适应度值将每两个染色体不重复的做交叉操作；

S4、根据适应值做选择操作，如果：

则做K变异算子计算，否则做普通变异算子计算；

S5、做模拟退火选择，如果fitnessnew＞fitnessthr，做轮盘赌选择，否则按照：

进入下一代；

其中，K为初始簇数量，a为维数，P为模拟退火选择概率，T为当前温度，cfitness为适应度数组，fitnessMax为最大适应值，fitnessEverage为平均适应值，fitnessMin为最小适应值，fitnessNew为新产生个体适应值，fitnessthr为适应度阙值。

可选的，还包括：

S6、计算剩余染色体适应值排序，并用当前最好染色体替换最差染色体；

S7、如果循环次数大于规定的最大循环次数，则运算结束，将数据解码得到最终聚类结果。

由上，本发明的改进的遗传聚类算法具有如下有益效果：

本发明通过在遗传聚类的交叉阶段，根据贪婪法的思想将染色体进行交叉，以保证子代尽可能的继承父代优秀基因，然后在遗传聚类的变异阶段，将变异算子的部分作为K变异算子进行处理，以加快算法收敛速度，最后通过模拟退火的选择过程，跳过局部最优的竞争点，以确保获得全局最优解，不仅执行的收敛速度加快，且在保证多样性的同时，将适应度值以最大限度的提高，时间及空间资源的消耗减少，迭代次数降低，实现了对遗传聚类中遗传方法进行优化。

上述说明仅是本发明技术方案的概述，为了能够更清楚了解本发明的技术手段，而可依照说明书的内容予以实施，并且为了让本发明的上述和其他目的、特征和优点能够更明显易懂，以下结合优选实施例，并配合附图，详细说明如下。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例的附图作简单地介绍。

图1为本发明的改进的遗传聚类算法的流程图。

具体实施方式

下面结合附图详细说明本发明的具体实施方式，其作为本说明书的一部分，通过实施例来说明本发明的原理，本发明的其他方面、特征及其优点通过该详细说明将会变得一目了然。在所参照的附图中，不同的图中相同或相似的部件使用相同的附图标号来表示。

如图1所示，本发明提供了一种改进的遗传聚类算法，具体包括以下步骤：

S1、对数据进行编码，得染色体种群；

S2、计算适应度数值，并进行排序，获得适应度数组；

S3、以贪婪法为基准，根据适应度值将每两个染色体不重复的做交叉操作；

S4、根据适应值做选择操作，如果：

则做K变异算子计算，否则做普通变异算子计算；

S5、做模拟退火选择，如果fitnessnew＞fitnessthr，做轮盘赌选择，否则按照：

进入下一代；

S6、计算剩余染色体适应值排序，并用当前最好染色体替换最差染色体；

S7、如果循环次数大于规定的最大循环次数，则运算结束，将数据解码得到最终聚类结果。

其中，K为初始簇数量，a为维数，P为模拟退火选择概率，T为当前温度，cfitness为适应度数组，fitnessMax为最大适应值，fitnessEverage为平均适应值，fitnessMin为最小适应值，fitnessNew为新产生个体适应值，fitnessthr为适应度阙值。

更为具体的，实验对比K-Means聚类算法、遗传聚类算法、结合贪婪交叉与K变异的遗传聚类算法、结合贪婪交叉与模拟退火的遗传聚类算法以及上述改进的遗传聚类算法在bezdekIris数据集和moni数据集上实验可知：

在bezdekIris数据集下，通过实验图像对算法的适应度变化进行分析，遗传聚类算法平均适应值为24.73，相比于K-Means算法的适应值高出3.58，说明遗传聚类算法的性能优于K-Means聚类算法，引入贪婪交叉与K变异算子之后，明显迭代次数有所减少，不仅从500多次减少到200多次，减少了大概300次的迭代次数，时间消耗的程度减少，运行效率提高，模拟退火的遗传聚类算法与遗传聚类算法图像对比来看，迭代次数相差不大，将改进的遗传聚类算法与其余图像进行对比分析发现适应度为25.28，是所有算法中最高的适应度。

在moni数据集下，研究四种算法的适应值情况可知，将遗传聚类和K-Means聚类比较，最佳适应值提高0.32，平均提高0.21，结合贪婪交叉与K变异算子之后，算法的迭代次数明显减少，收敛的速度也有所加快，但是适应值与原算法相比没有提高太多，结合贪婪交叉和模拟退火之后的遗传聚类算法，可以明显看到最佳适应度很高，且收敛速度加快，并与之前的算法相比平均适应值提高4.66。

由上述内容可知：原聚类算法的最优解次数最少，遗传聚类算法达到最优解的次数虽然增加，但时间消耗最大，而分别经过贪婪交叉的K变异算子和模拟退火算法优化的遗传聚类算法，尽管达到最优解的平均次数都有增加，但相比于原聚类算法，时间消耗仍有些大，而经过改进的遗传聚类算法达到最优解的次数不仅是最多的，且时间消耗程度最小。

综上所述，本申请所提出的改进的遗传聚类算法，不仅执行的收敛速度加快，且在保证多样性的同时，将适应度值以最大限度的提高，时间及空间资源的消耗减少，迭代次数降低。

最后应说明的是：以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。