摘要
自意大利学者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 引言 (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.1 群智能
成群的鸟、鱼、浮游生物、蚂蚁、蜜蜂等都是以集群形式进行筑巢、觅食、迁徙和逃避捕食者等复杂行为，而这些行为是单个个体不可能有足够的能力来指挥完成的。数以千计的个体如何组成一个群落，又如何相互协调、分工、合作来完成复杂任务的呢？通过生物学家对微生物、群居昆虫、群居动物的调查得出结论，各种社会型生物的各种集体行为似乎都可以找到几个共同的属性[1]：
(1)控制充分的分布在许多个体之中；
(2)个体之间的交流为局部交流；
(3)群体的行为要明显优于个体的行为；
(4)群体对外界的变化的反应具有鲁棒性和适应性。
受社会性昆虫行为的启发，计算机工作者通过对它们的模拟产生了一系列对于传统问题的新的解决方法，这些研究就是群集智能的研究。群集智能(Swarm Intelligence)中的群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解”。而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特性”。群集智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。
概括地说，使得社会型生物的个体相互协作而实现神奇的群体行为的答案是个体进行相互合作时体现的自组织行为[2]。自组织是一些动态环境条件的连续变化。Krieger 等用这种蚂蚁的阈值模型为一群在活动场地聚集目标物体的机器人定义了一个劳力分配的分布式系统[3,4]。在他们的实验中，由基于阈值行为活动控制的机器人能够完成聚集任务，同时这个系统作为一个整体显示了固有的容错性和功能衰减。一个或多个人行为的自适应，导致整体功能仅仅略微的降低。最重要的是，在系统设计时在机器人之间并没有外在的交流机制，同时在机器人的控制程序里没有明确包含在错误的环境里的应对措施。尽管这个实验是在大学的实验室条件下完成的，但它足以显示这种方法对于在开放的环境下控制工业机器人的变换是有很大的潜力的。由此可见，群智能有着以下几个方面的特点[1,3]：
(1)由于系统中单个个体的能力比较简单，这样每个个体的执行时间比较短，实现起来比较方便，具有简单性；
(2)单个个体具有改变环境的能力和系统自调节性；
(3)无中心控制和数据源。这样的系统更具有鲁棒性，不会由于某一个或者某几个个体的故障而影响整个问题的求解；
(4)群体中相互合作的个体是分布的。这个特点与计算机网络的工作环境非常相似；
(5)各个体通过对环境的感知进行合作，个体的增加或减少都不会加大系统通信的开销。这样，系统具有更好的可扩展性，同时也具有更好的安全性。
根据其特点，群智能能够被用于解决大多数优化问题或者能够转化用领域已扩展到各种工程优化问题，如电信路由选择、TSP 问题、车间调度问题、二次分配问题等等，并取得了意想不到的收获。虽说群智能的研究还处于初级阶段，并且存在着许多困难，但是可以预言群智能的研究代表了以后计算机研究发展的一个重要方向。本文所讨论的蚁群算法就是一种群智能算法[2]。
1.2 蚁群算法
蚁群觅食过程是一种典型的群智能行为过程[5]，蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”(pheromone)作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕远的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。受到蚂蚁觅食时的通信机制的启发，90年代Dorigo提出了蚁群算法(ant colony algorithm,ACA)来解决计算机算法学中经典的“旅行商问题”--如果有n 个城市，需要对所有n个城市进行访问且只访问一次的最短距离。在解决旅行商问题时，蚁群算法设计虚拟的“蚂蚁”将摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。虚拟“信息素”也会挥发，每只蚂蚁每次随机选择要走的路径，他们倾向于选择路径比较短的、信息素比较浓的路径。根据“信息素较浓的路线更近”的原则，即可以选择出最佳路线。由于这个算法利用了正反馈机制，使得较短的路线能够有较大的机会得到选择并且采用了概率算法，所以它能够不局限于局部最优解。蚁群算法对于解决旅行商问题并不是目前最好的方法，但首先它提出了一种解决旅行商问题的新思路；其次由于这种算法特有的解决方法，它已经成功的被应用于解决组合优化问题。作为通用型随机优化算法，蚁群算法自问世以来表现了强大的生命力，较之以往的启发式算法不论在搜索效率上，还是在算法的时间复杂度方面都取得了令人满意的效果，现在已经陆续应用到组合优化、人工智能、通讯数据挖掘、机器人路径规划等多个领域。另外蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有较强的发展潜力。从数值模拟结果看，它比目前广泛研究的一些优化算法有更好的适应性[6]。
以蚁群算法为代表的群体智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法已越来越多地被用于企业的运转模式的研究。美国五角大楼正在资助关于群体智能系统的研究工作--群体战略(SWARM STRATEGY)，它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面
车辆来转移敌人的注意力，让自己的军队在敌人后方不被察觉地安全行进。英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验。群体智能还被应用于工厂生产计划的制定和运输部门的后勤管理。美国太平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件，结果每年至少节约了1000万美元费用开支。英国联合利华公司已率先利用群体智能技术改善其一家牙膏厂的运转状况。美国通用汽车公司，法国液气公司，荷兰公路交通部和美国一些移民事务机构也都采用这种技术来改善其运转的机能。又如美国MCI https://www.doczj.com/doc/b614376089.html,公司一直研究人工蚂蚁，并用于管理公司的电话网，对用户记帐收费等工作。另外，还设计“人工蚂蚁”打算用于因特网的路由管理。鉴于群体智能广阔的应用前景，美国和欧洲联盟均于近几年开始出资资助基于群体智能模拟的相关研究项目，关在一些院校开设群体智能的相关课程。牛津大学出版社1999年版的E.Bonabeau和M.Dorigo等人编写的专著《群体智能:从自然到人工系统》(Swarm Intelligence: From Natural to Artificial System),以及2001年出版的J.Kennedy和R.Eberhart编著的《群体智能》(Swarm Intelligence)进一步扩大了群体智能的影响.IEEE进化计算会刊也于2002年8月出版了蚁群优化算特刊。国内也有研究者用蚂蚁算法求解全国144个城市的最短回路问题，求得的解同其它方法求到得解一样精确，这说明蚂蚁算法不但是求解组合优化问题的可行方法，而且是一种很有竞争力的算法。国家自然科学基金"十五"期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群体智能领域的进化,自适应与现场认知主题[7]。而且从1999年开始，几乎每年都会有几项相关项目获得资助。蚁群算法是一种新型的模拟进化算法，其在数据挖掘中的应用正逐步引起人们的关注。目前，人工蚁群在知识发现的过程中主要用于发掘聚类模型和分类模型。
1.3 聚类问题
聚类是将一组对象分成若干个群体，每个群体构成一个簇，使得簇内的对象尽可能具有最大的相似性，不同簇之间的对象尽可能有最大的相异性。目前，聚类方法主要有K均值法，模糊聚类、神经网络聚类、基于遗传算法的聚类、小波变换聚类以及将这些算法有效结合而形成的改进方法。随着蚁群算法研究的兴起，人们发现在某些方面采用蚁群模型进行聚类更加接近实际的聚类问题。将蚁群算法用于聚类分析，灵感源于蚂蚁堆积他们的尸体和分类他们的幼体。基于蚁群算法的聚类方法从原理上可分为两种：一种是基于蚁堆形成原理来实现数据聚类[8,9]，另一种是运用蚂蚁觅食的原理，利用信息来实现聚类分析[10]。
从实际应用的观点来看，聚类分析在科学数据探测、图像处理、模式识别、
医疗诊断、计算生物学、文档检索、Web 分析等领域起着非常重要的作用，它已经成为当前数据挖掘研究领域中一个非常活跃的研究课题。
1.4 本文研究工作
本文在第二章中，将介绍蚁群算法基本原理和人工蚂蚁与真实蚂蚁的对比。第三章为基本蚁群算法及其参数设置，几种典型的蚁群优化算法以及使用vc++实现基本蚁群算法。第四章研究一种依赖信息素解决聚类问题的蚁群聚类算法，并且把它应用在人造样本检验其寻找最优分类结果的性能，最后以2005中国24所高校综合实力能力分类进行案例分析，同时验证此蚁群聚类算法的正确性。
2 蚁群算法原理及算法描述
下面将介绍蚁群算法原理以及蚁群觅食过程计算机动态模拟。
2.1 蚁群算法原理
自然界中蚁群的自组织行为很早就引起了昆虫学家的注意[11-13]。
Deneubourg [14]等通过“双桥实验”对蚁群的觅食行为进行了研究。如图 2-1（a ）
所示，对称双桥（两桥的长度相同）A 、B 将蚁巢与食物源分隔开，蚂蚁从蚁巢
自由地向食物源移动。图 2-1（b ）是经过 A 、B 两桥的蚂蚁百分比随时间的变
化情况。实验结果显示，在初始阶段出现一段时间的震荡（由于某些随机因素，
使通过某座桥上的蚂蚁数急剧增多或减少）后，蚂蚁趋向于走同一条路经。在该
实验中，绝大部分蚂蚁选择了 A 桥。
在实验初期，A 、B 两座桥上都没有外激素存在，蚂蚁将以相同的概率选择
A 、
B 两座桥，故此时蚂蚁在两座桥上留下的外激素量相等。经过一段时间后，
由于随机波动致使大部分蚂蚁选择了 A 桥(也有可能为 B 桥），因此更多的外
激素将会留在 A 桥上，致使 A 桥对后来的蚂蚁有更大的吸引力。如图 2-1（b ）
所示，随着时间的推移，A 桥上的蚂蚁数将越来越多，而 B 桥上正好相反。
图 2-1 对称双桥实验
S. Goss [15] 等人给出了上述实验的概率模型。首先，假定桥上残留的外激素
量与过去一段时间经过该桥的蚂蚁数成正比（这意味着不考虑外激素蒸发的情
况）；其次，某一时刻蚂蚁按桥上外激素量的多少来选择某座桥，即蚂蚁选择某
座桥的概率与经过该桥的蚂蚁数成正比。当所有 m 只蚂蚁都经过两座桥以后，
设 A m 、B m 分别为经过 A 桥和 B 桥的蚂蚁数（A m + B m = m ），则第 m+1 只蚂
蚁选择 A 桥的概率为：
()()()()
h
m A h h m m A k p m A k B k +=+++ （2.1） 而选择 B 桥的概率为：
P B (m) = 1- P A (m) （2.2）
其中参数h 和k 用来匹配真实实验数据。第(m+1)只蚂蚁首先按（2.1）式计算选择概率P A(m)，然后生成一个在区间[0,1]上一致分布的随机数，如果≤P A(m)，则选择A 桥，否则选择B 桥。为了求得参数k 和h，通过蒙特卡罗模拟证实[17]，当k ≈20 ，h ≈ 2 时，公式（2.1）与实验数据相一致[16]。
另外，Goss[15]等人还用非对称双桥（两座桥的长度不相等）进行了实验。如图2-2 所示，图2-2(a)为蚂蚁经过非对称双桥开始觅食；图 1.2(b)显示绝大多数蚂蚁选择较短的桥；图2-2(c)显示最终有80%～100%的蚂蚁选择较短的桥。
在非对称双桥实验中，随机抖动对胜出桥（有较多蚂蚁选择的桥）的影响减小，而占主导作用的是随机外激素的引导行为。
在非对称双桥实验中，随机抖动对胜出桥（有较多蚂蚁选择的桥）的影响减小，而占主导作用的是随机外激素的引导行为。
图2-2 非对称双桥实验
处能够找到蚁巢和食物源之间的最短路径外，蚁群还有极强的适应环境的能力，如图2-3 所示，在蚁群经过的路线上突然出现障碍物时，蚁群能够很快重新找到新的最优路径。
图2-3蚁群的自适应行为
(a) 蚁群在蚁巢和食物源之间的路径上移动；(b) 路径上出现障碍物，蚁群以同样的概率向左、右方向行进；(c) 较短路径上的外激素以更快的速度增加；(d) 所有的蚂蚁都选择较短的路径。
2.2 蚁群优化的原理分析
ACO 是受自然界中真实蚁群的集体觅食行为的启发而发展起来的一种基
于群体的模拟进化算法，属于随机搜索算法。M. Dorigo 等人充分利用了蚁群搜索食物的过程与著名TSP 问题之间的相似性，通过人工模拟蚁群搜索食物的行为来求解TSP 问题。从上节的“双桥实验”可以看出，像蚂蚁这类社会性动物，虽然个体的行为极其简单，但由这些简单个体所组成的蚁群却表现出极其复杂的行为特征。如蚁群除了能够找到蚁巢与食物源之间的最短路径外，还能适应环境的变化，即在蚁群运动的路线上突然出现障碍物时，蚂蚁能够很快地重新找到最短路径。蚁群是如何完成这些复杂任务的呢？仿生学家经过大量地观察、研究发现，蚂蚁在寻找食物时，能在其经过的路径上释放一种蚂蚁特有的分泌物—外激素(eromone),使得一定范围内的其它蚂蚁能够感觉到这种物质，且倾向于朝着该物质强度高的方向移动。因此，蚁群的集体行为表现为一种信息正反馈现象：某条路径上经过的蚂蚁数越多，其上留下的外激素的迹也就越多（当然，随时间的推移会逐渐蒸发掉一部分），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径上外激素的强度。蚁群这种选择路径的过程被称之为自催化（Autocatalytic behavior），由于其原理是一种正反馈机制，因此也可将蚁群的行为理解成所谓的增强型学习系统（Reinforcement Learning System）[16-18]。
下面用图2-4和2-5 解释蚁群发现最短路径的原理和机制。
图2-4蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD 或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。
图2-4 蚁群觅食原理图
图2-5为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。
图2-5 蚁群觅食原理图
假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处
的信息素为2个单位，其比值为2：1。
寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。
若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD 路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。
若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。
蚁群算法就是模拟了蚂蚁觅食的这一过程，该算法的思想是用蚂蚁的行走路线表示待求问题的可行解。每只蚂蚁在解空间独立地搜索可行解。搜索到的解的质量越高，在“行走路线”(可行解)留下的信息素也就越多。随着算法的推进，代表较好解的路线上的信息素逐渐增多，选择它的蚂蚁也逐渐增多，最终整个蚁群在正反馈机制的作用下集中到代表最优解的路线上，也就找到了最优解。
2.3 算法基本流程
算法基本流程如图2-6。
图2-6蚁群算法流程图
当然，迄今为止蚁群算法已经有了很多的变型或改进算法，但基于蚁群算法（ACA）寻找问题近似解的思想及实现优化过程的机制还是没有改变。由上图可见，蚁群算法区别于其他传统优化算法，因为它具有以下3个特点：
(1) 模拟了一种大自然真实存在的现象，并建立模型；
(2) 不可确定性；
(3) 总是表现出一种并行性，不是在系统中强行加入，而是算法本身隐含具有的。
2.4 蚁群觅食过程计算机动态模拟
在上面小节中我们讲到了真实蚁群的集体觅食行为，在生活中我们可以见到，但是不会注意它们寻找食物的全过程，现在本文通过计算机动态模拟来模拟真实蚁群的集体觅食行为。使得大家对真实蚁群的集体觅食行为更加熟悉和了解，对真实蚁群的集体觅食行为的过程如图2-7、2-8、2-9、2-10所示：程序开始运行，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。
其中，‘F’点表示食物，‘H’表示窝，白色块表示障碍物，‘+’表示蚂蚁，‘O’表示找到食物的蚂蚁，粉红色的‘+’是代表第一只蚂蚁。
图2-7蚂蚁开始从蚁巢出来觅食
蚂蚁从蚁巢出发沿随机路线去寻找食物，并且在所走的路上留下信息素作为蚂蚁之间交流的介质。图中粉红色的那只蚂蚁是特殊标记，便于研究。
图2-8 蚂蚁沿各条路径随机觅食
已经有蚂蚁找到了食物并在图中用圆圈表示，最先找到食物的蚂蚁走的路线就是目前的最优路径，而且此时这条路径上的信息量浓度比别的路径大，所以有更多的蚂蚁正在沿着这条路走。
图2-9 已有蚂蚁找到最短路径
找到食物的蚂蚁在随机继续寻找着路径，以便发现更优的路径，而没有找到食物的蚂蚁此时大多数都是沿着上图中的最优路径继续寻找，而且也逐渐靠近食物，而此时的最有路径的信息量浓度也越来越大，所以走这条路径的蚂蚁也越来越多。
图2-10 所有蚂蚁找到最优路径
此图中所有蚂蚁都已找到最优路径，并沿着最优路径返回到蚁巢。
由以上4图我们可以清楚的知道蚁群的集体觅食行为的全过程并且得到了预期的结果——蚂蚁找到了最优路径。
2.5 人工蚂蚁与真实蚂蚁的对比
蚁群算法是受到人们对自然界中真实的蚂蚁社会行为的研究成果启发而提出的一种基于种群的模拟进化算法，属于随机搜索算法。Dorigo 等人提出该算法时，正是充分利用了蚁群搜索食物的过程与旅行商问题(TSP)的相似性，通过人工模拟蚂蚁觅食的过程来求解TSP 问题。下面简单介绍蚁群算法中的人工蚂蚁与真实蚂蚁的异同点。
蚁群算法中进行搜索的人工蚂蚁(Agent)的很多观点都来源于真实蚁群，因此它们都包括下列几项[19]。
(1) 存在一个群体中个体相互交流通信的机制，这里通常表现为信息素痕迹；
真实蚂蚁和人工蚂蚁都存在一种机制改变它当前所处的环境：真实蚂蚁经过的路径上留下化学刺激物——信息素(pheromone)，人工蚂蚁在它们经过的路径上改变了路径上存储的数字信息，这个信息记录了蚂蚁当前解和历史解的性能状态，而且能够被经过的其他人工蚂蚁读写。类似的，本文称这种数字信息为人工信息素。在蚁群优化算法中蚂蚁就是通过当前路径L 的信息素进行交流协作的。这种交流方式在收集可利用的知识上占据着重要的位置，其重要的作用在于它改变了当前蚂蚁所经过的路径周围的环境同时也像一个函数似的改变了整个蚁群所存储的历史信息。通常，在蚂蚁优化算法中有一个挥发机制，它像真实的信息
素挥发一样随着时间的推移改变路径上的人工信息素。挥发现象使得蚁群可以逐渐的忘却历史遗留信息、这样就可以使路径的选则不局限于过去蚂蚁的路径选择经验。
(2)群体中每个个体都记录当前遍历序列；
人工蚂蚁和真实蚂蚁都要完成－个相同的任务：寻找一个从源节点（巢穴到目的节点(食物源)的最短路径，它们都不具有跳跃性，都只能在相邻节点之间一步一步移动直至选择完所有城市得到一个遍历序列。为了能在多次寻优过程中找到最短路径，记录当前移动序列是必须的。
(3)利用当前信息进行路径的随机选择策略；
蚁群算法中人工蚂蚁从一个节点移动到下一个节点的求解方法是利用概率选择策略实现的，概率选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息，因此，该选择策略利用的都是当前信息。
在从真实妈蚁的行为中获得启发构造蚁群算法的过程中，人工蚂蚁还具备了真实蚂蚁不具有的一些特性[20]：
(1) 人工蚂蚁存在于一个离散的空间中，它们的移动是一个状态到另一个状态的转换；
(2) 人工蚂蚁具有一个记忆了它本身过去行为的内在状态；
(3) 人工蚂蚁更新信息素的时机是随不同问题而变化的，不反映真实蚁群的行为。如：有的问题中人工蚂蚁在产生一个解后改变信息量，有的问题中蚂蚁每做出一步选择就更改信息量。但无论哪种方法，信息素的更新并不是随时可以进行的。
(4) 为了改善系统的性能，人工蚁群算法中可以增加一些性能，如：预测未来、局部优化、回退等，这些行为在真实蚂蚁中是不存在的。在很多应用中人工蚂蚁可以在局部优化过程中相互交换信息，还有一些蚁群算法实现了简单预测。
2.6 本章小结
本章阐述了ACO 产生的背景、原理、模型及其研究现状。首先通过著名的“双桥实验”分析了蚁群的自组织行为及对该行为的数学建模。在此基础上，阐述了ACO 的原理并给出了蚁群算法的流程，而且还用计算机动态模拟了蚁群觅食过程。最后，进行了人工蚂蚁与真实蚂蚁的对比和分析。
3 基本蚁群优化算法及其改进
下面介绍基本蚁群算法及其典型的改进算法和对基本蚁群算法进行了计算机仿真。
3.1 旅行商问题
一般地，旅行商问题（Traveling Salesman Problem, 简称TSP）可描述如下：设C = {c1，c2，…，c n}为n 个城市的集合，L = {l ij |c i,c j∈C }是C 中元素两两连接的集合，G = (C，L)是一个图，TSP 问题的目的是从G 中找出长度最短的Hamiltonian 圈，即找出对C = {c1，c2，…，c n}中n 个城市访问且只访问一次的最短的一条封闭曲线。目前TSP 问题分为对称型和非对称型。在对称型TSP 问题中，有d ij = d ji，νc i,c j∈C(1，2，L，n)，d ij是l ij的长度，问题文件的后缀名为.tsp；而在非对称型TSP 问题中，至少存在一对c i,c j∈C ，使d ij≠d ji ，问题文件的后缀名为.atsp，对于部分对称型TSP 问题和非对称型TSP 问题，TSPLIB中还收集了到目前为止已知的最优解，其文件名为相应TSP问题名+.opt. tour。
3.2 基本蚁群算法及其典型改进
本小节将介绍蚁基本蚁群算法及其2种典型的改进算法。
3.2.1 蚂蚁系统
AS 算法具有如下优点：
(1)较强的鲁棒性：对AS 算法的模型稍加修改，便可以应用于其它问题；
(2)分布式计算：AS 算法是一种基于种群的进化算法，本质上具有并行性，易于并行实现；
(3)易于与其它方法结合：AS 算法很容易与多种启发式算法结合，以改善算法的性能。
虽然AS 算法有许多优点，但同时也存在一些缺陷，如：
(1)限于局部最优解，从算法解的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求是全局最优解。
(2)工作过程的中间停滞问题（stagnation behaviour），和算法开始时收敛速度快一样, 在算法工作过程当中, 迭代到一定次数后, 蚂蚁也可能在某个或某些局部最优解的邻域附近产生停滞。
(3)较长的搜索时间，尽管和其他算法相比，蚁群算法在迭代次数和解的质量上都有一定的优势，但对于目前计算机网络的实际情况，还是需要较长的搜索
时间。虽然计算机计算速度的提高和蚁群算法的并行性在一定程度上可以缓解这一问题, 但是对于大规模复杂的计算机网络，这还是一个很大的障碍。
对于以上三个问题，已经引起了许多研究者的注意，并提出了若干改进的蚂蚁算法，如M. Dorigo 提出的蚁群系统（ACS）[22]和T. Stützle[23-26]等人提出的最大-最小蚂蚁系统（MMAS）等。下面就代表性的改进算法本文将对3种改进算法进行讨论。
3.2.2 蚁群系统
蚁群系统（Ant Colony System，简称ACS）[22]是AS 最成功的后续算法之一，与AS 算法的主要区别在于：（i）在选择下一座城市时，ACS 算法更多地利用了当前的较好解；（ii）只在全局最优解所属的边上增加信息素；（iii）每次当蚂蚁从城市i 转移到城市j 时，边ij 上的信息素将会适当的减少。
3.2.3 最大-最小蚂蚁系统
最大-最小蚂蚁系统（MAX-MIN Ant System, 简称MMAS）[23-26]是Thomas Stützle（2000）[23]提出的。它的基本思想是在信息素更新过程中，只允许最好的解可以增加信息素实现对已有经验的利用；同时，利用一个限制信息素强度的简单机制，这样成功的避免了在搜索过程中蚂蚁过早的集中到同一条路径上去，而且通过加入局部搜索，MAX-MIN 蚂蚁系统是很容易进行扩展的，有利于算法的拓展。
3.3 基本蚁群算法仿真实验
在3.2.1小节中本文详细介绍了基本蚁群算法的原理等，在本小节中将通过计算机仿真来理解基本蚁群算法的原理，并将作出的路径图和最终结果自动保存到文本文档(.txt)与Excel(.xls)中。
3.3.1 软硬件环境
本实验采用的硬件/软件环境分别为：CPU 3.0GHz，内存256M，硬盘容量80G，操作系统是Microsoft windows XP Service Pack 2，开发平台是Microsoft Visual C++ 6.0、MATLAB 7.0。
3.3.2 重要参数设置
蚁群算法在TSP问题的应用中取得了良好的效果，但也存在一些不足：①如果参数α、β、ρ、m、Q等设置不当，导致求解速度很慢且所得解的质量特别差；
②基本蚁群算法计算量大，求解所需的时间较长；③基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给
定一定循环次数的条件下很难实现这种情况。另一方面,在其他的实际应用中，如图像处理中寻求最优模板问题，并不要求所有的蚂蚁都能找到最优模板，而只需要一只找到即可。如果要求所有的蚂蚁都找到最优模板,反而影响了计算效率。目前，对基本蚁群算法的参数设置和属性的研究大多还处于实验阶段，M. Dorigo [31, 32]等人通过大量的实验对蚂蚁系统的参数和基本属性进行了探讨。所以本实验中重要参数设置如下：
信息素浓度影响力参数α：所有算法α设为1.0。
启发式信息影响力参数β：所有算法β设为5.0。
信息素蒸发系数ρ((1-ρ)表示信息素的持久性系数)：所有算法ρ设为0.5(1-ρ即为0.5)。
蚂蚁数目m：本文将m设为问题规模n的2/5即m=n*2/5在算法开始时蚂蚁随机分布在各个城市上。（n为其中TSP问题中后面的数字，如:ATT48.TSP中48即为n 值）。
TSP问题：本文使用ATT48.TSP的TSP问题。
3.3.3仿真试验
用上两小节中设置的基本蚁群算法的条件进行计算机仿真，以此来说明基本蚁群算法的原理并更充分的了解基本蚁群算法。
图3-1 参数输入
在DOS环境下首先输入城市数目，蚂蚁数目，迭代次数，还有相关重要参数
α、β、ρ、Q，并且该程序具有容错能力。
图3-2 结果输出
图3-3 结果输出自动保存到.txt中
把刚才在DOS环境下运行时输入的参数和最后的输出结果在运行时就自动保存在此文本文档中，以便参考分析和下次运行时直接调用。
图3-4 结果输出自动保存到Excel中
用ACO 算法求解机器人路径优化问题 4.1 问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 4.2 算法理论 蚁群算法（Ant Colony Algorithm，ACA），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士在文献[30]中给出改进模型（ACS），文中 改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos给出了最大-最小蚂蚁系统（MAX-MINAS），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。 蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图 2-1 所示，AE 之间有
MATLAB实现基于蚁群算法的机器人路径规划 1、问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 2 算法理论 蚁群算法（Ant Colony Algorithm，ACA），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士给出改进模型（ACS），文中改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。Stützle 与Hoos给出了最大-最小蚂蚁系统（MAX-MINAS），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图2-1 所示，AE 之间有两条路ABCDE 与ABHDE，其中AB，DE，HD，HB 的长度为1，BC，CD 长度为0.5，并且，假设路上信息素浓度为0，且各个蚂蚁行进速度相同，单位时间所走的长度为1，每个单位时间内在走过路径上留下的信息素的量也相同。当t=0时，从A 点，E 点同时各有30 只蚂蚁从该点出发。当t=1，从A 点出发的蚂蚁走到B 点时，由于两条路BH 与BC 上的信息素浓度相同，所以蚂蚁以相同的概率选择BH 与BC，这样就有15 只蚂蚁选择走BH，有15 只蚂蚁选择走BC。同样的从E 点出发的蚂蚁走到D 点，分别有15 只蚂蚁选择DH 和DC。当t=2 时，选择BC 与DC的蚂蚁分别走过了BCD 和DCB，而选择BH 与DH 的蚂蚁都走到了H 点。所有的蚂蚁都在所走过的路上留下了相同浓度的信息素，那么路径BCD 上的信息素的浓度是路径BHD 上信息素浓度的两倍，这样若再次有蚂蚁选择走BC 和BH 时，或选择走DC 与DH 时，都会以较大的概率选择信息素浓度高的一边。这样的过程反复进行下去，最短的路径上走过的蚂蚁较多，留下的信息素也越多，蚁群这样就可以找到一条较短的路。这就是它们群体智能的体现。 蚁群算法就是模拟蚂蚁觅食过程中可以找到最短的路的行为过程设计的一种仿生算法。在用蚁群算法求解组合优化问题时，首先要将组合优化问题表达成与信息素相关的规范形式，然后各个蚂蚁独立地根据局部的信息素进行决策构造解，并根据解的优劣更新周围的信息素，这样的过程反复的进行即可求出组合优化问题的优化解。 归结蚁群算法有如下特点： （1）分布式计算：各个蚂蚁独立地构造解，当有蚂蚁个体构造的解较差时，并不会影响整体的求解结果。这使得算法具有较强的适应性； （2）自组织性：系统学中自组织性就是系统的组织指令是来自系统的内部。同样的蚁
2.1 蚁群算法的基本原理 蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。 蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食物源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。 (a) 蚁穴 1 2 食物源 A B (b) 人工蚂蚁的搜索主要包括三种智能行为： （1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。 （2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这样信息素就成为蚂蚁之间进行通信的媒介。 （3）蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数量也就越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发，从而变得越来越少。3.3.1蚂蚁系统 蚂蚁系统是最早的蚁群算法。其搜索过程大致如下： 在初始时刻，m 只蚂蚁随机放置于城市中， 各条路径上的信息素初始值相等，设为：0(0)ij ττ=为信息素初始值，可设0m m L τ=，m L 是由最近邻启发式方法构 造的路径长度。其次，蚂蚁(1,2,)k k m = ，按照随机比例规则选择下一步要转
利用蚁群算法优化前向神经网络 来源：深圳发票 https://www.doczj.com/doc/b614376089.html,/ 内容摘要：蚁群算法（ant colony algorithm，简称ACA）是一种最新提出的新型的寻优策略，本文尝试将蚁群算法用于三层前向神经网络的训练过程，建立了相应的优化模型，进行了实际的编程计算，并与加动量项的BP算法、演化算法以及模拟退火算法进行比较，结果表明该方法具有更好的全局收敛性，以及对初值的不敏感性等特点。关键词：期货经纪公司综合实力主成分分析聚类分析 人工神经网络（ANN）是大脑及其活动的一个理论化的数学模型，由大量的处理单元（神经元）互连而成的，是神经元联结形式的数学抽象，是一个大规模的非线性自适应模型。人工神经网络具有高速的运算能力，很强的自学习能力、自适应能力和非线性映射能力以及良好的容错性，因而它在模式识别、图像处理、信号及信息处理、系统优化和智能控制等许多领域得到了广泛的应用。 人工神经网络的学习算法可以分为：局部搜索算法，包括误差反传（BP）算法、牛顿法和共轭梯度法等；线性化算法；随机优化算法，包括遗传算法（GA）、演化算法（EA）、模拟退火算法（SA）等。 蚁群算法是一种基于模拟蚂蚁群行为的随机搜索优化算法。虽然单个蚂蚁的能力非常有限，但多个蚂蚁构成的群体具有找到蚁穴与食物之间最短路径的能力，这种能力是靠其在所经过的路径上留下的一种挥发性分泌物（pheromone）来实现的。蚂蚁个体间通过这种信息的交流寻求通向食物的最短路径。已有相关计算实例表明该算法具有良好的收敛速度，且在得到的最优解更接近理论的最优解。
本文尝试将蚁群算法引入到前向神经网络的优化训练中来，建立了基于该算法的前向神经网络训练模型，编制了基于C++语言的优化计算程序，并针对多个实例与多个算法进行了比较分析。 前向神经网络模型 前向人工神经网络具有数层相连的处理单元，连接可从一层中的每个神经元到下一层的所有神经元，且网络中不存在反馈环，是常用的一种人工神经网络模型。在本文中只考虑三层前向网络，且输出层为线性层，隐层神经元的非线性作用函数（激活函数）为双曲线正切函数： 其中输入层神经元把输入网络的数据不做任何处理直接作为该神经元的输出。设输入层神经元的输出为(x1,x2,Λ,xn)，隐层神经元的输入为(s1,s2,Λ,sh)，隐层神经元的输出为 (z1,z2,Λ,zh)，输出层神经元的输出为(y1,y2,Λ,ym)，则网络的输入-输出为： 其中{w ij}为输入层-隐层的连接权值，{w i0}隐层神经元的阈值，{v ki}为隐层-输出层的连接权值，{v k0}为输出层神经元的阈值。网络的输入-输出映射也可简写为： 1≤k≤m (5)
7.1 蚁群优化算法概述 ?7.1.1 起源 ?7.1.2 应用领域 ?7.1.3 研究背景 ?7.1.4 研究现状 ?7.1.5 应用现状
7.1.1 蚁群优化算法起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。
20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。
背景：人工生命 ?“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容。 ?研究如何利用计算技术研究生物现象。?研究如何利用生物技术研究计算问题。
?现在关注的是第二部分的内容，现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。 ?现在我们讨论另一种生物系统－社会系统。更确切的是，在由简单个体组成的群落与环境以及个体之间的互动行为，也可称做“群智能”(swarm intelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为（如鱼群和鸟群的运动规律），主要用于计算机视觉和计算机辅助设计。
?在计算智能(computational intelligence)领域有两种基于群智能的算法。蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization)。前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。
其中，表示在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率。allowedk = C ? tabuk表示蚂蚁k下一步允许选择的城市。α为启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强。β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越 大，则该状态转移概率越接近于贪心规则；ηij(t) 为启发函数，表达式为。式中，dij表示相邻两个城市之间的距离。（6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素（城市），并把该元素（城市）移动到该蚂蚁个体的禁忌表中。（7）若集合C中元素（城市）未遍历完，即k for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))^2+(CooCity(i,3)-CooCity(j,3))^2); end end MAXIT=10;%最大循环次数 Citystart=[]; % 起点城市编号 tau=ones(NC,NC); % 初始时刻各边上的信息痕迹为1 rho=0.5; % 挥发系数 alpha=1; % 残留信息相对重要度 beta=5; % 预见值的相对重要度 Q=10; % 蚁环常数 NumAnt=20; % 蚂蚁数量 routelength=inf; % 用来记录当前找到的最优路径长度 for n=1:MAXIT for k=1:NumAnt %考查第K只蚂蚁 deltatau=zeros(NC,NC); % 第K只蚂蚁移动前各边上的信息增量为零 %[routek,lengthk]=path(distance,tau,alpha,beta,[]); % 不靠率起始点[routek,lengthk]=path(distance,tau,alpha,beta,Citystart); % 指定起始点if lengthk 蚁群算法在车辆路径问题中的应用 摘要 蚁群算法（Ant Colony Optimization, ACO）是意大利学者M.Dorigo等人通过模拟蚁群觅食行为提出的一种基于种群的模拟进化算法。通过介绍蚁群觅食过程中基于信息素（pheromone）的最短路径的搜索策略，给出了基于MATLAB 的蚁群算法在车辆路径问题（Vehicle Routing Problem, VRP）中的应用。蚁群算法采用分布式并行计算机制，易于其他方法结合，而且具有较强的鲁棒性，但搜索时间长，容易陷入局部最优解。针对蚁群算法存在的过早收敛问题，加入2—opt方法对问题求解进行了局部优化，计算机仿真结果表明，这种混合型蚁群算法对求解车辆路径问题有较好的改进效果。 关键词：蚁群算法、组合优化、车辆路径问题、2-opt方法 1.车辆路径问题 车辆路径问题（VRP）来源于交通运输，1959年由Dantzig 提出，它是组合优化问题中一个典型的NP-hard问题。最初用于研究亚特兰大炼油厂向各个加油站投送汽油的运输路径优化问题，并迅速成为运筹学和组合优化领域的前沿和研究热点。 车路优化问题如下： 已知有一批客户，各客户点的位置坐标和货物需求已知，供应商具有若干可供派送的车辆，运载能力给定，每辆车都是从起点出发，完成若干客户点的运送任务后再回到起点。现要求以最少的车辆数和最少的车辆总行程来完成货物的派送任务。 2、蚁群系统基本原理 在蚂蚁群找到食物时，它们总能找到一条从食物到蚁穴之间的最短路径。因为蚂蚁在寻找食物时会在路途上释放一种特殊的信息素。当它们碰到一个还没有走过的路口时，会随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后面的蚂蚁再次碰到这个路口时，会选择激素浓度较高的路径走。这样形成了一个正反馈，最优路径上的激素浓度越来越高，而其他的路径上激素浓度却会随时间的流逝而消减。最终整个蚁群会找出最优路径。在整个寻找过程中，整个蚁群通过相互留下的信息素作用交换着路径信息，最终找到最优路径。 3、基本蚁群算法求解车辆路径问题 求解VRP问题的蚂蚁算法中，每只蚂蚁是一个独立的用 于构造路线的过程，若干蚂蚁过程之间通过信息素值来交换信 2007年第2期空间电子技术收稿日期：2006-04-03；收修改稿日期：2006-04-30 粒子群算法和蚁群算法的结合及其在 组合优化中的应用 张长春苏昕易克初 （西安电子科技大学综合业务网国家重点实验室，西安710071） 摘要文章首次提出了一种用于求解组合优化问题的PAAA 算法。该算法有效地 结合了粒子群算法和蚁群算法的优点，先利用粒子群算法的随机性、快速性、全局性得到 初始信息素分布（即粗搜索），再利用蚁群算法的并行性、正反馈性、求解精度高等优点求 精确解（即细搜索）。将文中提出的算法用于经典TSP 问题的求解，仿真结果表明PAAA 算 法兼有两种算法的优点，同时抛弃了各自的缺点。该算法在时间效率上优于蚁群算法，在 求精效率上优于粒子群算法，是综合了两种算法长处的一种新的启发式算法，达到时间性 能和优化性能上的双赢，获得了非常好的效果。 主题词蚁群算法粒子群算法旅行商问题PAAA 0引言 近年来对生物启发式计算（Bio-inspired Computing ）的研究，越来越引起众多学者的关注和兴趣，产生了神经网络、遗传算法、模拟退火、粒子群算法、蚁群算法等许多用于解决复杂优化问题的新方法。然而，面对各种问题的特殊性和复杂性，每种算法都表现出了自身的优势和缺陷，都存在时间性能和优化性能不能兼得的矛盾。 粒子群优化（Particie Swarm Optimization ，PSO ）算法[1， 2]是由Eberhart 和Kennedy 于1995年提出的一种全局优化算法，该算法源于对鸟群觅食行为的模拟。它的优势在于：（1） 算法简洁，可调参数少，易于实现；（2） 随机初始化种群，具有较强的全局搜索能力，类似于遗传算法；（3）利用评价函数衡量个体的优劣程度，搜索速度快；（4）具有较强的可扩展性。其缺点是：不能充分利用系统中的反馈信息，求解组合优化问题的能力不强。 蚁群算法[3，4]（Ant Coiony Optimization ，ACO ） 是由意大利学者M.Dorigo ，V.Maniezzo 和A.Coiorni 于20世纪90年代初提出的一种新型的智能优化算法，已经被应用到TSP 问题[5，6]、二次分配问题、工 件调度问题、图着色问题等许多经典组合优化问题中，取得了很好的效果。它的优点是：（1）采用一种正反馈机制，通过信息素的不断更新，达到最终收敛于最优路径上的目的；（2）是一种分布式的优化方法，易于并行实现；（3）是一种全局优化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（4）适合于求解离散优化问题；（5）鲁棒性强。但由于在算法的初始阶段信息素匮乏，所以求解速度较慢。 文章将粒子群算法和蚁群算法有机地结合，提出了PAAA 算法。它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解，汲取各自的优势，以达空间电子技术 SPACE ELECTRONIC TECHNOLOGY !" 摘要 自意大利学者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.蚁群算法 众所周知，蚁群算法是优化领域中新出现并逐渐引起重视的一种仿生进化算法它是群体智能的典型实现，是一种基于种群寻优的启发式搜索算法。自从M．Dorigo等意大利学者在1991年首先提出蚁群算法(Ant Colony System，ACS)以来，这种新型的分布式智能模拟算法已逐渐引起人们的注意并得到广泛的使用。 蚁群算法的特点主要表现在以下五个方面： (1)蚂蚁群体行为表现出正反馈过程。蚁群在寻优的过程中会释放一定量的信息素，蚁群的规模越大，释放的信息素的量也就越大，而寻优路径上存在的信息素浓度越高，就会吸引更多的蚂蚁，形成一种正反馈机制，然后通过反馈机制的调整，可对系统中的较优解起到一个自增强的作用，从而使问题的解向着全局最优的方向演变，最终能有效地获得全局相对较优解。 (2)蚁群算法是一种本质并行的算法。个体之间不断进行信息交流和传递．有利于最优解的发现，并在很大程度上减少了陷于局部最优的可能。 (3)蚁群算法易于和其他方法结合。蚁族算法通过和其他算法的结合，能够扬长避短，提高算法的性能。 (4) 蚁群算法提供的解具有全局性的特点。一群算法是一种群只能算法，每只蚂蚁巡游的过程相对独立，他们会在自己的活动空间进行搜索，蚂蚁在寻优过程中通过释放信息素，相互影响，互相通信，保证了解的全局性。 (5) 蚁群算法具有鲁棒性。蚁族算法的数学模型易于理解，可以广泛使用在很多复杂的优化问题中，蚁族算法区别于传统优化算法的一个特点在于该算法不依赖于初始点的选择，受初始点的影响相对较小，并且在整个算法过程中会自适应的调整寻优路径。 由此可见，在机器人寻找最优路径的过程中，采用蚁群算法实现路径的规划问题，可以高效，准确的找到最优的路径。 2.移动机器人的路径规划 2.1环境信息处理 假设机器人运行环境为边长分别为x和Y的矩形区域，在矩形区域内分布有n 用AＣＯ算法求解机器人路径优化问题 4.1问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗,最短行走路线，最短行走时间等),在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 4.２算法理论 蚁群算法（Aｎt ＣｏｌonｙＡｌｇoｒithm，ACA)，最初是由意大利学者Ｄｏｒigo M. 博士于１991 年首次提出，其本质是一个复杂的智能系统,且具有较强的鲁棒性,优良的分布式计算机制等优点。该算法经过十多年的发展,已被广大的科学研究人员应用于各种问题的研究，如旅行商问题,二次规划问题,生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Ｄorigｏ提出了精英蚁群模型（ＥAS）,在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢,并不能取得较好的效果。次年Dorigｏ博士在文献［3０]中给出改进模型(ACＳ),文中 改进了转移概率模型，并且应用了全局搜索与局部搜索策略,来得进行深度搜索。 Stüｔzｌe 与Hoｏｓ给出了最大－最小蚂蚁系统（MAX-MINAＳ),所谓最大－最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优,设定下限鼓励深度搜索。 蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的,蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物,蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能,可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图 2-1 所示,AE 之间有 蚁群算法在路径优化中的应用 作者：孙阳阳指导老师：刘冲 摘要针对蚁群算法在路径中的优化问题，本文首先介绍了蚁群算法的概念及其原理，利用数学 形式建立算法模型.根据蚁群算法计算的基本步骤来分析蚁群算法在交通路径优化、TSP问题等3 个方面的应用，由实验结果可知蚁群算法在路径优化中具有很好的可行性和优越性，能起到很 好的效果. 关键词蚁群算法算法模型算法步骤分析应用 1 引言 路径规划是指在具有障碍物的环境下，在符合某种评价条件中，寻找到一条从起始地点到目标地点最优的路径.蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化系统,计算法采用分布式并行计算和正反馈机制，且易于其它算法结合，目前已有许多关于其在路径规划方面的文献. 建立蚁群算法模型]2][1[，解决城市交通路径优化问题，实验结果表面在搜索效率和搜索最优解的能力两方面都有很大的提高.但是传统蚁群算法易陷入局部最优解和收敛速度较 4[ ，将传统蚁群算法进行改进，例如与栅格法相结合、慢，为此在机器人路径规划的应用中]7 在几何模型下建立模型等.提高了算法的有效性和鲁棒性，解决了蚁群过早陷入局部最优解的问题，扩大了蚂蚁的搜索空间，增强了蚁群算法在机器人路径规划中的适应能力. 本文通过对蚁群算法的研究以及解决几实际路径规划问题，得出了蚁群算法是有其可行性和优越性的，说明了该算法可以在众多优化领域中得到广泛的应用. 2 蚁群算法 蚁群算法(ant colony optimization),又称蚂蚁算法，简称ACO.是由Dorigom、Maniezzov、Colorni等人在1992年所发表的论文提出的，其灵感来源于蚂蚁在寻找食物中发现路径的行为.它是一种模拟进化算法，通过人工模拟蚂蚁觅食过程，即个体间的信息交流与合作不断排除不适合的路途，最终寻找到从蚁穴到食物源的最短路径. 2.1 蚁群算法的基本原理 蚂蚁在搜寻食物过程中总能找到一条从蚁穴到到食物的最优路径，这是因为蚂蚁在搜寻路径上释放一种特殊的信息素.当它们遇到一个还没有被走过的路口时，会随机的选择一条路径，而选择的路径与信息素的浓度有关，同时在该路径上它们也会释放自己的信息素.路径越短，信息素浓度越大；反正路径越长信息素堆积的越少.则过一段时间蚂蚁选择信息素浓度高的路径的概率越来越大，而其它路径随着蚂蚁越来越少的选择信息素浓度逐渐减小，这一就形成了一个正反馈现象，最终指导整个蚁群找到从蚁穴到食物源的最短路径. 2.2 蚁群算法的数学模型 2.2.1 问题的描述 蚁群算法在物流系统优化中的应用 ——配送中心选址问题 LOGO https://www.doczj.com/doc/b614376089.html, 框架 蚁群算法概述 蚁群算法模型 物流系统中配送中心选择问题 蚁群算法应用与物流配送中心选址 算法举例 蚁群算法简介 ?蚁群算法(Ant Algorithm简称AA)是近年来刚刚诞生的随机优化方法，它是一种源于大自然的新的仿生类算法。由意大利学者Dorigo最早提出，蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优的目的，最初又称蚁群优化方法(Ant Colony Optimization简称ACO)。由于模拟仿真中使用了人工蚂蚁的概念，因此亦称蚂蚁系统(Ant System，简称AS)。 蚁群觅食图1 ?How do I incorporate my LOGO and URL to a slide that will apply to all the other slides? –On the [View]menu, point to [Master],and then click [Slide Master]or [Notes Master].Change images to the one you like, then it will apply to all the other slides. [ Image information in product ] ?Image : www.wizdata.co.kr ?Note to customers : This image has been licensed to be used within this PowerPoint template only. You may not extract the image for any other use. MATLAB 实现基于蚁群算法的机器人路径规划 1、问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则（如最小能量消耗，最短行走路线，最短行走时间等），在其工作空间中找到一条从起 始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 2 算法理论 蚁群算法（Ant Colony Algorithm ，ACA ），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS ），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士给出改进模型（ACS ），文中改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos 给出了最大-最小蚂蚁系统（MAX-MINAS ），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图2-1 所示，AE 之间有两条路ABCDE 与ABHDE ，其中AB ，DE，HD，HB 的长度为1，BC，CD 长度为0.5，并且，假设路上信息素浓度为0，且各个蚂蚁行进速度相同，单位时间所走的长度为1，每个单位时间内在走过路径上留下的信息素的量也相同。当t=0 时，从A 点，E 点同时各有30 只蚂蚁从该点出发。当t=1，从A 点出发的蚂蚁走到B 点时，由于两条路BH 与BC 上的信息素浓度相同，所以蚂蚁以相同的概率选择BH 与BC ，这样就有15 只蚂蚁选择走BH，有15 只蚂蚁选择走BC 。同样的从E 点出发的蚂蚁走到D 点，分别有15 只蚂蚁选择DH 和DC。当t=2 时，选择BC 与DC 的蚂蚁分别走过了BCD 和DCB ，而选择BH 与DH 的蚂蚁都走到了H 点。所有的蚂蚁都在所走过的路上留下了相同浓度的信息素，那么路径BCD 上的信息素的浓度是路径BHD 上信息素浓度的两倍，这样若再次有蚂蚁选择走BC 和BH 时，或选择走DC 与DH 时，都会以较大的概率选择信息素浓度高的一边。这样的过程反复进行下去，最短的路径上走过的蚂蚁较多，留下的信息素也越多，蚁群这样就可以找到一条较短的路。这就是它们群体智能的体现。 蚁群算法就是模拟蚂蚁觅食过程中可以找到最短的路的行为过程设计的一种仿生算法。在用蚁群算法求解组合优化问题时，首先要将组合优化问题表达成与信息素相关的规范形式，然后各个蚂蚁独立地根据局部的信息素进行决策构造解，并根据解的优劣更新周围的信息素，这样的过程反复的进行即可求出组合优化问题的优化解。 归结蚁群算法有如下特点： （1）分布式计算：各个蚂蚁独立地构造解，当有蚂蚁个体构造的解较差时，并不会影响整体的求解结果。这使得算法具有较强的适应性； （2）自组织性：系统学中自组织性就是系统的组织指令是来自系统的内部。同样的蚁群算法中的各个蚂蚁的决策是根据系统内部信息素的分布进行的。这使得算法具有较强的鲁棒性； （3）正反馈机制与负反馈机制结合：若某部分空间上分布的信息素越多，那么在这个空间上走过的蚂蚁也就越多；走过的蚂蚁越多，在那个空间上留下的信息素也就越多，这就是存在的正反馈机制。但蚁群算法中解的构造是通过计算转移概率实现的，也就是说构造解的时候可以接受退化解，这限制了正反馈机制， 粒子群算法（PSO）和遗传算法(GA)都是优化算法，都力图在自然特性的基础上模拟个体种群的适应性，它们都采用一定的变换规则通过搜索空间求解。 PSO和GA的相同点： (1)都属于仿生算法。PSO主要模拟鸟类觅食、人类认知等社会行为而提出；GA主要借用生物进化中“适者生存”的规律。 (2)都属于全局优化方法。两种算法都是在解空间随机产生初始种群，因而算法在全局的解空间进行搜索，且将搜索重点集中在性能高的部分。 (3)都属于随机搜索算法。都是通过随机优化方法更新种群和搜索最优点。PSO中认知项和社会项前都加有随机数；而GA的遗传操作均属随机操作。 (4)都隐含并行性。搜索过程是从问题解的一个集合开始的，而不是从单个个体开始，具有隐含并行搜索特性，从而减小了陷入局部极小的可能性。并且由于这种并行性，易在并行计算机上实现，以提高算法性能和效率。 (5)根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。 (6)对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。PSO和GA不同点 (1)PSO有记忆，好的解的知识所有粒子都保存，而GA没有记忆，以前的知识随着种群的改变被破坏。 (2)在GA算法中，染色体之间相互共享信息，所以整个种群的移动是比较均匀地向最优区域移动。PSO中的粒子仅仅通过当前搜索到最优点进行共享信息，所以很大程度上这是一种单项信息共享机制，整个搜索更新过程是跟随当前最优解的过程。在大多数情况下，所有粒子可能比遗传算法中的进化个体以更快速度收敛于最优解。 (3)GA的编码技术和遗传操作比较简单，而PSO相对于GA，不需要编码，没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。(4)在收敛性方面，GA己经有了较成熟的收敛性分析方法，并且可对收敛速度进行估计；而PSO这方面的研究还比较薄弱。尽管已经有简化确定性版本的收敛性分析，但将确定性向随机性的转化尚需进一步研究。 (5)在应用方面，PSO算法主要应用于连续问题，包括神经网络训练和函数优化等，而GA 除了连续问题之外，还可应用于离散问题，比如TSP问题、货郎担问题、工作车间调度等。蚁群算法在车辆路径问题中的应用
粒子群算法和蚁群算法的结合及其在组合优化中的应用e
基本蚁群优化算法及其改进毕业设计
蚁群优化算法
目录 [隐藏]
? ?
比较
1 2
蚁群算法的提出： 人工蚂蚁与真实蚂蚁的异同
o o ? ? ? ? ?
3 4 5 6 7
2.1 2.2
相同点比较 不同点比较
蚁群算法的流程图 基本蚁群算法的实现步骤 蚁群算法的 matlab 源程序 蚁群算法仿真结果 版权声明
[编辑]蚁群算法的提出：
人类认识事物的能力来源于与自然界的相互作用，自然界一直是人类创造力 的源泉。 自然界有许多自适应的优化现象不断地给人以启示，生物和自然中的生 态系 统可以利用自身的演化来让许多在人类看来高度复杂的优化问题得到几乎完美 的解决。近些年来，一些与经典的数学问题思想不同的，试图通过模拟自然生态 系统 来求解复杂优化问题的仿生学算法相继出现，如蚁群算法、遗传算法、粒子群算 法等。 这些算法大大丰富了现在优化技术，也为那些传统最优化技术难以处理的 组 合优化问题提供了切实可行的解决方案。 生物学家通过对蚂蚁的长期的观察发现，每只蚂蚁的智能并不高，看起来没 有集中的指挥，但它们却能协同工作，集中事物，建起坚固漂亮的蚁穴并抚养后 代， 依靠群体能力发挥出超出个体的智能。 蚁群算法是最新发展的一种模拟昆虫王国 中蚂蚁群体智能行为的仿生优化算法，它具有较强的鲁棒性、优良的分布式计算 机 制、易于与其他方法相结合等优点。尽管蚁群算法的严格理论基础尚未奠定，国 内外的相关研究还处于实验阶段， 但是目前人们对蚁群算法的研究已经由当初单 一 的旅行商问题(TSP)领域渗透到了多个应用领域，由解决一维静态优化问题发展 到解决多维动态组合优化问题， 由离散域范围内的研究逐渐扩展到了连续域范围 内的蚁群算法最优路径
matlab_蚁群算法_机器人路径优化问题
蚁群算法在路径优化中的应用3改
蚁群算法原理与应用讲解
(完整word版)基于蚁群算法的路径规划
粒子群蚁群算法路径优化算法
相关主题
文本预览