基于自适应交叉变异的飞蛾算法云计算任务调度策略

李宏伟

摘 要：针对云计算资源调度效率低的问题，提出一种基于自适应交叉变异的飞蛾优化算法云资源调度策略.首先引入综合学习策略，对飞蛾种群進行初始化，提高全局搜索能力.其次在迭代过程中加入自适应交叉变异策略，加强粒子跳出局部最优的概率.最后建立云计算任务调度问题的数学模型，将改进后的飞蛾算法对模型进行求解，并将实验结果与其他优化策略的实验结果在时间花费和能源花费中进行对比，取得了较优的结果.

关键词：飞蛾优化算法;云计算;资源调度;自适应交叉变异;综合学习

中图分类号：TP18  文献标识码：A  文章编号：1673-260X（2020）01-0026-06

云计算是一类集成网络计算与虚拟技术的新型计算模式，可以针对具有大数据量的计算问题进行处理[1].由于云计算模型复杂度较高且具有较强的非线性，因此可归为NP-Hard问题[2].在云计算的计算过程中，云计算中的资源调度通常呈动态特性，调度难以合理化[3]，并且云计算在运算过程中，每个节点的工作方式互异，处理的数据量大小也各不相同，导致云计算经常出现资源利用率不平衡的问题，很大程度影响了云服务的质量[4].因此，提高云计算效率的关键问题是如何合理对云资源进行调度.为了提高云计算的资源利用率，国内外许多学者展开了深入研究.

赵宏伟等提出一种改进细菌觅食的云计算资源调度策略，通过细菌算法对资源调度节点进行复制和消亡，调高资源利用率[5].罗云等提出一种改进粒子群算法的云资源调度策略[6]，通过混沌随机数扰动策略加强了粒子群算法的全局收敛能力，减少任务完成时间，提高了云计算效率.任神河等将直觉模糊时间序列预测用于平衡云计算网络动态负载[7]，很大程度提升了云计算的运算效率.李佳等提出一种基于布谷鸟算法的云资源调度策略[8]，降低了时间消耗成本和能源消耗成本，提高云计算资源的利用率.王欣欣等提出一种基于双适应度动态遗传算法的优化策略[9]，提出代价函数用于辅助权值的分配，提高了算法的寻优精度.在寻优策略中将能源消耗和时间消耗归为一个目标函数，并将改进后的算法对其求解，很大程度地提高了云计算效率.Yuan H等提出一种基于改进粒子群算法的云计算资源优化调度策略[10].Liu J等提出一种基于博弈优化模型的资源优化调度策略[11].以上策略在一定程度上提高了云资源的利用率，但单一机制的优化算法在处理维数较高的问题上，却存在一定缺陷，使得云计算在处理大规模任务量时，利用率仍不高，因此本文提出一种基于自适应交叉变异的飞蛾优化算法，求解云计算资源调度问题.

飞蛾优化算法的优点在于，算法寻优机制简单，易于实现，相对其他优化算法而言，算法控制参数较少，易于调节.但缺点在于算法全局搜索能力较差，易早熟收敛，陷入局部最优.因此本文针对以上缺陷通过引入综合学习策略和自适应交叉变异策略对算法进行改进，提高算法的全局收敛能力和求解高维问题的能力.并将改进后的飞蛾算法用于求解云计算资源调度问题.

1 云计算资源调度模型

云计算任务调度模型是一类具有多约束条件的非线性数学模型，目的是将m个独立任务合理分配给服务器n个可利用资源，降低云服务器执行任务的时间和能源消耗.因此在建立云计算任务调度模型时，主要考虑时间消耗和能源消耗最小化的问题.

1.1 时间消耗

时间消耗是指任务提交到任务完成，并将调度完成后的结果反馈给用户的时间间隔.在计算过程中，各独立任务均为并行执行，因此，假设在m个独立任务中，第k个任务完成时间最长，则将第k个任务的完成时间定义为云计算任务调度的时间消耗.其数学表达式如下所示：

式中，Timer为云计算任务调度的时间消耗，timei，j=TLi/Cpuj，表示第i个任务在第rj个资源节点的运算时间，j=[1，2，K，n]，n为服务器的资源数量.i=[1，2，L，m]，m为任务总数，Cpuj为虚拟机处理能力，TLi为第i个任务的长度.pi，j为任务执行判定条件，若pi，j=1则表示计算任务i在第rj个资源节点上执行，否则该任务不执行.

1.2 执行能耗

在n个务器资源中，每一个虚拟资源在完成任务后均会因处理数据而产生能量的消耗，这种消耗定义为执行能耗.因此可通过式（2）计算执行完m个独立任务后计算机产生的总执行能耗.其数学表达式如下所示：

