基于改进型哈里斯鹰算法的云制造服务组合优化方法研究

摘 要：云制造环境下，云平台以制造服务组合的形式为个性化需求提供按需服务，可显著提升订单响应速度与提高资源利用率。采用哈里斯鹰算法构建制造服务组合，针对制造服务间物流转运问题，建立独特的编码与解码机制。为解决该算法存在早熟收敛问题，引入Logistic一维混沌系统，设计非线性逃逸能量更新机制和3种邻域搜索策略。通过实验验证了改进后的哈里斯鹰算法在解决云制造服务组合优化问题时具有显著优越性。

关键词：云制造；服务组合；哈里斯鹰算法；任务调度

中图分类号：TH164文献标志码：A文章编号：1671-5276（2024）03-0127-05

Research on Cloud Manufacturing Service Composition Method Based on

Improved Harris Hawks Optimization Algorithm

Abstract：In cloud manufacturing environment， the cloud platform provides on-demand services for personalized needs in the form of manufacturing service composition， which can significantly improve order response speed and resource utilization. This paper uses Harris Hawks optimization algorithm to construct manufacturing service composition， and establishes a unique coding and decoding mechanism for the logistics transfer between manufacturing services. In order to solve the premature convergence problem of the algorithm， the Logistic one-dimensional chaotic system is introduced， the nonlinear escape energy updating mechanism and three types of neighborhood search strategies are designed. Experiments verify the significant advantages of the improved Harris Hawk algorithm in solving the cloud manufacturing service portfolio optimization problem.

Keywords：cloud manufacturing; service composition; Harris Hawks optimization algorithm; task scheduling

0 引言

制造业技术的不断突破推动了智能制造领域的蓬勃发展。为解决产能过剩并提高分布式制造资源的利用率，制造服务优化配置问题受到了密切关注。

目前针对制造服务优化配置问题已经有很多研究成果。DAO等［1］针对多企业的协同生产问题进行深入研究，提出一种独特的遗传算法，使得求解效率大幅提高。AKBARIPOUR等［2］针对分布式制造资源之间的物流问题对服务质量的影响进行充分研究，提出一种混合整数规划模型。WANG等［3］在制造服务异常的情况下提出了一种新的编码形式，可以对制造服务的异常情况进行动态重构。ZHANG等［4］提出了制造社区的概念与一种基于多目标优化的制造服务选择和组合方法。LIANG等［5］提出一种基于深度强化学习算法的QoS-aware云制造服务组合优化方法，规避了元启发式算法参数设置复杂的问题。王平等［6］提出一种基于双层规划模型的资源服务组合方法并采用云遗传算法对模型进行求解。

目前大多数的优化配置模型对多个任务与多个子任务进行求解的较少。为此，本文提出一种基于改进哈里斯鹰算法，提高了全局的搜索能力，以最小化加工成本为目标，解决了分布式制造服务优化配置的问题。

1 制造服务优化配置问题分析

在云制造环境中，接受订单的主体企业会将一部分订单需求分配给合适的制造商，以减轻自己的生产压力。因此需要在满足制造任务要求的情况下，选取合适的制造商和合适的物流线路，使得所有任务的完工总成本最小，具体的问题研究模型如图1所示。

为了能够更加直观地描述这一模型，现对该模型进行如下假设：

1）每个制造任务的不同制造子任务在不同制造商可以并行加工，不同制造任务的总装任务也可以在主体企业并行完成。

2）不同的制造商与制造商之间，制造商与主体企业之间只有一次运输。

3）货物运输时运载能力为无穷大，同时货物都可以在一次运输的过程中完成。

基于以上假设，本文建立以最小化成本为目标函数的模型，目标函数如下所示。

F=CM+CT（1）

式中：CM表示不同制造商的制造成本；CT表示在整个生产过程中由于物流而产生的成本。

式（1）表示所有任务的制造成本包括制造商和主体企业的制造成本两部分；式（2）表示制造商的制造成本包括所有制造商的制造任务成本总和；式（3）表示物流成本包括制造商之间的物流成本（式（4））和运输到主体企业之间的物流成本（式（5））两部分。式中符号的描述如表1所示。

2 制造服务优化配置问题模型求解

2.1 编码与解码

