面向个性化定制需求的异构制造资源服务组合优化方法

Optimization Method for Heterogeneous Manufacturing Resource Service Composition Catering to Personalized Customization Demands

摘要: 工业制造任务日趋复杂，组件服务组合优化问题相关的指标日益增多，需要综合考虑各个评价指标，从备选服务中筛选出最优服务组合。本文针对工业制造的特点，从服务成本、服务时间等服务质量(QoS)指标构建了组件服务评价指标体系。为了处理高维多目标优化问题并针对非支配排序遗传算法(NSGA-Ⅱ)只能求得最优解集的特点，本文提出改进ε-约束策略融合Pareto支配改进NSGA-Ⅱ算法，并将NSGA-Ⅱ和模糊决策相结合，利用模糊决策从最优解集中寻找最优解。

Abstract: With the increasingly complex tasks in industrial manufacturing, the metrics related to the optimization of component service combinations are growing. It’s essential to comprehensively consider various evaluation metrics to filter out the optimal service combinations from alternative services. This paper, targeting the characteristics of industrial manufacturing, constructs a framework of evaluation metrics for component services based on QoS indicators such as service cost and service time. To address high-dimensional multi-objective optimization problems and considering the lim-itation of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) in obtaining only the optimal solution set, this paper proposes an improved ε-constraint strategy integrated with the Pareto dominance-enhanced NSGA-II algorithm. Additionally, it combines NSGA-II with fuzzy deci-sion-making to search for the optimal solution within the obtained optimal solution set using fuzzy decision-making methods.

1. 引言

近年来，工业与城市互联网环境工业软件系统具有规模庞大、涵盖的软件组件与设备实体繁杂异构、跨平台、跨操作系统、跨编程语言、跨网络，跨IT/OT域集成等典型特征，工业软件组件实现对繁杂异构软件组件与设备实体进行服务化、组件化、标准化封装，提供统一的互操作访问接口，从而支撑灵活敏捷的大型工业软件系统构建开发。随着工业制造复杂程度的提高以及个性化需求增多，实现制造资源与组件服务的最优组合与配置，避免资源的闲置与浪费，是促进工业制造模式向传统制造产业深度融合与应用的关键技术之一。

服务组合是在制造环境下完成制造任务的主要实现方式，如何从大量服务组合中选择出最符合要求的服务组合方案，是目前服务组合面临的难题。国内外学者对服务组合优化问题不断探索，取得了一定的研究成果。Liu等人 [1] 提出了一种基于相似度的可信度计算模型，并通过相似度的倒数将其与QoS发布值相结合，使Web服务的QoS满足实际运行效果。Arunachalam等人 [2] 提出了一种基于改进余弦相似度的Web服务组合人工蜂群优化方案，从响应式服务组合过程中生成的工作流建模图中确定最优候选服务解决方案。尹超等人 [3] 通过建立包括非功能属性与历史评价属性的云制造服务评价指标体系来评估服务优选组合过程。翟振坤 [4] 提出一种扩展型 NSGA-II算法，通过改进协同进化算子和次优解筛选机制，提高 NSGA-II 在复杂优化问题应用环境中的算法性能。

在工业制造环境中，针对同一个子任务有大量功能属性相同但非功能属性不同的组件服务，组件服务的非功能性属性通常用QoS (服务质量)来描述 [5] 。在实际应用中，组件服务的QoS指标众多，QoS指标间往往是相互冲突的，且转化为单目标优化问题进行求解时极容易陷入局部最优解。本文综合考虑工业制造环境下的情况，提出了一种新的组件服务组合数学模型，该模型以服务时间、服务成本、服务可用性、服务能耗、服务满意度为指标体系，运用基于ε-约束法的NSGA-Ⅱ算法对该模型进行求解，使算法能够更好地处理高维多目标优化问题并消除量纲影响。对于求得的Pareto解集，采用模糊决策法对解集中的所有组合方案进行评估，为选取最优服务组合提供参考。

2. 工业软件组件服务组合优化模型

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

2.1. QoS评价指标体系

工业软件组件服务需要更多地考虑服务需求方的需求和工业制造场景的特点，并结合指标的可量化性，选取服务成本、服务时间、服务可用性、服务能耗、服务满意度5个指标，构建QoS评价指标体系。

