蚁群算法的改进及其在聚类分析中的应用

《蚁群算法的改进及其在聚类分析中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代号10530学号200811031420分类号TP391密级硕士学位论文蚁群算法的改进及其在聚类分析中的应用学位申请人戴皇冠指导教师石跃祥教授学院名称信息工程学院学科专业计算机科学与技术研究方向图像语义检索与智能处理二○一一年六月五日AntColonyAlgorithmforImprovementAndItsApplicationintheClusterAnalysisCandidateDaihuangguanSupervisorProfessorShiYueXiangCollegeCollegeofInformationEngineeringProgr

2、amComputerScienceandTechnologySpecializationSemanticImageRetrieval&IntelligentProcessingDegreeEngineeringMasterUniversityXiangtanUniversitythDateJune,5,2011湘潭大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明

3、。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湘潭大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期：年月日导师签名：日期：年月日摘要从蚂蚁群体寻找最短路径觅食行为受到启发，意大利学者Dorigo等人1991年提出了一种仿生学原理的模拟进化算法——蚁群算法。它具有优良的分布

4、计算、信息正反馈机制和启发式搜索等优点，在解决复杂优化问题方面已经展现出巨大的发展潜力。蚁群算法在若干领域已经获得了成功的应用，近年来蚁群算法被应用到数据挖掘中，给数据挖掘的聚类分析提供了更广阔的思路。本文综述当前国内外蚁群算法的研究进展，对其进行了研究与分析，并提出了改进算法。本文的主要工作如下：(1)蚁群信息素增量研究。本文概述了两种典型改进蚁群算法——蚁群系统gb(AS)和最大—最小蚁群(MMAS)，但其都仅仅只利用全局最优解(s)或迭代最优ib解(s)中的一个解更新信息素，针对两种改进算法信息素更新规则的不足，提出gbib了信息素增量动态混合更新策略，

5、能充分利用s和s动态混合更新信息素增量，防止蚂蚁过早集中于一条路径，克服局部优化问题，有利于发现更优解；同时引用逆转变异因子，改善整个群体性能，减少计算时间，并给出了实例验证。(2)单一群智能聚类分析研究。本文先分析聚类分析原理、数字模型及一些常用的聚类分类方法和聚类评价标准。再针对传统聚类算法对复杂问题难于解决的局限性，研究了几种仿生智能聚类算法，给出了基于遗传算法的聚类、蚁群聚类及基于粒子群聚类的基本思想和实现过程，为第四章的改进算法作理论铺垫和仿真实验对比分析。(3)基于混合交叉因子的蚁群聚类算法研究。为了充分利用各单一群智能聚类的优点，形成优势互补，本

6、文分析了近年来几种具有代表性的融合群智能聚类算法，并结合其特点，提出了一种全新的基于混合交叉因子的蚁群聚类算法，该方法融合蚁群算法和遗传算法的优势，并采用改进的混合交叉因子，该因子采用结合分阶段调整策略和启发式多点交叉策略的混合策略，其中分阶段调整策略动态调整交叉点规模，显著降低交叉操作的无效性概率；启发式策略建立在适应度的基础上能有效地保留父代优秀基因，从而使交叉操作同时满足对未知空间的探索和对已发现区域的求精。本文对蚁群算法的信息素增量和空间搜索能力进行了研究和改进，实验结果表明此改进有效地提高了蚁群算法的收敛速度和聚类效果以及稳定性。为蚁群算法的研究提供

7、了一定的理论基础，并具有一定的实际意义。关键词：蚁群算法；混合交叉因子；变异因子；群智能聚类；混合蚁群聚类IAbstractAntcolonyalgorithmisakindofsimulatedevolutionaryalgorithmbasedonbionicprincipleswhichsimulatesants’behavioroffindingfoods.Thealgorithmhasseveralvirtuessuchasdistributedcomputing,positivefeedbackmechanismandheuristicsearch

8、ability,andhasdemon