改进鱼群算法在云计算任务调度中的应用

张晓丽

（西安航空学院 计算机学院，陕西 西安710077）

改进鱼群算法在云计算任务调度中的应用

张晓丽

（西安航空学院 计算机学院，陕西 西安710077）

云计算环境中的任务调度问题一直是云计算研究的重点，任务调度的目的寻找最优的任务调度策略，以高效地完成计算任务。针对云计算环境下资源规模庞大、异构性的特点，为了克服传统调度算法存在的缺点，提出一种基于改进自适应人工鱼群算法的任务调度算法。该算法以任务总执行时间作为目标函数，在迭代过程中动态自适应的调整人工鱼的视野和步长，同时对觅食行为进行改进，加快算法的收敛速度，避免算法陷入局部最优，以此提高任务调度的性能。通过在CloudSim平台进行仿真对比实验，相较于其他智能寻优算法，该算法在任务执行时间和收敛速度上都有明显的优势，是一种有效的任务调度算法。

云计算；任务调度；人工鱼群算法；自适应

云计算[1-2]作为一种新兴的计算服务商业模式，集成了网格计算、分布式计算和并行计算等技术，自提出以来就成为一个热点研究方向。云计算采用虚拟化技术，将大量通过网络连接的计算资源存储资源与软件资源整合起来，构成大规模的共享虚拟资源池，为用户提供廉价的按需服务，同时将用户提交的任务分配给计算机资源池进行合理调度。由于云计算中存在诸多形态不同的云端，且面对的计算资源种类众多、提供服务效率不一、计算任务数量巨大，在“云”中如何将众多任务进行合理调度满足用户对服务质量的要求并且更有效利用云计算系统中的资源一直是一个核心关注热点[2-3]。大量研究结果表明，云计算任务调度实际上是一个NP难题[4]，也是一个组合优化问题。针对云计算的任务调度问题，国内外学者对其进行了相应的研究，提出了大量的云计算任务调度算法。例如最小最小（min-Min）[5]、Sufferage算法[6]和一些启发式算法如基于蚁群的调度算法[7]、基于遗传的调度算法[8]、基于粒子群的调度算法[9]、基于遗传模拟退火算法的调度算法[10]等。但这些算法通常都存在收敛性能或搜索全局最优解的能力较低，容易陷入局部最优值，调度目标单一等问题。

文献[11]提出的人工鱼群算法作为人工智能领域的研究成果之一，采用自下而上的信息寻优模式，具有较强的跳出局部极值点的能力，对搜索空间具有一定的自适应能力，并具有鲁棒性强，对初值的敏感性小，简单易实现等诸多优点，在求解大规模复杂优化问题上取得了较好效果。因此，考虑上述现有调度算法存在的不足，文中针对云计算任务调度的特点，对云环境中资源的高效合理调度进行了研究，为了克服基本人工鱼群算法在后期收敛速度慢和计算量大的缺陷，提出一种动态自适应的人工鱼群算法，并将该改进算法应用于云计算任务调度问题研究，实验证明该算法能有效减少云计算任务调度的总时间。

1 云计算任务调度模型

云计算环境下的任务调度是以任务为基本单位，按照一定的任务调度策略，将相互独立的多个任务以最合理的方案分配到可用的计算资源上，以使得任务的总执行时间跨度最短同时能够充分利用现有资源。因此云计算任务调度模型的优劣直接影响任务的执行效率，从而影响整个云的性能和用户的满意度。文中只考虑任务之间相互独立的情况，并且假设每个任务在计算资源节点上的执行时间是已知的。

根据云计算任务调度的特点，定义如下的数学参数模型：{T，R，TR，TS，ETC，MT}

1）T={t1，t2，…，tn}表示任务模型，包括 n个相互独立的任务，其中ti表示第i个任务；

2）R={r1，r2，…，rm}表示资源模型，包括m个可用于执行任务的高性能计算资源，其中m＜n，rj表示第j个计算资源；

3）TR=[tr]m×n表示任务和资源之间的映射关系，如果任务i调度给资源j执行，则trji=i，否则trji=0；

4）TS=[ts]m×n表示任务开始时间矩阵，其中tsji表示任务ti调度给计算资源rj的开始时间，初始值设为0；

5）ETC=[etc]m×n表示预测执行时间矩阵，etcji表示任务ti在资源rj上的预测执行时间；

6）MT=[mt]m×n表示任务的预测完成时间，mtji则表示任务ti在资源rj上的预测完成时间，由以上参数可知，任务ti在资源rj上预测完成时间如式（1）:

