融合局部搜索与Pareto支配的多目标任务调度模型.pdf

为了解决复杂任务群调度过程中资源利用不均、任务完成时间较长等问题，以最小化资源负载均方差和最小化任务群完成时间为目标构建复杂任务群资源调度模型，提出一种融合局部搜索和 支配的多目标优化算法 （，）。该算法采用有效的编码方式与交叉变异算子进行迭代寻优，并利用基于边界区域局部搜索的精英保留策略扩大算法搜索范围，保存种群优良个体。实验结果表明，相较于其他多目标算法在收敛性和多样性上有显著的提升，同时算法收敛速度更快，种群质量更高，明显优化了最终目标函数的结果值。关键词：多目标优化；局部搜索；智能算法；任务调度；支配中图分类号：文献标志码：文章编号：（）：，（，；，）：，：；引言工业 时代的到来，加快了产业智能化的推进，生产过程中出现的各类任务与所需资源的调度问题也愈发复杂。工业生产场景下遇到的大型任务如车间生产、故障联合处置等，需要调用多方资源协作完成，资源根据不同任务的需求可分为设备资源、运输资源和人员资源等，本文将此类问题抽象为一个复杂任务群调度问题，将一段时间内产生的多个任务定义为一个任务群，每个任务根据复杂程度又可进一步细分为多个具有关联关系的原子任务，原子任务是任务执行与持有资源的最小单元。针对工业场景下复杂任务群的调度就是要在考虑完成时间、资源利用率等因素的情况下为所有原子任务合理分配资源。国内外针对复杂场景下多任务调度问题的研究已经取得了一定的成果，但多数都是针对单一目标进行的。文献 利用混合进化算法以最小化任务完成时间为目标构建了生产资源配置模型；文献 ，以最小化事件延期成本为目标提出了结合遗传算法与自适应策略的调度模型；文献 ，将粒子群算法进行离散化处理，并且验证了在生成高质量资源任务配置方案方面的有效性；文献 考虑到了任务优先级差异，提出了混合精确算法与遗传算法的任务调度框架；文献 ，从安全性的角度出发，提出了任务调度隐私保护策略。以上研究均从单一维度出发对问题进行建模，缺少了对实际应用的综合考虑，应当从多目标出发，构建符合实际场景的多目标优化模型。在求解多目标问题上，主要有基于加权聚合和基于 排序两种方式。基于加权聚合的多目标优化策略通过降维的方式把问题简单化，偏离了多目标优化研究的本质，同时权值的选择有较强的主观性。因此，多目标优化问题的研究更倾向于使用另一种基于 前沿的多目标优化策略，该策略通过对个体的多个目标函数值进行非支配排序，从而选择出一组最优的解集。基于 的 多目标算法利用快速非支配排序对种群进行分层，并结合拥挤度比较算子保留将优良个体保留下来，从而找到一组非支配解集。文第 卷第 期 年 月计 算 机 应 用 研 究 献 采用基于过程的随机变异策略和交叉方法生成新一代种群，并改进了精英保留策略。针对工业车间调度问题，文献 在原有多目标算法的基础上提出了一种智能决策优化算法。文献 引入了 部分优势的概念，使 在多维解空间中进行有效搜索，但是仍然存在算法易早熟、收敛速度较慢等问题。文献 采用多区域采样重组策略，有针对性地调整粒子在多个方向上的收敛能力。文献 ，的研究表明，利用局部搜索可以有效提升多目标优化问题解的质量，但会产生大量局部解，导致计算量成倍增加。从以上分析可知，目前针对工业场景下复杂任务群资源调度问题的研究多集中于将问题建模为一个单目标优化问题，然而实际应用场景中资源分配方案需要考虑多方面因素，如任务群完成时间、资源负载情况等。同时，传统多目标算法寻优能力不足、易进入局部最优的缺陷，亦是需要解决的问题，局部搜索策略为问题的求解提供了思路，但需要解决计算量过大的问题。本文首先以最小化任务群完成时间和最小化资源负载均方差为目标，构建了双目标复杂任务群资源调度模型；其次针对问题模型的求解提出了一种融合边界范围局部搜索和 支配的多目标优化算法（，），算法利用混沌变量扩大解的搜索范围，即有更大的概率发现更为优质的任务群调度方案，弥补了算法陷入局部最优的缺陷，同时加快了算法的收敛速度，能够在更短的时间内找到更为优质的解；最后通过仿真实验对算法性能进行测试，结果表明与现有算法相比，本文提出的 算法在收敛性和多样性上相较于标准 算法分别平均提升了 和 ，并且生成的资源调配方案在两个目标值上的结果均优于其他具有代表性的多目标算法。问题模型 问题描述有 个资源（，）和由 条任务（，）组成的任务群，任务 由 个具有次序约束关系的不重叠原子任务（，）组成，每一个原子任务的处置可选用多个同类型资源中的任一资源，原子任务的处置时间随所选资源的不同而不同，调度目标是为每个原子任务选择最合适的处置资源，确定每个资源被任务占用的开始与结束时间，使得整个调度方案的某些性能达到最优。因此，问题的求解可细化为以下两个方向：）资源分配，即为每一个原子任务分配所需的资源；）原子任务执行排序，为需要占用同一资源的原子任务安排资源使用顺序。符号定义为了方便后续描述，本文模型所涉及到的符号及含义如表所示。表 模型符号 符号定义符号定义任务群规模 不使用资源 使用 资源总数 原子任务 的开始时间任务编号，原子任务 的结束时间任务 的原子任务数 占用 时长任务群原子任务总数，即任务 的完成时间 任务 的第 个原子任务 资源 最终释放时间资源编号，问题假设）同一个任务群中，不同任务间没有处理优先级的差异；）不同任务的原子任务之间没有约束关系；）所有任务在 时刻都可以被处置；）每个原子任务都需要占用具有特定属性的资源。模型约束模型约束可分为资源约束、时序约束和状态约束三大类。）资源约束如式（）所示，一个原子任务只可以占用一个资源。（）时序约束如式（）所示，一个任务的原子任务之间存在执行顺序约束，即只有完成全部前序子任务后才可以开始执行当前任务。（）（）状态约束如式（）所示，原子任务一旦占用资源开始执行，就不可以中途停止。（）优化目标在实际工业场景下的复杂任务群调度中，需要考虑多个优化目标，本文以最小化任务群完成时间 和最小化资源负载均方差 两个目标为导向，制定任务群资源调配方案。）最小化任务群完成时间。，（），（）其中：表示任务 的处置完成时间，即该任务最后一个原子任务的完成时间。）最小化资源负载均方差。（珚）（）（）（）珚 （）资源负载均方差体现资源利用的均衡程度，其中，为所有资源的总负载，珚为所有资源的平均负载，为资源总数。多目标优化算法 算法概述前一章已对本文需要解决的复杂任务群调度问题进行了建模，本章将介绍对该问题模型进行求解的算法。此类任务群调度问题是 问题，以遗传算法为代表的元启发式算法是解决此类问题的重要方法，所以本文所提出的 沿用了进化算法的框架，如图所示，算法具体由染色体编码、交叉变异、精英选择三大模块组成。图 算法框架 首先通过染色体编码将任务资源的匹配方式以染色体的形式表示，每一条染色体代表一种任务群调度方案，染色体的编码需要考虑 、节中的假设和约束；其次通过交叉变异扩大种群的多样性，即丰富调度方案的多样性；最后以 节提出的优化目标为评价指标，利用精英选择策略保留优良个体，对染第 期韩迪雅，等：融合局部搜索与 支配的多目标任务调度模型色体优中选优，直到达到进化结束条件并生成最优解集，在最优解集中任一染色体均可作为最优个体，通过解码获得最优调度方案。各模块具体描述将在后续章节进行详细介绍。染色体编码染色体编码是将任务与所需资源调度问题的解以基因位组合成的形式表达出来，本文采用分段编码（，）的方式对染色体分为资源选择部分（，）和原子任务排序部分（，）分别编码。染色体编码结构如图 所示，分别代表 的每个原子任务，表示资源选择部分基因位按照任务中原子任务的顺序依次排列；每一个基因值表示当前原子任务在其可选资源集中的位置，如 对应基因位的值为 ，表示选择可选资源集中的第二位，即；原子任务排序部分的每一位基因用任务在任务群中的编号直接编码，任务号出现的顺序代表原子任务的资源使用顺序，如图 中该部分编码为 ，对应原子任务的资源使用顺序为 。图 染色体编码 交叉变异因为随机性的交叉与变异方式会导致大量非可行解的产生，所以本文设计了两种交叉变异算子来解决此问题。交叉算子将一对染色体资源选择部分的同一个基因位点进行交叉可以保证新选择的资源仍在可选资源集内，交叉过程如下：）在 ，）内随机生成两个整数 、；）对亲本染色体 和 的 、基因位分别进行交换；）经过交换所生成的新染色体为子染色体 和。变异算子本文设计了一种多点变异策略（，），保证基因位变异后染色体所表示的解依然可行。）资源选择部分随机选择一变异位点，在当前位点所表示的原子任务的可选资源集中随机选择另一资源，并用其在可选资源集中的编号替换当前位置基因值。）原子任务执行排序部分对原子任务排序部分采用互换变异策略，随机选择两个变异基因位点，交换其基因值，如图 所示。图 染色体变异 基于边界区域局部搜索的精英保留策略因为研究 表明局部搜索和多区域采样能有效提高解的质量，但是盲目的扩张搜索范围在增加发现优质解可能的同时会导致计算量过大从而使得收敛速度较慢，本文提出了一种基于边界搜索的精英保留策略（，），引导算法有目的地对种群周边区域进行探索，发现优质解的同时提高寻优速度，同时结合精英保留策略最大程度保留优质解作为下一代进化的亲本，促进种群整体向评价指标更优的方向迭代发展。主要包含快速非支配排序、边界区域局部搜索和精英保留三个部分，下面将对其进行详细说明。快速非支配排序以非支配分层的方式将种群进行层次划分，以本文所解决的双目标优化问题为例，如果个体 所表示方案的资源负载均方差和任务群完成时间均小于个体 所表示的方案，则 ，读做 支配 ，即 的支配层级高于 。优先将分层靠前的个体加入下一代种群，使得优良个体有更大的概率保留下来，从而使种群不断向 前沿进化。快速非支配排序步骤如下：）遍历种群，计算每个个体 的 和。其中 为种群中支配 的个体数量，为种群中被 支配的个体集合，初始化非支配等级数 。）找出种群中所有 的个体，将它们存入集合 （），即非支配等级为 。）对于 （）中每个个体 ，其所支配的个体集合为，遍历 中的每个个体 ，执行 ，若 ，则将个体 加入集合 。）以 作为新的种群，回到步骤 ），直到将种群中个体全部分级。边界区域局部搜索具体来说，经过快速非支配排序，种群被划分为若干层级。定义单个目标函数上表现最优的个体为边界点，每个层级的所有边界点构成当前层级边界点集合，以所有 为中心进行局部搜索，如果搜寻到支配 的个体，则将新个体加入种群，转向搜索下一边界点，否则继续以该点为中心搜索。利用边界范围局部搜索，避免优良个体处于停滞进化的状态，从而引导种群发展跳出局部最优，防止算法早熟。种群层级划分与边界点如图 所示，示例中种群被划分为个层级，由 个边界点组成边界点集合，其中两个目标函数均向最小化方向寻优。算法伪代码如下：算法 边界区域局部搜索输入：种群 。输出：加入局部更优解的新种群 。说明：种群中非支配层级数 局部搜索步长 染色体长度 ，（，）（）的边界点集合 （），基因匹配位 中对 、位点进行变异 将 加入种群 精英保留规模为 的父种群 和子种群、经过合并与边界区域局部搜索后，形成规模为 的新种群 ，其中 为通计 算 机 应 用 研 究第 卷过搜索发现的新个体数。经过种群分层与个体拥挤度计算，每个染色体都具有两个属性，分别是非支配等级 和拥挤度，为了构成规模为 的新一代父种群 ，优先选择非支配等级数小的个体。直到添加到 （），此时种群规模超过，对 （）中的所有染色体进行拥挤度排序，选择拥挤度更大者，直到生成规模为 的新种群 。图 种群分层和边界点 算法流程基于以上模块，算法整体流程如图 所示。首先利用分段编码的方式将任务资源组合方案转换为由基因组成的染色体，并生成初始化种群；其次采用混合交叉与多点变异策略生成两个子种群、，并将新生成的染色体种群与父种群 合并；最后利用基于边界搜索的精英保留策略选择最优质的染色体构成下一代父种群，继续进化，直到达到最大进化代数，并找出最优解。图 算法流程 实验设计与结果分析 实验环境本章实验均使用 编程实现，运行环境为 （四核 ，内存）。为验证本文所提出的多目标优化算法 的性能以及在解决复杂任务群调度问题上有效性设计了两个对比实验。用于对比的算法有标准 、基于多邻域局部搜索的 和基于精英分布局部搜索的 。其中实验 为算法性能测试，该实验使用 个双目标优化问题常用的测试函数，通过相应的评价指标量化对比算法计算得出的 前沿与函数本身真实 前沿的拟合程度，从而对算法的性能进行评估；实验 为 在解决实际复杂任务群调度问题中的有效性测试，以资源负载均方差和任务群完成时间这两个目标作为评价指标，对比各算法在相同进化代数下的表现。实验 设计与结果分析因为无法确切地知道自定义的多目标优化问题真实 前沿所在的位置，所以本实验使用双目标优化问题常用的 系列测试函数 对算法的寻优性能进行测试，系列函数有真实的 前沿，且均为多变量的无约束优化问题，能够很好地测试优化算法的性能，函数具体内容如表 所示。表 测试函数具体内容 测试问题目标函数约束条件和特征 （）（）槡 （），真实 凸 （）（）()()（），真实 凹 （）（）槡()（）（），真实 凸且非连续 （）（）槡 （）（）（），真实 凸多目标优化算法需要紧密围绕着如何实现以下两个目标来设计：）非支配解集要尽可能地向问题的 前沿靠近；）使各个解均匀分布在非支配解集中。从以上两个目标出发，选用解的多样性 和解的收敛性 作为性能评价指标，其定义如下：）解的多样性 。（）（）其中：为非支配解集规模；为算法所求得解集中相邻两解之间的距离；和 是非支配解集两个边界点与真实解集边界点之间的距离；为 的平均值；越小解的多样性越优秀，当非支配解集完全均匀分布在真实 前沿时，。）解的收敛性 。（）其中：为非支配解集规模；为非支配解集中第 个解与真实 前沿中所有参考点之间欧氏距离的最小值；越小，算法趋向真实 前沿的程度越好，当算法所求得的非支配解集与真实最优解集重合时，。算法 、实验参数设置如下：初始种群规模为 ，最大迭代次数为 ，交叉概率 为 ，变异概率 为 。设置最大计算量为 ，使用 第 期韩迪雅，等：融合局部搜索与 支配的多目标任务调度模型系列测试函数对每个算法重复 组实验，并采用收敛性 与多样性 的均值进行量化计算，实验结果如表 和 所示。表 收敛性实验结果 测试函数算法收敛性指标 均值标准差 表 多样性实验结果 测试函数算法种群多样性指标 均值标准差 根据表的实验对比结果，所求得 解集的收敛性在 上均优于同组对比算法，说明 算法所求得的 最优解集更接近于真实 最优解集。以标准 算法收敛性均值和标准差为基准，在 上的平均优化比例分别为 和 ；在 上的平均优化比例分别为 和 ；在 上的平均优化比例分别为 和 ；在 上的平均优化比例分别为 和 。根据表的实验对比结果，所求得 解集的多样性在 上均优于同组对比算法，说明通过 算法得到的 解在前沿上分布得更均匀，种类更丰富。以标准 算法多样性的均值和标准差为基准，在 上的平均优化比例分别为 和 ；在 上的平均优化比例分别为 和 ；在 上的平均优化比例分别为 和 ；在 上的平均优化比例分别为 和 。综上，本文所提出的融合边界范围局部搜索的多目标优化算法 较标准 在综合性能方面有明显的提升，在保证收敛性的同时增强了种群多样性，同时，结合基于多邻域局部搜索的 和基于精英分布局部搜索的 的实验结果，验证了引入局部搜索对算法寻优能力的积极影响。实验 设计与结果分析为了验证本文所提的 算法在实际场景中复杂任务群调度方面的有效性，本节结合真实案例数据，整理形成了符合实验要求的三种规模的仿真算例，详细信息如表 所示。表 算例规模 算例编号任务群规模原子任务总数资源数 四种算法的初始种群规模均设置为 ，交叉概率 为 ，变异概率 为 ，交叉部分均采用混合交叉方法，在变异部分，采用本文提出的多点变异策略 ，、和 采用随机变异策略，每组实验都进行 次进化迭代，实验目的在于对比进化代数相同时，不同算法所得出的平均任务群完成时间和平均资源负载均方差的差别。与三种对比算法的目标值随进化代数的变化情况如图 所示，结果表明：）由于算例规模的不同，算法达到收敛时所需代数也有所差异，但 算法始终能够在 代以内实现收敛，而标准 、达到收敛时的代数始终大于 ；）从算法最终收敛到的目标值结果来看，的求解较标准 有显著的提升，同时明显优于 和 。图 算例 运行结果对比 图 算例 运行结果对比 图 算例 运行结果对比 最终生成的种群分布与标准 的对比情况计 算 机 应 用 研 究第 卷如图 所示，其中“”点构成 最优解集，算法所找出的 解集中的解在每个优化目标上均优于原始 最终解集中的解，即选择 算法的 解集中的任意解，都能够得到资源负载均方差更小、任务群完成时间更短的调度方案。图 种群分布对比 因为本文的两个优化目标都是向最小化的方向寻优，而相较于标准 ，改进后的 算法的种群整体分布明显更靠近于坐标系的左下方，所以结果显示 算法最终生成的种群整体上更为优质。结束语本文首先以最小化任务群完成时间和最小化资源负载均方差为目标构建了复杂任务群资源调度模型；其次针对复杂任务群资源调度模型的求解，提出了一种融合边界区域局部搜索策略的多目标优化算法 ，利用混沌变量扩大了算法的搜索范围；最后，通过仿真实验与现有标准 、和 进行对比，结果表明 的解有更好的收敛性与多样性，同时有效提高了收敛速度，所生成的方案在目标值上的表现更优质。目前的研究是针对双目标优化问题展开的，后续工作将尝试把本文的思想融入当目标维数大于 时的高维多目标优化问题，以解决更复杂场景下的应用问题。参考文献：，：，：，：，：张怀强，卢远超，王孟 混合遗传算法的战时舰艇伴随保障人员优化配置 火力与指挥控制，（）：（，（）：）张莉莉，杨文文，罗冠聪 面向时间优化的“任务人员”匹配逆最优值方法：以石化设备抢修为例 中国管理科学 ：（，“”：），：，：陈芮莹，王承涛，刘振元 考虑服务水平的 运维人员调度的智能遗传算法 系统仿真学报，（）：（，（）：），（）：，：，：，：，：，：，：，（）：，：，（）：，：，：，：张闻强，邢征，杨卫东 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题 计算机应用，（）：（，（）：），：，：，：，（）：，：，（）：第 期韩迪雅，等：融合局部搜索与 支配的多目标任务调度模型