蚁群优化算法

蚁群优化算法Ant Colony Optimization蚁群优化算法蚁群优化算法 蚁群优化算法简介蚁群优化算法简介 一 蚂蚁系统蚂蚁系统二 蚁群优化算法的改进版本蚁群优化算法的改进版本三 蚁群优化算法相关应用蚁群优化算法相关应用四ACOACO是一种全局最优化搜索方法，解决典型组是一种全局最优化搜索方法，解决典型组合优化问题具有明显的优越性，具有鲁棒性合优化问题具有明显的优越性，具有鲁棒性强、全局搜索、并行分布式计算、易于其他强、全局搜索、并行分布式计算、易于其他算法结合的优点。算法结合的优点。蚁群优化算法（蚁群优化算法（ACOACO）由）由DorigoDorigo（多里格）（多里格）等人于等人于19911991年提出，是模拟自然界真实蚂蚁年提出，是模拟自然界真实蚂蚁觅食过程的一种随机搜素算法。觅食过程的一种随机搜素算法。1.1 1.1 基本原理基本原理提提 出出性性 质质1.1 1.1 基本原理基本原理 A （1）蚂蚁没有发育完全的视觉）蚂蚁没有发育完全的视觉感知系统，其在寻找食物的过感知系统，其在寻找食物的过程中是如何选择路径的呢？程中是如何选择路径的呢？（2）蚂蚁往往像军队般有纪律、）蚂蚁往往像军队般有纪律、有秩序地搬运食物，它们通过有秩序地搬运食物，它们通过什么方式进行群体间的交流协什么方式进行群体间的交流协作呢？作呢？信息素是一种化学物质，由蚂蚁自身释放，是实现蚁群内信息素是一种化学物质，由蚂蚁自身释放，是实现蚁群内间接通信的物质。蚂蚁随机选择路径，但是能感知当前地间接通信的物质。蚂蚁随机选择路径，但是能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向前进面上的信息素浓度，并倾向于往信息素浓度高的方向前进。信息素1.1 1.1 基本原理基本原理双桥实验双桥实验蚁穴蚁穴食物源（a）两个路具有同样的长度自身催化（正反馈）过程自身催化（正反馈）过程自身催化（正反馈）过程自身催化（正反馈）过程1.1.起初两条分支上不存在信息起初两条分支上不存在信息 素，蚂蚁以相同的概率进行素，蚂蚁以相同的概率进行 选择。选择。2.2.随机波动的出现，选择某一随机波动的出现，选择某一 条分支的蚂蚁数量可能比另条分支的蚂蚁数量可能比另 外一条多。外一条多。3.3.实验最终结果：所有的蚂蚁实验最终结果：所有的蚂蚁 都会选择同一分支。都会选择同一分支。1.1 1.1 基本原理基本原理双桥实验双桥实验（b）两条分支具有不同长度1.1.起初两条分支上不存在信息起初两条分支上不存在信息 素，蚂蚁随机选择一条路径。素，蚂蚁随机选择一条路径。2.2.短分支上的信息素积累速度短分支上的信息素积累速度 比长分支的快。比长分支的快。3.3.实验最终结果：所有的蚂蚁实验最终结果：所有的蚂蚁 都会选择较短的分支。都会选择较短的分支。4.4.有很小比例的蚂蚁会选择较有很小比例的蚂蚁会选择较 长的分支。长的分支。路径探索路径探索1.1 基本理基本理论蚁穴蚁穴食物源食物源（c）30分钟后添加短分支30分钟后双桥实验双桥实验1.1.实验最终结果：除了极少的实验最终结果：除了极少的 蚂蚁选择较短的分支以外，蚂蚁选择较短的分支以外，整个群体几乎都困在较长的整个群体几乎都困在较长的 分支上。分支上。2.2.长分支上的信息素浓度高，长分支上的信息素浓度高，而信息素的蒸发速度过于缓而信息素的蒸发速度过于缓 慢。慢。1.1基本理论基本理论双桥实验总结1 1选择路径是一个概率随机过程，启发式信选择路径是一个概率随机过程，启发式信息多以及信息浓度大的路径被选中概率更息多以及信息浓度大的路径被选中概率更大。大。2 2信息素会不断的蒸发。信息素会不断的蒸发。3 3路径探索也是必需的，否则容易陷入路径探索也是必需的，否则容易陷入局部最优。局部最优。1.1基本理论基本理论蚁群觅食现象蚁群觅食现象蚁群优化算法蚁群优化算法蚁群搜索空间的一组有效解（种群规模m）觅食空间问题的搜索空间（问题的规模、解的维数n）信息素信息素浓度变量蚁巢到食物的一条路径一个有效解找到的最短路问题的最优解蚁群觅食现象和蚁群优化算法的基本定义对照表蚁群觅食现象和蚁群优化算法的基本定义对照表2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改进算法的提出，应用领域更广各种改进算法的提出，应用领域更广 引起学者关注，在应用领域得到拓宽ACO首次被系统的提出首次被系统的提出自然界中真实蚁群集体行为1.2 1.2 研究进展研究进展历史进展历史进展1.2 1.2 研究进展研究进展算法进展算法进展蚂蚁系统(AS)1991年基于排列蚂蚁系统 1997年蚁群系统(ACS)1997年连续蚁群(CACO)2000年超立方体AS(HC-ACO)2001年连续正交蚁群(COAC)2008年精华蚂蚁系统(EAS)1991年最大最小蚂蚁系统(EAS)1996年1.2 1.2 研究进展研究进展理论进展理论进展总结总结1.收敛性证明。一些性能优越的ACO算法（MMAS和ACS）不管有没有使用局部搜素，都是值收敛的。2.将ACO纳入了基于模型的搜索框架中。趋势1.利用ACO算法去解决更为复杂的优化问题，例如：动态问题、随机问题、多目标问题。2、ACO算法的高效并行执行。3.更理论化的理解和刻画ACO算法在求解问题时的行为。4.与其他算法结合（粒子群算法）。蚁群优化算法蚁群优化算法 蚁群优化算法简介蚁群优化算法简介 一 蚂蚁系统蚂蚁系统二 蚁群优化算法的改进版本蚁群优化算法的改进版本三 蚁群优化算法相关应用蚁群优化算法相关应用四2.1 TSP问题问题简述：问题简述：已知有已知有 个城市的集合个城市的集合 ，任意两个城市之间均有路任意两个城市之间均有路径连接，径连接，表示城市与之间的距离。旅行商问题就是需要表示城市与之间的距离。旅行商问题就是需要寻找这样的一中周游方案：周游路线从某个城市出发，经过每个城市寻找这样的一中周游方案：周游路线从某个城市出发，经过每个城市一次且仅一次，最终回到出发城市，使得周游的路线总长度最短。一次且仅一次，最终回到出发城市，使得周游的路线总长度最短。第一个第一个ACOACO蚂蚁系统，就是以蚂蚁系统，就是以NPNP难的难的TSPTSP问题问题作为应用实例提出的。作为应用实例提出的。2.2 贪婪算法贪婪算法 贪婪算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。基本理论基本理论P87页，四个城市间的距离矩阵如下：用贪婪算法求解：例如从城市A出发得A C D B A 路径长度为：1+2+4+3=102.3 蚂蚁系系统理理论AS系统三个版本：1.蚂蚁圈2.蚂蚁数量3.蚂蚁密度 其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经过路径的长度。d为城市间的距离。信息素更新方式2.3 蚂蚁系系统理理论AS算法（蚂蚁圈版本）对TSP的求解流程主要有两大步骤：路径构建和信息素更新1.路径构建路径构建 定义定义5.1 AS中的随机比例规则：对每只蚂蚁k，路径记忆向量 按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在的城市为i，则其选择城市j作为下一个访问对象的概率为：其中，表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列中的城市集合。是一个启发式信息，通常由 直接计算。表示边 上的信息量2.3 蚂蚁系系统理理论1.路径构建路径构建 由公式知，长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。和 是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重。时算法演变成了传统的随机贪婪算法；当 蚂蚁完全只根据信息素浓度确定路径，算法快速收敛，构建出的最优路径与实际目标有较大的差异。实验表明：设置 ，比较合适。2.3 蚂蚁系系统理理论2.信息素更新信息素更新初始化时：m是蚂蚁的个数，是由贪婪算法构造的路径的长度。是信息素的蒸发率，规定 通常设置为 是第k只蚂蚁在它经过的边上释放的信息素量；表示路径的长度，它是 中所有边的长度和。2.3 蚂蚁系系统理理论参数设置参数设置参数参数参数的意义参数的意义蚂蚁数目m影响着算法的搜素能力和计算量信息素挥发因子影响蚂蚁个体之间相互影响的强弱，关系到算法的全局搜索能力和收敛速度初始信息素量决定算法在初始化阶段的探索能力，影响算法的收敛速度2.3 蚂蚁系系统理理论参数设置参数设置1 1蚂蚁数目过多，迭代的计算量大且被搜索过的路径上信息素变化比较平均，此时全局搜索能力增强，但收敛速度减慢2 2蚂蚁数目过少时，算法的探索能力变差，容易出现早熟现象。特别是当问题的规模很大时，算法的全局寻优能力会十分糟糕3 3在用蚂蚁系统、精华蚂蚁系统、基于排列的蚂蚁系统和最大最小蚂蚁系统求解TSP时，m取值等于城市数目时有较好性能。蚂蚁数目2.3 蚂蚁系系统理理论参数设置参数设置1 1信息素挥发因子较大，信息素挥发速率大，从未被蚂蚁选择过的边上信息素急剧减少到接近0，降低算法的全局探索能力。2 2信息素挥发因子较小，算法具有较高的全局搜索能力，但是由于每个路径的信息素浓度差距拉大较慢，算法收敛速度较慢。信信息息素素挥发因因子子3 3对于AS和EAS，；基于排列的蚂蚁系统，；MMAS,;ACS,算法的综合性能提高。2.3 蚂蚁系系统理理论参数设置参数设置1 1初始信息素量太小，未被蚂蚁选择过的边上信息素太少，蚂蚁很快就全部集中在一条局部最优的路径上，算法易早熟。2 2初始信息素太大，信息素对搜索方向的引导能力增长十分缓慢，算法收敛慢。初初始始信信息息素素量量3 3对于AS ；EAS，；，；MMAS,;ACS,2.4 蚂蚁系系统算法算法初始化每条边上的信息素量1对每只蚂蚁，随机选择一个出发城市2对每只蚂蚁根据启发式信息和信息素浓度选择下一个访问城市3计算每只蚂蚁构建的路径长度，更新每条边上的信息素量4判断是否满足结束条件52.4 蚂蚁系统算法蚂蚁系统算法结束条件束条件1将最大循环数设定为500、1000、5000，或者最大的函数评估次数，等等。也可以使用算法求解到一个可接受的解作为终止条件。23当算法在很长一段迭代中没有得到任何改善时。2.4 蚂蚁系统算法蚂蚁系统算法构建方式构建方式并行构建并行构建顺序构建顺序构建所有蚂蚁都从当前城市移动到下一个城市。所有蚂蚁都从当前城市移动到下一个城市。当一只蚂蚁完成一轮完整的构建并返回到初始城市之后，下一只蚂蚁才开始构建两种构建方式，对于蚂蚁系统来说是等价的，因为他们都两种构建方式，对于蚂蚁系统来说是等价的，因为他们都没有明显地改变算法的行为特征。对于其他没有明显地改变算法的行为特征。对于其他ACO算法而言算法而言这两种方法就不等价了，例如：这两种方法就不等价了，例如：ACS算法。算法。3.1 精华蚂蚁系统精华蚂蚁系统提出背景：提出背景：当城市的规模较大时，问题的复杂度呈指数级增长，仅靠AS系统中这样一个基础单一的信息素更新机制引导搜索偏向，搜索效率有瓶颈。能否用一张“额外手段”强化某些最可能成为最有路径的边，让蚂蚁搜索的范围更快、更正确地收敛呢？精华蚂蚁系统是对基础AS的第一次改进，它在原AS信息素更新原则上增加了一个对至今最优路径的强化手段。提出背景：提出背景：当城市的规模较大时，问题的复杂度呈指数级增长，仅靠AS系统中这样一个基础单一的信息素更新机制引导搜索偏向，搜索效率有瓶颈。能否用一张“额外手段”强化某些最可能成为最有路径的边，让蚂蚁搜索的范围更快、更正确地收敛呢？蚁群优化算法蚁群优化算法 蚁群优化算法简介蚁群优化算法简介 一 蚂蚁系统蚂蚁系统二 蚁群优化算法的改进版本蚁群优化算法的改进版本三 蚁群优化算法相关应用蚁群优化算法相关应用四3.1 精华蚂蚁系统精华蚂蚁系统信息素的更新：信息素的更新：信息素的更新：信息素的更新：参数e作为 的权值，是算法开始至今最优路径的长度，其中搜索到至今最优路径用 表示。信息素的更新：信息素的更新：3.2 基于排列蚂蚁系统基于排列蚂蚁系统提出背景：提出背景：在EAS提出后，有没有更好的一种信息素更新方式，它同样使 各边的信息浓度得到加强，且对其余各边的信息素更新机制亦有改善？基于排列的蚂蚁系统就是这样的一种改进版本，在每一轮所有蚂蚁构建完路径后，将按照所得路径的长度进行排名，只有生成了至今最优路径的蚂蚁和排名在前（w-1）的蚂蚁才允许释放信息素，蚂蚁在边（i,j）上释放的信息素的权值由蚂蚁的排名决定。在EAS提出后，有没有更好的一种信息素更新方式，它同样使 各边的信息浓度得到加强，且对其余各边的信息素更新机制亦有改善？3.2 基于排列蚂蚁系统基于排列蚂蚁系统信息素的更新：信息素的更新：至今最优路径不一定出现在当前迭代的路径中，各种蚁群算法均假设蚂蚁有记忆能力，至今最优路径总是能被记住。路径 将获得最多的信息素量，排名越前的蚂蚁释放的信息素量越大，权值对不同路径的信息素浓度差异起了一个放大作用。一般3.3 最大最小蚂蚁系统最大最小蚂蚁系统最大最小最大最小蚂蚁系系统提出背景：提出背景：1.对于大规模的TSP，由于搜索蚂蚁的个数有限，而初始化时蚂蚁的 分布是随机的，这会不会造成蚂蚁只搜索了所有路径中的小部分就 以为找到了最好的路径，而真正优秀的路径并没有被探索到呢？2.当所有蚂蚁都重复构建着同一条路径的时候，意味着算法已经进入 了停滞状态，有没有办法利用算法停滞后的迭代过程进一步搜索以 保证找到更接近真实目标的解呢？3.3 最大最小蚂蚁系统最大最小蚂蚁系统在基本在基本AS算法基础上的改进：算法基础上的改进：1 1只允许迭代最优蚂蚁或者至今最优蚂蚁释放信息素。2 2信息素量大小的取值范围被限制在一个区间内。3 3信息素初始值为信息素取值区间的上限，并伴随一个较小的信息素蒸发速率4 4每当系统进入停滞状态，问题空间内所有边上的信息素量都会被重新初始化。3.3 最大最小蚂蚁系统最大最小蚂蚁系统信息素更新信息素更新若只使用迭代最优更新规则，则算法的探索能力会增强，但收敛速度会下降；只使用至今最优更新规则进行信息素的更新，搜索导向性很强。一种好的方式，在算法迭代过程中，逐渐加大至今最优更新的概率。当被允许的蚂蚁是至今最优蚂蚁时，这时有 ；当其为当前迭代最优的蚂蚁，这时有 ，其中 是当前迭代的最优路径长度。一般而言，在MMAS中，迭代最优更新规则和至今最优更新规则会被轮流使用。3.3 最大最小蚂蚁系统最大最小蚂蚁系统信息素限制信息素限制1 1在MMAS中任何一条边可能存放的信息素大小都被限制在由一个取值范围 内。2 2在算法执行了足够多的迭代次数后，任何一条边上含有的信息素量的上界是 ,其中 代表最优路径的长度。故，MMAS使用对 的估计值 来定义 每当发现一条新的至今最优路径，就更新 的值。相应地，信息素量的下界被设定为 ，其中a是一个参数。3.3 最大最小蚂蚁系统最大最小蚂蚁系统信息素的初始化与重新初始化信息素的初始化与重新初始化1 1算法开始时，所有边上的信息素初始值都被设定为信息素上界的一个估计值，并选一个较小的信息素蒸发参数，使得不同边上的信息素之间的差异只能够缓慢的增加，故初始阶段，具有很强的探索性。2 2当算法接近或者进入停滞状态时，问题空间内所有边上的信息素浓度对将被重新初始化，使算法具有更强的全局寻优能力。3.4 蚁群系统蚁群系统蚁群系统使用了一种伪随机比例规则选择下一城市节点，建立开发当前路径与探索新路径之间的平衡。信息素全局更新规则只在属于至今最优路径的边上蒸发和释放信息素。新增信息素局部更新规则，蚂蚁每次经过空间内的某条边，它都会去除该边上一定量的信息素，以增加后续蚂蚁探索其余路径的可能性。蚁群系统与蚁群系统与AS不同不同3.4 蚁群系统蚁群系统1.状状态转移移规则 定义定义5.2 5.2 ACSACS中的伪随机比例规则：对于蚂蚁中的伪随机比例规则：对于蚂蚁k k，路径记忆向量，路径记忆向量按照访问顺序记录了所有按照访问顺序记录了所有k k已经经过的城市序号。设蚂蚁已经经过的城市序号。设蚂蚁k k当前所在城市当前所在城市为为i i，则下一个访问城市，则下一个访问城市其中，表示从城市可以直接到达的且又不在蚂蚁访问过的城市序列 中的城市集合。是启发式信息，表示边 上的信息素量。是描述信息素浓度和路径长度信息相对重要性的控制参数。是一个区间内的参数。3.4 蚁群系统蚁群系统1.状状态转移移规则开发：当产生的随机数 时，蚂蚁直接选择使启发式信息与信息素量的 指数乘积最大的下一个城市节点，我们称之为开发。偏向探索：当产生的随机数 时，ACS将和各种AS算法一样使用轮盘赌选择策略，公式如下，我们通常将 时的算法执行方式为偏向探索。3.4 蚁群系统蚁群系统参数参数设置置 是ACS中引入的一个很重要的控制参数，在ACS的状态转移规则中，蚂蚁选择当前最优移动方向的概率为 ，同时，蚂蚁以 的概率有偏向地搜索各条边。通过调整，能有效调节“开发”与“探索”之间的平衡，以决定算法是集中开发最优路径附近的区域，还是探索其他的区域。在ACS 中 3.4 蚁群系统蚁群系统2.信息素全局更新信息素全局更新规则不论是信息素的蒸发还是释放，都在只属于至今最优路径的边上进行，此与AS有很大的区别。更新后的信息素浓度被控制在旧信息素量与新释放的信息素量之间，用一种隐含又更简单的方式实现了MMAS算法中对信息素量取值范围的控制。3.4 蚁群系统蚁群系统3.信息素局部更新信息素局部更新规则对每只蚂蚁，每当其经过一条边 时，它立即对这条边进行如下的信息素更新.其中，是信息素局部挥发速率，满足 。是信息素的初始值。通过实验，时，算法对大多数实例有着非常好的性能。其中n为城市个数，是由贪婪算法构成的路径的长度。，信息素局部更新规则作用于某条边上会使得这条边被其他蚂蚁选中的概率减少。这种机制大大增加了算法的探索能力，后续蚂蚁倾向于探索未被使用过的边，有效地避免算法进入停滞状态。3.5 蚁群算法的其他改进版本蚁群算法的其他改进版本近似非确近似非确近似非确近似非确定性树搜索定性树搜索定性树搜索定性树搜索使用部分解的完全代价估计的下界来计算各边使用部分解的完全代价估计的下界来计算各边的启发式信息；使用加法实现启发式信息与信的启发式信息；使用加法实现启发式信息与信息素的结合；没有直观的信息素蒸发步骤息素的结合；没有直观的信息素蒸发步骤多态蚁多态蚁群算法群算法将蚁群中的蚂蚁分为三类：侦查蚁、搜索蚁、将蚁群中的蚂蚁分为三类：侦查蚁、搜索蚁、工蚁工蚁连续正交连续正交连续正交连续正交蚁群算法蚁群算法蚁群算法蚁群算法在问题空间内自适应的选择和调整一定数量的在问题空间内自适应的选择和调整一定数量的区域，利用蚂蚁在这些区域内进行正交搜索、区域，利用蚂蚁在这些区域内进行正交搜索、在区域间进行状态转移，并更新各个区域的信在区域间进行状态转移，并更新各个区域的信息素来搜索问题空间中的最优解。息素来搜索问题空间中的最优解。蚁群优化算法蚁群优化算法 蚁群优化算法简介蚁群优化算法简介 一 蚂蚁系统蚂蚁系统二 蚁群优化算法的改进版本蚁群优化算法的改进版本三 蚁群优化算法相关应用蚁群优化算法相关应用四4 蚁群优化算法的相关应用蚁群优化算法的相关应用蚁群优化蚁群优化算法算法的应用的应用 1.车间作业调度问题车间作业调度问题2.车辆路径问题车辆路径问题 3.数据挖掘与图像处理数据挖掘与图像处理LOGO