基本蚁群优化算法及其改进共63页文档

5、蚂蚁的初始分布
为了测试蚂蚁的初始分布对AS算法性能的影响，M.Dorigo分别对随机 分布的16城市的TSP问题，4×4网格问题和Oliver30问题进行了测试。分 两种情况，（i）所有蚂蚁初始时刻放在同一个城市；（ii）蚂蚁分布在不同的 城市中。结果发现第（ii）种情况可获得较高的性能。同时也测试了随机分布 与统一分布的性能差异，结果发现其差别不大。
图2.1ant-cycle求解CCA0问题时信息素分布的进化过程 (a)初始时刻信息素迹的分布； (b)算法迭代100次后信息素迹的分布
2、参数α、β对AS算法性能的影响
定义2.1在蚂蚁搜索解的过程中，所有蚂蚁都选择同样的路径，即系统不再 搜索较好的解，称为停滞现象（Stagnation behavior）。 当参数设置为某些值时，算法迭代到一定代数后将出现停滞现象。其原因是 因为较好路径上的信息素远大于其它边上的，从而使所有蚂蚁都选择相同的路径。 定义3.2设τmin(r,s) 、 τmax(r,s) 分别为与节点r相连的边上最大、最小信息 素值，令δ (r) =τmax (r,s )－τmin (r,s) ，对某个给定的λ(0<λ<1)，则在所有与 节点r相连的边中，信息素量大于等于λδ(r) ＋τmin (r,s) 的边的数量称为节点r的 节点分支数（node branching）。其中λ可根据实际需要确定。 定义3.3设θ(r)为节点r(r=1,2,…,n) 的节点分支数，n为节点数，则平均节 点分支数（Average Node Branching,简称ANB）为 。
图2.2是ant-cycle求解Oliver30问题时ANB的进化情况。在某些参数 设置下，当算法迭代2500次后，ANB到达2。就对称TSP问题而言，这意味 着所有的蚂蚁都选择同样的路径，即算法出现停滞现象。

05
蚁群优化算法的改进与优 化
信息素更新策略的改进
动态更新策略
根据解的质量实时调整信息素浓度，以提高算法的搜 索效率。
自适应更新策略
根据蚂蚁移动过程中信息素挥发的情况，动态调整信 息素更新规则，以保持信息素浓度的平衡。
局部与全局更新结合
在蚂蚁移动过程中，既进行局部更新又进行全局更新 ，以增强算法的全局搜索能力。
该算法利用了蚂蚁之间信息素传递的 机制，通过不断迭代更新，最终找到 最优路径或解决方案。
蚁群优化算法的起源与发展
蚁群优化算法最初起源于对自然界中蚂蚁觅食行为的研究， 发现蚂蚁能够通过信息素传递找到从巢穴到食物源的最短路 径。
随着研究的深入，蚁群优化算法逐渐发展成为一种通用的优 化算法，广泛应用于各种组合优化问题，如旅行商问题、车 辆路径问题等。
任务调度问题
总结词
蚁群优化算法在任务调度问题中能够实现高效的任务调度，提高系统整体性能。
详细描述
任务调度问题是指在一个多任务环境中，根据任务的优先级、资源需求等因素，合理分配任务到不同 的处理单元，以实现系统整体性能的最优。蚁群优化算法通过模拟蚂蚁的行为，利用信息素传递机制 ，能够实现高效的任务调度，提高系统整体性能。
利用已知领域知识
将领域专家的经验或启发式信息融入算法中，以提高算法的搜索 效率和准确性。
利用问题特性
根据问题的特性，引入与问题相关的启发式信息，以引导蚂蚁的移 动方向和选择行为。
自适应调整启发式信息
根据算法的搜索过程和结果，动态调整启发式信息的权重或规则， 以平衡算法的全局搜索和局部搜索能力。
06
蚂蚁行为规则的改进
引入变异行为
01
在蚂蚁移动过程中，随机选择某些蚂蚁进行变异操作，以增强

