蚁群优化算法.ppt

1、蚁群优化算法 Ant Colony Optimization,2,蚁群优化算法,3,1.1 基本原理,提 出,性 质,4,1.1 基本原理,（1）蚂蚁没有发育完全的视觉感知系统，其在寻找食物的过程中是如何选择路径的呢？ （2）蚂蚁往往像军队般有纪律、有秩序地搬运食物，它们通过什么方式进行群体间的交流协作呢？,信息素是一种化学物质，由蚂蚁自身释放，是实现蚁群内 间接通信的物质。蚂蚁随机选择路径，但是能感知当前地 面上的信息素浓度，并倾向于往信息素浓度高的方向前进。,信息素,5,1.1 基本原理,双桥实验,（a）两个路具有同样的长度,自身催化（正反馈）过程,6,1.1 基本原理,双桥实验,（b）两

2、条分支具有不同长度,路径探索,7,1.1 基本理论,（c）30分钟后添加短分支,双桥实验,8,1.1基本理论,9,1.1基本理论,蚁群觅食现象和蚁群优化算法的基本定义对照表,10,1.2 研究进展,历史进展,11,1.2 研究进展,算法进展,12,1.2 研究进展,理论进展,13,蚁群优化算法,14,2.1 TSP问题,问题简述：,第一个ACO蚂蚁系统，就是以NP难的TSP问题 作为应用实例提出的。,15,2.2 贪婪算法,基本理论,P87页，四个城市间的距离矩阵如下：,用贪婪算法求解： 例如从城市A出发得,路径长度为：1+2+4+3=10,16,2.3 蚂蚁系统理论,AS系统三个版本：,信息

3、素更新方式,17,2.3 蚂蚁系统理论,AS算法（蚂蚁圈版本）对TSP的求解流程主要有两大步骤：路径构建和信息素更新,1.路径构建,定义5.1 AS中的随机比例规则：对每只蚂蚁k，路径记忆向量 按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在的城市为i，则其选择城市j作为下一个访问对象的概率为：,其中， 表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列 中的城市集合。 是一个启发式信息，通常由 直接计算。 表示边 上的信息量,18,2.3 蚂蚁系统理论,1.路径构建,19,2.3 蚂蚁系统理论,2.信息素更新,初始化时：,20,2.3 蚂蚁系统理论,参数设置,21,2.3 蚂

4、蚁系统理论,参数设置,22,2.3 蚂蚁系统理论,参数设置,23,2.3 蚂蚁系统理论,参数设置,24,2.4 蚂蚁系统算法,2,25,2.4 蚂蚁系统算法,结束条件,26,2.4 蚂蚁系统算法,构建方式,顺序构建,所有蚂蚁都从当前城市移动到 下一个城市。,两种构建方式，对于蚂蚁系统来说是等价的，因为他们都 没有明显地改变算法的行为特征。对于其他ACO算法而言 这两种方法就不等价了，例如：ACS算法。,27,3.1 精华蚂蚁系统,提出背景：,精华蚂蚁系统是对基础AS的第一次改进，它在原AS信息 素更新原则上增加了一个对至今最优路径的强化手段。,提出背景：,28,蚁群优化算法,29,3.1 精华

5、蚂蚁系统,信息素的更新：,信息素的更新：,信息素的更新：,30,3.2 基于排列蚂蚁系统,提出背景：,基于排列的蚂蚁系统就是这样的一种改进版本，在每一轮所有蚂蚁 构建完路径后，将按照所得路径的长度进行排名，只有生成了至今 最优路径的蚂蚁和排名在前（w-1）的蚂蚁才允许释放信息素，蚂 蚁在边（i,j）上释放的信息素的权值由蚂蚁的排名决定。,31,3.2 基于排列蚂蚁系统,信息素的更新：,32,3.3 最大最小蚂蚁系统,最大最小蚂蚁系统,提出背景：,33,3.3 最大最小蚂蚁系统,在基本AS算法基础上的改进：,34,3.3 最大最小蚂蚁系统,信息素更新,35,3.3 最大最小蚂蚁系统,信息素限制,36,3.3 最大最小蚂蚁系统,信息素的初始化与重新初始化,37,3.4 蚁群系统,蚁群系统与AS不同,38,3.4 蚁群系统,1.状态转移规则,定义5.2 ACS中的伪随机比例规则：对于蚂蚁k，路径记忆向量 按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市 为i，则下一个访问城市,39,3.4 蚁群系统,1.状态转移规则,40,3.4 蚁群系统,参数设置,41,3.4 蚁群系统,2.信息素全局更新规则,42,3.4 蚁群系统,3.信息素局部更新规则,对每只蚂蚁，每当其经过一条边 时，