法律状态公告日
法律状态信息
法律状态
2020-06-02
授权
授权
2018-08-21
实质审查的生效 IPC(主分类):G06Q10/04 申请日:20180206
实质审查的生效
2018-07-27
公开
公开
技术领域
本发明属于多智能体协同调度领域，涉及一种基于可塑性机制的重调度方法的多智能体多目标优化方法。
背景技术
智能体，顾名思义，就是具有智能的实体，英文名为Agent。智能体是指驻留在某一环境下，能持续自主地发挥作用，具备驻留性、反应性、社会性、主动性等特征的计算实体。智能体既包括机器人，又包括计算机、计算机集群等计算实体。多智能体系统是多个智能体组成的集合，其目的是将大而复杂的系统建设成小的、彼此互相通信和协调的，易于管理的系统。随着社会的不断发展，多智能体的应用愈发广泛。
多机器人系统(Multi-robot systems,MRS)是由多个结构相对简单，通过相互协作来并行执行某一个或某一组复杂任务的整体系统。由任务资源对MRS中每个机器人的合理分配，可以有效提升整体任务的执行速度，达到单个机器人难以达到的任务需求。因此，研究多机器人之间的任务合理分配，实现个体机器人之间和有效协同，提高MRS整体的任务执行能力，具有很重要的研究意义与实际应用价值。
在MRS的协同调度中，最为重要的一个挑战是如何合理考虑多个机器人之间的相互竞争的冲突关系，通过合理有效的资源分配，以最大程度地提升MRS 的整体执行能力。而在整体任务需求多样化的背景下，同样需要考虑如何根据所设定的多个目标，结合多个目标之间的制约条件，从而合理给出备选策略集合。通常在这种合作协同的系统中，机器人个体之间、多个目标之间的需求均是相互制约与冲突的，如RoboCup机器人世界杯赛、机器人下棋等多机器人系统中常常会考虑到这些问题。
在现实应用中，某一组复杂任务往往由多个简单子任务混合构成，而每个简单子任务往往会有相互制约的完成条件。如只有在该任务的所有前级任务完成的情况下，此任务才具有可以被执行的条件。只有当所有任务都被完整完成的情况下，该复杂任务组才被完全完成。此种具有相互牵制子任务的复杂任务需求环境，往往可以对应于工业过程的机器人调度、云计算中工作流调度等应用环境。
在实际的多机器人执行任务的过程中，考虑出现的偶然失误因素具有很重要的研究价值。当任务失败率服从一定分布的情况下，需要对失败任务进行重新的整合与发布，并通过调用现有的当前任务空闲的机器人资源，对任务进行重新执行，实现一定执行失误率情况下，对失败任务执行的补充调度，使得整个任务组被有效地完成。
在不同的应用环境中，多机器人协同系统会具有不同的任务需求，如多机器人协同搜救，往往会以整体搜救时间最短作为主要目标；在多机器人协同环境探索的应用背景下，往往会以整体机器人耗费路程最短作为策略优劣的主要依据。所以，其根据应用场景的不同，所选取的主要评价指标则各有偏重。通过将多个互相制约的评价指标设立为目标函数，采用多目标优化算法求取最优策略解集，既可以客观描述各个目标函数之间的制约关系，同时也能为某种特定场景下的策略选择提供参考集合。
多智能体的调度及任务机制与工作流模型类似，因此工作流管理的研究对多智能体协同调度有着一定的参考意义。CN 102509197A提出了一种对多个工作流引擎的集中管理；CN 101615269在工作流的任务背景下对任务的回退机制进行了优化，实现了在工作流执行过程中任务可以任意回退的操作，增强了任务执行实现的灵活性；CN 106845642A提供了一种带约束云工作流调度的自适应多目标进化方法，能够提高多目标进化方法的全局探测和局部开采能力，适用于解决带约束的多目标优化问题，并可应用于云计算环境中工作流调度技术领域。虽然上述发明对工作流模型进行了一定的优化，一定程度上能够提供多目标优化问题的解决方案，但其针对的为优化的单个环节，并未提供完整可靠的多目标优化方法。
因此，研究一种完整且优化效果好的多智能体多目标优化方法极具现实意义。
发明内容
本发明的目的是克服现有技术的不足，提供一种基于动态偶然失败任务环境的多智能体多目标优化方法，该方法基于可塑性机制的重调度方法，该重调度方法的重调度引擎通过可塑性机制进行了优化，其通过单位时间内失误频率的波动来动态调整重调度失败任务合并比例，在随机任务失败的情况下保持任务成功率稳定；并在此基础上由改进的NSGAIII目标优化算法求取Pareto解集和目标解集即得到了策略集合与策略执行结果集合，再确定最优元素选取策略，并按照选取策略调度多智能体完成多目标优化。
为了达到上述目的，本发明采用的技术方案为：
一种基于可塑性机制的重调度方法的多智能体多目标优化方法，本发明通过对调度策略进行优化实现多智能体系统多目标优化(缩短整体完工时间、个体最大完工时间及执行任务的总耗费时间)，针对各智能体随机失误的环境，首先对所有智能体进行顺序编码，把智能体作为种群基因初始化种群，种群个体为针对所有智能体的调度策略，根据个体完成的前后关系即任务的先后关系建立工作流模型，再应用基于可塑性机制的重调度方法对工作流模型求解得到最优策略模型，使得在任一种预先指定的任务分配策略下，所输出的多目标(整体完工时间、整体耗费以及个体最大完工时间)尽量稳定以实现容错即具有容忍随机失误的能力，主要表现在多目标(整体完工时间、整体耗费以及个体最大完工时间)不会随着失误较大波动，然后应用改进的NSGA III优化算法进行多目标优化处理求得Pareto解集和目标解集，在目标解集确定最优元素并选取Pareto解集中的对应调度策略，最后按照前步选取的调度策略调度多智能体执行任务即完成多目标优化；Pareto解集中每个元素代表一组优化后的调度策略，目标解集中每个元素代表一组目标即优化后的调度策略执行的结果，Pareto解集与目标解集中的各元素一一对应；在考虑所有目标的情况下，进行多目标优化处理，那么得到的最终结果则应该是一组策略解集和与之对应的目标解集，策略解集即表在多个目标的权衡下得出的一组以策略为元素所组成的集合；
所述多目标包括整体完工时间W1、个体最大完工时间W2及执行任务的总耗费时间W3；所述确定最优元素是指针对单一元素中的W1、W2及W3加权求和得到综合指标
所述基于可塑性机制的重调度方法是指利用可塑性机制对重调度引擎进行优化得到的重调度方法，所述优化的方法为：在真实环境中，任务往往具有先后承接的特性，某个任务只有在所有前级任务完成的情况下，才可以被执行，针对真实环境中失败任务偶然发生的情况，根据相邻两次失败任务产生的时间间隔，动态地调整重调度引擎对失败任务的合并比例，任务失败率分布保持不变的前提下，当相邻两次失败任务产生的时间间隔较小，降低失败任务合并比例，相当于间接提高了该段时间内任务执行的成功数；
所述最优策略模型是指反映调度策略与目标即调度策略执行结果关系的模型；
所述改进的NSGA III多目标优化算法是指利用Knee Point思想对NSGA III 多目标优化算法进行改进后得到的算法，所述改进的方法为：结合基于参考点远近的筛选方法与Knee Point的筛选方法作为NSGAIII的个体挑选规则，从最后一个非支配层级挑选个体进入子代。
作为优选的技术方案：
如上所述的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，该方法的具体步骤为：
(1)首先对所有智能体进行顺序整数编码，把智能体作为种群基因初始化种群，种群个体为针对所有智能体的策略，根据个体完成的前后关系建立工作流模型；
(2)针对多智能体并行执行多任务的调度环境中偶然失败的情况，本发明基于神经科学中内在可塑性机制对重调度方法中的重调度引擎进行优化，得到基于可塑性机制的重调度方法；
(3)应用基于可塑性机制的重调度方法对工作流模型求解得到最优策略模型，使得固定任务分配策略下模拟调度的最终结果尽量保持稳定；
(4)针对此种动态环境，对最优策略模型运用改进的NSGAIII目标优化算法计算得到指标更好的Pareto解集和与其对应的目标解集，改进是指在最后一个非支配层级挑选个体进入子代时，结合基于参考点远近的筛选方法与Knee Point 的筛选方法作为NSGAIII的个体挑选规则；
(5)在目标解集确定最优元素，并选取Pareto解集中的对应调度策略，最终按照选取的调度策略调度多智能体执行任务即完成多目标优化。
如上所述的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，所述对重调度引擎进行优化具体为：
根据相邻两次失败任务产生的时间间隔，动态地调整重调度引擎对失败任务的合并比例，时间间隔与合并比例的关系如下：
其中T为相邻两次失败任务产生的时间间隔，s为失败任务的合并比例，p 为相关系数，主要取决于整体任务的数目，R为调整门限，决定调整过程中的相对应调整公式的截距，C为调整灵敏度，决定调整过程中T变化引起的变化的大小。
如上所述的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，所述重调度方法为MaxMin调度方法。
如上所述的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，所述应用基于可塑性机制的重调度方法对工作流模型求解得到最优策略模型是指：将工作流模型由模型解释器读取加入基于可塑性机制的重调度方法的队列中得到最优策略模型。
如上所述的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，所述结合基于参考点远近的筛选方法与Knee Point的筛选方法作为NSGAIII的个体挑选规则是指：先按照基于参考点远近的筛选方法从最后一个非支配层级挑选距离参考点最近的n％个个体，再在其中按照KnEA算法中Knee Point的筛选方法选取Knee Point个体作为更新个体即选取与坐标轴围成的超体积最小的个体进入子代，依次进行选择，直至更新个体的数量与种群规模数相等，取得了的效果优于NSGAIII与其他多目标进化算法。
如上所述的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，所述按照选取的调度策略调度多智能体是指将调度策略中的子策略按照其与智能体的对应关系依次输入到各智能体，各智能体根据输入指令执行命令，所述子策略为调度策略中单个智能体对应的策略。
如上所述的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，所述改进的NSGAIII目标优化算法的HV值≥0.450643，IGD值≤0.229190，本发明相较于现有技术显著提高了HV值，降低了IGD值，即本发明的算法得到解集的多样性更好，算法收敛速度更快。
有益效果：
(1)本发明的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，在固定调度策略即任务固定的条件下，可根据单位时间内错误率的波动，动态地调整重调度引擎对重新发布与委派失败任务的合并比例，从而尽可能保持优化目标(整体完工时间、个体最大完工时间及执行任务的总耗费时间)的稳定；
(2)本发明的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，对NSGAIII进行了改进，使用该改进算法对模型进行求解，算法的HV值和IGD上更优于NSGAIII与其他多目标进化算法，本发明改进算法的收敛速度及得到解集的多样性更好；
(3)本发明的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，可有效对多智能体系统的任务执行能力进行优化，动态调整多智能体的任务执行过程。
附图说明
图1是本发明的流程图；
图2是本发明的基于可塑性机制的重调度方法的流程图；
图3是本发明的改进NSGAIII算法的流程图；
图4是工作流测试模型Montage-100示意图；
图5是本发明的最优策略模型的测试结果；
图6是本发明改进NSGAIII算法的HV值统计结果；
图7是本发明改进NSGAIII算法的IGD值统计结果。
具体实施方式
下面结合具体实施例，进一步阐述本发明。应理解，这些实施例仅用于说明本发明而不用于限制本发明的范围。此外应理解，在阅读了本发明讲授的内容之后，本领域技术人员可以对本发明作各种改动或修改，这些等价形式同样落于本申请所附权利要求书所限定的范围。
本发明的一种基于可塑性机制的重调度方法的多智能体多目标优化方法，如图1所示，其具体步骤如下：
(1)首先对所有智能体进行顺序整数编码，把智能体作为种群基因初始化种群，种群个体为针对所有智能体的策略，根据个体完成的前后关系建立工作流模型；
(2)针对多智能体并行执行多任务的调度环境中偶然失败的情况，本发明基于神经科学中内在可塑性机制对重调度方法即MaxMin调度方法中的重调度引擎进行优化，得到如图2所示的基于可塑性机制的重调度方法；
在神经科学中，内在可塑性是神经元自我调节的一种客观存在的机制。当神经元接受的刺激信号过于频繁时，神经元本身会逐渐地提高自身的接受刺激的阈值；当神经元接受的刺激信号变得稀少时，神经元本身会逐渐地降低自身接受刺激的阈值；在任务调度环境中，考虑当某一段时刻执行任务的错误率较高时，所对应的整个系统的任务执行能力会大幅下降；基于内在可塑性机制对重调度引擎进行优化，动态缩小任务的打包大小，间接提高成功执行任务的数目，使得在这种情况下仍维持有一定程度的任务执行能力，具体为：
根据相邻两次失败任务产生的时间间隔，动态地调整重调度引擎对失败任务的合并比例，时间间隔与合并比例的关系如下：
其中T为相邻两次失败任务产生的时间间隔，s为失败任务的合并比例，p 为相关系数，主要取决于整体任务的数目，R为调整门限，决定调整过程中的相对应调整公式的截距，C为调整灵敏度，决定调整过程中T变化引起的变化的大小；
(3)应用基于可塑性机制的重调度方法对工作流模型求解得到最优策略模型，即如图2所示，将工作流模型由模型解释器读取加入基于可塑性机制的重调度方法的队列中得到最优策略模型，使得固定任务分配策略下模拟调度的最终结果尽量保持稳定；
在调用框架下，调度策略是通过任务分配器传入到“当前队列”模块之中，而模型解释器通过读取预先设定的工作流模型，由每个子任务的前级任务是否被完成，将具有可以被执行条件的任务传入到“当前队列”模块之中；只有在当前队列中某个任务存在的情况下，任务分配器才能通过调用某个执行单元，对当前队列中的任务进行执行；除此之外，其余执行单元均处于空闲状态；仿真环境中，错误监视器为执行单元是否执行完成分配的任务提供评判标准，从而区分已完成任务和失败的任务；通过重调度引擎对失败的任务进行重新打包，再次加入“当前队列”模块中，所重新加入的重调度任务将仍受任务失败率的影响；当前空闲的最大执行任务能力的执行单元去执行具有最小耗时需求的任务，如此循环往复直至所有任务完全执行完毕；
(4)改进NSGA III多目标优化算法，其具体结构与改进规则如图3所示，在最后一个非支配层级挑选个体进入子代时，结合基于参考点远近的筛选方法与 Knee Point的筛选方法作为NSGAIII的个体挑选规则，从最后一个非支配层级挑选个体进入子代，具体为：
先按照基于参考点远近的筛选方法从最后一个非支配层级挑选距离参考点最近的n％个个体，再在其中按照KnEA算法中Knee Point的筛选方法选取KneePoint个体作为更新个体即选取与坐标轴围成的超体积最小的个体进入子代，依次进行选择，直至更新个体的数量与种群规模数相等；
(5)对最优策略模型运用改进的NSGAIII目标优化算法计算得到指标更好的Pareto解集和与其对应的目标解集，Pareto解集中每个元素代表一组优化后的调度策略，目标解集中每个元素代表一组目标即优化后的调度策略执行的结果， Pareto解集与目标解集中的各元素一一对应，目标包括整体完工时间W1、个体最大完工时间W2及执行任务的总耗费时间W3；
(6)在目标解集确定最优元素并选取Pareto解集中的对应调度策略，确定最优元素为针对单一元素中的W1、W2及W3加权求和得到综合指标
(7)按照选取的调度策略调度多智能体执行任务完成多目标优化，即将调度策略中的子策略按照其与智能体的对应关系依次输入到各智能体，各智能体根据输入指令执行命令，子策略为调度策略中单个智能体对应的策略。
本实施例调用Montage_100工作流模型输入步骤(2)进行测试，Montage 模型是一种公认的多智能体工作流模型，由NASA/IPAC所创建，为一种在外太空探测时对多个所摄星空图像进行拼接集成的工作流模型。
在Montage_100中，总共有100个任务需求节点，具体的各个任务依托关系如图4所示意。可见，除了第一级任务外，每个任务都有至少一个所依托的前级任务。这种情况下，只有在前级任务完全被完成，则此任务才有被进行执行的条件。并设定20个可用的任务执行单元，即最多有二十个任务被同时并行运行。
在其工作流执行系统中，假设执行任务的失败率服从Weibull分布：
其中x为随机变量，λ>0为比例参数，k>0为形状参数。
在测试过程中，某个执行单元与任务节点之间的调度关系为预先固定。只有在任务失败时，进行重调度策略的情况下，才采用基于可塑性机制优化后的重调度引擎对当时的状况进行弥补。
设定形状参数k＝1，在该设定条件下任务执行失误率服从指数分布。对仿真结果进行统计实验，在每组比例参数状况下将步骤(3)的最优策略模型独立运行5000次并统计分析。具体结果可见图5，由图5可以发现随着失误率的增长，执行结果在整体完工时间、整体耗费和个体最大完工时间这三个目标上波动不大。
设定Weibull分布的参数为：k＝1，λ＝100，选用NSGAII、MOEA/D、DBEA、 NSGAIII、RVEA及本发明的改进NSGAIII(K-NSGAIII)算法对最优策略模型分别独立运行50次，统计实验结果如图6(HV)、图7(IGD)、表1(HV)及表2(IGD)所示。由表1及表2可以发现，本发明的改进NSGAIII算法的HV 值远大于其他算法，IGD值小于其他算法具有计算的解集多样性高，收敛快的优势，由图6及7可以看出，本发明的算法在多次统计实验上，在HV值和IGD 值上具有相对波动不大，也就是方差较小，稳定性好。由此可见，本发明在建立一种基于可塑性机制的重调度方法，并运用该调度方法对工作流模型进行求解得到最优策略模型，并在最优策略模型的基础上，提出了一种针对该模型的改进 NSGAIII的多目标优化算法，应用算法对最优策略模型求解，在求解过程中解集多样性高且收敛速度快。本发明选用较为真实的仿真环境，具有相对显著的实践意义，在此基础上，通过将其应用于多智能体调度系统，可以描述各个目标之间的制约关系，同时有效的迭代计算出Pareto解集，为选择最优的多智能体任务调度策略提供合适的参考策略集合。
表1
表2 。
机译： 汽车电液智能转向系统及其多目标优化方法
机译： 参数多目标优化装置，参数多目标优化方法和参数多目标优化程序
机译： 多目标优化设备，多目标优化方法和多目标优化程序