➢蚂蚁系统中的精英策略
– 每次循环之后给予最优解以额外的信息素量 – 这样的解被称为全局最优解（global-best solution） – 找出这个解的蚂蚁被称为精英蚂蚁(elitist ants)
16 16
带精英策略的蚂蚁系统
➢信息素根据下式进行更新
其中
ij (t 1) ij (t) ij i*j
实现过程
33 33
实现过程
34 34
实现过程
35 35
中国旅行商问题
ACATSP(C,100,10,1,5,0.1,100) 1.5602e+04
36 36
遗传算法和蚁群算法在 求解TSP问题上的对比分析
37 37
开始
细菌觅食机理
i=i+1
趋向性操作
设细菌种群大小为S，一个细菌所处的位 置表示一个问题的候选解，细菌i的信息 用D维向量表示为
➢较强的鲁棒性 ·➢分布式计算
➢易于与其他方法结合
需要较长的搜索时间 容易出现停滞现
15 15
带精英策略的蚂蚁系统
➢带精英策略的蚂蚁系统（Ant System with elitist strategy,
ASelite）是最早的改进蚂蚁系统。
➢遗传算法中的精英策略
– 传统的遗传算法可能会导致最适应个体的遗传信息丢失 – 精英策略的思想是保留住一代中的最适应个体
ij (t n) ij (t) ij
m
ij
k ij
(2)
k 1
其中，ρ为小于1的常数，表示信息的持久性。
Q
k ij
Lk
ij lk
(3)
0 otherwise
其中，Q为常数；Lk 表示第k只蚂蚁在本次迭代中走过 的路径长度。

Pijk(i,
j)
(i,u)(i,u)
uJki
,
jJk i
0,
其他
其中，J i 表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列
R
k
k
中的城市集合。
i,
j 是一个启发式信息，通常由i, j=1/d 直接计算。 ij
i , j 表示边 i , j 上的信息量
-
2.3 蚂蚁系统理论
四
蚁群优化算法相关应用
-
问题简述：
2.1 TSP问题
已知有 n
个城市的集合
Cc,c,L,c
n
12
n
，任意两个城市之间均有路
径连接，dij i,j1,2,L,n表示城市与之间的距离。旅行商问题就是需要 寻找这样的一中周游方案：周游路线从某个城市出发，经过每个城市
一次且仅一次，最终回到出发城市，使得周游的路线总长度最短。
-
1.1 基本原理
双桥实验
蚁穴
食物源
（a）两个路具有同样的长度
1.起初两条分支上不存在信息 素，蚂蚁以相同的概率进行 选择。
2.随机波动的出现，选择某一 条分支的蚂蚁数量可能比另 外一条多。
3.实验最终结果：所有的蚂蚁 都会选择同一分支。
自身催化（正反馈）过程
-
双桥实验
1.1 基本原理
1.起初两条分支上不存在信息 素，蚂蚁随机选择一条路径。
2.将ACO纳入了基于模型的搜索框架中。
趋势
1.利用ACO算法去解决更为复杂的优化问题，例如：
动态问题、随机问题、多目标问题。 2、ACO算法的高效并行执行。 3.更理论化的理解和刻画ACO算法在求解问题时的行为。 4.与其他算法结合（粒子群算法）。

蚁群算法的基本原理与改进
A
1
蚁群算法
蚁群算法(ant colony alogrithm)是一种模拟进化算法。 蚁群算法（又称为人工蚁群算法）是由意大利学者M.Dorigo，
V.Mahiezzo，A.Colorni等人受到人们对自然界中真是蚁群集体 行为的研究成果的启发而首先提出来的。这个算法的主要目的是在 图中寻找优化路径的机率算法。 蚁群算法最早是为了解决TSP问题（即旅行商问题）。 TSP问题的要求：路径的限制是每个城市只能拜访一次；最后 要回到原来出发的城市。求得的路径路程为所有路径之中的最小 值。
并不要求所有的蚂蚁都找到最优模板，而只需要一只找到最优模板即可。如果 要求所有的蚂蚁都找到最优模板，反而影响了计算效率。 蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。 蚁群算法一般需要较长的搜索时间，其复杂度可以反映这一点；而且该方法容 易出现停滞现象，即搜索进行到一定程度后，所有个体发现的解完全一致，不 能对解空间进一步进行搜索，不利于发现更好的解。
（4）它是一种全局优化的方法；不仅可用于求解单目标优化问题，而 且可用于求解多目标优化问题；
（5）它是一种启发式算法；计算复杂性为 O(NC*m*n2)，其中NC 是 迭代次数，m 是蚂蚁数目，n 是目的节点数目。
A
13
下面是对蚁群算法的进行过程中采用的规则进行的一些说明。
范围
蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半 径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且 能移动的距离也在这个范围之内。
最后，经过一段时间运行，就可能会出现一条最短的路径被大 多数蚂蚁重复着。
A
3
基本原理
蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算 法。

