《蚁群优化算法》.ppt

蚂蚁的生活习性
蚁群优化的起源
蚁群优化 (ant colony optimization, ACO)，又名蚁群算法。
。
通过模拟自然界中蚂蚁集体寻径的行为而提出的一种蚂蚁的生活习性
蚁群优化的起源
蚁群优化 (ant colony optimization, ACO)，又名蚁群算法。
。
通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法。
蚁群优化的特征
一种典型的群体智能模式。
充分利用蚁群能通过个体间简单的信息传递来进行寻优。
通过正反馈、分布式协作进行路径寻优。
正反馈原理：蚂蚁释放信息素(pheromone)。
蚁群优化的正反馈机制
旅行商问题（TSP）
旅行商问题（traveling salesman problem, TSP）。
一名商人要遍历多个城市，各个城市之间可达且距离已知，如何找到在访问每个城市一次后再回到起点的最短路径。
TSP问题举例
TSP问题的解
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
路径 1
路径2
：信息素强度
：启发程度
蚂蚁 k 由位置 i 移动 j 到的概率
蚁群优化描述
蚁群优化描述
广州
南宁
长沙
福州
:信息素强度
:启发因子
蚁群优化描述
信息素残留系数，(0, 1)
信息素增量
启发程度与距离成反比
概率分配的实现方法
一等奖
二等奖
三等奖
轮盘赌
0 1

概率1
概率2
概率3
概率
积累概率
蚁群优化的流程
带精英策略的蚂蚁系统
当前最优解
精英蚂蚁
带精英策略的蚂蚁系统
带精英策略的蚂蚁系统（Ant System with elitist strategy）是最早的改进蚂蚁系统。
精英策略的思想是保留住一代中的最适应个体。
蚂蚁系统中的精英策略：
每次循环之后给予最优解以额外的信息素量。
这样的解被称为全局最优解（global-best solution）。
找出这个解的蚂蚁被称为精英蚂蚁(elitist ants)。
带精英策略的蚂蚁系统
信息素根据下式进行更新
其中
带精英策略的蚂蚁系统
表示精英蚂蚁引起的路径(i, j)上的信息素量的增加。
是精英蚂蚁的个数。
是所找出的最优解的路径长度。
带精英策略的蚂蚁系统的特征
可以使蚂蚁系统找出更优的解。
找到这些解的时间更短。
精英蚂蚁过多会导致搜索早熟收敛。
比较两组概率
第一组概率：

A B C D E F G H
第二组概率：

A B C D E F G H
较优的解，取不到怎么办？
蚁群系统
蚁群系统(Ant Colony System, ACS)是由Dorigo和Gambardella在1996年提出的。
蚁群系统做了三个方面的改进：
状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法。
全局更新规则只应用于最优的蚂蚁路径上。
在建立问题解决方案的过程中，应用局部信息素更新规则。
蚁群系统状态转移规则
一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s
其中，S根据下列公式得到
蚁群系统状态转移规则
q是在[0,1]区间均匀分布的随机数。
q0的大小决定了利用先验知识与探索新路径之间的相对重要性。
上述状态转移规则被称为伪随机比例规则。
特点是算法倾向于选择短的且有着大量信息素的边作为移动方向。
比较两组概率
第一组概率：

A B C D E