式中，ei，j为第i个任务在第j个资源节点上产生的执行能耗.

因此，考虑时间消耗和能源消耗最小化的云计算任务调度模型的目标函数为：

minf（x）=？姿1*Timer（x）+？姿2*JC（x）  （3）

式中，？姿1和？姿2为时间消耗和执行能耗的惯性权重，且？姿1+？姿2=1，？姿1>0，？姿2>0.

2 飞蛾优化算法的改进策略

2.1 基本飞蛾火焰优化算法

飞蛾火焰优化算法[12]（Moth-flame Optimization Algorithm， MFO）是Mirjalili S.于2015年提出的一种以飞蛾扑焰行为为基础的智能优化算法.设MFO算法的种群为M：

M=[m1，m2，L，mn]T  （4）

式中，mi=[mi，1，mi，2，L，mi，d]T;n为飞蛾数量;d为维数.由于飞蛾个体适应度值均储存于矩阵OM中，因此定义：

OM=[OM1，OM2，L，OMn]T  （5）

在飞蛾火焰优化算法中，火焰被描述为算法当前迭代所得最佳位置，因此设最优位置矩阵为F，其适应度值存放于矩阵OF之中.

F=[f1，f2，L，fn]T  （6）

OF=[OF1，OF2，L，OFn]T  （7）

式中fi=[fi，1，fi，2，L，fi，n]T.在飞蛾优化算法中，飞蛾通过一种类似横向定位机制进行导航.因此飞蛾会在火焰附近进行更新，直到搜索到最佳方案，這种行为可以被描述为捕焰行为和弃焰行为.首先飞蛾Mi会以一种对数螺线的方式朝向距自身最近的火焰Fj移动：

S（Mi，Fj）=Di*ebt*cos（2？仔t）+Fj  （8）

式中，S（Mi，Fj）为更新后的飞蛾位置;b为参数，决定螺旋形状;t为[-1，1]之间的随机数;通常当t→1时，表示飞蛾离火焰距离最远，当t→-1时，表示飞蛾距火焰距离最近;Di=|Fj-Mi|为飞蛾距火焰之间的距离;其次，在MFO算法中，火焰数量会自适应减少，直到找到一个最优的火焰位置，这个减少过程被描述为弃焰行为：

flame=round（N-t*（N-1）/Tmax）  （9）

式中，t为算法当前迭代次数;Tmax为最大迭代次数;N为最大火焰数量.

2.2 自适应交叉变异的飞蛾火焰优化算法（Adaptive Cross-mutation Moth Optimization Algorithm， ACMOA）

首先，飞蛾优化算法在种群初始化阶段，搜索范围完全依赖随机性，难以保证全局最优解一定在搜索范围内，以致算法最终找到的全局最优解的精度不高，甚至导致算法早熟收敛陷入局部最优.根据研究表明，初始种群的位置在很大程度会影响算法的寻优精度，因此针对上述问题，本文利用综合学习策略对飞蛾优化算法进行种群初始化.ACMOA的种群位置初始化过程表述如下：

1）首先对飞蛾种群进行随机初始化操作：M（t=0）={mij}，i=1，2，…，NP，j=1，2，…，ND;

2）计算反向飞蛾种群M′（t=0）={m′ij};其中：mmax，j表示种群mi第j维元素最大值，mmin，j表示种群mi第j维元素最小值.

3）从种群{M（t=0）∪M′（t=0）}中选择NP个适应度值较小的蜂群位置作为ACMOA算法的最终初始种群.

通过综合学习策略对飞蛾粒子的初始位置进行初始化，有效地保证了解的质量，丰富了种群多样性，提高了算法搜索到全局最优解的概率，提高了算法的收敛精度.

其次，算法在迭代过程中，会出现陷入局部最优早熟收敛的情况，这是由于在算法迭代后期，粒子始终会围绕当前适应度较高的粒子进行局部搜索，导致算法难以跳出最优解的吸引，早熟收敛.传统的交叉变异策略使得种群中全部粒子获得的变异概率相同，但根据实验表明，适应度值较高的粒子因变异产生的新的粒子，新粒子的适应度值并不一定优于变异前的粒子.因此本文引用一种自适应的概念，根据粒子当前适应度值的大小自适应获得交叉变异概率.该策略以反正切函数y=arctan（x）为基础，使得适应度值较低的粒子过得较大的交叉变异概率，适应度值较高的粒子，获得较小的交叉变异概率.ACMOA算法的自适应交叉变异公式如下所示.其中交叉概率记为pc，变异概率记为pm.

