基于改进NSGA-II 算法的多目标云制造服务组合优化研究＊

2023-10-24袁东维凤飞龙

制造技术与机床 2023年10期

袁东维凤飞龙

（①西北政法大学管理学院，陕西西安710122；②陕西师范大学物理学与信息技术学院，陕西西安710119）

随着全球经济一体化的发展，单一的制造服务已经无法满足生产需求。云制造作为一种面向服务的网络化制造新模式，其以客户为核心、以知识为支撑，构建了一个虚拟化、分布式以及按需分配的资源共享平台[1]，企业将自身的技术设备等制造资源和业务功能进行服务化封装，发布到云制造服务平台，由平台按需调配，极大程度地盘活了制造资源，提高了企业的竞争力。

当单个云制造服务无法满足日渐复杂的制造任务时，云平台会根据现有云制造服务的粒度，将制造任务分解为若干子任务，从众多功能属性相同而服务质量（quality of services， QoS）不同的云服务集[2]中为每个子任务匹配相应的服务，形成云服务组合。如何获得QoS 最优且契合用户需求的服务组合是目前国内外学者关注的重点。

群智能算法是当下解决云服务组合优化的主流方法[3-7]，Pan W 等[4]将遗传算法和混沌思想相结合实现种群优化，提高了服务组合的效率，但组合的可靠性没有明显改善；Seghir F 等[6]采用人工蜂群算法提高算法的搜索能力，优化结果显著提高，但其在构建组合优化求解模型时，主要关注服务自身的QoS 属性；齐琦等[7]采用邻域搜索和模拟退火算法来改进NSGA-II 算法的局部搜索能力，其云服务组合能力得到极大的提升，但NSGA-II 算法在目标维数过高时，算法运行效率低，优化效果不明显；赖文星等[8]提出了基于支配强度的改进NSGA-II 算法，该算法在多个领域取得较好的结果。本文改进了支配强度的概念，提出了基于改进NSGA-II 算法的云制造服务组合优化方法，具有以下特点：

（1）针对多目标优化Pareto 前沿解集过大，改进了支配强度的概念，可以快速有效地确定个体的优劣。

（2）优化局部搜索能力，在算法前期重点搜索优秀个体，加速算法收敛，算法后期则对稀疏个体融合邻域搜索与模拟退火算法来增加种群多样性，使算法能够更好地处理多目标优化问题。

1 云制造服务组合优化模型

在云制造服务组合中，用户需求被抽象表示为一个制造任务T，每个制造任务在云平台中被分解为n个子任务，即T={S T1,S T2,···,S Tn}，子任务在云平台中对应的服务集合为{CS1,CS2, ···,CSn}，其中第i个子任务的候选服务集合CSi={CSi1,CSi2, ···,CS im}，表示第i个子任务共有m个候选制造服务，它们都能完成相同的功能属性。

云制造服务组合就是从各候选服务集合中选择一个具体的制造服务来完成用户需求。

1.1 QoS 评价指标

云制造服务既考虑服务本身的质量，又对线下制造部分充分挖掘，采用的QoS 评价指标有以下5 个。

（1）服务时间C1：指用户提出服务请求到服务执行结束所需要的时间。

（2）服务成本C2：指用户获得服务所支付的费用，包括制造成本、物流运输成本和服务成本。

（3）服务可靠性C3：指成功执行云制造任务的能力，一般指产品质量的达标率。

（4）交工准时性C4：指云制造服务商的按时交货率。

（5）服务满意度C5；指用户在服务完成后，对云制造服务商整体服务的满意度。满意度的评分规则借鉴文献[9]中的量化规则，划分为 5 个等级，各级赋分为非常不满意（1 分）、不满意（3 分）、基本满意（5 分）、满意（7 分）、非常满意（9 分）。

1.2 云制造服务组合优选方法及模型

云制造服务组合工作流程内部结构复杂，但其主要结构包括四种模式：顺序、并行、选择和循环[10]。不同组合模式下的云制造服务组合QoS 计算模型见表1，其中， γi是候选云制造服务Si被选中的概率，且=1； λ为服务Si的循环次数。

表1 不同模式QoS 计算模型

则构建的云制造服务组合优化模型如下：

式中：QC1表示云制造服务组合总的时间，QC2、QC3、QC4和QC5分别表示云制造服务组合总的成本、总的可靠性、总的交工准时性和总的服务满意度。约束条件（3）表示制造服务组合总时间和成本不能超过用户给定的最长时间Tmax和最大成本Cmax。

2 云制造服务组合优化算法

云制造服务组合优选问题是一个多目标优化问题，非支配遗传算法NSGA-II[11]是目前解决这类问题的最优秀的算法之一。但是当目标函数的维数过高时，会导致帕累托前沿上解集过大，算法的收敛度显著下降；同时NSGA-II 算法自身缺少良好的局部搜索能力，在优化过程中容易陷入局部最优解。本文通过改进支配强度概念来快速有效地确定Pareto 最优解个体的优劣，在NSGA-II 算法的基础上构建灵活的局部搜索策略。算法流程图如图1 所示，算法实现步骤如下。