由于计算资源是并行运行的，基于以上描述，云计算环境下的任务调度的主要目标是寻找最优的调度策略以最小化计算任务在各个资源上的完成时间，使其得到最高的执行效率，即min（mtji）。

2 改进自适应鱼群算法的任务调度

2.1 基本人工鱼群算法

人工鱼群算法[11-12]（Artificial Fish Swarm Algorithm，AFSA）是李晓磊等人于2002年基于模拟鱼群行为提出的一种群体智能优化算法。该算法在迭代的过程中主要通过人工鱼的觅食、聚群和追尾行为实现自我更新，通过鱼群中各个体之间的集体协作以达到全局寻优的目的，该算法简单易实现，能够很好的解决组合优化问题。

该算法的数学模型描述如下：

人工鱼个体的状态 X=（x1，x2，…，xn），其中 xi（i= 1，2，…，n）为需要寻优的变量；每个人工鱼当前所在位置的食物浓度表示为f（X），即求解的目标函数值；人工鱼个体之间的距离di，j=‖Xi-Xj‖；人工鱼的视野范围用Visual表示；移动的步长用Step表示；拥挤度因子用δ表示；人工鱼每次觅食最大的试探次数用try_number表示。

2.2 改进的人工鱼群算法

2.2.1 视野和步长的改进

分析基本鱼群算法的数学模型可知，AFSA中的控制参数会直接或间接影响算法的求解质量与速度。文献[14]的研究结果表明，AFSA算法控制参数中的视野和步长对算法的收敛速度和求解精度都有较大影响。

视野参数确定人工鱼的搜索范围，在其固定不变的情况下，当人工鱼个体逐渐逼近最优解时，只有少量人工鱼的状态与最优解不同，如果这时的人工鱼依然以原始视野进行觅食行为显然是盲目的，因此在这种情况下应该使用较小的视野范围进行深度搜索。如果视野范围较小，则人工鱼的局部搜索能力较强，但会导致算法收敛速度变慢，且计算量大，甚至陷入局部最优；而视野范围较大，则人工鱼在前期收敛很快且全局搜索能力较强，但容易跳过最优解。为了解决上诉问题，需要对基本的人工鱼群算法进行改进，在算法运行前期，采用较大的视野，以增强算法的全局搜索能力和收敛速度，随着算法的迭代进行，视野范围逐渐减小，从而加强算法的局部搜索能力和提高搜索解的精度。但是，如果后期视野范围太小则会影响最优解的搜索。因此，改进的鱼群算法在迭代过程中通过式（3）动态调整人工鱼的视野，当人工鱼的当前视野值减小到最小视野时，使用最小视野作为当前视野，从而有效地改善算法的性能。

其中，g为当前迭代次数，Gmax为最大迭代次数，visualmin为最小视野，visualg表示当前的视野。文中设定visualmin=1。

步长参数决定了算法的收敛速度和求解精度，步长越大则前期收敛速度越快，但有时会出现振荡现象，难以准确逼近最优值的情况；步长越小则收敛速度越慢，但求解精度越高。因此对于步长参数，本文使用式（4）随视野范围动态调整。

其中step0为步长设置的初始值，使用式（4）变步长在搜索初期可以得到较快的收敛速度，后期可以进行更加细致的搜索，从而提高搜索到最优值的几率。

另外，文献[14]指出，拥挤度因子δ越小，觅食和随机行为比较突出，从而人工鱼摆脱局部极值的能力也就越强。因此，在迭代过程中，文中采用指数式的衰减策略计算拥挤度因子[15，17]：

其中，α为衰减因子，文中设置α=0.6。

2.2.2 觅食行为的改进

人工鱼的觅食行为是算法收敛的基础，在基本人工鱼群算法中，觅食行为是一种盲目性搜索，没有充分利用之前的搜索信息，因此不利于在视野范围内尽可能多地去寻找较优解。改进的觅食行为是当人工鱼个体没有找到较优状态时，随机选择一个新的状态，如果该状态优于当前位置，则直接跳跃到该位置，否则在试探次数内再随机选择一状态进行判断，当其试探次数超过try_number，如果依然不满足前进条件，则依据概率P（0≤P≤1）向之前搜索到的全局最优解的方向移动一步，概率P为一个随机数，文中设置P=0.5。

2.2.3 算法步骤

改进人工鱼群算法的流程图如图1所示。

图1 算法流程图