1) 服务成本C。服务需求方提交服务请求到取得服务结果所花费的总时间。可表示为

$C=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}{c}_i,i=1,2,\cdots ,n$ (1)

式中，c_i为子任务i对应服务提供方完成子任务的成本。

2) 服务时间T。从服务需求方提交任务开始，到获得服务结果所花费的总费用。可表示为

$T=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}{t}_i,i=1,2,\cdots ,n$ (2)

式中，t_i为子任务i对应服务提供方完成子任务时间。

3) 服务可用性A。可表示为

$A=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\frac{{{\displaystyle \sum }}_{i=1}^n{a}_i}{n},i=1,2,\cdots ,n$ (3)

式中，a_i为子任务i对应服务提供方完成子任务时间，n为子任务数。

4) 服务能耗E。在生产制造过程中产生的能源消耗E，可表示为

$E=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}{e}_i,i=1,2,\cdots ,n$ (4)

式中，e_i为子任务i对应服务提供方完成子任务时间。

5) 服务满意度S。组件服务组合的满意度是服务需求方对各个服务提供方通过打分得到的历史服务评价结果，取值在0~1之间，数值越高，表示服务提供方的服务水平越好。可表示为

$S=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\frac{{{\displaystyle \sum }}_{i=1}^n{s}_i}{n},i=1,2,\cdots ,n$ (5)

式中，s_i为服务需求方对子任务i所对应的服务提供方的服务满意度打分评定结果；n为子任务数。

2.2. 多目标组合优选模型

组件服务组合的总体目标是使得所优化指标，即服务成本、服务时间、服务能耗最小、服务可用性、服务满意度最高来完成制造任务。本文建立的组件制造服务组合优化模型如下：

$F\left(X\right)=\left(\min C,\min T,\min E,\max A,\max S\right)$ (6)

