《蚁群优化算法》PPT课件.ppt

蚁群优化算法Ant Colony Optimization,蚁群优化算法,1.1 基本原理,提 出,性 质,1.1 基本原理,（1）蚂蚁没有发育完全的视觉感知系统，其在寻找食物的过程中是如何选择路径的呢？（2）蚂蚁往往像军队般有纪律、有秩序地搬运食物，它们通过什么方式进行群体间的交流协作呢？,信息素是一种化学物质，由蚂蚁自身释放，是实现蚁群内间接通信的物质。蚂蚁随机选择路径，但是能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向前进。,信息素,1.1 基本原理,双桥实验,（a）两个路具有同样的长度,自身催化（正反馈）过程,1.1 基本原理,双桥实验,（b）两条分支具有不同长度,路径探索,1.1 基本理论,（c）30分钟后添加短分支,双桥实验,1.1基本理论,1.1基本理论,蚁群觅食现象和蚁群优化算法的基本定义对照表,1.2 研究进展,历史进展,1.2 研究进展,算法进展,1.2 研究进展,理论进展,蚁群优化算法,2.1 TSP问题,问题简述：,第一个ACO蚂蚁系统，就是以NP难的TSP问题作为应用实例提出的。,2.2 贪婪算法,基本理论,P87页，四个城市间的距离矩阵如下：,用贪婪算法求解：例如从城市A出发得,路径长度为：1+2+4+3=10,2.3 蚂蚁系统理论,AS系统三个版本：,信息素更新方式,2.3 蚂蚁系统理论,AS算法（蚂蚁圈版本）对TSP的求解流程主要有两大步骤：路径构建和信息素更新,1.路径构建,定义5.1 AS中的随机比例规则：对每只蚂蚁k，路径记忆向量 按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在的城市为i，则其选择城市j作为下一个访问对象的概率为：,其中，表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列中的城市集合。是一个启发式信息，通常由 直接计算。表示边 上的信息量,2.3 蚂蚁系统理论,1.路径构建,2.3 蚂蚁系统理论,2.信息素更新,初始化时：,2.3 蚂蚁系统理论,参数设置,2.3 蚂蚁系统理论,参数设置,2.3 蚂蚁系统理论,参数设置,2.3 蚂蚁系统理论,参数设置,2.4 蚂蚁系统算法,2,2.4 蚂蚁系统算法,结束条件,2.4 蚂蚁系统算法,构建方式,顺序构建,所有蚂蚁都从当前城市移动到下一个城市。,两种构建方式，对于蚂蚁系统来说是等价的，因为他们都没有明显地改变算法的行为特征。对于其他ACO算法而言这两种方法就不等价了，例如：ACS算法。,3.1 精华蚂蚁系统,提出背景：,精华蚂蚁系统是对基础AS的第一次改进，它在原AS信息素更新原则上增加了一个对至今最优路径的强化手段。,提出背景：,蚁群优化算法,3.1 精华蚂蚁系统,信息素的更新：,信息素的更新：,信息素的更新：,3.2 基于排列蚂蚁系统,提出背景：,基于排列的蚂蚁系统就是这样的一种改进版本，在每一轮所有蚂蚁构建完路径后，将按照所得路径的长度进行排名，只有生成了至今最优路径的蚂蚁和排名在前（w-1）的蚂蚁才允许释放信息素，蚂蚁在边（i,j）上释放的信息素的权值由蚂蚁的排名决定。,3.2 基于排列蚂蚁系统,信息素的更新：,3.3 最大最小蚂蚁系统,最大最小蚂蚁系统,提出背景：,3.3 最大最小蚂蚁系统,在基本AS算法基础上的改进：,3.3 最大最小蚂蚁系统,信息素更新,3.3 最大最小蚂蚁系统,信息素限制,3.3 最大最小蚂蚁系统,信息素的初始化与重新初始化,3.4 蚁群系统,蚁群系统与AS不同,3.4 蚁群系统,1.状态转移规则,定义5.2 ACS中的伪随机比例规则：对于蚂蚁k，路径记忆向量按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则下一个访问城市,3.4 蚁群系统,1.状态转移规则,3.4 蚁群系统,参数设置,3.4 蚁群系统,2.信息素全局更新规则,3.4 蚁群系统,3.信息素局部更新规则,对每只蚂蚁，每当其经过一条边 时，它立即对这条边进行如下的信息素更新.,3.5 蚁群算法的其他改进版本,蚁群优化算法,4 蚁群优化算法的相关应用,蚁群优化算法的应用,Thank You!,