图1 算法流程图

步骤1：初始化种群，为保证初始种群有足够的数量，随机生成种群大小为N的1.2 倍的初始种群P0，检查约束条件（3），删除违反约束条件或者重复的个体，然后对种群进行快速非支配排序[8]，计算个体的非支配等级、支配强度和拥挤距离。

步骤2：对当前种群Pt（t为种群代数）进行锦标赛选择，选出种群Pt中的优秀个体，并对其进行均匀两点交叉和基本位变异，得出子代种群Ps。

步骤3：合并父代种群Pt和子代种群Ps，对混合种群进行非支配排序，计算其中个体的的非支配等级、支配强度和拥挤距离，选出规模大小为N的新种群Pg。

步骤4：取新种群的部分个体进行局部搜索，将其得到的非支配解加入到外来种群当中。

步骤5：将外来种群与新种群Pg合并，淘汰不良个体，得到规模大小为N下一代种群Pt+1。

步骤6：判断当前迭代次数t与最大迭代次数Gmax的大小，若t≤Gmax，则转步骤2 ；否则跳出循环，按综合评价值降序输出 Pareto 最优解集。

2.1 编码方式

根据云制造服务组合的特征，采用自然数编码方式，对各子任务对应的候选云服务集中的服务进行编码，每个子任务选择的服务编码作为相应染色体上的基因位。例如云制造服务组合序列CS13-CS26-CS32-CS47-CS52，表示的编码序列为[3 6 2 7 2]。

2.2 支配强度及个体间的比较

当目标函数维度过高时，基于Pareto 支配寻优很难评判个体优劣，导致Pareto 前沿解集过大，使算法的性能下降。引用支配强度[9]来比较非支配集中个体的优劣。因为本文同时有最大值和最小值优化，所以对非支配集中个体i的支配强度定义如下：

式中：Ckmax、Ckmin分别代表第k个子目标的最大值和最小值。

改进后的NSGA-II 算法经过非支配排序、支配强度计算及拥挤距离计算后，每个个体就有了三个属性：非支配等级Ranki、支配强度 ξi和拥挤距离Di。对于任意两个个体i和j有以下的的优先级关系：

2.3 局部搜索

由于NSGA-II 算法前期仍然存在搜索随机性差、收敛速度慢、算法后期解的分布均匀性较差[12]等问题，针对这种情况，本文提出与进化代数相关的局部搜索策略。在进化代数的前半部分，对优秀个体进行邻域搜索，以加速算法收敛；而在算法后半部分，选择拥挤距离最大的个体，采用邻域搜索和模拟退火算法来增加解集的广泛性。局部搜索流程如图2 所示，R为执行局部搜索的次数，种群的规模为N。

图2 局部搜索流程图

2.3.1 邻域搜索

算法中每个基因位对应的是具体的云制造服务，本文采用随机选择1-opt 交换、2-opt 和3-opt 交换的邻域搜索方式，对候选云制造服务组合进行搜索，具体操作如图3 所示。

图3 邻域搜索方式

2.3.2 模拟退火操作

在当前非支配解中以拥挤距离最大的解作为稀疏解，引入模拟退火操作对其进行局部搜索。由于模拟退火算法是单目标优化算法，对于多目标优化问题，算法随机选取一个目标函数作为搜索方向，将所获新个体放入外来种群。

2.4 优选策略

得到非支配解集后，需要选择满足用户偏好的最优云制造服务组合。对于用户偏好的权重分配，本文借鉴文献[13]的方法，由用户及行业专家对QoS 指标进行两两对比，得到n阶初始矩阵A=(Cij)n*n，其中：

对A中的每一行求和得到模糊矩阵：Q=(q1,q2,···,qn)T

其中：

各目标函数的权重向量依次为

由于云制造服务的QoS 指标量纲不同，不能直接进行选优，因此使用归一化方法对各指标进行规范化处理，见式（1），其中QC1、QC2为成本型目标函，QC3、QC4、QC5为效益型目标函数。

则在最后的Pareto 最优解集中，第h个候选云制造服务组合的综合评价值为

3 实验与结果分析

3.1 实验描述与分析

本节以一个小型电动车驱动系统制造任务为例，验证本文算法进行云制造服务组合优化的可行性。云平台将电动车驱动系统制造任务分解成5 个制造子任务，如图4 所示，每个子任务匹配到5 个符合制造要求的云服务，各候选云服务集参数见表2。

图4 电动车制造工艺流程图

表2 候选云制造服务集相关参数

本文在Matlab 2017 环境下进行多目标优化求解，企业要求总成本不超过18 000 元，服务周期不超过320 个单位时间。设置实验种群规模N=100，交叉概率0.95，变异概率0.04，最大进化代数Gmax=100，生成初始种群，按照第2 节所述步骤进行，直到输出非支配解集。对用户偏好进行两两对比得到5 阶初始矩阵A：

对A中的每一行求和，计算得到QoS 各指标权重见表3。