基于混合算法的云制造资源配置研究

李贻婷

基于混合算法的云制造资源配置研究

李贻婷

（南京信息工程大学，江苏 南京 210044）

针对云环境下制造资源优化配置模型求解问题，提出一种在花朵授粉算法基础上引入遗传算法和模拟退火算法的混合算法。首先，在花朵授粉算法的基础上引入遗传算法，用于前期种群初始化；然后，在迭代过程中加入模拟退火算法，避免陷入局部最优；最后，使用该混合算法求解实际问题，验证该算法处理资源配置问题的有效性和准确性。

云制造；资源配置；花朵授粉算法；遗传算法；模拟退火算法

0 引言

云制造资源配置是在云环境下实现资源合理高效地配置[1-2]。资源配置可以解决制造资源与制造能力不均衡带来的资源闲置、资源短缺、制造能力不足、制造能力过剩等问题。建立资源模型是实现资源合理配置的重要环节。文献[3]构建双层规划数学模型，并采用改进的多目标遗传算法对模型求解，实现云制造资源优化配置；文献[4]利用遗传算法和蚁群算法相结合的混合算法解决云制造资源调度；文献[5]结合遗传算法和分层序列法的优势，提出一种遗传分层序列多目标决策方法；文献[6]使用改进的布谷鸟算法解决资源配置问题，利用自适应性调整部分参数和Levy飞行步长，采用模拟退火思想防止陷入局部最优；文献[7]使用改进的鲸鱼优化算法，引入编码解码方式和惯性权重对资源模型进行求解。以上文献中的算法大都存在易早熟、局部搜索能力弱、过分依赖参数设置等问题。本文根据文献[8-10]，提出一种在花朵授粉算法基础上引入遗传算法和模拟退火算法的混合算法，并应用于求解资源模型，为云环境下制造资源合理配置提供一种新的解决方案。

1 问题描述

云平台接受不同产品的订单并将其汇总统计，通过资源配置将制造资源分配给合适的服务商，为用户提供便捷高效的服务[11]。云制造模式的评价体系主要由时间、成本、质量和服务组成[12]。资源配置也围绕这4个指标进行。

如现有订单需求加工一套设备，客户将设备制造需求上传到云平台，云平台进行信息加工处理后，对制造这套设备的各个资源配置进行建模。假设制造这套设备可以分解为项分任务，那么任务集合为

GeneralTask = {Task|= 1, 2, ... ,}

其中，Task为总任务中第项分任务。

每项分任务都有多个候选资源，假设Task有m个候选资源，可表示为

TaskResources= {Resources|= 1, 2, ... ,m}

其中，Resources为第项分任务对应的第个制造资源。

2 建立资源配置模型

根据客户提出的任务需求，以时间、成本、质量和服务这4个指标模型作为求解优化目标。

完成任务的总时间为

完成任务的总成本为

加工产品总质量为

加工产品总服务反馈为

式中：

由于4个指标之间的量纲不同，将它们都化为成本型指标即求解最小化目标函数，则总目标函数为

约束条件：

约束条件公式(6)～(10)即任务要求不超过最大任务加工时间和加工成本，不低于最小任务加工质量和服务反馈。各个权重和为1。

3 求解资源配置模型

3.1 编码

花朵授粉算法由英国剑桥学者YANG提出，基本思想来源于对自然界花朵自花授粉、异花授粉的模拟，前者对应局部搜索，后者对应全局搜索。在花朵授粉算法中，花粉位置对应资源序号，采取实数编码方式，个体位置元素在[0,1]之间选取，假设有8项分任务，则编码方案如表1所示。

表1 编码方案

用轮盘赌解码的方式将个体位置元素转换成资源序号。如任务1有4个地区可以选取资源，默认这4个地区的适应度相等。具体而言，当个体位置元素落入（0，1/4）区间时表示选择第一个地区资源；当个体位置元素落入（1/4，2/4）区间时表示选择第二个地区资源，以此类推直到所有任务选取完资源。表1中个体位置元素所对应的资源序号是（1，2，1，2，2，3，1，1）。

3.2 混合算法

混合算法是在花朵授粉算法的基础上，通过引入遗传算法和模拟退火算法进行改进。花朵授粉算法采用遗传算法初始化种群，将得到的较优解代替花朵授粉算法随机产生的初始解，使花朵授粉算法后续迭代更容易找到最优解。同时，引入模拟退火算法，避免算法陷入局部最优。混合算法有6个步骤。

1）初始化种群和各参数。使用遗传算法对初始种群进行优化，并输出最后一次迭代种群。

2）将导入花朵授粉算法，并用代替花朵授粉算法中的初始解。

3）比较适应度值大小，选出最优解和最优值。

4）根据转换概率的大小选择自花授粉还是异花授粉，如果转换概率> rand，则进行异花授粉，即全局授粉，按公式(11)更新。

电容器的击穿故障很容易发现，但是当并联多个元件时，很难确定具体的故障分量。电容器的开路故障可以通过将相同类型和容量的电容器与检测到的电容器并联以观察电路功能是否恢复来确定。电容和电参数变化的检测比较麻烦。一般可按下列方法进行。首先，电容器的一根引线应该从电路板上移除，以避免周围部件的影响。其次，根据电容器的不同情况，采用不同的方法进行检查：

式中：

式中：

如果转换概率< rand，则进行自花授粉，即局部授粉，按公式(13)更新。

式中：

5）计算并比较适应度值大小择优，根据接受概率公式(14)保留随机解。