本文主要考虑3个问题：多个制造任务、制造商的选择和物流方式的选择，因此种群编码也与这3部分有关，如图2所示。

图2中制造任务由制造任务数目与制造任务子任务的数目有关。深色序列的上半部分表示制造子任务序列，深色序列的下半部分表示制造子任务的制造商。物流运输选择包括物流节点序列和物流节点决策变量两个部分。物流部分的上方表示物流节点序列，其具体的节点序列与制造子任务序列有关，主要满足以下规则：

1）运输节点序列中有意义数目与第一部分的不重复制造商节点数有关；

2）运输节点序列的顺序与第一部分制造商节点的序列顺序相同。

转化后得到的物流部分编码如图3所示，无色部分无意义。深色上方序列表示运输节点序列，深色下方序列表示对应节点的决策变量。

决策变量的解析主要满足以下规则：

①具有相同的决策变量的运输节点在同一次运输过程中；

②不同的运输节点在同一个运输过程中，则物流路线总是从左侧向右侧运输；

③所有运输线路的终点都是主体企业；

④如果没有相同的决策变量，则该制造商完成任务后直接运输到主体企业。

根据以上规则，可以得出5条物流线路，其中4条分别是3号、5号、10号、6号直接运输到主体企业；第5条物流线路是4号，首先运输到1号然后再运输到主体企业。

2.2 种群初始化

为了使算法的初始解具有更强的全局搜索能力，引入一维logistic混沌系统，如式（6）所示。

x（i+1）=μ×x（i）×（1－x（i））（6）

初始化流程如下（图4）。

1）生成小数序列：随机生成范围为（0，1）的28个混沌个体与种群的28个维度相对应，完成第一步初始化。

2）整数化：取得的28个混沌个体，扩大10倍，并向上取整得到整数序列。

3）物流编码处理：在整数序列中，前18位是制造商选择部分，后10位是物流部分。将制造商选择部分在不改变顺序的情况下，除去重复的制造商，得到运输节点序列。

2.3 种群更新策略

本文提出MHHO（Multi-HHO）算法，在HHO算法的基础上通过改进逃逸能量更新策略和增加邻域搜索策略两种方式，增加算法的全局搜索能力，改进后的HHO算法（MHHO）流程如图5所示。

搜索阶段如式（7）和式（8）所示，在开始阶段，HHO算法会根据初始种群，在可行解空间内进行搜索。

式中：x（t）和x（t+1）分别表示本次迭代和下一次迭代过程中哈里斯鹰的位置向量；xm（t）表示本次迭代中哈里斯鹰种群的平均位置；xrand（t）是猎物的位置；r1、r2、r3、r4和q是区间（0，1）中的随机数；UB、LB分别表示变量的上限和下限；xrand是当前种群中随机选择的哈里斯鹰的位置；N表示种群数量。

由图5可以看出，开发阶段较为复杂，HHO算法会根据猎物的捕捉概率r和猎物的逃逸能量E两部分确定哈里斯鹰的迭代点位。逃逸能量的更新如式（9）所示。

E=2×（1－t/T）×E0（9）

式中：E表示猎物的逃逸能量；E0表示区间（-1，1）的随机数；t表示当前的迭代次数；T表示算法预设的最大迭代次数。当|E|≥0.5时表示有较多的逃逸能量。r≥0.5表示在本次捕猎中，猎物最终被追捕。基于这两个参数，在这个阶段包括4种迭代策略。

1）软围攻：当|E|≥0.5和r≥0.5时，如式（10）所示。

X（t+1）=Xrabbit（t）－X（t）－E|JXrabbit（t）－X（t）| （10）

式中J=2（1-r5）表示猎物尝试逃离时的能量强度，其中r5（0，1）是一个随机数。

2）硬围攻：当|E|＜0.5和r≥0.5时，如式（11）所示。

X（t+1）=Xrabbit－EXrabbit（t）－X（t）（11）

3）渐进式软围攻： |E|≥0.5和r＜0.5，如式（12）所示。

式中：D表示种群的维度；S表示一个随机个体；LF的Levy飞行函数；表示更优。

4）渐进式硬围攻：当|E|＜0.5和r＜0.5时，如式（13）所示。

5）逃逸能量更新策略