由上述算法流程可以看出，在每一次迭代过程中，算法将会选择鱼群中的最优解来更新公告板，最后得到的人工鱼模型则是公告板记录的最优解，也就是任务调度的最终分配方案。

3 仿真试验结果与分析

为了验证和评价本文算法的正确性和可靠性，采用墨尔本大学开发的开源的云仿真平台CloudSim[16]来进行仿真对比实验，首先在相同的实验环境和参数相同的情况下对比测试了本文算法和基本ASFS算法的收敛性，然后在任务数改变以及计算资源改变的环境下分别对本文算法、蚁群算法[7]、改进遗传算法[8]和改进粒子群算法[9]的性能进行对比试验。

1）算法的收敛性对比

模拟云计算资源数为10，调度任务数为100的仿真云环境，在此环境下，设置基本参数如表1所示，测试本文算法和基本AFSA算法的收敛性，得到收敛曲线如图1所示。

表1 基本参数设置

图2 算法收敛性比较

从图2的收敛曲线图看以看出，在基本参数设置相同的情况下，本文方法的收敛速度明显优于基本AFSA，并且比基本鱼群算法优先达到最优方案。这主要是因为改进后的算法在迭代过程中，根据迭代的次数动态调整算法的视野范围和步长，使其在前期保持较大的视野和步长，而后期使用较小的视野和步长。而基本鱼群算法在整个迭代过程中使用固定的视野和步长，这就导致在后期收敛速度变慢，甚至可能陷入局部最优。

2）计算资源相同，任务数改变时完成时间对比

针对云计算环境任务动态性的特点，分别模拟在10个计算资源、50个子任务以及10个计算资源、500个子任务两种调度规模下，对算法的性能进行了对比。在相同的实验环境下，取各算法多次运行的平均结果作为实验的最终结果。本实验的目的是为了测试在计算资源相同的情况下，任务数发生变化对调度结果性能的影响。4种调度算法的任务完成时间如图3所示。

由图3可知，在资源相同，任务数不同的调度规模下，当任务量较少时，3种算法均能获得云计算任务调度性能较优的方案，且快速收敛，性能上不存在太大的差异。但是随着任务数的增加，任务之间的竞争相对激烈，3种算法的总任务完成时间都在增加，从图3中可以看出，使用本文算法在收敛速度和总任务完成时间上优于对比算法。这主要是由于本文算法在迭代过程中动态自适应调整人工鱼的搜索范围和移动步长，获得更高的资源利用率，提高任务调度的效率。对比结果表明，文中算法在迭代过程中动态自适应调整人工鱼的视野和步长，加快了收敛速度，有效避免了算法陷入局部最优解，使其求解效率更高，在优化性能上取得了相对较好的效果。

图3 不同任务数时，任务总完成时间比较

3）计算资源数改变，任务数相同时完成时间对比

本实验是为了测试在任务数不变情况下，计算资源数发生变化时对调度结果的影响。文中模拟了在任务数固定为1 000，计算资源数从10变化到50的环境下，分别测试了本文算法、蚁群算法、改进遗传算法和改进粒子群算法的任务调度总完成时间，测试结果如图4所示。

图4 计算资源数改变，任务完成时间的比较

从图4中可以看出，随着计算资源数的增加，由于任务的完成时间都在逐步减小。这是因为随着资源节点数的扩充，对任务来说可选择的资源范围逐渐变大，任务对资源的竞争相对减弱，任务可以选择性能更高的节点进行调度，进而缩短任务完成时间，在相同情况下，使用文中算法的优势更明显。由于本文算法在调度的过程中，结合计算资源的性能和分布情况为依据来进行任务调度，有效的保证了资源的充分利用，很大程度的提高了任务的完成时间。

由图3和图4的实验结果可以看出，无论是在任务数增加还是资源节点增加的情况下，使用文中算法进行任务调度，相比同类算法得到的总任务完成的时间都相对较小，并且能得到较好的收敛效果。

4 结束语

文中对云计算任务调度问题进行综合分析，针对当前云计算任务调度算法存在收敛速度慢，资源利用率不足等缺陷，利用人工鱼群算法收敛速度快，对初值要求低、易于实现、计算简单等优点，提出一种云计算环境下基于改进人工鱼群算法，并使用改算法对云计算任务调度问题进行优化。在算法中自适应调整人工鱼的视野、步长和拥挤度因子，同时对觅食行为进行改进。通过仿真对比实验可知，在相同的环境下，文中算法的收敛性和调度性能略优于同类算法，可以在云计算环境下实现较为理想的任务调度结果，有效地解决云计算环境下任务调度问题。

