西安交通大学：《工程优化方法及其应用》研究生课程教学课件（PPT讲稿）14 全局优化算法之蚁群优化算法

蚁群优化算法

蚁群优化算法 1

蚁群的自适应行为NestFood1088800000蚂蚁总能找NestFood到蚁穴与食Obstacle物之间的最短路径FoodNestObstacleNestFoodSSE

蚁群的自适应行为 蚂蚁总能找 到蚁穴与食 物之间的最 短路径 2

蚁群的自适应行为研究发现：1、是一种遗留在往来路径上的挥发性化学元素（信息素）在起作用；2、信息素浓度越高蚂蚁越容易选择；3、经过较长时间，多数蚂蚁就会聚集在较短路径。BotootooA--丰to车3

蚁群的自适应行为 研究发现： 1、是一种遗留在往来路径上的挥发性化学元素 （信息素）在起作用； 3、经过较长时间，多数蚂蚁就会聚集在较短路径。 2、信息素浓度越高蚂蚁越容易选择； A B 3

蚂蚁的食行为及其优化过程双桥实验（Deneubourg等）路径A上蚂蚁的百分比路径B上蚂蚁的百分比O15cm10075蚁穴食物源60°50°25B025305.101520Time(minutes)蚁穴食物源对于非对称双桥，结果表明：最终80%-100%的蚂蚁选择较短的桥

蚂蚁的觅食行为及其优化过程 双桥实验（Deneubourg等） 100- 75- 50- 25- 0 5 10 15 20 25 30 Time（minutes） B A 路径B上蚂蚁的百分比 路径A上蚂蚁的百分比 对于非对称双桥，结果表明： 最终80%-100%的蚂蚁选择较短的桥。 4

随机模型Deneubourg和他的同事提出了一个简单的随机模型用以描述在双桥实验中观测得到的蚁群动态行为。设V支蚂蚁以速度>从某个方向过桥并释放1个单位信息素l和l分别为短分支和长分支长度Pis则通过两分支的时间分别为：蚁穴Q1t,=%,t,=%=r,食物源节点节点Pia：蚂蚁到达节点时分支a上il信息素的大小Pia：蚂蚁到达节点时选择分支a的概率LP

随机模型 Deneubourg和他的同事提出了一个简单的随机模型， 用以描述在双桥实验中观测得到的蚁群动态行为。 l s和l l分别为短分支和长分支长度 s l l s s rt v l t v l t = , = = 则通过两分支的时间分别为： . , 1 单位信息素 设支蚂蚁以速度v从某个方向过桥 并释放 个 . : 信息素的大小 ia 蚂蚁到达节点i时分支a上 节点 s is l  l il l  p :蚂蚁到达节点i时选择分支a的概率. ia 节点 5

随机模型定义(t, +Pis(t)a(一般取α=2)Pis(t) =(t, +s(t) +(t, + Pa(t)isPi(t) = 1- Pis(t)蚁穴食物源节点信息素更新：节点dpis(t)/dt =y Pis(t-t,)+y Pis(t)Pildpiu(t)/dt =y P;(t-t,)+y Pi(t)其中i=l，j=2；i=2，j=1

随机模型 ( 2) ( ( )) ( ( )) ( ( )) ( ) = + + + + =        一般取 定 义 t t t t t t p t s is s il s is is 节点 s is l  l il l  p (t) 1 p (t) il = − is 信息素更新： 节点 d (t) dt p (t t ) p (t) is = js − s + is d (t) dt p (t t ) p (t) i l = jl − l + i l 其中i = 1，j = 2；i = 2，j = 1 6

模拟结果利用上述模型，设定每秒钟通过0.5支蚂蚁，进行了1000次蒙特卡洛模拟。每次模拟统计从第501只到第1000只过桥蚂蚁的分支选择信息。结果如下：100两条分支具有相等长度的实验结果500~2020~4040~6060~8080~100在较短分支上的流量百分比

模拟结果 两条分支具有相等 长度的实验结果 利用上述模型，设定每秒钟通过0.5支蚂蚁，进行 了1000次蒙特卡洛模拟。每次模拟统计从第501 只到第1000只过桥蚂蚁的分支选择信息。结果如 下： 7

模拟结果100.长路径=2倍短路径实验结果500E0~20 20~40 40~60 60~80 80~100在较短分支上的流量百分比(b):

模拟结果 长路径=2倍短路径 实验结果 8 在较短分支上的流量百分比

蚁群算法概述蚁群算法(AntColony Algorithm)food是由意大利学者Dorigo M,ColorniA等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于nest种群的启发式仿生进化算法。图1蚁群寻径模拟99

蚁群算法概述 nest food 蚁群算法(Ant Colony Algorithm) 是由意大利学者 Dorigo M， Colorni A等人于 图1 蚁群寻径模拟 20世纪90年代初期通过模 拟自然界中蚂蚁集体寻径 的行为而提出的一种基于 种群的启发式仿生进化算 法。 99

蚁群算法概述最早提出的蚁群优化算法称为蚂蚁系统（AntSystem，AS）应用于解决经典的旅行商问题（TSP），取得了较好的实验结果该算法的出现，开创了ACO研究的先河.虽然研究时间不长，但是现有的研究结果显示该算法在求解复杂优化问题方面有一定优势，是一种有发展前景的算法，目前已有许多改进的ACO算法应用已扩展到求解大规模集成电路综合布线问题,机器人路径规划，网络路由、图像处理和模式识别等领域。10

蚁群算法概述 ⚫ 最早提出的蚁群优化算法称为蚂蚁系统（Ant System, AS）应用于解决经典的旅行商问题（ TSP），取得了较好的实验结果. ⚫ 该算法的出现，开创了ACO研究的先河.虽然研 究时间不长，但是现有的研究结果显示该算法 在求解复杂优化问题方面有一定优势，是一种 有发展前景的算法。 ⚫ 目前已有许多改进的ACO算法. ⚫ 应用已扩展到求解大规模集成电路综合布线问 题,机器人路径规划，网络路由、图像处理和模 式识别 等领域。 10