求解保障任务分配问题的综述
来源:用户上传
作者:
摘 要 本文首先对保障任务分配问题的基本概念进行了阐述，分析了今年来求解任务分配问题的数学方法及研究现状，最后总结了现行有效的群智能优化算法并进行了内容阐述。
关键词 任务分配 群智能算法 保障问题
中图分类号：TN925 文献标识码：A
1任务分配问题概述
问题描述：N个人分配N项任务，一个人只能分配一项任务，一项任务只能分配给一个人，将一项任务分配给一个人是需要支付报酬的，如何分配任务，保证支付的报酬总数最小？在任务分配问题中，每个人完成每个项目的花费成本是不同的，最终所求是所有人完成所有工作的最花费成本最低。
2任务分配问题的研究现状
任务分配问题是一个线性规划问题，数学模型构成简单，约束条件可根据所构造数学模型的要求进行设置，因此在实际中应用范围很广，适合大部分离散分配问题。仅2018年就有众多学者们用感兴趣的群智能优化算法对各类问题进行求解，取得了很好的效果。吕龙等人在求解工作流系统的任务分配问题时，基于蚁群算法通过考虑协作兼容性和每个执行程序的工作量来实现优化，并取得了较好的结果。董海霞等人采用粒子群算法求解无人机的任务分配问题，通过实验仿真可以实现对多种群的多目标优化方案求解。同样是面对无人机任务分配问题，魏政磊等人分析了动态任务分配的特点，设计了目标任务序列编码的方式，提出用改进的灰狼优化算法进行求解，并通过实验仿真证明，算法收敛且有效。
3任务分配问题的求解方法
从上述研究现状中可以看出，使用群智能优化算法是求解任务分配问题的一个较好的解决办法。目前经过大量文献阅读可知，此类群智能优化算法有：蚁群算法、粒子群算法、灰狼优化算法等。
3.1蚁群优化算法
意大利学者Colorni等人最早于20世纪90年代提出了蚁群算法（ant colony algorithm），该算法通过模拟自然界中蚂蚁群体寻找路径的行为而提出。蚂蚁利用一种被称为信息素的东西进行交流，所有蚂蚁在寻找路径的过程中会在自己行走过的路径中不断释放信息素，并感知其它蚂蚁留下的信息素浓度，经过多轮迭代后确定信息素浓度最强的路径即为最短路径。各路径上的信息素浓度为：
蚁群算法利用信息素进行交流的方式实质上是一种正反馈机制，即可通过正反馈机制的调整，对较优解起到增强的作用，使算法向着最优解演变;同时蚁群算法具有较强的鲁棒性，可以应用于很多领域;同时蚁群算法具有并行性，能够实现全局收敛。但同时蚁群算法也具有前期收敛速度慢等缺点，还需在求解相关实际问题中不断改进。
3.2粒子群算法
粒子群算法（particle swarm optimization）是一种基于群体的随机优化算法，最早是由Kennedy等在1995年提出的，它是模拟鸟类觅食过程来寻求最优解的算法。在算法中，每个优化问题的解都是搜索空间中的一只被称为粒子的鸟，所有粒子都对应一个目标公式的值，依据较优目标公式值会得出每个粒子的飞行方向和距离，这两个数值由粒子本身个体极值和全局极值来确定，具体进化的速度和位置的求解方式如下：
粒子群算法的特点是既保持了算法结构简单的特性又可以做到运输中收敛速度快的较高运算性能，且鲁棒性、并行性较好，无论全局还是局部的寻优能力都较强，缺点是容易早熟，但在求解优化问题时依然具有很好的求解能力。
3.3灰狼优化算法
灰狼优化算法（grey optimization algorithm）是S Mirjalili等人于2014年时提出来的一种群智能优化算法，该算法模拟了自然界灰狼种群领到层级和捕食机制提出来的。灰狼种群中由统治阶级alpha级狼统治，狼群在其命令下，由beta等级的狼协助其进行决策活动，delta等级的狼执行前两类狼的决策，具体求解公式如下：
灰狼优化算法在求解多維、多峰的连续函数时，与其它算法相比具有较好的收敛速度和鲁棒性，但是在离散应用方面发展较慢，还需更多研究开发相关算法。
参考文献
[1] Lv Long，Hu Haiyang，Li Zhongjin.Optimizing task allocation in workflow system based on ant colony optimization[J]. Computer Integrated Manufacturing Systems，2018，24（07）：1723-1735.
[2] 董海霞，邹杰.基于AMPSO算法的无人机任务分配问题研究[J].电光与控制，2018（01）.
[3] 魏政磊，赵辉，黄汉桥等.基于SAGWO算法的UCAVs动态协同任务分配[J].北京航空航天大学学报，2018（01）.
[4] 于连伯.蚁群算法的研究[J].江苏科技信息，2010（09）.
[5] 邓伟林，胡桂武.粒子群算法研究与展望[J].现代计算机，2006（11）.
[6] Seyedali，M.&M.M.Seyed&L.Andrew.Grey wolf optimizer[J].Advances in Engineering Software，2014（69）：46-61.
转载注明来源:https://www.xzbu.com/1/view-14927853.htm