(1)只允许迭代最优蚂蚁（在本次迭代构建出最短路径的 蚂蚁），或者至今最优蚂蚁释放信息素。
(2)信息素量大小的取值范围被限制在一个区间内。 (3)信息素初始值为信息素取值区间的上限，并伴随一个
较小的信息素蒸发速率。 (4)每当系统进入停滞状态，问题空间内所有边上的信息
素量都会被重新初始化。
3.3 最大最小蚂蚁系统
（3）蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信 息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂 蚁爬过的次数越多、它所获得的信息素也越多。
（4）迭代（2），直至算法终止。
2 算法流程
信息素更新
m
(i, j) (1 r) (i, j) k (i, j),
食物
6：我自己走，说不定能探索 出一条更短的路径呢，
到时候你们就都会跟着我了
蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度， 并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物 质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素 的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并 倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的 最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径 上行进。
长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。和是
两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权
重关系。当=0时，算法演变成传统的随机贪心算法，最邻近城市被 选中的概率最大。当=0时，蚂蚁完全只根据信息素浓度确定路径，
算法将快速收敛，这样构建出的最优路径往往与实际目标有着较大 的差异，算法的性能比较糟糕。

1 给定一个外循环的最大数目，表明已经有足够的蚂蚁工作；
2 当前最优解连续K次相同而停止，其中K是一个给定的整数， 表示算法已经收敛，不再需要继续；
3 目标值控制规则，给定优化问题（目标最小化）的一个下界 和一个误差值，当算法得到的目标值同下界之差小于给定的误 差值时，算法终止。
2021/10/10
E可以随机选择路径 HD = HB = 1 CD = CB = 0.5 备注： D->H D->C B->H B->C 图中数字表示蚂蚁的个数
2021/10/10
7
下面以TSP为例说明基本蚁群算法模型。
首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下 一个城市j的概率为:
3.蚁群系统
蚁群系统已被提出。
2021/10/10
20
4.基于排序的蚂蚁系统（ ASrank ） 所有解决方案都根据其长度排名。然后为每个解决方案衡量信
息素的沉积量，最短路径相比较长路径的解沉积了更多的信息素。 5.连续正交蚁群（COAC）
COAC的信息素沉积机制能使蚂蚁协作而有效地寻解。 利用正 交设计方法，在可行域的蚂蚁可以使用增大的全局搜索能力和精度， 快速、高效地探索他们选择的区域。 正交设计方法和自适应半径 调整方法也可推广到其他优化算法中，在解决实际问题施展更大的 威力。
4
假设以下条件： 每个时间单位有30只蚂蚁（A->B） 每个时间单位有30只蚂蚁（E->D） 蚂蚁过后留下的外激素为1 初始时刻，路径无信息存在且位
于B和E可以随机选择路径 HD = HB = 1 CD = CB = 0.5 图中的数字表示距离
2021/10/10
5
假设以下条件： 每个时间单位有30只蚂蚁（A->B） 每个时间单位有30只蚂蚁（E->D） 蚂蚁过后留下的外激素为1 初始时刻，路径无信息存在且位于B和

蚁群优化算法技术介绍
目录
• 蚁群优化算法概述 • 蚁群优化算法的基本原理 • 蚁群优化算法的实现过程 • 蚁群优化算法的改进与优化 • 蚁群优化算法的案例分析
01 蚁群优化算法概述
定义与原理
定义
蚁群优化算法是一种模拟自然界 中蚂蚁觅食行为的仿生优化算法 。
原理
通过模拟蚂蚁的信息素传递过程 ，利用正反馈机制寻找最优解。
算法特点
分布式计算
蚁群算法中的蚂蚁可以并行地搜索解空间，提高了算法的搜索效 率。
鲁棒性
对初始解和参数选择不敏感，能在多变的搜索空间中寻找到最优 解。
易于实现
算法实现简单，可扩展性强，适用于解决复杂优化问题。
应用领域
路径规划
任务调度
用于解决车辆路径规划、 物流配送等问题。
应用于多核处理器任务 调度、云计算资源分配
蚂蚁的移动规则
随机选择
蚂蚁在移动时，会根据当前位置和目标位置之间的路径上信息素浓度随机选择 下一个移动的节点。
避免重复
为了避免重复访问同一个节点，蚂蚁会根据一定的概率选择新的节点，这个概 率与路径上的信息素浓度成正比。
蚂蚁之间的协作机制
共享信息
蚂蚁通过释放和感知信息素来共享彼此的路径信息和状态，从而在群体中形成一 种协作效应。
网络路由问题求解
总结词
蚁群优化算法在网络路由问题求解中具有较好的应用 效果，能够优化网络路由和提高网络性能。
详细描述
网络路由问题是一个重要的网络通信问题，旨在根据 网络拓扑结构和通信需求，选择最优的路由路径和转 发策略，以实现数据包的可靠传输和网络性能的提升 。蚁群优化算法通过模拟蚂蚁的行为，利用信息素传 递机制来指导搜索过程，能够有效地解决网络路由问 题，优化网络路由和提高网络性能。