式中，pcmax为交叉概率上限，pcmin为交叉概率的下限，根据大量实验表明，pcmax=0.75，pcmin=0.36时算法的收敛最优.pmmax为变异概率的上限，pmmin为变异概率的下限，pmmax=0.85，pmmin=0.26时算法的收敛最优.favg为种群中全部粒子的平均适应度值.fmax为种群中全部粒子的最大适应度值.f为变异个体的适应度值.f′表示两个进行交叉操作的个体中适应度值较大解.

ACMOA算法的寻优步骤如下所述：

Step1：初始化参数：即飞蛾种群规模大小NP，最大迭代次数tmax.交叉概率的最大值pcmax=0.75和最小值pcmin=0.36，变异概率的最大值pmmax=0.85和最小值pmmin=0.26.

Step2：在解空间内初始化飞蛾种群的位置，再利用反向学习算法产生反向种群.计算两个种群中全部个体的适应度值，并进行排序，选择NP个最优个体作为最终的初始化种群.

Step3：计算出NP个个体适应度值的大小，找出适应度值最小的个体位置作为最优位置.

Step4：依照式（8）和式（9）对飞蛾个体的位置进行更新计算.

Step5：依照式（10）和式（11）对粒子进行自适应交叉变异操作.

Step6：对更新后的粒子进行辩解处理.

Step7：判断算法是否达到终止条件，既是否达到最大迭代次数.是，则输出全局最优解.否，则返回返回Step3.

2.3 基于测试函数的性能测试

为验证本文所提ACMOA算法的整体性能，首先选取12个基准测试函数做为评价函数，对ACMOA进行求解，记录算法求解的平均值和标准差.12个基准测试函数如表1所示.

其次为了验证ACMOA算法相较其他用于云计算资源调度的优化算法具有更高的搜索精度，本文将ACMOA算法的实验结果分别与改进的鸡群算法（ICSO）[13]、改进的蝙蝠算法（HS-BA）[14]和改进的蚁群算法（TCLB-EACO）[14]的实验结果进行对比.其中f1至f4为单峰函数，f5至f8为多峰函数，维数分别设置为10、30和50，f9至f12为固定维函数.为了保证实验的公平性，四种算法迭代次数均为100，种群规模均为50，四种算法对12个测试函数个独立运行30次并记录最佳结果.具体测试结果如表2所示，最优解加粗表示.

从表2中可得，对于单峰测试函数而言，首先，四种算法均可以收敛到全局最优解，但本文所提ACMOA算法所求解的平均值最小，说明ACMOA算法相较其他三种算法具有更高的收敛精度.其次，随维度的增加，算法求解的复杂度增加，除ACMOA算法外，其他三种算法的收敛精度均大幅下降，且ACMOA算法求解的标准差更小，说明ACMOA算法的鲁棒性要优于其他三种算法，算法的整体性能更优.

其次，对于多峰测试函数而言，ACMOA算法同样可以取得更小的平均值和标准差.说明DPSSO算法相较其他四种算法而言，具有更高的全局搜索能力，搜索成功率也更高，算法稳定性更强.同样，ACMOA算法在求解过程中，随维度增加，虽然求解精度会适当降低，但依然远优于其他三种算法.说明ACMOA算法适用于求解具有复杂非线性的问题.

最后，对于固定维函数而言，由于目标函数求解维数较少，使得四种算法的求解精度和算法稳定性均有所提高.但ACMOA算法的标准差较其他三种算法相比，可以求解到更小的值，说明ACMOA算法鲁棒性更高.总体而言ACMOA算法克服了早熟收敛，陷入局部最优的问题，很大程度提高了算法整体性能和收敛精度.

3 仿真实验及分析

本文将改进后的飞蛾优化算法优化云计算资源调度模型，其中仿真平台为MATLAB 2014a，CPU为Inter Core i5-5200U，主频为2.20 GHz.为了验证ACMOA算法的实际调度能力，将本文所得实验结果与ICSO算法、HS-BA算法和TCLB-EACO的实验结果从时间花费和能耗花费两个指标进行对比.

3.1 小规模任务性能对比

首先，本文在任务量较小的情况下，对四种算法进行对比验证，具体实验结果如图1～圖2所示.

从图1中可得，相较其他三种算法而言，ACMOA算法所用时间最短，说明ACMOA算法的收敛精度更高且收敛速度更快，算法在迭代后期，收敛速度不会出现减缓甚至停滞的现象.因此很大程度的缩短了云计算的计算时间，节约了时间成本.其次，在云计算过程中，随任务量增加ACMOA算法求解时间没有出现较大波动，说明ACMOA算法的全局收敛能力更强，搜索范围更广.

