下载文档原格式
摘要自意大利学者M. Dorigo于1991年提出蚁群算法后，该算法引起了学者们的极大关注，在短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。
本文首先讨论了该算法的基本原理，接着介绍了旅行商问题，然后对蚁群算法及其二种改进算法进行了分析，并通过计算机仿真来说明蚁群算法基本原理，然后分析了聚类算法原理和蚁群聚类算法的数学模型，通过调整传统的蚁群算法构建了求解聚类问题的蚁群聚类算法。
最后，本文还研究了一种依赖信息素解决聚类问题的蚁群聚类算法，并把此蚁群聚类算法应用到对人工数据进行分类，还利用该算法对2005年中国24所高校综合实力进行分类，得到的分类结果与实际情况相符，说明了蚁群算法在聚类分析中能够收到较为理想的结果。
【关键词】蚁群算法；计算机仿真；聚类；蚁群聚类Study on Ant Colony Algorithm and its Application inClusteringAbstract：As the ant colony algorithm was proposed by M. Dorigo in 1991,it bringed a extremely large attention of scholars, in past short more than ten years, optimized, the network route, the function in the combination optimizes, domains and so on data mining, robot way plan has obtained the widespread application, and has obtained the good effect.This acticle discussed the basic principle of it at first, then introduced the TSP,this acticle also analysed the ant colony algorithm and its improved algorithm, and explanated it by the computer simulates, then it analysed the clustering algorithm and the ant clustering algorithm, builded the ant clustering algorith to solution the clustering by the traditioned ant algorithm. At last, this article also proposed the ant clustering algorith to soluted the clustering dependent on pheromon. Carry on the classification to the artificial data using this ant clustering algorithm; Use this algorithm to carry on the classification of the synthesize strength of the 2005 Chinese 24 universities; we can obtain the classified result which matches to the actual situation case. In the next work, we also should do the different cluster algorithm respective good and bad points as well as the classified performance aspect the comparison research; distinguish the different performance of different algorithm in the analysis when the dates are different.Key words：Ant colony algorithm; Computer simulation; clustering; Ant clustering目录1 引言 (3)1.1群智能 (2)1.2蚁群算法 (3)1.3聚类问题 (4)1.4本文研究工作 (5)2 蚁群算法原理及算法描述 (5)2.1蚁群算法原理 (5)2.2蚁群优化的原理分析 (8)2.3算法基本流程 (10)2.4蚁群觅食过程计算机动态模拟 (11)2.5人工蚂蚁与真实蚂蚁的对比 (13)2.6本章小结 (14)3 基本蚁群优化算法及其改进 (15)3.1旅行商问题 (15)3.2基本蚁群算法及其典型改进 (15)3.2.1 蚂蚁系统 (15)3.2.2 蚁群系统 (16)3.2.3 最大-最小蚂蚁系统 (16)3.3基本蚁群算法仿真实验 (16)3.3.1 软硬件环境 (16)3.3.2 重要参数设置 (16)3.3.3仿真试验 (17)3.4本章小结 (19)4 蚁群聚类算法及其应用 (20)4.1聚类问题 (20)4.2蚁群聚类算法的数学模型 (21)4.3蚁群聚类算法 (21)4.3.1 蚁群聚类算法分析 (22)4.3.2 蚁群聚类算法流程 (25)4.4蚁群聚类算法在高校分类中的应用 (25)4.5本章小结 (27)5 结论与展望 (28)参考文献 (29)致谢 (31)附录 (32)1 引言下面将介绍群智能以及蚁群算法和聚类问题。
蚁群算法的基本原理与改进蚁群算法是一种模拟蚂蚁群体行为的启发式算法，通过模拟蚂蚁在寻找食物和归巢过程中的行为，来解决优化问题。
蚂蚁在移动的过程中，通过信息素的释放和感知，实现了全局信息传递和局部信息更新。
蚁群算法基于这种行为特性，通过模拟蚂蚁在解空间中的过程，找到问题的最优解。
1.初始化一群蚂蚁在问题的解空间中随机选择一个起点。
2.每只蚂蚁根据问题的特性和上一次的行走经验，利用概率选择下一步要行走的方向。
3.每只蚂蚁根据选择的方向进行移动，并释放一定量的信息素到路径上。
4.蚁群中的每只蚂蚁根据选择的方向和移动的结果，更新自己的经验和信息素矩阵。
5.重复步骤2-4，直到达到停止条件。
1.路径选择策略的改进：蚂蚁选择下一步行走方向的概率通常根据路径上的信息素浓度和启发式信息来计算，可以根据具体问题的特性，采用不同的路径选择策略，如轮盘赌选择、最大值选择等，来提升算法的能力。
2.信息素更新策略的改进：信息素释放和更新对算法的性能起到重要影响。
可以通过引入一定的衰减因子，控制信息素的挥发速率，降低过快的信息素挥发过程；同时，可以通过引入信息素增强/衰减机制，根据蚂蚁经验和当前信息素浓度调整信息素的更新速率，以提升算法的收敛速度和稳定性。
3.多种启发式信息的融合：在算法中，蚂蚁根据启发信息来选择下一步行走方向。
可以采用多种启发式信息，并将它们进行适当的融合，以增加算法对问题的能力。
4.并行计算和局部：蚁群算法由于全局信息传递的特性，容易陷入局部最优解。
可以通过引入并行计算和局部机制，增加算法的广度和多样性，提升算法的全局能力。
5.参数的自适应调节：蚁群算法中存在一些参数，如信息素释放量、信息素衰减因子等，合理的参数设置对算法的性能至关重要。
可以考虑通过自适应调节参数的方法，如基于概率或规则的自适应机制，自适应地调节参数值，以提高算法的效果。
总而言之，蚁群算法通过模拟蚂蚁的行为特性，实现了全局信息传递和局部信息更新，并通过适当的改进措施，提升了算法的能力和收敛速度。
第!卷第"期北华大学学报（自然科学版）#$%&!’$&"())*年+(月,-./’01-23456.0.’5#4/7589（’:;<=:%7>?@A >@）!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!B @>&())*文章编号：+))C D *E ((（())*）)"D )!F (D )G 基本蚁群算法及其改进孔令军+，张兴华(，陈建国G（!"北华大学教育技术中心，吉林吉林!#$%$!；$"北华大学电气信息工程学院，吉林吉林!#$%$!；#"北华大学后勤服务总公司，吉林吉林!#$%$!）摘要：给出了群体智能的一个分支———蚁群算法的一个改进算法，充分利用了算法的并行特点，提高了算法的效率&关键词：蚁群算法；信息矩阵；组合优化中图分类号：8H G )+&"文献标识码：0收稿日期：())*D )*D +F 作者简介：孔令军（+C "F I ），男，工程师，主要从事计算机应用研究&近年来，计算机网络得到了飞速的发展，网络已成为社会生活不可缺少的部分&同时，人们对网络信息传输的质量和效率的要求也越来越高&为了进一步提高网络的效率，更多新算法被引入这个领域，蚁群算法就是其中之一&!初期的蚁群算法基本的蚁群算法07可以简单表述如下：在)时刻进行初始化过程，蚂蚁放置在不同的城市，每一条边都有一个初始外激素强度值!&’（)）"每一只蚂蚁禁忌表的第一个元素置为它的开始城市"然后，每一只蚂蚁从城市&移动到城市’，依据两个变量的概率函数选择移动城市（包括参数"和#，见公式（+"*））"在(次循环后，所有蚂蚁都完成了一次周游，同时他们的禁忌表将满，这时，计算每一只蚂蚁)的路径长度*)，!!)&’依据公式（+"G ）更新"而且，保存由蚂蚁找到的最短路径（即J ?A *)，)++，…，,），置空所有禁忌表"重复这一过程直到周游计数器达到最大（用户定义）周游数J :K -.，或者所有蚂蚁都走同一路线"后一种情况被称为停滞状态"如果算法在-.次循环后结束，蚂蚁算法的复杂度为/（-.·((·,）"信息素更新公式：!&’（01(）+$·!&’（0）1!!&’，（+"+）其中，$是一个参数，+2$表示在时刻0和01(之间外激素的蒸发，!!&’+",)++!!)&’，（+"(）!!)&’是单位长度上在时刻0和01(之间第)只蚂蚁在边3（&，’）留下的外激素的数量，其中!!)&’+4，*)如果在时刻0和01(之间第)只蚂蚁使用边3（&，’），)，其他#$%"（+"G）4是一个常数，*)是第)只蚂蚁周游的路程长度&第)只蚂蚁从城市&到城市’的跃迁概率为5)&’（0）+［!&’（0）］"［%&’］#")&&)［!&)（0）］"［%&)］#，’&&)；)，’’&)#$%"（+"G）其中&)+｛-2;:L <)｝，-为一组城市，;:L <)表示第)只蚂蚁的禁忌表，"和#都是控制外激素与可见度的相对重要性的参数!跃迁概率是可见度和"时刻外激素强度的权衡!综合以上所述，图"给出用基本蚁群算法原理解决路由选择优化问题的流程图!图!基本蚁群算法解决问题流程"#$%!"&’(’)*+,#-+./-’&’.01基本蚁群算法的不足之处从上面针对路由选择优化问题的分析可以看出，虽然蚁群算法已经被证明是一种有效的解决组合优化问题的方法，但是由于问世的时间比较短，还存在如下不足：（"）限于局部最优解!从算法解的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求是全局最优解!（#）工作过程的中间停滞问题!和算法开始时收敛速度快一样，在算法工作过程当中，迭代到一定次数后，蚂蚁也可能在某个或某些局部最优解的邻域附近发生停滞!（$）较长的搜索时间!尽管和其他算法相比，蚁群算法在迭代次数和解的质量上都有一定的优势，但对于目前计算机网络的实际情况，还是需要较长的搜索时间!虽然计算机计算速度的提高和蚁群算法的并行性在一定程度上可以缓解这一问题，但是对于大规模复杂的计算机网络，这还是一个很大的障碍!2加强信息利用率的蚁群算法下面从实际应用的角度提出一个改进的算法———加强信息利用率的蚁群算法，其主要改进思想是蚂蚁在网络图中转移的同时在信息矩阵中转移，让寻找不同路径的蚂蚁可以协同工作!根据这个思想建立了新的信息矩阵（略），使蚂蚁遗留下的信息可以对多次工作产生影响!这充分利用了算法的并行特点，减少了算法的循环次数和计算时间，提高了算法在解决这一问题时的效率!下面通过仿真结果进行分析!图1建立信息矩阵流程图2路径优化情况"#$%1"&’(’)3’45&#.$’)#.)’63+/#’.3+/6#7"#$%289+6/’)’:/#3#;#.$6’</5$%&第’期孔令军，等：基本蚁群算法及其改进图!网络模型拓扑连接图"基本蚁群算法仿真结果#$%&!’()(*(%$+,**$-.(/-012(3.4(50*#$%&"6$47*,1$(-3087*1(/9,8$+,-1+(*(-:图!是系统的仿真结果即路径优化结果，横坐标代表循环次数，纵坐标代表蚂蚁经过节点的数目"仿真过程中，初始信息量定为#"$%，衰减系数定为#"&%，循环次数为’#次"和图%基本蚁群算法基于图’的仿真结果相比，可以看出，引入了改进思想后，算法的性能有了比较明显的改善，一般在(%!!#次循环后就可以稳定在最优路径上"在用基本算法进行仿真时，干扰路径较多的路径很容易停滞在不是最优的结果上，在改进算法中，一样很快达到了最优"!结论蚁群算法是近年新出现的一种从群体智能思想演变而来的新算法，在解决大规模组合优化问题上显示了强大的实力"本文将蚁群算法引入路由选择优化问题，并做了如下的研究探索：蚁群算法作为一种新兴的群体智能算法，在应用方面有比较突出的成绩，但研究者仅局限于仿真试验和思想的引入；从理论的角度详细的论证了蚁群算法解决此问题的可行性，并结合算法工作的过程，分析了基本蚁群算法的特点，提出了改进的方向；为了改善基本蚁群算法的不足，提出了一种针对解决路由选择优化问题的改进蚁群算法———加强信息利用率的蚁群算法"参考文献：［(］谭跃进，陈英武，易进先"系统工程原理［)］"长沙：国防科技大学出版社，(&&&"*+,-./01,，23/,-1,45.，-161,71+,"*3/*3/89:8;<:=>/?@,41,//91,4［)］"23+,4=3+：A +>18,+B C /;/,D /*/D 3,8B 84:E .F B 1D +>18,，(&&&"［!］*38?+=G ")+.;/9"H E 技术基础———编址和路由［)］"北京：机械工业出版社，!###"*38?+=G ")+.;/9"I +=1D*3/89:8;H E*/D 3,8B 84:———G J J 9/==+,JG D D /==［)］"I /101,4：)/D 3+,1D +B H ,J .=>9:E.F B 1D +>18,，!###"［K ］胡适耕，施保昌"最优化原理［)］"武汉：华中理工大学出版社，!###"L .<314/,4，<31I +8D 3+,4"*3/*3/89:8;M N >1?1O +>18,［)］"P .3+,：E .F B 1D +>18,8;)1J J B /231,+Q ,1R /9=1>:8;*/D 3,8B 84:，!###";,8$+<-1=3(7)(/<*%(3$1>4,-5?18?4)3(@040-1!"#$%&’()*+’(，,-.#$/&’()0+1!，2-3#4&1’)(+5K （(!"#$%&’()*+,(--./*’/0)12/(3$&4*(5/06(’7，8(-(*(K !#!(，.3(*&；!!"-/%’0(%9*1)0:&’()*"*;(*//0(*;.)--/;/)12/(3$&4*(5/06(’7，8(-(*(K !#!(，.3(*&；K !+/05(%/.):<&*7)12/(3$&4*(5/06(’7，8(-(*(K !#!(，.3(*&）.67891:8：GF 9+,D 38;D 8B 8,:1,>/B B 14/,D /———1?N 98R /?/,>?/>38J 8;+,>498.N 8;+B 4891>3?，F +=1D +,>498.N8;+B 4891>3?1=1,>98J .D /J +,J +B 4891>3?=/;;/D >1=1?N 98R /J 8F R 18.=B :"!;<=59>7：G ,>D 8B 8,:+B 4891>3?；H ,;89?+>18,?+>917；28?F 1,+>891+B 8N >1?1O +>18,【责任编辑：吕洪斌】’$%北华大学学报（自然科学版）第%卷基本蚁群算法及其改进作者：孔令军， 张兴华， 陈建国作者单位：孔令军(北华大学,教育技术中心,吉林,吉林,132021)， 张兴华(北华大学,电气信息工程学院,吉林,吉林,132021)， 陈建国(北华大学,后勤服务总公司,吉林,吉林,132021)刊名：北华大学学报（自然科学版）英文刊名：JOURNAL OF BEIHUA UNIVERSITY(NATURAL SCIENCE)年，卷(期)：2004，5(6)被引用次数：6次1.谭跃进.陈英武.易进先系统工程原理 19992.Thomas A Maufer IP技术基础--编址和路由 20003.胡适耕.施保昌最优化原理 20001.学位论文李德华配电网络重构的改进模糊遗传算法研究2009在配电网优化的各项措施中，通过网络重构可以在不增加投资的基础上，充分发挥现有配电系统的作用，提高供电的经济性、可靠性和优质性，具有巨大的经济效益和社会效益。
