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

一种基于贪婪自适应蚁群算法的任务调度一种基于贪婪自适应蚁群算法的任务调度效率因子和可自适应调整的挥发系数来加快蚁利用前后调度结果的信息来有针对性的调节挥中还引入蚁群接力来破解约束条件下单蚂蚁路2在(1)式中的代表初始时刻f时贪婪算法提供的最优方案所包含的任一两个前后相在(2)式中代表初始时刻f时其余非最优方案中包含的任意两个前后相联节点a和b的最优方案路径距离值Lenbest(f)和其余每一个非最优方案路径距离值Lennow(f)相比得到，故每条非最优方案的ξ值随着本方案的路径距离不同而各不相同；将蚁群迭代的最大循环将所有蚂蚁的起始点随机放置于各个待配送节点；总路径距离值会加上该2)计算蚂蚁k在时刻t时从当前节点i到下一节点j的转移概率按轮盘赌的方式3始化定义；公式(3)通过将所有可行下一节点的信息素和启发式因子值转化为被选择的概Loadi，否则当资源剩余量不能满足任一未配送节点时则触发约束条件返回配送中心；是由下一节点j的资源需求量Wj、当前节点下资源的剩余量Loadi和距离因素当蚂蚁K出发后再次回到配送中心时，若此时禁忌表尚未清空则重新派出一只蚂蚁在共享蚂蚁K的禁忌表后，随机选择一个禁忌表中的剩余节点，加上该点到配送中心的距离t+1时刻表示上面出现过的任一时刻t的下一时刻，此时蚂蚁K已经完成节点选择和可行方案的构建；(5)式中表示t+1时刻方案m中任意两个前后相连节点i和j路径间的局部信息素更新值；r"t)表示前一时刻t时这些路径的信息素量，Rm表示方案m经过的所有节点构成的路径集合，ρ(t)为t时刻的由于采用了蚂蚁间接力的方法来破除在约束条件下对一个物流任务调度问题的求解，4)记录当前最优方案，对最优方案的路径进行信息素的全4新的挥发系数ρ(t+1)，然后使用公式(8)对本次所有方案中的最优路径的信息素进行全局刻本次迭代的最优方案m中前后相连节点i和j路径信息素的全局更新值，该值为新的残留系数1-ρ(t+1)和t+1时刻路径间局部更新后5)反复重复上述迭代蚁群算法中的步骤1)至4)，直此处实例为物流资源调度，设置了一个配送中心和若干个在每组方案的起始路线选择时会依次指定除配送中心外的其余节点作为该路线的第二个5群算法的优点是不需要复杂的数学模型和繁杂的参数设计就可以处理非常复杂的组合最将基于此类任务调度模型来说明对蚁群算法的工业领域中在约束条件下对大规模数据和资源进行任务调度和路[0005]本发明是创造了贪婪自适应蚁群算法(GSA-ACO)，通过引入贪婪算法来加速蚁群算法的初始化速度，加入效率因子和可自适应调整的挥发系数来加快蚁群算法的寻优速6[0007]算法中的自适应是指引入对算法参数中挥发系数的自适应调整和在启发式因子带约束的任务调度问题。如图1所示该模型设置了一个配送中心和若干个待配送客户节点7这里的物流调度问题可以转化为在考虑汽车载重的情况下在一个图中遍历所有节点寻找满足任一未配送节点的需求或所有节点都已经配送完毕这些方案为蚁群算法的初始化和迭代时的节点选取提供了数[0030]在(1)式中的代表初始时刻f时贪婪算法提供的最优方案所包含的任一8[0031]在(2)式中代表初始时刻f时其余非最优方案中包含的任一两个前后相联节法给出的最优方案路径长度值Lenbest(f)和其余每一个非最优方案路径长度值Lennow(f)相比[0032]初始化后得到的各节点间路径的初始信息素值将会在蚁群算法节点选取时由概距离值会加上该初始节点到配送中心的距离。接下来为每只蚂蚁设置各自的初始禁忌表，[0037]在这里蚂蚁k指代该步骤中出现的所有需要选择节点的蚂9是由下一节点j的资源需求量Wj、当前节点下资源的剩余量Loadi和距离因素的已知信息和优化需求还可以设置更多参数来进一步指[0040]当蚂蚁K出发后回到配送中心时，若此时禁忌表尚未清空则重新派出一只蚂蚁在共享蚂蚁K的禁忌表后，随机选择一个禁忌表中的剩余节点，加上该点到配送中心的距离残留系数，Δτm(t+1)(i,j)是t+1时刻该方案经过的任一两个相连节点i和j之间路径的信息[0044]由于采用了蚂蚁间接力的方法来破除在约束条件下(此处为汽车载重量)对一个本次全局更新的挥发系数，然后使用公式(8)对本次最优方案的路径的信息素进行全局更后t+2时刻后蚁群算法更新的新全局最优路径距离值。这里的信息素挥发系数ρ(t+1)的值系数ρ(t+1)就同比减小,因为同比降低挥发系数ρ(t+1)可以更好聚焦该路径进行寻优；提