从图2中可得，其他三种算法随任务量的增加，能耗花费曲线波动较大，说明其他三种算法在能量消耗上的稳定性不高，但ACMOA算法在迭代过程中，曲线波动较为平缓，说明ACMOA算法在能量消耗稳定性上远优于其他三种算法.此外，ACMOA算法的最大能耗仅为其他算法的50%～75%，说明ACMOA算法的能量消耗远低于其他三种算法.因此，ACMOA算法较大程度地降低了计算资源调度的能耗花费，合理分配了任务资源.ACMOA算法在能耗花费方面要远优于其他三种算法.

3.2 大规模任务性能对比

其次，本文在任务量较大的情况下，对四种算法进行对比验证，具体实验结果如图3～图4所示.

从图3中可得，本文所提ACMOA算法的花费时间远远低于其他三种算法的花费时间，虽然随任务量的增加，四种算法的花费时间均有明显增加，但ACMOA算法受影响更小，曲线上升趋势更加平稳.因此ACMOA算法在处理时间花费的问题上，优化结果远优于其他三种算法，鲁棒性更强.

图4为四种算法的能量消耗对比图，从图中可得，本文所提ACMOA算法的能量消耗最低，并且随任务量的增加，变化趋势不大，稳定性远优于其他三种算法，因此在求解大规模任务问题上，ACMOA算法的整体性能仍然更优.

4 结论

本文针对云计算资源调度不合理导致云计算效率低的问题，提出一种基于自适应交叉变异的飞蛾优化算法对其进行优化.首先针对传统飞蛾优化算法收敛精度低，收敛速度慢，在迭代过程中易早熟收敛陷入局部最优的问题，通过综合学习策略和自适应交叉变异策略对算法进行改进，丰富了算法的种群多样性，提高了算法的全局搜索能力和算法跳出局部最优的能力，很大程度高了算法的整体优化性能.其次通过数值仿真实验，验证了所提算法具有较强的收敛能力.最优将改进后的算法用于云计算资源调度优化，实验结果表明ACMOA算法在优化过程中取得了较好的结果，很大程度降低了云计算的时间成本和能耗成本，提高了云资源的调度效率.

参考文献：

〔1〕林伟伟，齐德昱.云计算资源调度研究综述[J].计算机科学，2012，39（10）：1-6.

〔2〕胡艳娟，朱非凡，王艺霖，石超，武理哲.云制造环境下的资源调度研究综述[J].制造技术与机床，2018（03）：33-39.

〔3〕贾嘉，慕德俊.基于粒子群优化的云计算低能耗资源调度算法[J].西北工业大学学报，2018，36（02）：339-344.

〔4〕林伟伟，刘波，朱良昌，齐德昱.基于CSP的能耗高效云计算资源调度模型与算法[J].通信学报，2013，34（12）：33-41.

〔5〕赵宏伟，田力威.基于改进细菌觅食算法的云计算资源调度策略[J].计算机科学：1-10[2019-10-06].

〔6〕罗云，唐丽晴.云计算调度粒子群改进算法[J].计算机系统应用，2019，28（07）：151-156.

〔7〕任神河，郑寇全，关冬冬，惠军华.基于IFTS的云计算网络动态负载均衡方法[J].系统工程理论与实践，2019，39（05）：1298-1307.

〔8〕李佳，夏云霓.云计算资源调度问题求解的布谷鸟搜索算法[J].控制工程，2019，26（01）：170-174.

〔9〕王欣欣，刘晓彦.基于双适应度动态遗传算法的云计算资源调度[J].计算机工程与设计，2018，39（05）：1372-1376+1421.

〔10〕Yuan H ， Li C ， Du M . Optimal Virtual Machine Resources Scheduling Based on Improved Particle Swarm Optimization in Cloud Computing[J]. Journal of Software， 2014.

〔11〕Liu J， Guo Z. Scheduling Algorithm of Cloud Computing Based on DAG Diagram and Game Optimal Model[J]. International Journal of Grid and Distributed Computing， 2015， 8.

〔12〕Seyedali Mirjalili. Moth-flame optimization algorithm： A novel nature-inspired heuristic paradigm[J]. Knowledge-Based Systems，2015，89.

〔13〕陈暄，龙丹.基于改进的鸡群算法在云计算资源调度中的研究[J].计算机应用研究，2019，36（09）：2584-2587.

〔14〕李天朝，李蜀瑜.基于改进的蝙蝠算法在云计算资源调度中的研究[J].电子设计工程，2017，25（01）：43-46.

〔15〕聂清彬，蔡婷，王宁.改进的蚁群算法在云计算资源调度中的应用[J].计算机工程与设计，2016，37（08）：2016-2020.