基于正交方法求解连续优化问题的蚁群搜索算法 【研究背景和意义】 目前，以蚁群算法为代表的群体智能算法得到越来越多的重视。原因是其以生物的群体行为为研究对象，通过系统仿真，设计出求解各种问题的优化算法。这些算法无论在速度和灵活性上都比传统的确定性算法更适合于求解大规模的优化问题。蚁群算法利用蚂蚁寻找食物时会释放一定量的信息素，而信息素又会随时间蒸发消失的特点，通过设计信息素的释放和蒸发模型，配合启发式信息的使用，使得蚁群算法中的人工蚂蚁通过协作搜索出问题的最优解。 蚁群算法最初由M. Dorigo提出，用于求解旅行商（TSP）问题，后来人们把算法进行扩充和改进，应用到诸如车辆调度、车间调度、路由问题等，并取得很好的计算效果。因此，蚁群算法一直都是用于解决离散组合优化问题的算法。然而，蚁群算法在求解连续优化问题上也具有很好的发展前景，本文就是对蚁群算法求解连续问题的研究成果。 【研究的内容，研究中采取的方法，手段和新的发现】 通过对蚁群算法的研究，本文作者发现，求解连续问题的最大困难在于如何让蚁群中的蚂蚁学到连续空间中的信息，由于不同于TSP问题已经给定有形的路径，连续空间的搜索是无定向的，因此蚂蚁需要高效的方法了解其所处位置周围的状况。 本文提出的正交蚁群搜索方法，首先基于正交试验的方法让蚂蚁快速测试周围正交位置上的优劣程度，根据测试的结果获取当前环境的信息，尝试移动到最优的邻近位置；其次自适应调整测试的邻域的范围，让蚂蚁的搜索更具鲁棒性；最后，通过设计新的信息素释放与蒸发的模式，让蚁群中的蚂蚁以更快的速度交换各自的搜索信息，吸引同伴朝最优的区域探索。 【研究的创新点和主要贡献】 本文与其他学者已经提出的求解连续空间优化问题的蚁群算法的不同之处，在于本文首次提出利用多因素试验中的正交试验法，加强蚂蚁的搜索能力，并提出动态区域的方法，让蚂蚁以更大的自由度试验连续空间中通过正交表产生的测试点。这些思想在同类型的群体智能优化方法中是首创，通过17个连续问题的测试，显示出本文提出的方法既发扬了蚁群的搜索优点，也大大提高了蚁群在连续空间中的搜索能力。 此外，本文提出的正交试验和区域的调整方法是一种基础模型，可以容易地扩充到其他类型优化算法中，为进一步的研究提供良好的借鉴。
Ch9 蚁群算法 9.1生物学知识 1、蚁群算法(Ant Colony Algorithm ,ACA)是由意大利M. Dorigo等人于1990到2000发展起来的，模拟进化算法。模拟了自然界蚂蚁群体的觅食行为。 2、蚁群社会 在昆虫世界中，蚂蚁的组成是一种群居的蓼袭大家庭，称为蚁群。蚁群中除了亲缘上的互助关系外，成蚁划分为世袭制的蚁王和工蚁两个等级，蚁群的大小从几十个到几千万个，蚁群具有高度组织的社会性，彼此间的沟通不仅可以借助触觉的的联系，在大规模的协调行动上，借助外激素之类的生化信息介质。 其中每个工蚁具有如下的职能： 平时在巢穴附近作无规则行走； 一旦发现食物，如果独自能搬的就往回搬，否则就回巢穴搬兵； 一路上它会留下外激至少的嗅迹，其强度与食物的品质和数量成正比； 其他工蚁遇到嗅迹，就会循迹前进，也会有一定的走失率(选择其他路径)，走失率与嗅迹的强度成反比。 蚁群的行为表现出一种信息正反馈的现象； 某一路径上走过的蚂蚁越多，则后来选择该路径的概率就大，蚂蚁个体间就是通过这种信息的交流达到搜索食物的目的。 3、蚁群觅食过程 意大利学者M. Dorigo是最早发现蚂蚁的觅食习性的，蚂蚁总能找到巢穴与食物源之间的最短路径。 蚂蚁在寻找食物源后，会在其经过的路径上释放一种信息素，并能够感知其他蚂蚁释放的信息素。当某些路径上走过的蚂蚁越来越多时，留下的信息素也会越来越多，以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度，逐渐形成了一条它们自己事先并未意识到的最短路线。 蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径的信息素的浓度，形成一个正反馈。 路径上的信息浓度会随时间的推进，而不断挥发，从而不断降低，这似乎也是变异。 9.2ACA算法的基本思想 左图表示初始状态中，在结点A与C有30只蚂蚁，线上的数字(1,0)表示距离为1，
＊)国家自然科学基金项目(10471045)、广东省自然科学基金(04020079)、华南理工大学自然科学基金(B13-E5050190)。吴广潮 讲师,博士研究生,研究领域为算法设计与分析,数据库与信息处理;黄 翰 博士研究生,研究领域为进化计算方法的理论基础,进化计算方法的优化设计及其应用。 计算机科学2008V ol .35№.3 基于离散数字编码的蚁群连续优化算法＊) 吴广潮1,2 黄 翰2 (华南理工大学数学科学学院 广州510640)1 (华南理工大学计算机科学与工程学院 广州510640) 2 摘 要 本文提出了一种基于离散编码的蚁群连续优化算法(CA CO -D E ),用于求解连续优化问题。以往蚁群算法(A CO )的研究,以求解离散优化问题为主,较少涉及连续优化问题。与经典的A CO 算法不同,CACO -DE 将有限精度的实数转化为一个数字串,数字串的每位取0到9之间的数字,从而实现了用离散编码描述实数的效果。CA CO -DE 延用了经典A CO 算法的框架,并加入了特殊的选择机制、信息素更新方式和局部搜索策略。测试实验结果表明:CA -CO -DE 比以往同类算法求解速度更快且精度更高。关键词 蚁群算法,连续优化,离散数字编码 Ant Colony Continuous Optimization Based on Discrete Numerical Encoding W U G uang -Chao 1,2 H U AN G Han 2 (School of M athematical S cien ces ,S ou th China University of Tech nology ,Guangzhou 510640)1 (S chool of Computer S cien ce and En gineering ,S outh China Univers ity of Technology ,Gu angz hou 510640) 2 A bstract T he pr esented paper pro po ses an ant colony algo rithm fo r continuo us o ptimization (CA CO -DE ).A CO alg o -rithms are alway s used fo r discr ete o ptimizatio n problem s ,but rar ely fo r continuous o ptimiza tion .CA CO -DE is de -sig ned based o n the numerical encoding in which each real numbe r is chang ed into a string made up of character s {0,…,9}.T he leng th o f enco ding depends on the accuracy and dimension of the so lutio n .A r tificial ants construct so lutio ns being guided by a hig h dimensio n phero mone v ector .T he f ramewo rk of the proposed algo rithm is similar to the cla ssi -cal ACO except for the upda ting rule a nd local sear ch stra teg y .So me pr elimina ry re sults o btained o n benchmar k pro b -lems sho w that the new method can so lv e co ntinuous o ptimizatio n problem s faster than o the r a nt and no n -a nt methods .Keywords A nt co lo ny alg o rithm ,Co ntinuous optimizatio n ,Discre te numerical encoding 1 引言 蚁群算法(ACO )[1] 是由M .Do rig o 及其同伴在上世纪90年代提出的一种仿生算法,用于求解如旅行商问题[2]之类的组合优化问题。目前,A CO 算法的应用已经扩展到解决多种优化问题,如:V ehicle Ro uting [3]、Q uadra tic assig nment [3]、Qo S [4]、Job sho p [5]等,但这些问题几乎都是离散优化问题。 与遗传算法、粒子群算法和进化规划算法不同,ACO 算法求解连续优化问题的设计研究较少。第一种求解连续函数优化问题的蚁群算法为Co ntinuous A CO (CA CO )算法[6],其主要思想是将连续区间分段,离散化后区间段视为T SP 问题中的城市。CA CO 算法虽然实现了A CO 算法求解连续优化问题0的突破,但是求解效果并不理想。后期又对CACO 算法作了些改进[7,8],提高了求解的精度,但是改进的程度有 限。后来相应又有A PI [9]和CIAC [10]。另外两种算法出现,取得了一定的改进效果,但这些算法加入了遗传算法等其他计算工具的策略,只是用了A CO 算法的框架而已。最新的算法还有基于正态分布的ACO 算法[11],然而这种算法也需要将区间分段离散化,从而会出现两个缺点:1.算法求解精度有限;2.算法求解的计算复杂度较高,需要花费较多的函数评估次数。 作为改进,本文在文[12]基础上提出了一种新型的求解连续优化问题的A CO 算法:基于离散编码的蚁群算法(CA -CO -DE )。实验结果表明:CACO -D E 比以往其他ACO 算法 求解的效果更好,而且速度更快。 2 AC O 算法基本思想介绍 自然界蚂蚁在其经过的路径上会留下某种生物信息物质(信息素),该物质会吸引蚁群中的其它成员再次选择该段路径。食物与巢穴之前较短的路径容易积累较多的信息素,因而使得更多的蚂蚁选择走该段路径,最终几乎所有的蚂蚁都集中在最短路径上完成食物的搬运。M .Do rigo 等从此现象中抽象出路径选择和信息素积累的数学模型,作为蚁群算法的核心;并通过对蚂蚁寻找最短路径的计算机模拟,实现了对TS P 问题的求解[2]。 按M .Do rigo 的设计[3],蚁群算法的基本框架如图1所示 。 图1 蚁群算法(A CO )的基本框架 一般情况下,A CO 算法可以分为三个部分:生成解(Co n -structA ntsSo lutio ns ),更新信息素(U pdatePhero mone s )和附 加策略(DaemonA ctions )。 · 146·
第２２卷第３期计算机辅助设计与图形学学报Ｖ０１．２２Ｎｏ．３２０１０年３月ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒ—ＡｉｄｅｄＤｅｓｉｇｎ＆ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓＭａｒ．２０１０ＧＰＵ中的流体场景实时模拟算法 陈曦，王章野’，何戬，延诃，彭群生 （浙江大学ＣＡＤ＆ＣＧ国家重点实验室杭州３１００２７） （ｃｈｅｘｉｚ＠ｃａｄ．ｚｊｕ．ｅｄｕ．ｏｎ） 摘要：为了实时模拟真实的大规模流体场景，提出一种基于平滑粒子流体力学（ＳＰＨ）进行流体场景模拟的算法．首先提出了新的精细程度函数作为非均匀采样的依据，以减少实际模拟时所需的粒子数，提高模拟的速度；然后引入一种三维空间网格划分算法和改进的并行基数排序算法，以加快模拟过程中对邻域粒子和边界的查找及其相互作用的计算；最后使用最新的ＮＶＩＤＩＡ＠ＣＵＤＡ＠架构，将ＳＰＨ的全部模拟计算分配到ＧＰＵ流处理器中，充分利用ＧＰＵ的高并行性和可编程性，使得对ＳＰＨ方法的流体计算和模拟达到实时．实验结果表明，采用文中算法能对流体场景的计算模拟达到实时，并实现比较真实的模拟效果．与已有的ＳＰＨ流体ＣＰＵ模拟方法相比，其加速比达到２个数量级以上，同时相比已有ＧＰＵＳＰＨ方法，能模拟出更为丰富的细节效果． 关键词：流体场景；实时模拟；ＧＰＵ加速；基于物理的模拟；自适应平滑粒子水动力学 中图法分类号：ＴＰ３９１ ＡｎＩｎｔｅｇｒａｔｅｄＡｌｇｏｒｉｔｈｍｏｆＲｅａｌ—ＴｉｍｅＦｌｕｉｄＳｉｍｕｌａｔｉｏｎｏｎＧＰＵ ＣｈｅｎＸｉ，ＷａｎｇＺｈａｎｇｙｅ。，ＨｅＪｉａｎ，ＹａｎＨｅ，ａｎｄＰｅｎｇＱｕｎｓｈｅｎｇ （ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙｏｆＣＡＤ８ＬＣＧ，ＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉｔｙ。Ｈａｎｇｚｈｏｕ３１００２７） Ａｂｓｔｒａｃｔ：Ｓｉｍｕｌａｔｉｎｇｌａｒｇｅ－ｓｃａｌｅｆｌｕｉｄｓｃｅｎｅｓｉｎｒｅａｌ—ｔｉｍｅｉｓｏｆｇｒｅａｔｖａｌｕｅｉｎｂｏｔｈｒｅｓｅａｒｃｈａｎｄａｐｐｌｉｃａｔｉｏｎ．Ｔｏａｃｈｉｅｖｅｔｈｉｓｇｏａｌ，ｗｅｐｒｅｓｅｎｔａｎｉｎｔｅｇｒａｔｅｄａｌｇｏｒｉｔｈｍｆｏｒｆｌｕｉｄｓｃｅｎｅｓｉｍｕｌａｔｉｏｎ．Ａｎｅｗｆｕｎｃｔｉｏｎｏｆｆｉｎｅｎｅｓｓｉｓｐｒｏｐｏｓｅｄｔｏｍａｋｅｄｅｃｉｓｉｏｎｉｎｏｕｒｎｏｎ—－ｕｎｉｆｏｒｍｐａｒｔｉｃｌｅｒｅ—－ｓａｍｐｌｉｎｇｐｒｏｃｅｓｓｔｏｂｏｔｈｒｅｄｕｃｅｔｈｅｎｕｍｂｅｒｏｆｐａｒｔｉｃｌｅｓｉｎｎｅｅｄｏｆｓｉｍｕｌａｔｉｏｎａｎｄｅｎｈａｎｃｅｓｉｍｕｌａｔｉｏｎｓｐｅｅｄ．Ｗｅａｌｓｏｐｒｏｐｏｓｅａ ｎｏｖｅｌ３Ｄｓｐａｔｉａｌｇｒｉｄｐａｒｔｉｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄｐａｒａｌｌｅｌｒａｄｉｘｓｏｒｔａｌｇｏｒｉｔｈｍｔｏｉｎｃｒｅａｓｅｓｐｅｅｄｆｏｒｓｅａｒｃｈｉｎｇｎｅｉｇｈｂｏｒｉｎｇｐａｒｔｉｃｌｅｓａｎｄｉｎｔｅｒａｃｔｉｎｇｗｉｔｈｂｏｕｎｄａｒｉｅｓ：ＷｅｕｓｅｔｈｅｎｅｗＮＶＩＤＩＡ＠ＣｏｍｐｕｔｅＵｎｉｆｉｅｄＤｅｖｉｃｅＡｒｃｈｉｔｅｃｔｕｒｅ（ＣＵＤＡ）ｔｏｃｏｍｐｕｔｅＳＰＨｅｎｔｉｒｅｌｙｏｎＧＰＵ，ｗｈｉｃｈｍａｋｅｓｆｕｌｌｕｓｅ０ｆｔｈｅｈｉｇｈｐａｒａｌｌｅｌｉｓｍａｎｄｐｒｏｇｒａｍｍａｂｉｌｉｔｙｏｆＧＰＵｔｏｓｉｍｕｌａｔｅｆｌｕｉｄｉｎｒｅａｌ—ｔｉｍｅｕｓｉｎｇＳＰＨｍｅｔｈｏｄ．Ｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅｍｅｔｈｏｄｐｒｏｐｏｓｅｄｃａｎｂｅｕｓｅｄｔｏｓｉｍｕｌａｔｅｆｌｕｉｄｓｃｅｎｅｉｎｒｅａｌ—ｔｉｍｅｗｉｔｈｓａｔｉｓｆａｃｔｏｒｙｅｆｆｅｃｔ，ａｎｄｔｈｅｃｏｍｐｕｔａｔｉｏｎｓｐｅｅｄｉｎｃｒｅａｓｅｓｕｐｔｏｍｏｒｅｔｈａｎｔＷＯｏｒｄｅｒｓｏｆｍａｇｎｉｔｕｄｅｉｎｃｏｍｐａｒｉｓｏｎｗｉｔｈｔｈｅｅｘｉｓｔｉｎｇＣＰＵＳＰＨｍｅｔｈｏｄｓ．ＭｏｒｅｄｅｔａｉｌｅｆｆｅｃｔｓｔｈａｎｏｔｈｅｒＧＰＵＳＰＨｍｅｔｈｏｄｓｃａｎｂｅｇｅｎｅｒａｔｅｄ． Ｋｅｙｗｏｒｄｓ：ｆｌｕｉｄｓｃｅｎｅｓ；ｒｅａｌ—ｔｉｍｅｓｉｍｕｌａｔｉｏｎ；ＧＰＵａｃｃｅｌｅｒａｔｉｎｇ；ｐｈｙｓｉｃａｌｌｙｂａｓｅｄｓｉｍｕｌａｔｉｏｎ；ＳＰＨ 自然场景的真实感实时模拟，特别是流体场景的模拟，在数字娱乐产业中（如电影特效、游戏制作、计算机动画、虚拟现实以及航海模拟和灾难救援等）有着广泛的应用．但由于基于物理复杂模型的真实感建模与快速实时模拟一直存在着矛盾，因此它一直是国际计算图形学领域研究的热点与难点之一． 收稿日期：２００９—０６—１５；修回日期：２００９—１１—０５．基金项目：国家“九七ｉ”重点基础研究发展计划项目（２００９ＣＢ３２０８０２）；国家自然科学基金重点项目（６０８３３００７）；国家“八六三”高技术研究发展计划（２００７ＡＡ０１２３１６）｝国家自然科学基金项目（６０９７００７５），浙江省自然科学基金杰出青年团队项目（Ｒ４０７０４２）．陈ｔ（１９８７一），男，主要研究方向为计算机图形学、计算机视觉、数字图像处理；王章野（１９６５一），男，博士．副教授，硕士生导师，论文通讯作者，主要研究方向为计算机图形学、虚拟现实氇［外成像仿真（ｚｙｗａｎｇ＠ｃａｄ．ｚｊｕ．ｅｄｕ．ｏｎ）；何矗（１９８３一），男，硕士研究生，主要研究方向为计算机图形学、虚拟现实；延诃（１９８３～），男，硕士，主要研究方向为计算机图形学、虚拟现实｝彭群生（１９４７一），男，博士，教授，博士生导师。ＣＣＦ高级会员。主要研究方向为计算机图形学，生物计算、虚拟现实等． 万方数据
第!"卷第!期#$%&!"’$&!控制与决策 ()*+,)-.*/012343)* 5667年!月 8 888888888888888888888888888888888888888888888888888888888888888888 9:;&5667文章编号56?5667@6!=66A B=6A 蚁群算法在连续空间寻优问题求解中的应用 汪镭C吴启迪 ?同济大学电子与信息工程学院C上海5666>5@ 摘要<将蚁群算法引入连续空间的函数寻优问题求解C通过将传统蚁群算法中的D信息量留存E过程 拓展为连续空间中的D信息量分布函数E C定义了相应的求解算法F对多极值函数和非线性连续函数的寻 优实例仿真取得了良好的结果C显示了蚁群算法在连续空间优化问题中的应用前景F 关键词<蚁群算法G连续空间寻优G信息量分布函数 中图分类号
基于蚁群算法的连续函数优化通用MATLAB源代码 此源码是对人工蚁群算法的一种实现，用于无约束连续函数的优化求解，对于含有约束的情况，可以先使用罚函数等方法，把问题处理成无约束的模型，再使用本源码进行求解。 function [BESTX,BESTY,ALLX,ALLY]=ACOUCP(K,N,Rho,Q,Lambda,LB,UB) %% Ant Colony Optimization for Unconstrained Continuous Problem %% ACOUCP.m %% 无约束连续函数的蚁群优化算法 %% 此函数实现蚁群算法，用于求解无约束连续函数最小化问题 %% 对于最大化问题，请先将其加负号转化为最小化问题 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→https://www.doczj.com/doc/d411467770.html,/greensim %% 输入参数列表 % K 迭代次数 % N 蚁群规模 % Rho 信息素蒸发系数，取值0～1之间，推荐取值0.7～0.95 % Q 信息素增加强度，大于0，推荐取值1左右 % Lambda 蚂蚁爬行速度，取值0～1之间，推荐取值0.1～0.5 % LB 决策变量的下界，M×1的向量 % UB 决策变量的上界，M×1的向量 %% 输出参数列表 % BESTX K×1细胞结构，每一个元素是M×1向量，记录每一代的最优蚂蚁 % BESTY K×1矩阵，记录每一代的最优蚂蚁的评价函数值 % ALLX K×1细胞结构，每一个元素是M×N矩阵，记录每一代蚂蚁的位置 % ALLY K×N矩阵，记录每一代蚂蚁的评价函数值 %% 测试函数设置 % 测试函数用单独的子函数编写好，在子函数FIT.m中修改要调用的测试函数名即可 % 注意：决策变量的下界LB和上界UB，要与测试函数保持一致 %% 参考设置 % [BESTX,BESTY,ALLX,ALLY]=ACOUCP(50,30,0.95,1,0.5,LB,UB) %% 第一步：初始化 M=length(LB);%决策变量的个数 %蚁群位置初始化 X=zeros(M,N); for i=1:M x=unifrnd(LB(i),UB(i),1,N); X(i,:)=x; end %输出变量初始化 ALLX=cell(K,1);%细胞结构，每一个元素是M×N矩阵，记录每一代的个体 ALLY=zeros(K,N);%K×N矩阵，记录每一代评价函数值
摘要 自意大利学者M. Dorigo于1991年提出蚁群算法后，该算法引起了学者们的极大关注，在短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。本文首先讨论了该算法的基本原理，接着介绍了旅行商问题，然后对蚁群算法及其二种改进算法进行了分析，并通过计算机仿真来说明蚁群算法基本原理，然后分析了聚类算法原理和蚁群聚类算法的数学模型，通过调整传统的蚁群算法构建了求解聚类问题的蚁群聚类算法。最后，本文还研究了一种依赖信息素解决聚类问题的蚁群聚类算法，并把此蚁群聚类算法应用到对人工数据进行分类，还利用该算法对2005年中国24所高校综合实力进行分类，得到的分类结果与实际情况相符，说明了蚁群算法在聚类分析中能够收到较为理想的结果。 【关键词】蚁群算法；计算机仿真；聚类；蚁群聚类
Study on Ant Colony Algorithm and its Application in Clustering Abstract： 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 2
蚁群算法的提出： 人工蚂蚁与真实蚂蚁的异同
o o ? ? ? ? ?
3 4 5 6 7
2.1 2.2
相同点比较 不同点比较
蚁群算法的流程图 基本蚁群算法的实现步骤 蚁群算法的 matlab 源程序 蚁群算法仿真结果 版权声明
[编辑]蚁群算法的提出：
人类认识事物的能力来源于与自然界的相互作用，自然界一直是人类创造力 的源泉。 自然界有许多自适应的优化现象不断地给人以启示，生物和自然中的生 态系 统可以利用自身的演化来让许多在人类看来高度复杂的优化问题得到几乎完美 的解决。近些年来，一些与经典的数学问题思想不同的，试图通过模拟自然生态 系统 来求解复杂优化问题的仿生学算法相继出现，如蚁群算法、遗传算法、粒子群算 法等。 这些算法大大丰富了现在优化技术，也为那些传统最优化技术难以处理的 组 合优化问题提供了切实可行的解决方案。 生物学家通过对蚂蚁的长期的观察发现，每只蚂蚁的智能并不高，看起来没 有集中的指挥，但它们却能协同工作，集中事物，建起坚固漂亮的蚁穴并抚养后 代， 依靠群体能力发挥出超出个体的智能。 蚁群算法是最新发展的一种模拟昆虫王国 中蚂蚁群体智能行为的仿生优化算法，它具有较强的鲁棒性、优良的分布式计算 机 制、易于与其他方法相结合等优点。尽管蚁群算法的严格理论基础尚未奠定，国 内外的相关研究还处于实验阶段， 但是目前人们对蚁群算法的研究已经由当初单 一 的旅行商问题(TSP)领域渗透到了多个应用领域，由解决一维静态优化问题发展 到解决多维动态组合优化问题， 由离散域范围内的研究逐渐扩展到了连续域范围 内的
还有页眉没有添加，页眉上写章标题，把我给你标注的问题改完就 可以打印了 摘要 根据蚂蚁生态学提出的蚁群算法是一种新颖的用于求解复杂组合优化问题的模拟进化算法,具有典型的群体智能特征,表现出较强的学习能力和适应能力。本文阐述了该算法的基本原理、算法模型和在TSP( Traveling Salesman Problem，旅行商)问题中的具体应用过程,并对算法进行了总结和展望。 关键词：蚁群算法，旅行商问题，外激素
目录 摘要Ⅰ 目录II 第一章引言 (1) 第二章蚁群算法的基本原理和模型 (2) 2.1 蚁群算法的基本原理 (2) 2.2 蚁群算法的模型 (3) 第三章基于蚁群算法的TSP求解 (5) 3.1 TSP问题的描述 (5) 3.2 基于蚁群算法的TSP求解 (5) 3.3 蚁群算法的局限性 (6) 第四章蚁群算法的改进 (8) 4.1 优选参数m (8) 4.2 参数 的调整 (8) 4.3 信息素的更新 (8) 4.4 信息素链表L 和禁忌链表TL 的构建 (9) 第五章改进的算法基本流程 (10) 第六章结论 (11) 参考文献 (12)
第一章引言 研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决许多复杂的问题。蚁群算法就是利用群集智能解决组合优化问题的典型例子。蚁群算法（Ant Colony Algorithm, ACA）是由意大利学者M.Dorigo，V.Mzniezzo，A.Colorni 等人在20世纪90年代初首先提出来的。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等元启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。 蚁群算法不仅能够智能搜索、全局优化，而且具有稳健性A、鲁棒性B、正反馈、分布式计算、易与其它算法结合等特点。利用正反馈原理，可以加快进化过程；分布式计算使该算法易于并行实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合，可改善算法的性能；由于鲁棒性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题。因此，蚁群算法的问世为诸多领域解决复杂优化问题提供了有力的工具。 TSP 问题，又称旅行商问题，就是一个销售商从n 个城市中的某一城市出发，不重复地走完其余n﹣1 个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。它是组合优化中研究最多的问题之一，是一个经典的NP 难题。 第二章蚁群算法的基本原理和模型
蚁群优化算法ACO 一、蚁群算法的背景信息 蚁群优化算法(ACO)是一种模拟蚂蚁觅食行为的模拟优化算法，它是由意大利学者Dorigo M等人于1991年首先提出，之后，又系统研究了蚁群算法的基本原理和数学模型，并结合TSP优化问题与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行了仿真实验比较，为蚁群算法的发展奠定了基础，并引起了全世界学者的关注与研究 蚁群算法是一种基于种群的启发式仿生进化系统。蚁群算法最早成功应用于解决著名的旅行商问题(TSP)，该算法采用了分布式正反馈并行计算机制，易于与其他方法结合，而且具有较强的鲁棒性。 二、蚁群算法的原理[1] 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 基本的ACO模型由下面三个公式描述： 式（2-1）、式(2-2)和式(2-3)中：m为蚂蚁个数；n为迭代次数；i为蚂蚁所在位置；j为蚂蚁可以到达的置；为蚂蚁可以到达位置的集合；为启发性信息
，这里为由i到j的路径的能见度，即；为目标函数，这里为两点间欧氏(Euclidean)距离；为由i到j的路径的信息素强度；为蚂蚁k由i到j的路径上留下的信息素数量；为路径权；为启发性信息的权；为路径上信息素数量的蒸发系数；Q为信息素质量系数；为蚂蚁k从位置i移动到位置j的转移概率。 三、改进的蚁群算法[3] 蚁群算法具有如下一些优点：①通用性较强，能够解决很多可以转换为连通图结构的路径优化问题；②同时具有正负反馈的特点，通过正反馈特点利用局部解构造全局解，通过负反馈特点也就是信息素的挥发来避免算法陷入局部最优； ③有间接通讯和自组织的特点，蚂蚁之间并没有直接联系，而是通过路径上的信息素来进行间接的信息传递，自组织性使得群体的力量能够解决问题。 但是，基本蚁群算法也存在一些缺点：①从蚁群算法的复杂度来看，该算法与其他算法相比，所需要的搜索时间较长；②该算法在搜索进行到一定程度以后，容易出现所有蚂蚁所发现的解完全一致这种“停滞现象”，使得搜索空间受到限制 3.1基于遗传学的改进蚁群算法研究 该文献[2]提出的算法弥补了基本蚁群算法中“容易陷入停滞状态”和“盲目随机搜索”的不足。文献中提出的解决办法是在每一次迭代搜索后，都把当前解和最优解进行交叉变异,这样既能搜索更大的解空间，又能使系统陷入局部最优后跳出停滞状态。 这种基于遗传学的蚁群算法（G-蚁群算法）的基本思想是在以蚁群算法为主体的基础上引入遗传算法的思想，目的是让蚁群算法经过迭代产生遗传算法所需的初始种群数据，提高种群数据的多样性。然后，遗传算法经过选择、交叉和变异操作,将处理后的数据交由蚁群算法模块进行判断处理，若满足结束条件则退出系统，否则重新进行迭代操作。 该文献中的交叉操作采用了Davis提出的OX交叉算子，即按照交叉概率Pc进行交叉操作，通过一个亲体中挑选出的子序列路径作为后代相对位置的子序列，变异操作以变异概率Pm执行变异操作，在子代序列路径中随机选择两点进行变异操作，在交叉变异操作结束后，判断当前解是否满足收敛条件，若满足收敛条件则更新当前最优解，返回蚁群算法程序,执行下一次的迭代操作。若不满足收敛条件则继续进行遗传算法的交叉变异操作。
蚁群优化算法的JAVA实现 一、蚁群算法简介 蚁群算法是群智能算法的一种，所谓的群智能是一种由无智能或简单智能的个体通过任何形式的聚集协同而表现出智能行为，它为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础，比如常见的蚂蚁觅食，大雁南飞等行为。蚁群算法是模拟自然界中蚂蚁觅食的一种随机搜索算法，由Dorigo等人于1991年在第一届欧洲人工生命会议上提出[1] 。 二、蚁群算法的生物原理 通过观察发现，蚁群在觅食的时候，总能找到一条从蚁巢到食物之间的一条最短的路径。这个现象引起了生物学家的注意，根据研究，原来是蚂蚁在行进的过程中，会分泌一种化学物质——信息素，而蚂蚁在行进时，总是倾向于选择信息素浓度比较高的路线。这样，在蚁巢和食物之间假如有多条路径，初始的时候，每条路径上都会有蚂蚁爬过，但是随着时间的推迟，单位时间内最短的那条路上爬过的蚂蚁数量会比较多，释放的信息素就相对来说比较多，那么以后蚂蚁选择的时候会大部分都选择信息素比较多的路径，从而会把最短路径找出来。 蚁群算法正是模拟这种蚁群觅食的原理，构造人工蚂蚁，用来求解许多组合优化问题。 有关蚁群算法的详细信息，可参考[2]——[5]。 三、蚁群算法的JAVA实现 我个人认为利用JAVA编写一些计算密集型的算法不是一个好的选择。本身一些算法是要要求高效率的，但是我感觉JAVA语言的性能不够，所以编写算法最好用c，其次也可以用c++。当然，这仅是一家之言，欢迎拍砖。 四、算法说明 算法以求解TSP问题为例，用来演示ACO的框架。 算法设定了两个类，一个是ACO，用来处理文件信息的读入，信息素的更新，路径的计算等；另一个是ant，即蚂蚁的信息。 算法中用到的数据，可以从TSPLib 上面下载，使用的是对称TSP数据，为了简化算法的代码，下载下来的数据需要做一个简单处理，即把TSP文件中除去城市节点信息部分之外的内容都删除掉，然后在文件首插入一行，写入此文件包含的城市的数目，以att48.tsp为例，下载下来的文件内容如下：