《几种改进蚁群算法及其在生产调度中的应用.ppt》由会员分享，可在线阅读，更多相关《几种改进蚁群算法及其在生产调度中的应用.ppt（28页珍藏版）》请在三一文库上搜索。
1、几种改进蚁群算法及其在生产调度中的应用,报告内容：,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 Co
2、lony System,Max-Min Ant System,为了克服在Ant-Q中可能出现的停滞现象，此外，德国学者Thomas Stutzle和Holger Hoos提出另一种改进的蚁群算法“最大最小蚁群系统”MMAS (MAX-MIN Ant System) 。 只有最佳路径上的支路才允许增加其外激 素浓度,并保持在高水平上 。,Max-Min Ant System,各条路径可能的外激素浓度限制于 超出这个范围的值将被强制设为 或者 采用了让轨迹上外激素浓度的增加正比于和当前浓度之差的平滑机制(pheromone trail smoothing) ，其中,相遇蚁群算法,吴斌、 史忠植首先
3、在蚁群算法的基础上提出了基于MAX-MIN算法(MMAS)的相遇算法MMMAS ( Meeting MAX-MIN Ant System)。 将一只蚂蚁的一次周游分由两只蚂蚁分头进行，在路径中间碰头合成一次周游路径 最短的一次周游影响路径信息量。 选择一个节点后，即计算当前路径长度，如果长度超过本次循环己得到的最小值即结束此次周游 。,相遇蚁群算法,MMMAS算法步骤如下: Step1 初始化参数: Step2 NC加1； Step3 一组蚂蚁开始相遇循环； Step4. 两只蚂蚁选择同一起点节点； Step5. 第一只蚂蚁以公式（1）计算的跃迁概率选择节点； Step6.第二只蚂蚁以公式（1
4、）计算的跃迁概率选择节点; （1）,相遇蚁群算法,Step7. 当前路径长度大于本次 组相遇循环己知最短路径，结束此次两只蚂蚁周游,转Step10； Step8. 禁忌表未满转至Step5； Step9. 2-opt局部优化路径(可选)； Step10.如果 转至Step3； Step11.计算本次组蚂蚁相遇循环的最短路径，置空禁忌表；,相遇蚁群算法,Step12 .用公式（2）（3）（4）更新路径信息数 (最短路径增加，其它衰减)； Step13 . 小于 且未进入停滞状态，转至 Step2； Step14 .输出最优解。 （2） （3） （4）,针对不同出发点的改进蚁群算法,针对Muth-
5、Thompson的 Job Shop问题，将蚂蚁分布到不同的Job时获得的最优结果也不同，并不是每个点都允许在初始化的时候放置蚂蚁的，它存在着顺序约束 。 表1不同的Job作为蚂蚁出发点时得到的结果 Table1 Different results with variety job as ants starts,针对不同出发点的改进蚁群算法,具有相同出发点的蚂蚁更新相应的外激素轨迹强度，而不同出发点的蚂蚁留下的外激素轨迹强度之间互不相扰 。 改进的状态转移规则： Y没有根据概率分布来进行选择，而是在 对中任意选择，这样能够更好地克服停滞现象。,针对不同出发点的改进蚁群算法,单只蚂蚁的更新规则为
6、： 蚁群的更新规则为： 一次循环后的路径上外激素消散规则为：,针对不同出发点的改进蚁群算法,表2 不同的轨迹更新规则,针对不同出发点的改进蚁群算法,的job-shop调度问题 ，蚂蚁总数K等于总的工序数36，系统迭代的结束条件1000代，其余的参数设置为 计次数为10次 。 图1 改进型蚁群算法的最优值演化曲线图,针对不同出发点的改进蚁群算法,表3 仿真结果统计,带蚁群搜索的多种群遗传算法,蚁群搜索是基于各个种群的最优个体 。 蚁群开始索时，各个路段的初始信息素不是一个常数，而是据各个种群的最优个体确定的，不同路段有不同的初始信息素。 蚁群搜索得到的解替代种群中的若干较劣个体 。,带蚁群搜索的
7、多种群遗传算法,算法结构 :,带蚁群搜索的多种群遗传算法,初始信息素的设置如下： 其中， 为第k个种群的最优个体所对应路径的总长度，NUM为种群总数。,带蚁群搜索的多种群遗传算法,对10 10的Muth&ThompsonJSP基准问题进行求解 :,带蚁群搜索的多种群遗传算法,仿真计算的参数选择如下：在MGAAS中，种群数目pop_NUM = 5，各个种群的规模均为pop_ SIZE = 100，交叉概率 ，变异概率 ，一个进化周期内的进化代数ge_NUM = 1，蚂蚁数目ant_NUM =5，一个蚁群搜索周期的循环数目s_NUM = 1，总循环次数为300,算法各随机运行10次,结果如表4所示
8、：,带蚁群搜索的多种群遗传算法,表4 Muth&Thompson 10 10 问题的一个最优加工方案,双向收敛蚁群算法,将历史最差解看作目前不可接受的解,对其进行惩罚。 算法在计算路径转换可能性的过程中,不按照传统的方法将路径长度考虑在内。这是由于传统上单纯使用路径长度作为因子,导致完成时间较长的操作在蚂蚁寻径过程中处于不利地位,影响了算法的正确性。,双向收敛蚁群算法,状态转移规则： 信息素更新规则：,双向收敛蚁群算法,Muth&Thompson 的6 6 基准问题： 表5 挥发系数对收敛结果的影响,双向收敛蚁群算法,表6 蚂蚁数目对收敛结果和耗时的影响,双向收敛蚁群算法,表7 双向收敛ACO和ACO最优解的比较,谢谢!,