改进算法。
在基于聚类分析的蚁群优化算法中，算 法首先利用聚类分析技术将问题空间划 分为多个子空间，然后将蚂蚁分配到不
同的子空间中进行搜索。
这种算法通过聚类分析技术将问题空间 划分为多个子空间，可以减少蚂蚁搜索
范围，提高算法的寻优效率。
基于粒子群的蚁群优化算法
基于粒子群的蚁群优化算法是 一种将粒子群优化算法与蚁群 优化算法相结合的改进算法。
THANKS
感谢观看
蚁群优化算法课件
目录
• 蚁群优化算法简介 • 蚁群优化算法的基本原理 • 蚁群优化算法的实现细节 • 蚁群优化算法的改进版本 • 蚁群优化算法的实验与分析 • 么是蚁群优化算法
蚁群优化算法是一种启发式优化算法，通过模拟 01 自然界中蚂蚁寻找食物的行为来求解优化问题。
在基于粒子群的蚁群优化算法 中，每只蚂蚁被视为一个粒子 ，每个粒子都有一个位置和一 个速度。
该算法通过粒子的位置和速度 来描述蚂蚁的状态，并利用粒 子群优化算法的优点来指导蚂 蚁的搜索行为。
05
蚁群优化算法的实验与分析
在TSP问题上的应用
总结词
高效、稳定
详细描述
蚁群优化算法在TSP问题上具有高效、稳定的性能表现。通过模拟蚂蚁觅食行为 ，该算法能够在较短的时间内寻找到一条最短路径，并且具有较好的鲁棒性。
果的质量。
02
蚁群优化算法的基本原理
蚂蚁的行为特征
01 蚂蚁具有记忆能力
蚂蚁能够记住之前走过的路径和相关的信息，如 食物的来源、路径的长度等。
02 蚂蚁具有协作能力
在寻找食物的过程中，蚂蚁之间会相互协作，通 过信息素的传递来共享信息。
03 蚂蚁具有适应性
蚂蚁能够根据环境的变化来调整自己的行为和策 略，以适应不同的环境条件。

2.1.3
蚁群优化算法研究背景
13
1/3
群智能理论研究领域有两种主要的算法：蚁 群算法(Ant Colony Optimization, ACO) 和微粒群算法（Particle Swarm Optimization, PSO）。 前者是对蚂蚁群落食物采集过程的模拟，已成功 应用于许多离散优化问题。 微粒群算法也是起源于对简单社会系统的模拟， 最初是模拟鸟群觅食的过程，但后来发现它是 一种很好的优化工具。
5
LC=2LB
蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路 线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个 时间单位行走一步，本图为经过9个时间单位时的情形：走 ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一 半路程。
6
LC=2LB
本图为从开始算起，经过18个时间单位时的情形：走 ABD的蚂蚁到达终点后得到食物又返回了起点A，而走 ACD的蚂蚁刚好走到D点。
10
1.1.1 蚁群优化算法起源
11
20世纪50年代中期创立了仿生学，人们从生物进化的机理中 受到启发。提出了许多用以解决复杂优化问题的新方法，如进 化规划、进化策略、遗传算法等，这些算法成功地解决了一些 实际问题。 20世纪90年代意大利学者M．Dorigo，V．Maniezzo， A．Colorni等从生物进化的机制中受到启发，通过模拟自然界 蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法—— 蚁 群算法，是群智能理论研究领域的一种主要算法。 用该方法求解TSP问题、分配问题、job-shop调度问题，取得了 较好的试验结果．虽然研究时间不长，但是现在的研究显示出， 蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有 一定优势，表明它是一种有发展前景的算法．