6）判断是否满足结束条件，若不满足跳到步骤4）；若满足，退出程序并输出最优解和最优值。

混合算法流程图如图1所示。

图1 混合算法流程图

4 实例分析

根据参考文献[13]，某型号齿轮加工可分解为8项任务，每项任务都需要对应的加工设备。通过云平台搜索所有符合该任务的加工设备资源，并以时间少、成本低和高质量为目标配置资源方案。加工设备资源分布表如表2所示。设定最终交付地为E，区域之间的运输时间和费用关系如表3所示。

表2 加工设备资源分布表

表3 时间成本表

使用层次分析法得到时间、成本、质量、服务的权重系数分别为1= 0.171 5，2= 0.230 4，3= 0.506 2，4= 0.091 9。把表1、表2的数据代入公式(1)～(4)，可分别得到max= 16 550、max= 3 890、min= 42、min= 45。

采用传统遗传算法、花朵授粉算法、混合算法分别求解目标函数。

传统遗传算法（GA）：染色体长度为8，种群规模为30，交叉概率= 0.5，= 0.2，迭代次数为200。

花朵授粉算法（FPA）：位置纬度为8，种群规模为30，转换概率为0.8，迭代次数为200。

混合算法（AFPA）：位置纬度为8，种群规模为30，转换概率为0.8，迭代次数为200，交叉概率= 0.5，= 0.2，退火方式Q+1=αQ，初始温度= 500，其中冷却系数取0.5。

3种算法适应度曲线变化图如图2所示。

图2 3种算法适应度曲线变化图

图2中，由于混合算法前期采用遗传算法进行初始化，因此收敛速度明显高于花朵授粉算法；引入模拟退火算法，在后期步长较短的情况下，避免陷入局部最优，快速找到最优解；混合算法得到最优配置的资源序号是（3,1,2,2,4,3,2,3），即立车3→自动车床1→摇臂钻床2→铣齿机2→圆弧倒角机4→立磨3→研磨2→配对机3。

5 结语

本文使用混合算法求解云制造资源配置模型。通过实例求解，将混合算法与传统遗传算法、花朵授粉算法进行分析比较，验证了混合算法的有效性。

[1] 苏凯凯.云制造环境下的制造资源优化配置方法研究[D]. 北京:北京交通大学,2017.

[2] 侯绍波.云制造模式下制造资源优化配置研究[D].天津:天津理工大学,2017.

[3] 殷亮,周临震,刘德仿,等.面向云制造资源的优化配置方法研究[J].组合机床与自动化加工技术,2018(12):155-160.

[4] 邰丽君,胡如夫,赵韩,等.面向云制造服务的制造资源多目标动态优化调度[J].中国机械工程,2013,24(12):1616-1622.

[5] 汪勇,徐琼,张凌,等.基于遗传分层序列法的云制造资源优化配置[J].统计与决策,2016(20):80-83.

[6] 杨喜娟,杨博,武福.基于改进自适应布谷鸟算法的云制造资源配置优化研究[J].制造技术与机床,2018(5):137-142.

[7] 吴书强,栾飞.基于改进型鲸鱼算法的云制造资源配置研究[J].制造业自动化,2019,41(12):95-98,124.

[8] 窦学.花朵授粉算法及其改进方法研究[D].阜新:辽宁工程技术大学,2016.

[9] 肖辉辉,万常选,段艳明.一种改进的新型元启发式花朵授粉算法[J].计算机应用研究,2016,33(1):126-131.

[10] 高新勤,荆彦臻,杜景霏.基于改进型遗传算法的制造资源优化配置方法研究[J].制造业自动化,2017,39(11):99-104.

[11] ZHANG Q, QI D Y. Service-oriented collaborative design platform for cloud manufacturing [J]. Journal of South China University of Technology (Natural Science Edition), 2011,39 (12):75-81.

[12] 王艺霖,胡艳娟,朱非凡,等.云制造资源优化配置研究综述[J].制造技术与机床,2017(11):36-42.

[13] 易建亮,陈志广,肖侬,等.基于代理的并行文件系统元数据优化与实现[J].计算机研究与发展,2018,55(2):438-446.

Research on Resource Allocation of Cloud Manufacturing Based on Hybrid Algorithm

LI Yiting

(Nanjing University of Information Technology, Nanjing 210000, China)

An improved flower pollination algorithm is proposed for the solution of the optimal allocation model of manufacturing resources in the cloud environment. On the basis of the basic flower pollination algorithm, other algorithms are introduced—the genetic algorithm is used in the initial population initialization part, and the simulated annealing algorithm is added in the iterative process to avoid falling into the local optimum. Finally, the algorithm is used to solve actual problems, and the effectiveness and accuracy of the algorithm in dealing with resource allocation problems are verified.

cloud manufacturing; resource allocation; flower pollination algorithm; genetic algorithm; simulated annealing algorithm

TH166；TP391

A

1674-2605(2022)02-0007-05

10.3969/j.issn.1674-2605.2022.02.007

李贻婷，女，1996年生，硕士研究生，主要研究方向：智能优化算法的改进及应用、资源配置。E-mail：2697090317@qq.com

李贻婷.基于混合算法的云制造资源配置研究[J].自动化与信息工程,2022,43(2):41-44,48.

LI Yiting. Research on resource allocation of cloud manufacturing based on hybrid algorithm[J]. Automation & Information Engineering, 2022,43(2):41-44,48.