几种改进蚁群算法及其在生产调度中的应用.ppt

几种改进蚁群算法及其在生产调度中的应用 报告内容： Ant Colony System Max-Min Ant System 相遇蚁群算法 针对不同出发点的改进蚁群算法 带蚁群搜索的多种群遗传算法 双向收敛蚁群算法 Ant Colony System 1996年,Gambardella和Dorigo在ant-cycle system基础上提出一种修正的蚁群算法,他们称之为蚁群系统(ant colony system, ACS) 。 它与ant-cycle system算法的不同之处在于蚂蚁选择节点时遵循的规则不同 。 特点：1.“确定性搜索”与“随机性搜索” 2.加快算法收敛速度 Ant Colony System Max-Min Ant System 为了克服在Ant-Q中可能出现的停滞现象，此外，德国学者Thomas Stutzle和Holger Hoos提出另一种改进的蚁群算法“最大最小蚁群系统”MMAS (MAX-MIN Ant System) 。 只有最佳路径上的支路才允许增加其外激 素浓度,并保持在高水平上 。 Max-Min Ant System 各条路径可能的外激素浓度限制于 超出这个范围的值将被强制设为 或者 采用了让轨迹上外激素浓度的增加正比于和当前浓度之差的平滑机制(pheromone trail smoothing) ，其中 相遇蚁群算法 吴斌、 史忠植首先在蚁群算法的基础上提出了基于MAX-MIN算法(MMAS)的相遇算法MMMAS ( Meeting MAX-MIN Ant System)。 将一只蚂蚁的一次周游分由两只蚂蚁分头进行，在路径中间碰头合成一次周游路径 最短的一次周游影响路径信息量。 选择一个节点后，即计算当前路径长度，如果长度超过本次循环己得到的最小值即结束此次周游 。 相遇蚁群算法 MMMAS算法步骤如下: Step1 初始化参数: Step2 NC加1； Step3 一组蚂蚁开始相遇循环； Step4. 两只蚂蚁选择同一起点节点； Step5. 第一只蚂蚁以公式（1）计算的跃迁概率选择节点； Step6.第二只蚂蚁以公式（1）计算的跃迁概率选择节点; （1） 相遇蚁群算法 Step7. 当前路径长度大于本次 组相遇循环己知最短路径，结束此次两只蚂蚁周游,转Step10； Step8. 禁忌表未满转至Step5； Step9. 2-opt局部优化路径(可选)； Step10.如果 转至Step3； Step11.计算本次组蚂蚁相遇循环的最短路径，置空禁忌表； 相遇蚁群算法 Step12 .用公式（2）（3）（4）更新路径信息数 (最短路径增加，其它衰减)； Step13 . 小于 且未进入停滞状态，转至 Step2； Step14 .输出最优解。 （2） （3） （4） 针对不同出发点的改进蚁群算法 针对Muth-Thompson的 Job Shop问题，将蚂蚁分布到不同的Job时获得的最优结果也不同，并不是每个点都允许在初始化的时候放置蚂蚁的，它存在着顺序约束 。 表1不同的Job作为蚂蚁出发点时得到的结果 Table1 Different results with variety job as ants starts 针对不同出发点的改进蚁群算法 具有相同出发点的蚂蚁更新相应的外激素轨迹强度，而不同出发点的蚂蚁留下的外激素轨迹强度之间互不相扰 。 改进的状态转移规则： Y没有根据概率分布来进行选择，而是在 对中任意选择，这样能够更好地克服停滞现象。 针对不同出发点的改进蚁群算法 单只蚂蚁的更新规则为： 蚁群的更新规则为： 一次循环后的路径上外激素消散规则为： 针对不同出发点