[1]Foster I，Zhao Yong，Raicu I，et al.Cloud Computing and Grid Computing 360-degree Compared [C]//Proc.of Grid Computing Environments Workshop.Washington D.C.，USA:IEEE Computer Society，2008:1-10.

[2]Armbrust M，Fox A，Griffith R，et al.Above the Clouds:A Berkeley View of Cloud Computing [EB/OL].[2009-11-21].http://www.eecs.berkeley. edu/Pubs/TechRpts/2009/EECS-2009-28.pdf.

[3]李乔，郑啸.云计算研究现状综述[J].计算机科学，2011，38（4）:32-37

[4]Arfeen M A，Pawlikowski K，Willig A.A Framework for Resource Allocation Strategies in Cloud Computing Environment[J].Computer Software and ApplicationsConferenceWorkshops（COMPSACW），2011 IEEE 35th Annual，2011:261-266．

[5]王观玉.网格计算中任务调度算法的研究和改进[J].计算机工程与科学，2011，33（10）:186-190.

[6]Buyya R.Economic-based Distributed Resource Managementand Scheduling for Grid Computing[D]. Melbourne，Australia:Monash University，2002.

[7]魏赟，陈元元.基于改进蚁群算法的云计算任务调度模型[J].计算机工程，2015，41（2）:12-16.

[8]李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法 [J].计算机应用，2011，31（1）: 184-186.

[9]封良良，张陶，贾振红，等.云计算环境下基于改进粒子群的任务调度算法[J].计算机工程，2013，39（5）：183-186.

[10]Gan Guoning，Huang Tinglei，Gao Shuai.Genetic Simulated Annealing Algorithm for Task Scheduling Based on Cloud Computing Environment[C]// Proc.of International Conference on Intelligent Computing and Integrated Systems.Guilin，China: [s.n.]，2010.

[11]李晓磊，邵之江，钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践，2002，22（11）:32-38.

[12]李小磊.一种新型的智能优化方法——人工鱼群算法[D].杭州:浙江大学，2003.

[13]DEAN J，GH EMAWAT S.MapReduce:simplified data processing on large clusters[C]//Proceedings of the 6th Symposium on Operating System Design and Implementation.New York:ACM，2004:137-150.

[14]王联国，施秋红.人工鱼群算法的参数分析[J].计算机工程，2010，36（24）：169-171.

[15]何静媛，邹东升，何中市.RNA二级结构预测的自适应鱼群算法模型[J].系统仿真学报，2010，22（6）: 1370-1374.

[16]Calheiros R N，Ranjan R，Beloglazov A，et al. CloudSim:a toolkit for modeling and simula-tion of cloud computing environments and evaluation of resource provisioning algorithms [J].Software: Practice and Experience，2011，41（1）:23-50.

[17]李孝宇，李涛，李鹏，等.基于自适应人工鱼群算法的大型光伏电站燃气轮机组的优化配置 [J].陕西电力，2013（8）：15-20.

Application of improved Artificial Fish Swarm Algorithm in cloud computing task schedule

ZHANG Xiao-li
（School of Computer，Xi'an Aerotechnical University，Xi'an 710077，China）

Tasks scheduling is an important issue to be resolved in cloud computing research.The purpose of task scheduling is to find the best optimal scheduling scheme to compute tasks efficiently. Focusing on the characteristics of resources under large scale heterogeneous in cloud computing environment，and to overcome the shortcut of the existing task scheduling algorithm，a task scheduling algorithm based on improved self-adaptive artificial fish swarm algorithm was proposed.The algorithm used the task execution time as objective function，adjusted artificial fish vision and step dynamically in iterative procedure，and improved prey behavior，to speed up the convergence rate，reduce the probability of local optimum，and improve the performance of task scheduling.Through the simulation experiment on CloudSim platform， the algorithm has obvious advantages in the task execution time and convergence speed compared to other intelligent optimization algorithms， it is an efficient task scheduling algorithm.

cloud computing；task schedule；Artificial Fish Swarm Algorithm（AFSA）；self-adaptive

TN919

：A

：1674－6236（2017）06-0014-05

2016-04-05稿件编号：201604038

陕西省网络计算与安全技术重点实验室项目（15JS078）；西安市科技计划资助项目（CXY1518（1））

张晓丽（1980—），女，重庆人，硕士，讲师。研究方向：Web服务、分布式计算。