CN111967643B 一种基于贪婪自适应蚁群算法的任务调度方法（北京工业大学）

(19)国家知识产权局(12)发明专利有限公司11203GO6N3/006(2023.0群混合算法求解旅行商问题.计算机仿真.2016,(11),第274-279.审查员高莘尧一种基于贪婪自适应蚁群算法的任务调度方法一种基于贪婪自适应蚁群算法的任务调度效率因子和可自适应调整的挥发系数来加快蚁利用前后调度结果的信息来有针对性的调节挥2由下面两个公式将得到的路径信息转化为蚁群算法中路在(1)式中的代表初始时刻f时贪婪算法提供的最优方案所包含的任一两个前后相的最优方案路径距离值Lenbest(f)和其余每一个非最优方案路径距离值Lenow(f)相比得到，将所有蚂蚁的起始点随机放置于各个待配送节点；总路径距离值该蚂蚁的禁忌表中清除；2)计算蚂蚁k在时刻t时从当前节点i到下一节点j的转移概率,按轮盘赌的方式3为当前时刻蚂蚁k所在节点，节点j表示待选始化定义；公式(3)通过将所有可行下一节点的信息素和启发式因子值转化为被选择的概Load,否则当资源剩余量不能满足任一未配送节点时则触发约束条件返回配送中心；当蚂蚁K出发后再次回到配送中心时，若此时禁忌表尚未清空则重新派出一只蚂蚁在共享蚂蚁K的禁忌表后，随机选择一个禁忌表中的剩余节点，加上该点到配送中心的距离t+1时刻表示上面出现过的任一时刻t的下一时刻，此时蚂蚁K已经完成节点选择和可行方案的构建；(5)式中表示t+1时刻方案m中任意两个前后相连节点i和jTm(t+1)(i,j)是t+1时刻方案由于采用了蚂蚁间接力的方法来破除在约束条件下对一个物流任务调度问题的求解，4)记录当前最优方案，对最优方案的路径进行信息素的全局更新，然后清空所有节点4迭代产生的最优方案及路径值len(t+1);在下一时刻t+2将会使用公式(7)得出本次全局更新的挥发系数p(t+1),然后使用公式(8)对本次所有方案中的最优路径的信息素进行全局刻本次迭代的最优方案m中前后相连节点i和j路径信息素的全局更新值，该值为新的残留系数1-p(t+1)和t+1时刻路径间局部更新后的信息素值的乘积与已被初始化的此处实例为物流资源调度，设置了一个配送中心和若干个待配送客户节点，下面简称在每组方案的起始路线选择时会依次指定除配送中心外的其余节点作为该路线的第二个5群算法的优点是不需要复杂的数学模型和繁杂的参数设计就可以处理非常复杂的组合最[0005]本发明是创造了贪婪自适应蚁群算法(GSA-ACO),通过引入贪婪算法来加速蚁群算法的初始化速度，加入效率因子和可自适应调整的挥发系数来加快蚁群算法的寻优速是限制蚁群算法在大规模资源调度问题中实际应用的障碍。而贪婪算法可在0(n)的时间复2/6页2/6页6[0007]算法中的自适应是指引入对算法参数中挥发系数的自适应调整和在启发式因子公式中引入效率因子。通过引入对信息素挥发系数基于前后调度结果的提升幅度进行分析的自适应调整机制来解决运行时出现的优化停滞或者困于局部最优解的问题。在出现优化停滞时增大挥发系数扩大搜索范围来跳出当前最优，优化速度慢时降低挥发系数来快速寻优。目前的启发式因子公式一般只是考虑距离因素，在这里本算法提出了效率因子加入到启发式因子公式中来弥补节点路径选择的粗疏性。效率因子是在选择下一节点时结合该节点执行时间，传输时间和执行载体的当前状态这三类信息得到的因式，本质上是为了平衡整体运行效率。两处调整机制让蚁群算法在面对优化停滞时有了明确的优化方向，解决了迭代方向不明确的问题。[0008]本发明还提出了蚁群中蚂蚁接力调度的新方法。传统蚁群算法以一只蚂蚁的模拟结果来得出一个可行的最终解，但对于一个复杂任务调度问题而言，在约束条件下一只蚂蚁一次迭代无法得到整个任务的最终解，这时需要将几只蚂蚁的成果互补作为一组可行方案。目前有人提出将两只蚂蚁分为一组同时进行路径选择的方法，但是一组蚂蚁需要同步选择下一节点，这就带来了互相干扰寻优和节点重复选择需要回退的问题。而且很多时候两只蚂蚁也未必可以完成任务。在这里引入了蚂蚁间进行接力的新方法，如果一只蚂蚁在约束条件下未能清空禁忌表就已经因为约束条件终止调度了，则再派出一只蚂蚁通过共享上一蚂蚁的禁忌表来继续完成任务，若禁忌表仍未被清空再派出下一只蚂蚁，直至禁忌表被清空。再将得到的多个互补的调度结果合并为一组可行方案。[0009]上述三项改进解决了蚁群算法对约束条件下大规模任务调度不适用的难题。例如在大型集群调度的资源调度利用率问题中，常规蚁群算法就很难落地应用，原因在于迭代运行速度慢，节点选择不确定性强且单蚂蚁路径很难满足各类约束条件。另外该算法的通用性很强，各项改进都可以对目前各类蚁群算法的变种进行有益的补充和优化。[0014]步骤4、开始执行蚁群算法，结合自适应调整机制最终给出最优方案。[0015]整个算法的流程图在图4中给出。附图说明[0016]图1物流问题示意图[0017]图2贪婪算法得出的可行解示意图[0018]图3蚁群算法得出的最优解示意图具体实施方式[0020]以下结合实例与附图对本发明进行详细说明。[0021]本发明的实施方式仅以解决物流资源调度难题为例，但算法本身广泛适用于各类带约束的任务调度问题。如图1所示该模型设置了一个配送中心和若干个待配送客户节点7实例中设置为100t,所以不可能只由一辆车就能完成所有的配送任务，故一个可行解中必这里的物流调度问题可以转化为在考虑汽车载重的情况下在一个图中遍历所有节点寻找这些方案为蚁群算法的初始化和迭代时的节点得出一条可行路径。这里的解决方案是在每组方案的起始路线[0030]在(1)式中的代表初始时刻f时贪婪算法提供的最优方案所包含的任一两个前法设置的所有节点路径间的初始信息素，此处设置的值为0.01,因为在实例中节点间的路8[0031]在(2)式中代表初始时刻f时其余非最优方案中包含的任一两个前后相联节得到，故每条非最优方案的ξ值随着本方案的路径距离不同而各不相同。值的设置是[0032]初始化后得到的各节点间路径的初始信息素值将会在蚁群算法节点选取时由概距离值会加上该初始节点到配送中心的距离。接下来为每只蚂蚁设置各自的初始禁忌表，[0037]在这里蚂蚁k指代该步骤中出现的所有需要选择节点的蚂蚁，t时刻为任一时刻，节点i为当前时刻蚂蚁k所在节点，节点j表示待选择的下一节点。公式中J(i)是t时刻在i[0038]公式(4中!是指t时刻i节点待选择的下一节点j的启发式因子值，表示i、j9小于Load,,否则当资源剩余量不能满足任一未配送节点时则触发约束条件返回配送中心。的已知信息和优化需求还可以设置更多参数来进一步[0040]当蚂蚁K出发后回到配送中心时，若此时禁忌共享蚂蚁K的禁忌表后，随机选择一个禁忌表中的剩余节点，加上该点到配送中心的距离残留系数，△Tm(t+1)(i,j)是t+1时刻该方案经过的任一两个相连节点i和j之间路径的信息[0044]由于采用了蚂蚁间接力的方法来破除在约束条件下(此处为汽车载重量)对一个[0048]t+1时刻我们得到每一个方案后，我们对其路径间的信息素进行了局部更新，并最终得出本次迭代产生的最优方案的路径值len(t+1)。在下一时刻t+2将会使用公式(7)得出本次全局更新的挥发系数，然后使用公式(8)对本次最优方案的路径的信息素进行全局更新。[0049]如公式(7)所示，Len(t)为t时刻的全局最优路径距离值，len(t+1)为t+1时刻得到的本次迭代最优路径距离值。Lenbest(+2)是Len(t+1)、len(后t+2时刻后蚁群算法更新的新全局最优路径距离值。这里的信息素挥发系数p(t+1)的值是通过对比前后最优路径的提升幅度来进行自适应调整。本次最优路径提升得越多，挥发系数p(t+1)就同比减小，因为同比降低挥发系数p(t+1)可以更好聚焦该路径进行寻优；提升越小甚至没有提升时，挥发系数p(t+1)就相对增大，因为增加挥发系数可以扩大蚁群的搜索空间。这样就解决了实际调度中运用蚁群算法遇到的迭代次数过多或者困于局部最优解的问题。[0050]公式8中的τ;;(t+2表示t+2时刻本次迭代的最优方案中任一路径的前后相连节点i和j的路径信息素的全局更新值。值为残留系数1-p(t+1)和t+1时刻路径间局部更新后的信[0052]反复重复上述迭代蚁群算法中的步骤1至4,直至迭代次数达到设置好的上限NCmx即50次后输出最后求得的最优路径。得到的调度方案如示意图3所示，该调度方案可以用于指导实际物流调度中调度方案的设计。从图2和图3两个示意图的对比中我们可以看出是否精心设计调度方案会对最终的执行结果带来很大的差距。如果能采用改进的蚁群算法得出最优化方案来最终执行，不仅可以明显提高物流公司调度过程中的资源利用率，避免资源浪费，还可以提升客户的体验，最终可以为物流公司带来良好的经济和社会效益。[0053]以上实施例仅为本发明的示例性实施例，不用于限制本发明，本发明的保护范围由权利要求书限定。本领域技术人员可以在本发明的实质和保护范围内，对本发明做出各种修改或等同替换，这种修改或等同替换也应视为落在本发明的保护范围内。OO0