$\text{s}\text{.t}.\{\begin{array}{c}C\le C_{\max }\\ T\le T_{\max }\\ E\le E_{\max }\\ A\ge A_{\min }\\ S\ge S_{\min }\end{array}$ (7)

目标函数(6)表示服务组合的服务成本、服务时间、服务能耗尽可能达到最小化，而服务可用性、服务满意度需尽可能达到最大化。5个约束分别表示模型中的服务成本C不超过服务需求者规定的最高成本C_max，服务时间T不超过服务需求者规定的最长时间T_max，服务能耗E不超过服务需求者规定的最长时间E_max，服务可用性A不低于服务需求者规定的最低可用性A_min，服务满意度S不低于规定的最低服务满意度S_min。

3. 工业软件组件服务组合优化算法

3.1. ε-约束法

在目标函数维度较高时，基于Pareto支配的多目标进化算法会遇到收敛度显著下降的问题。在NSGA-Ⅱ算法对于3个以上的目标时性能会显著下降，按照Pareto支配的定义，当一个个体A只要没有在所有指标上等于且至少有一个优于个体B，则这两个个体之间互不支配，在高维度目标时这就很难找到一个个体支配另一个个体，导致Pareto前沿上的解集过大，使得算法的寻优能力大大降低。因此本文将从约束条件处理方面，将ε-约束法加以改进并由于对NSGA-Ⅱ算法进行改进。

根据式(6) (7)的多目标优化模型，我们定义约束违反度：

$O\left(x\right)=\underset{x\in X}{{\displaystyle \sum }}\left[f\left(x\right)+\left|f\left(x\right)\right|\right]$ (8)

其中，X为可行域，f(x)为误差度，我们定义为：

$f\left(x\right)=\{\begin{array}{c}\sum Q_{\min }-Q越大越好的\text{QoS}\\ \sum Q-Q_{\max }越小越好的\text{QoS}\end{array}$ (9)

式中，Q_min、Q_max为所规定的每种QoS指标的上下限，Q为每种QoS的值。

当在进行快速非支配排序时，当个体X₁和个体X₂的违反约束度均小于等于ε时，则两者均视为可行解，此时O(x)为0，按照原有步骤确定支配关系；当X₁的约束违反度小于等于ε，X₂的约束违反度大于ε时，则认为X₁支配X₂；当X₁和X₂的约束违反度均大于ε，且X₁的约束违反度小于X₂的约束违反度时，则认为X₁支配X₂。

ε-约束法的关键在于确定ε的值，在迭代初期，为了让部分有较好基因但为不可行解的个体能遗传到下一代，ε应设为较大值；在迭代后期，为了使结果收敛为可行解，ε应趋于0。按照这个思想，设计ε的公式为：

$\epsilon \left(n\right)=\max \left[{\epsilon }_{\max }-\frac{{\epsilon }_{\max }}{n}\left(n-1\right),0\right]$ (10)

式中n为当前迭代代数；ε_max为迭代代数为1时的ε值。

3.2. 基于ε-约束法的NSGA-Ⅱ算法

本文利用基于ε-约束法的NSGA-Ⅱ算法对组件服务组合优化问题的多目标优化模型进行求解，具体步骤如下：

步骤1：初始化种群，随机生成大小为N的种群P，设置种群规模、进化代数、交叉概率、变异概率及ε_max的值。对于每个个体采用整数编码的方式，根据备选组件服务的序号对各个组件服务进行编码。

步骤2：对种群P进行基于ε-约束法的非支配排序和所有个体拥挤度的计算。

步骤3：对父代种群P进行锦标赛竞选，我们将每次选取种群规模的60%个体进行比较，选择非支配序小且拥挤度大的个体。根据组件服务的特点，本场景下的组合优化问题适合使用整数编码的均匀两点交叉以及邻近变异产生子代，最终得到子代种群Q，并将父代和子代种群合并(P + Q)。

步骤4：整数编码在交叉变异后可能会产生重复的个体，影响了种群的多样性，因此需要对重复的个体进行剔除，并补充随机新个体直至种群规模为2N。

步骤5：对新种群进行基于ε-约束法的非支配排序及拥挤度计算，并根据等级排序及拥挤度选出种群大小为N的下一代父代种群P_n+1。

步骤6：判断此时是否达到进化的最大代数，若是则结束迭代并输出最终的非支配前沿解集；若还未达到则重复步骤3~5直至进化最大代数。

3.3. 基于模糊决策的组合优选算法

当得到非支配前沿解集后，需要从解集中选出最适合的一种组合服务。模糊决策是指在模糊环境下进行决策的数学理论和方法。其原理为将模糊技术应用到决策过程中，使用模糊事实、模糊规则来描述决策过程中存在的不确定性和不准确性，通过使用模糊推理技术获得决策候选方案以及使用模糊综合评判以获得最佳决策方案。本文采用模糊优选法的基本理论构建多目标模糊优选模型。总体的步骤为：

1) 确定评价指标，评价指标数量为m。(QoS数量)

2) 确定评价指标等级，数量为o。(给每种QoS评价优劣的等级)

3) 确定评价指标的权重向量 $A=\left(a_1,a_2,\cdots ,a_m\right)$ ，其中∑a_m = 1，a_m > 0。

4) 进行单因素模糊评价。针对每个非劣解计算其各个指标等级的隶属度，得到模糊关系矩阵R，R是m行o列矩阵。

5) 多指标综合评价。利用权矢量A和模糊关系矩阵R合成模糊综合评价结果矢量B，即B = A∙R，其中B中值最大的方案即为最优方案。

若Pareto解集中有n个备选方案，在选择方案时需要综合考虑m个目标对每个方案的影响，那么可以构建指标矩阵如下：

$X=\left[\begin{array}{cccc}{x}_{11}& x_{12}& \cdots & x_{1n}\\ x_{21}& x_{22}& \cdots & x_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ x_{m1}& x_{m2}& \cdots & x_{mn}\end{array}\right]$ (11)

矩阵X中x_ij表示第j个方案中第i个目标的QoS值。

由于各个目标的基本参量不同，为了便于对各个方案进行评价，首先要对QoS属性值进行归一化，即求出各个目标值的相对优属度。

