论文部分内容阅读
目前，随着网络信息量的增加，从大量无序的数据中提取隐含的、有效的信息成为人们要解决的问题。聚类作为数据挖掘的一项强有力的工具，成为目前研究的热点。在研究聚类问题的过程，聚类往往被看作是一个优化问题，且可以用不同的优化方法来解决。
Memetic算法因其良好的函数优化能力，成为目前优化算法的一个研究热点。本文中，将Memetic算法应用于聚类问题，分别提出了基于克隆选择算法的Memetic自动聚类算法和基于图形聚类的迭代局部搜索算法，在此之前提出了基于多种群的粒子群Memetic算法解决车间调度问题。具体工作主要包括以下：
1.提出一种基于多种群的粒子群Memetic算法。算法中，首先，将整个种群分为三个子种群，采用三个子种群协同进化的方式，克服了Memetic算法由于缺乏种群多样性而产生早熟收敛的缺陷。其次，三个子种群分别引入了不同的局部搜索算法，保持了种群多样性，并且能快速收敛。对25个流水车间调度问题进行测试，实验结果表明，该算法比对比算法在三个指标上都具有优势。
2.提出一种基于克隆选择算法的Memetic自动聚类算法。算法中，首先，使用基于类标的编码方式，来实现图形集类别数的确定。其次，针对图形自动聚类问题的特性，提出了三个局部搜索算法，分别为基于模拟退火算法的局部搜索算法、基于聚类中心的局部搜索算法和基于类内相似度距离总和的局部搜索算法，以实现聚类结果的优化。对5个图形集合进行测试，实验结果表明，该算法在图形自动聚类中，类别数的确定和聚类正确率，都优于对比算法。
3.提出一种基于迭代局部搜索的图形自动聚类算法。在第三章中采用的计算图形相似度方法和评价函数的基础上，结合图形聚类问题的特殊性，提出了一种基于图形聚类的局部搜索算法。同时对算法的时间复杂度进行了分析。对5个图形集合测试结果表明，本文方法在图形的自动聚类的结果上较第二章算法有所提高。