下载文档原格式
蚁群算法的应用与改进作者：宗泽宏来源：《电子技术与软件工程》2017年第01期蚁群算法（ACA）作为一种仿生进化算法，现多应用于优化领域。
它是通过对自然界蚂蚁的寻径方式进行仿真分析之后而获得一种随机搜索方法，该方法可用于处理组合优化问题。
在本文，在对该算法的基本原理进行介绍之后，对数学模型的构建以及算法的进一步优化进行阐释，最后对其应用前景予以预测。
【关键词】蚁群算法仿生进化随机搜索1 引言在信息量不断扩大的今天，数据挖掘技术所具有的优良性能开始凸现。
数据挖掘技术的改进与优化有利于帮助我们从大规模数据中筛选出有用的信息与应用模式。
对于数据挖掘技术而言，探寻一种更高效的算法是改进与优化此技术的核心。
1991年，意大利著名研究学者M.Dorigo率先提出了一种新型仿生算法ACA，也就是本文所研究的蚁群算法。
在对蚂蚁的一系列行为进行深入研究之后提出了其基本原理并构建了相应的数学模型——蚁群算法，之后将其用于获得旅行商问题（TSP）的解释。
2 蚁群算法的原理ACA是通过深入研究蚂蚁行为而形成的一种自然算法。
该算法最突出的特征是蚂蚁会通过“信息素” （pheromone）和其他蚂蚁保持间接异步联系。
蚂蚁在行动的过程中，会在其走过的路上残留下一些信息素，这些信息素能够被同群的蚂蚁伙伴所感知，并且会对蚂蚁行为产生影响。
即在相同时间内，离食物愈近的路径会被更多的蚂蚁选择，所留下的信息素也会愈来愈浓，后期蚂蚁选择此路径的概率便会更大。
该过程会持续迭代，一直持续到所有蚂蚁都选择了较短路线。
阿根廷蚂蚁在开始觅食时就会自动分泌并残留费洛蒙（pheromone）痕迹。
实验者准备了两个大槽，其中一个放入阿根廷蚁群，另外一个放入食物。
之后，在两个槽之间搭建了一个小桥。
实验者们在这座桥上进行了特别设计，即在桥的跨距1/4的地方，划分为两条路，尽管两条路都能够达到食物槽，不过其路径距离不同，其中一条路大约是另一条路的2倍。
对此，蚂蚁们会做出什么样的选择呢？就像预期的那样，蚂蚁在非常短的时间内就明确了最佳路径。
c law enforcement. Therefore, c congestion was ciency of the improved algorithm with the Dijkstra algorithm. Thus, it could simulate the optimal driving path with better performance, which was targeted and innovative.关键词：蚁群算法;实际路况;最优路径Key words ：ant colony optimization; actual road conditions; optimal path文／张俊豪蚁群算法在最优路径选择中的改进及应用0 引言在国务院发布的《国家中长期科学和技术发展规划纲要（2006-2020年）》中，将交通拥堵问题列为发展现代综合交通体系亟待解决的“三大热点问题”之一。
智能交通系统作为“互联网+交通”的产物，利用先进的科学技术对车、路、人、物进行统一的管控、调配，成为了当下各国缓解交通拥堵的一个重要途径。
路径寻优是智能交通系统的一个核心研究内容，可以有效的提升交通运输效率，减少事故发生频率，降低对城市空气的污染以及提升交通警察的执法效率等。
最著名的路径规划算法是Dijkstra算法和Floyd算法，Dijkstra算法能够在有向加权网络中计算得到某一节点到其他任何节点的最短路径；Floyd算法也称查点法，该算法和Dijkstra算法相似，主要利用的是动态规划思想，寻找加权图中多源节点的最短路径。
近些年，最优路径的研究主要集中以下几个方面：（1）基于A*算法的路径寻优。
A*算法作为一种重要的路径寻优算法，其在诸多领域内都得到了应用。
随着科技的发展，A*算法主要运用于人工智能领域，特别是游戏行业，在游戏中，A*算法旨在找到一条代价（燃料、时间、距离、装备、金钱等）最小化的路径，A*算法通过启发式函数引导自己，具体的搜索过程由函数值来决定。
收稿日期:2002211202;修返日期:2002212221智能蚂蚁算法———蚁群算法的改进曹浪财,罗 键,李天成(厦门大学自动化系,福建厦门361005)摘 要:蚁群算法是一种解决组合优化问题的有效算法。
在蚁群算法的基础上,提出了一种新的启发式搜索方法———智能蚂蚁算法。
智能蚂蚁算法与蚁群算法相比,主要在以下四点进行了改进:第一,取消了外激素;第二,自动调整选择最优路径的比例;第三,目标城市的选择方法不同;第四,引入扰动以避免陷入局部优化。
实验结果表明,智能蚂蚁算法可以在减少计算量的同时,取得更好的搜索结果。
关键词:智能蚂蚁算法;蚁群算法;旅行商问题(TSP );外激素中图法分类号:TP301.6 文献标识码:A 文章编号:100123695(2003)1020062203Intelligent Ant System :An Improved Alg orithm over ACSC AO Lang 2cai ,LUO Jian ,LI T ian 2cheng(Dept.o f Automation ,Xiamen University ,Xiamen Fujian 361005,China )Abstract :Ant C olony System (ACS )is an effective alg orithm to s olve combinatorial problems such as T SPs.Based on ACS ,a new alg o 2rithm ,Intelligent Ant System (I AS ),is designed to im prove the performance.T here are four new characters in I AS.T he first is eliminating pherom one ,which occupied much CP U time.T he second is to adjust propotion of ch oosing the city in best route.T he third is new criteri 2on in determining which city to visit.T he last is the introduction of disturbation to av oid local optimization.T he ex perimental results verify the effectiveness of the new alg orithm.K ey w ords :I AS;ACS;T SP ;Pherom one1 蚂蚁算法蚂蚁算法作为一种新的仿生类进化算法是由D orig o 首先提出的,该算法模仿蚂蚁觅食时的行为,按照启发式思想,通过信息传媒———外激素(Pherom one )的诱发作用,逐渐收敛到问题的全局最优解。
蚁群算法的改进与实现作者：何巧亮指导老师：吴超云摘要近年来蚁群算法的研究有了很大的进展，本文介绍了一种基于信息素更新的蚁群算法—最优-最差蚂蚁系统.该算法通过对局部信息素、全局信息素更新的改进，以及对最优解进行更大限度的增强和对最差解的削弱，使得属于最优路径的边与属于最差路径的边之间的信息素量差异进一步增大，从而使得蚁群的搜索行为更集中于最优解的附近.最后通过仿真实验，证明了改进算法可以得到最优解，且收敛速度比一般的蚁群算法更快.关键词蚁群算法TSP信息素1 引言蚁群算法（Ant Colony Algorithm）是通过对自然界中真实的蚁群集体行为的研究而提出的一种基于种群的模拟进化算法.该算法属于随机搜索算法，由意大利学者M.Dorigo等[1]首先提出.该算法充分利用了蚁群搜索食物的过程来求解TSP，为了区别于真实蚂蚁群体系统，称该算法为“人工蚁群算法”.用蚁群方法求解NP-complete问题如TSP问题[2]、分配问题以及job-shop调度问题等，取得了较好的试验结果.蚁群算法的近10年来的研究表明：蚁群算法用于解决组合优化问题时具有很强的发现解的能力，且具有分布式计算、易于与其它方法结合、鲁棒性强等优点，在动态环境下表现出高度的灵活性和健壮性.除了业已得到公认的遗传算法、模拟退火算法、禁忌搜索算法、神经网络算法等热门进化类方法，新加入的蚁群算法也开始崭露头角，为复杂困难的系统优化问题提供了新的求解方法.尽管一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自于大自然.这种由欧洲学者提出并加以改进的新颖系统优化思想，正在吸引着越来越多的学者的关注和研究，应用范围也开始遍及到许多科学技术和工程领域.蚁群算法在运算过程中，蚁群的转移是由各条路径上留下的信息量强度和城市之间的距离来引导的.蚁群运动的路径总是趋近于信息量最大的路径.通过对蚁群以及蚁群算法的研究表明，不论是真实蚁群还是人工蚁群系统，通常情况下，信息量最强的路径与所需要的最优路径比较接近.然而，信息量最强的路径不是所需要最优路径的情况仍然存在，而且在人工蚁群系统中，这种现象经常出现.这是由于在人工蚁群系统中，路径上的初始信息量是相同的，蚁群创建的第一条路径所获得的信息主要是城市之间的距离信息，这时蚁群算法等价于贪婪算法.第一次循环中蚁群在所经过的路径上留下的信息不一定能反映出最优路径的方向，特别是蚁群中个体数目较少或者所计算的路径组合较多时，就更不能保证蚁群创建的第一条路径能引导蚁群走向全局最优路径.第一次循环后，蚁群留下的信息会因为正反馈作用使得这条路径不是最优的路径，而且可能使离最优路径相差很远的路径上的信息得到不应有的增强，从而阻碍以后的蚂蚁发现更好的全局最优路径.不仅是第一次循环所建立的路径可能对蚁群产生误导，任何一次循环，只要这次循环所利用的信息较平均地分布在各个方向上，这次循环所释放的信息素就可能会对以后蚁群的决策产生误导.因此蚁群所找出的解需要通过一定的方法来增强，使蚁群所释放的信息素尽可能地不对以后的蚁群产生误导.同时，蚁群算法存在搜索时间长、易于停滞的缺点.近年来的研究表明，在解的质量和最优解的距离之间存在着一定的关系.因此将搜索集中于搜索过程中所找出的最优解的周围，是这些改进算法提高算法性能的基本着重点.2 基本蚁群算法系统模型基本蚁群算法系统是我们研究改进的蚁群算法的基础，在近年的研究中起着极其重要的作用，下面我们将引入其模型以及相关改进算法的说明.2.1 TSP 问题下的基本蚁群算法]3[Ant System 最先用于求解旅行商问题(TSP),下面就以TSP 问题为例来说明Ant System.设m 为蚁群数量；ij d 为城市i ，j 之间的距离；)(t τ为t 时刻连接城市i 和j 的路径(i,j)上的残留信息量，初始时刻各路径上信息量相等，设C =)0(τ（C 为常数）；η表示城市i 转移到城市j 的期望程度，可根据某种启发式算法具体确定，在TSP 问题中一般取ij ij d l /=η.蚂蚁k(k=1,2,…,m)根据各条路径上的信息量决定转移方向，t 时刻蚂蚁k 从城市i 向城市j转移的概率)(t P kij 计算式为()()()0ij ij k ijis is t t P t otherwiseαβαβτητη⎧⨯⎪=⨯⎨⎪⎩∑ （2.1） 式中,j ∈allowed k ，s ∈allowed k ，allowed k ={0,1,…,n-1}-tabu k 表示蚂蚁k 下一步允许选择的城市.与自然蚁群系统不同之处在于人工蚁群系统具有一定的记忆力, tabu k（k=1,2,…,m ）用于记录蚂蚁k 所走过的城市,集合tabu k 随着进化过程进行动态调整.人工蚁群保留了自然蚁群信息素挥发特点,随着时间的推移,以前留下的信息逐渐消逝,参数ρ (10<≤ρ)表示信息素的持久性，1-ρ则表示信息素的衰减度.在每只蚂蚁完成对所有城市(n 个)的访问后(即一次循环结束) ,各路径的信息素量根据式(2.2) ,式(2.3) 进行调整.ij ij ij t n t τρτρτ∆-+=+)1()(.)( (2.2)∑=∆=∆mk kijij 1ττ (2.3) 在(2.3)式中,kij τ∆表示第k 只蚂蚁在本次循环中留在路径(i ，j)上的信息素量,ij τ∆表示本次循环中路径(i ，j)上的信息素增量. 否则 ）时刻经过路径（只蚂蚁在若第⎪⎩⎪⎨⎧+=∆ 0,1 j i t k L Qk kij τ （2.4） 在(2.4)式中, Q 是1 个常数, 表示蚂蚁所留的信息素量，k L 表示第k 只蚂蚁在本次循环中所走路径的长度.在初始时刻，。
【转】蚁群算法原理及其实现（python）蚁群算法(AG)是⼀种模拟蚂蚁觅⾷⾏为的模拟优化算法，它是由意⼤利学者Dorigo M等⼈于1991年⾸先提出，并⾸先使⽤在解决TSP（旅⾏商问题）上。
之后，⼜系统研究了蚁群算法的基本原理和数学模型.蚁群算法的基本思想:蚁群算法的基本原理:1、蚂蚁在路径上释放信息素。
2、碰到还没⾛过的路⼝，就随机挑选⼀条路⾛。
同时，释放与路径长度有关的信息素。
3、信息素浓度与路径长度成反⽐。
后来的蚂蚁再次碰到该路⼝时，就选择信息素浓度较⾼路径。
4、最优路径上的信息素浓度越来越⼤。
5、最终蚁群找到最优寻⾷路径。
⼈⼯蚁群与真实蚁群对⽐:基于TSP问题的基本蚁群算法：TSP求解中，假设蚁群算法中的每只蚂蚁是具有以下特征的简单智能体：每次周游，每只蚂蚁在其经过的⽀路（i,j）上都留下信息素。
‚蚂蚁选择城市的概率与城市之间的距离和当前连接⽀路上所包含的信息素余量有关。
ƒ为了强制蚂蚁进⾏合法的周游，直到⼀次周游完成后，才允许蚂蚁游⾛已访问过的城市（这可由禁忌表来控制）。
基本蚁群的两个过程:(1)状态转移(2)信息素更新(1)状态转移为了避免残留信息素过多⽽淹没启发信息，在每只蚂蚁⾛完⼀步或者完成对所有n个城市的遍历(也即⼀个循环结束)后，要对残留信息进⾏更新处理。
由此，t+n时刻在路径(i,j)上的信息量可按如下规则进⾏调整：(2)信息素更新模型蚁周模型（Ant-Cycle模型）蚁量模型（Ant-Quantity模型）蚁密模型（Ant-Density模型）区别：1.蚁周模型利⽤的是全局信息，即蚂蚁完成⼀个循环后更新所有路径上的信息素；2.蚁量和蚁密模型利⽤的是局部信息，即蚂蚁完成⼀步后更新路径上的信息素。
基本流程:蚁群算法中主要参数的选择:蚁群算法中主要参数的理想选择如下:国内外，对于离散域蚁群算法的改进研究成果很多，例如⾃适应蚁群算法、基于信息素扩散的蚁群算法等，这⾥仅介绍离散域优化问题的⾃适应蚁群算法。
