基于NSGA-Ⅱ和TOPSIS算法的云制造服务组合优选模型

叶宗鑫，徐雷，余方超，高涵

（四川大学机械工程学院，成都 610065）

0 引言

随着物联网、云计算、大数据、5G通讯技术等新一代信息技术的快速发展及其与制造业的不断融合，各制造强国纷纷颁布了一系列以“智能制造”为主题的国家战略，例如美国工业互联网计划、德国工业4.0及中国制造2025等[1]。我国正面临向制造强国转型的阶段，整个制造行业资源使用率和共享程度会是一个关键突破点。云制造是在现有制造技术的基础上，受到云计算思想的启发，结合信息技术发展起来的一个新概念[2]。云制造通过建立制造资源共享系统，充分利用社会制造资源，实现了制造资源的集成共享[3]。云制造服务组合是在云制造环境下完成制造任务的主要实现方式[4]，如何从大量云服务组合中选择出最符合要求的服务组合方案，是目前云制造服务组合面临的难题。

近些年来，对于云制造服务组合问题的研究，已经获得了阶段性的成果[5]。如Seghir等[6]构建了时间、成本、可靠性、可用性综合最优的云制造资源模型，将遗传算法与果蝇算法相结合，提高了算法的搜索效率；Lartigau等[7]除考虑服务质量等参数外，还将范围扩展到制造资源的物理位置，通过自适应人工蜂群算法进行优化。如马文龙等[8]通过服务质量评估模型进行服务组合优选，运用改进蚁群算法在动态环境中减少转移时间和成本；易安斌等[9]对于云制造环境下制造资源异地的服务组合优选问题，建立了以时间、成本、可靠性的多目标模型；姚锡凡等[10]对人工蜂群算法进行了改进，引入食物源扰动的协同机制，来处理复杂的服务组合优选问题。

本文综合考虑服务需求方和云制造系统的利益，提出了一种新的云制造资源组合数学模型，该模型以执行时间、服务成本、交付物质量、云平台能耗、服务满意度为指标体系，运用NSGA-Ⅱ算法对该模型进行求解。对于求得的Pareto解集，采用TOPSIS法对解集中的所有组合方案进行排序，为选取最优服务组合提供参考。

1 云制造服务组合问题描述

云制造系统服务组合优选流程如图1所示。云制造系统包括服务需求方、服务提供方和平台运营方3个主体，在云制造环境下，服务需求方发送制造服务要求到云制造服务组合要经历任务分解、子任务搜索匹配、服务组合优选3个阶段。在任务分解阶段，服务需求方上传任务需求到云制造系统，云平台调用任务解析工具对整个需求按照一定的规则进行分解，分解得到的每个子任务能够被单个候选资源集满足；在子任务搜索匹配阶段，通过调用搜索匹配工具为每个子任务匹配相应的候选云制造资源集合，得到一系列候选资源集；在服务组合优选阶段，平台在多目标和多约束的条件下在各候选资源集中选取一个候选资源得到云制造服务优选组合，该服务组合用来执行服务需求方提交的总任务，整个服务组合过程由云制造系统进行跟踪和反馈。

图1 云制造服务组合优选过程

2 云制造服务组合数学建模

考虑云制造平台在服务执行过程中的动态性、不稳定性，为方便建立数学优化模型，作出以下假设：1）服务组合过程中不存在一个云制造资源同时为多个制造子任务服务的情况；2）以顺序结构作为云制造服务组合的研究对象。

2.1 约束指标

2.1.1 服务需求方约束指标

本文充分考虑服务需求方的需求和云制造服务运行特点，并结合指标的可量化性，选取执行时间、服务成本、交付物质量3个指标，构建服务需求方指标约束体系[11]。

1）执行时间T。服务需求方提交服务请求到取得服务结果所花费的总时间。表达式为

防止服务过程出现风险，云制造系统会对服务提供方的服务满意度P进行约束。为了减少环境破坏，发展低能耗、低排放的低碳经济，云平台运营方会增加对供应商的能耗E评估[12]。

1）能耗E。云制造平台在生产制造过程中产生的能源消耗E的计算公式为

2.2 多目标组合优选模型

云制造服务组合的总体目标是使得所优化指标，即服务需求方的QOS最小、云制造平台的能耗最低、服务满意度最高来完成制造任务。综合考虑服务需求方和云平台的约束指标，建立云制造服务组合数学模型：

5个约束分别表示模型中的执行时间T不超过服务需求者规定的最长时间Tmax，服务成本C不超过服务需求者规定的最高成本Cmax，交付物质量Q不低于服务需求者规定的最低交付物质量Qmin，能耗E不超过云平台运营方要求的云制造服务组合过程中产生的最大能耗Emax，服务满意度P不低于云平台规定的最低服务满意度Pmin。

3 模型求解

3.1 NSGA-II算法

本文所构建的云制造服务组合模型是一个多目标优化问题，与单目标优化相比，多目标优化问题在求解时，由于优化的多个目标存在着相互制约的关系，某些目标函数值的改进可能会削弱其余目标函数，所以不可能同时让多个目标达到最优。多目标优化的解通常是一组Pareto解集，其特点是在改进任一目标函数时，必然会导致至少一个其余目标函数的劣化。本文所选NSGA-II算法[13]是一种基于Pareto最优思想的多目标智能优化算法，它是由Deb和Srinivas在NSGA的基础上提出的，与NSGA相比，NSGA-II主要有以下三方面改进[14]：1）提出了新的非支配排序算法，算法复杂度下降了一个量级；2）精英保留策略，父代和子代种群共同竞争，选取最优良的个体来组成下一代的种群，保证了种群的整体水平；3）采取拥挤距离比较算子，确定同一层级个体中不同个体的拥挤度值，并且将其视为同级个体的比较标准，确保种群的多样性。使用NSGAII算法求解云制造服务优选组合模型的具体步骤如图2所示。

