柴旭清 董永亮

摘 要：为了解决蚁群算法在解决云计算中大规模任务调度问题时收敛速度较慢且易陷入局部最优解的缺陷，设计了一种基于蚁群算法的云计算自适应任务调度算法，该算法在多态蚁群算法的基础上加入了信息素自适应更新调整机制，用来提高算法的收敛速度，有效地避免的局部最优解的出现。实验数据表明，在解决大规模任务调度问题时本文算法性能更好。

【关键词】云计算 任务调度 蚁群算法 自适应

1 自适应任务调度算法

1.1 信息素初始化

将蚂蚁分为两类：侦查蚂蚁和搜索蚂蚁。前者以每个城市为活动中心，仅在城市附近进行局域搜索，并将结果用侦查素标记，对搜索蚂蚁提供辅助作用；后者进行全局搜索，当到达一个新的城市后，根据该城市的周边城市侦查素和前辈蚂蚁释放信息素来选择下一个旅游城市，直到选出最佳路径。

1.1.1 侦查蚂蚁

由于在现实中可能会出现服务器j的剩余性能无法满足任务i性能要求的情况，因此需要优化传统的多态蚁群算法的侦查素生成方式，使城市i和城市j之间是非连通的，具体生成方式如下：

每个城市布置一只侦查蚂蚁，并侦查剩余（m-1）个城市信息，将结果与先验知识结合生成侦查素s[i][j]，标记路径Lij上。

1.1.2 搜索蚂蚁

搜索蚂蚁负责全局搜索工作，在时刻t，城市i中的搜索蚂蚁k通过路径Lij转移到城市j的概率计算如下：

allowedk是未被蚂蚁k访问的城市，即蚂蚁k的禁忌表。

由公式（1）（2）可知，若存在服务器seri无法满足任务tj的性能需求，则该节点上的侦查素s[i][j]=0，即在初始状态下，城市i无法到达城市j，保证在蚁群算法的首次迭代中不会将任务tj分配到服务器seri上。

由公式（3）可知，当搜索蚂蚁在到达一个新城市时，结合该城市侦查素将缩小下一城市的搜索规模，加快了收敛速度。

1.2 信息素更新规则

信息素更新分为信息素局部更新和信息素全局更新。

1.2.1 局部更新

局部更新是指单一蚂蚁在一次迭代过程中选定下一个目标城市后，立即更新该城市的信息素，而不影响此次迭代过程中其他并行蚂蚁及其后续蚂蚁的路径选择，具体更新公式如下：

1.2.2 全局更新

信息素的全局更新是指在蚁群算法在进行一次迭代后，对出现在迭代最优解的蚂蚁所经的路径上所有城市的信息素进行更新，具体更新公式如下：

其中，MAT（z）表示在第z次迭代中搜索发现的最优解的匹配距离。

为保证不出现将任务tj调度到不满足需求的服务器seri上，在每次迭代后需要对所有城市的信息素进行修正，公式如下：

2 性能测试

通过matlab对本文算法和传统蚁群算法进行仿真分析，在仿真过程中分别将等待调度的任务总数和服务器总数为Num=100，200，信息素启发参数α和视界启发参数β分别为α=1，β=2及α=5，β=10、信息素挥发参数ρ=0.5、蚂蚁总数M=2Num、调和常数Q=5及迭代次数N=100。仿真10次后求得的平均值的结果如图1，2所示。

由实验数据可以看出，在初次迭代后，本文算法搜索到的最优解要优于传统蚁群算法，原因是传统蚁群算法初始状态下各路径信息素相同，首次迭代中信息素对蚂蚁的路径选择没有帮助，而在本文算法中由于侦查素的存在，使得初始状态下各条路径上的信息素存在差异，对蚂蚁路径选择产生影响，使其搜索到更优秀解的可能性增大。

当信息素启发参数α和视界启发参数β较小且任务总数小于100时，本文算法在收敛速度要优于传统蚁群算法，但在最优解方面存在一定不足；当任务总数大于100时，本文算法在收敛速度和最优解方面均要明显优于传统的蚁群算法。

当信息素启发参数α和视界启发参数β较大时，两类算法收敛速度都要明显加快。当任务总数较小时，本文算法和传统算法互有优劣，但当任务总数大于100时，本文算法性能上优势明显。

参考文献

[1]刘文.一种定向式挖掘的连续域蚁群算法[J].计算机科学，2013，40（12）：292-294.

[2]张燕，顾才东.一种求解云计算资源优化的改进蝙蝠算法[J].科技通报，2014（11）.

[3]张春艳，刘清林，孟珂.基于蚁群优化算法的云计算任务分配[J].计算机应用， 2012，35（2）：1418-1420.

作者简介

柴旭清（1982-），女，河南省南阳市人。硕士学位。现为河南师范大学网络中心工程师、CCF会员，主要从事计算机网络，HPC，云计算等研究。

董永亮（1978-），男，河北省永年县人。硕士学位。现为河南师范大学新联学院讲师，主要从事计算机网络。

作者单位

1.河南师范大学网络中心 河南新乡市 453007

2.河南师范大学新联学院 河南省郑州市 453000