文中通过使用一种非线性逃逸能量更新策略，其逃逸能量更新如式（14）所示，曲线如图6所示。

由图6可以看出，改进的逃逸能量曲线中在120次迭代左右依然有一定的概率进入搜索阶段，能够在全局的范围内搜索更优的可行解，大大提高了算法的全局搜索能力。

6）邻域搜索策略

邻域搜索通过不同种群个体进行交叉、置换等操作，寻找该个体附近的优秀编码。在本算法中主要包括3种邻域搜索策略：

策略1，随机选择1个个体，随机选择某个位置，将该位置的编码重新生成；

策略2，随机选择2个个体，随机选择2个位置，将2个位置之间的编码交换；

策略3，随机选择2个个体，随机选择位置，将指定位置的编码进行交换。

3 仿真验证与分析

3.1 算法设计

文中设计的制造服务优化配置仿真实验包括3种情况：制造规模为3×10、4×10、5×10，表示制造任务数目分别为3、4、5个，制造商的数目为10个。其中制造任务1—5的生产周期分别为27 d、26 d、25 d、26 d和28 d。

3.2 仿真结果分析

为了验证文中MHHO算法的优越性，将相同的问题与HHO、PSO（particle swarm optimization）、NSGA-Ⅱ（non-dominated sorting genetic algorithm-II）4种算法在上述仿真环境中进行比较。仿真实验利用MATLAB2021a进行程序编写，运行环境为Win10系统，2.6GHz，16G内存。每个算法的种群规模为100，迭代次数选定为200次。收敛曲线对比如图7—图9所示。

从图7—图9中可以看出，MHHO算法具有最低的最小化成本，在不陷入局部收敛的情况下，具有最快的收敛速度。同时，由于引入Logistic一维混沌系统，MHHO算法在初始具有最低的适应度。MHHO算法的中期乃至后期都具有一定的搜索能力，并没有出现局部收敛的问题。

将上述算法重复运行30次，最优解、平均解、平均收敛次数和平均求解时间等结果如表2所示。不同制造规模下MHHO算法都可以获得更高质量的最优解和平均解。在平均收敛次数方面，MHHO算法稍劣于HHO和PSO，但是有效避免了陷入局部最优的问题。相较于NSGA-Ⅱ，MHHO算法的平均收敛次数更低，最优解与平均解的质量更高。MHHO算法的平均求解时间最长。但随着制造任务数量的增多，平均求解时间与其他算法的差距越来越小。

4 结语

针对分布式制造服务优化配置问题，文中从制造任务数目、制造商选择和物流方案三方面进行研究，建立优化目标模型，设计独特的编码与解码方式。针对HHO算法全局搜索能力差的问题，从种群初始化、逃逸能量更新和邻域搜索3个角度进行改进。最后，通过不同规模制造任务的案例，验证了MHHO算法在求解质量、收敛速度方面的有效性和优越性。同时随着制造规模的增加，MHHO算法将具有更强的优势。

参考文献：

［1］ DAO S D，ABHARY K，MARIAN R. An innovative GA for optimisation of integrated manufacturing-transportation scheduling in VCIM systems［J］. Operational Research，2020，20（3）：1289-1320.

［2］ AKBARIPOUR H，HOUSHMAND M. Service composition and optimal selection in cloud manufacturing：Landscape analysis and optimization by a hybrid imperialist competitive and local search algorithm［J］. Neural Computing and Applications，2020，32（15）：10873-10894.

［3］ WANG Y， WANGS， KANG L， et al. An effective dynamic service composition reconfiguration approach when service exceptions occur in real-life cloud manufacturing［J］. Robotics and Computer-Integrated Manufacturing，2021，71：102143.

［4］ ZHANG Y，TANG D B，ZHU H H，et al. A flexible configuration method of distributed manufacturing resources in the context of social manufacturing［J］. Computers in Industry，2021，132：103511.

［5］ LIANG H， WEN X， LIU Y， et al. Logistics-involved QoS-aware service composition in cloud manufacturing with deep reinforcement learning［J］. Robotics and Computer-Integrated Manufacturing，2021，67：101991.

［6］ 王平，肖涵，潘燕华. 基于双层规划的云制造资源服务组合［J］. 计算机集成制造系统，2022，28（1）：51-58.