${x^{\prime }}_{ij}=\{\begin{array}{l}\frac{x_{ij}-x_{\min }}{x_{\max }-x_{\min }},目标值越大越好\\ \frac{x_{\max }-x_{ij}}{x_{\max }-x_{\min }},目标值越小越好\end{array}$ (12)

本文的隶属函数选取如下：

$f_{ij}=\{\begin{array}{l}1f_{ij}<f_{i\min }\\ {x^{\prime }}_{ij}{f}_{i\min }<f_{ij}<f_{i\max }\\ 0f_{ij}>f_{i\max }\end{array}$ (13)

式中f_ij为在Pareto解集中的第j个最优解在第i个QoS指标数值的隶属度；f_imin为第i个QoS指标数值下限；f_imax为第i个QoS指标数值上限。

本文前半部分是利用基于ε-约束法的NSGA-Ⅱ求解出收敛种群对应的Pareto解集，再利用模糊决策对求解出的Pareto解集进行计算所得的多目标综合最优解。总体流程图如图1所示。

Figure 1. The flowchart of NSGA-Ⅱ algorithm was improved

图1. 改进NSGA-Ⅱ算法流程图

4. 实验与结果分析

4.1. 算例模型

为验证所提模型及方法的可行性和有效性，本文分别设计了算法测试和应用算例。实验在pycharm2022.2.2软件上实现，系统为Windows 10，内存8 GB。

本节模拟用户将制造任务和相关需求提交至平台，系统根据任务解析工具将制造任务分解的行为，以验证工业组件服务组合优化模型的可行性。由于尚未有公开的数据集，本文采用在合理范围内随机生成的模拟数据以验证模型。表1为5个子任务分配的候选资源服务，每个子任务会在初始时刻选择其中一个资源服务。

Table 1. Candidate service resources

表1. 候选服务资源

本文在pycharm 2022.2.2环境中进行多目标优化模型求解，T_max= 200 h，C_max = 1800元，A_min = 0.85，E_max = 200 kW∙h，S_min = 0.9。首先将工业制造任务划分为5个子任务，各子任务按照顺序结构执行，表示为{ST₁, ST₂, ST₃, ST₄, ST₅}；根据子任务的需求为其匹配相应的组件服务待选；最后为每个子任务选择一个资源进行随机组合，通过所选算法求出最优的组合方案集合。

4.2. 算例验证

采用种群规模为50，最大进化代数200，交叉概率0.95，变异概率0.05，ε_max = 20，生成初始种群；模糊决策的权重向量 $A=\left(0.3,0.15,0.15,0.3,0.1\right)$ 。通过算例仿真求解，输出的非支配解集及目标函数值如表2所示。其中服务组合中的数字表示对应子任务下备选组件服务的编号。

Table 2. Patrol solution set and the value of the objective function

表2. Patrol解集及目标函数值

根据求得的Pareto解集各组合服务的QoS参数指标构建模糊决策矩阵，根据权重向量的设定以及隶属度的确定，应用模糊决策算法对求得的Pareto最优组合服务进行评估，表3为求解的最优组合服务。

Table 3. The optimal Pareto solutions for service composition

表3. 服务组合最优Pareto解

本文在每个种群规模下采用两种算法分别独立进行5次实验，得到的平均最优解集的大小如图2所示。

Figure 2. The comparison of the number of individuals in the optimal solution sets of the two algorithms

图2. 两种算法最优解集个体数量对比

实验结果表明，与NSGA-Ⅱ算法相比，基于ε-约束法的NSGA-Ⅱ算法其非支配解集个体数目随种群规模扩大上涨不大，解集明显较小，大大减小了组合优选步骤的计算量；这是因为原NSGA-Ⅱ算法基于Pareto支配，在高维度情况下很难确定支配关系，从而导致解集几乎占据了整个种群，进而使得各个目标下的QoS指标值变差。

4.3. 结论

工业物联网的发展使得工业制造任务日趋复杂，本文分析了工业组件服务组合的重要性和服务流程，提出了一种以服务时间最少、服务成本最低、服务可用性最大、服务能耗最小、服务满意度最高的工业组件服务组合优化模型，为了使多个目标同时达到优化，运用基于ε-约束法的NSGA-Ⅱ对多目标数学模型求解，对于求得的Pareto解集，采用模糊决策法对解集中的服务组合进行综合评估，选取最符合需求的服务组合。通过算例实验论证，验证了所提模型和求解算法在解决工业组件服务组合问题的有效性和可行性。