图2 NSGA-II算法流程图

步骤1:g=0，随机生成初始化种群Pg，种群数量为N，对种群Pg进行非支配排序和所有个体拥挤度的计算。

步骤2:通过锦标赛法，从种群Pg选取部分个体交叉变异，产生种群数量为N的子代种群Qg。

步骤3:合并Pg和Qg，形成种群数量为2N的种群Rg。

步骤4:对种群Rg的个体进行非支配排序，得到k个非支配解集F1，F2，…，Fk。

步骤5: 按照非支配解集排序从组合种群Rg依次选取种群个体，直到种群数量大于N，假设此时的非支配解集为Fi。

步骤6:若F1，F2，…，Fi中的所有个体数目超过N，对Fi中所有个体进行拥挤度计算。根据精英策略，选择Fi中较好的个体和F1～Fi-1中的所有个体合并组成种群数量为N的新种群Pg+1。

步骤7:令g=g+1，反复迭代步骤2～步骤6，直至满足流程终止条件。此时求解出云制造服务组合模型的Pareto解集。

根据云制造服务组合模型的特点，本文构造了NSGA-II算法的染色体基因编码、交叉和变异过程，具体表示如下:

1）染色体编码。采用整数方式编码，对每一个子任务所对应的候选制造资源进行编号，染色体{3，2，4，1，3}分别对应云制造服务组合{CMS13，CMS22，CMS34，CMS41，CMS53}，染色体基因编码串与云制造服务组合逐一映射，如图3所示。

图3 云制造服务组合与染色体映射关系图

2）交叉。用单点交叉处理处理云制造服务组合的交叉操作。单点交叉为在染色体编码串中随机选取一个点，在该点处相互交换两个个体的部分染色体，如图4所示。

图4 单点交叉遗传操作示意图

3）变异。依据变异概率，在染色体编码串上随机选取某个点进行变异，如图5所示。

图5 变异操作遗传示意图

3.2 服务组合优选算法

TOPSIS法是一种接近理想点的排序算法，由K. Yoon和C. L. Hwang于1981年提出，其基本原理是找出评价对象的正理想与负理想方案，依次计算各个方案与正、负理想方案的距离，确定各个方案与理想方案的接近程度，最后通过各个方案的满意度排序选取一组最优解[15]。本文运用TOPSIS法对Pareto解集中的多个服务组合方案进行求解，得到最优云制造服务组合，其算法处理流程如下：

步骤1:NSGA-II算法求得的Pareto解集构成初始化决策矩阵X=（xij）m×n。zi=A+，则Ci=1；zi=A－，则Ci=0；Ci的值越高，方案的满意度越好。

4 算例论证

4.1 算例模型

某企业用户将制造任务和相关需求提交至云平台，云制造系统根据任务解析工具将制造任务分解。5个子任务分配的候选资源服务如表1所示，表2为云制造候选资源指标参数。

表1 候选资源服务

表2 候选资源评价指标相关参数

根据服务需求方的制造需求和云制造系统的相关约束，服务组合中所需的算例参数分别为：WT=0.2，WC=0.4，WQ=0.4；Tmax=250 h，Cmax=2000 元，Qmin=0.95，Emax=400 kW·h，Pmin=0.87。结合式（8）可得云制造优选服务组合模型，并用NSGA-Ⅱ和TOPSIS算法求解。

4.2 算例仿真

采取最大迭代次数Gmax=200，交叉率Pc=0.9，变异率Pm=0.1，种群数量Np=50。通过算例仿真求解，实验结果如图6所示。图中每个圆点代表一个Pareto最优服务组合方案，可以看出通过NSGAII算法求解模型所得的服务组合数量为22个。

图6 Pareto解集示意图

根据求得的Pareto解集各服务组合的指标参数构建规范化决策矩阵，按照服务需求方的偏好和云制造系统的实际情况，执行时间、服务成本、交付物质量、云平台能耗、服务满意度对应的权重分别为0.15、0.30、0.30、0.10、0.15，应用TOPSIS理想解法对求得的Pareto最优服务组合进行排序，表3为求解的最优服务组合。

表3 服务组合的最优Pareto解集

根据表3结果，选择云制造资源［CMS13，CMS21，CMS32，CMS23，CMS44，CMS52］为服务组合的最优解,实验结果证明了算法与模型的有效性。此外，服务需求方可以根据实际需求偏好重新向云制造平台提交指标权重要求，云制造平台只需根据新的权重就可对Pareto解集中的服务组合重新排序，无需再进行求解，节省了双方大量时间。

5 结论

如何减少在云制造模式下的能耗，实现经济的可持续发展是未来国家智能制造发展的主要关注点。本文分析了云制造服务组合的重要性和服务流程，在充分考虑云制造平台在服务过程的不确定性前提下，提出了一种以执行时间最少、服务成本最低、交付物质量最优、云平台能耗最小、服务满意度最高的云制造服务组合优化模型，为了使多个目标同时达到优化，运用快速非支配排序遗传算法（NSGA-Ⅱ）对多目标数学模型求解，对于NSGA-Ⅱ求得的Pareto解集，采用TOPSIS优劣解距离法对解集中的服务组合进行综合排序，选取最符合服务需求方和云制造平台利益的服务组合。通过算例实验论证，验证了所提模型和求解算法在解决云制造服务组合问题的有效性和可行性。