一种基于云环境下蚁群优化算法的改进研究

李德启， 田素贞

(商丘职业技术学院计算机系， 河南 商丘 476000)

0 引 言

云计算作为一种全新的网络服务方式，是通过互联网络连接的超级计算模式，其中包括了并行处理(parallel computing)、分布式处理(distributed computing)和网格计算(grid computing)等计算机相关理论与技术，也是计算机科学概念的商业体现[1].云计算为广大用户提供了很大的方便，与此同时，对此环境下的任务调度技术和使用效率也提出了更高的标准[2].然而，目前云环境下的任务调度方法是利用虚拟机级别上的调度策略和一定的调度技术相结合为虚拟机内部应用进行调度，试验证明，当前任务调度策略普遍缺乏精确性[3].蚁群优化算法源于蚂蚁觅食行为过程的模拟，提出的解决NP-hard问题中离散组合问题的方法具有很高的并行性、协作性、易扩展性和鲁棒性，是一种以群体为基础的自适应搜索算法，尤其在动态环境下它的灵活性和健壮性能够很好的体现，可用来解决很多系统组合优化问题[4].云环境下任务调度的关键问题是能够从资源分配给任务的不同组合中挑选出一种效果理想的动态组合方式，基于蚁群优化算法的特点，此算法非常适用于云环境中的资源调度.

对资源调度算法的选择对云环境的工作效率至关重要，它是更好地发挥云计算环境性能的关键.笔者在深入研究标准的蚁群优化算法的基础上，结合云环境的特殊性和遗传算法对全局收敛的优点，将遗传算法融入到蚁群优化算法的每一次迭代中，用于解决标准的蚁群优化算法搜索速度慢和局部最优的问题，使云环境下的求解速度和寻优能力得到了提高，保证了云计算环境资源调度的效率.

1 标准蚁群优化算法的原理和实现

20世纪90年代，意大利M. Dorigo、V. Maniezzo和A. Colorni等学者在研究蚂蚁群落生物进化的机理中获得启发，发现蚁群在觅食过程中总能找出一条从蚁巢到食物源的最优路径.通过模拟现实生活中蚂蚁觅食的情况，它们构造出了群体智能理论研究算法[5].所谓群体智能是指具有简单智能的主体通过群体的相互协作表现出复杂智能行为的特性.蚁群是利用信息素的正反馈机制和集团自催化行为找出最优最优路径的[6].首先，他们提出了一种新型的模拟进化算法—蚂蚁系统(AS)，通过大量试验表明AS有很高的鲁棒性和很好的搜索能力，但是此系统也有先天性的缺陷，如收敛速度慢和易于停滞等[4]，为此他们又提出了蚁群系统等算法，在性能上得到了进一步的提升，并且很好地消除了搜索过程中的停滞现象.为了给蚂蚁系统提供一个统一的框架和坚实的理论基础，学者们后来提出了蚁群优化算法(Ant Colony Optimization，ACO).

1.1 标准蚁群优化算法的原理

标准蚁群优化算法的原理是在生物学家和仿生学家研究发现蚂蚁个体之间通过一种叫做外激素(Pheromone)的物质相互传递信息，从而完成复杂觅食任务而受到启发的基础上建立的算法[7].蚂蚁在觅食过程中，在其所经过的路径上留下外激素，通过感知外激素的强弱程度，自然地倾向于在外激素强的路径上移动，从而形成了大量蚁群的集体行为，表现出一种正反馈现象，即选择某条路径的蚂蚁数量越多，则该路径将会被更多的蚂蚁选择.蚁群从初始状态到找到最优路径的过程，即蚁群优化算法的原理如下所述：

假设在蚁群的初始状态下，从A点至E点(或E点至A点)存在两条不同的路径，分别为A-B-C-D-E和A-H-D-E，但路段B-H-D的长度为路段B-C-D的2倍，蚁群总体数量m为60.在时间t=0时刻(最初始时刻)，在路径上不存在外信息素的情况下，蚂蚁以相同的概率选择不同的路径运动，分别有30只蚂蚁选择BC和BH路径.在现实情况下，蚂蚁留在路径的部分外激素会随着时间推移而挥发，为了更好的说明留在不同路径上的信息量，笔者在此做以下假设：蚂蚁是按照相同的速度匀速爬行；外激素的挥发量与时间的长短成正比，也就是说，不同路径上外激素的剩余量(用τ表示)与时间成反比；蚂蚁选择路径的概率与该路径上留有的外激素量τ成正比.因为路径B-H-D的长度是路径B-C-D的2倍，所以蚂蚁所需时间也是路径B-C-D的2倍，由以上假设条件可得，留有路径B-C-D上的外激素量是路径B-H-D的2倍，在t=1时刻(蚁群第一次返回时刻)，当蚁群量为60的蚂蚁从E点到达D点时，根据蚂蚁的特性，将会有40只蚂蚁选择路径D-C-B，20只蚂蚁选择路径D-H-B.随着时间的推移，会越来越多的蚂蚁选择路径B-C-D.最终经过长时间的爬行后，蚁群将会选择最优路径A-B-C-D-E.

1.2 标准蚁群优化算法的实现

下面以ASP模型求解平面上n个节点的TSP问题为例，系统说明标准蚁群优化算法的实现过程.

(1)

其中：τij(t)表示t时刻节点i和节点j连线上信息的剩余量，一般情况下τij(0)=C(C为常数)；ηij表示在t时刻由节点i到节点j的启发信息，正常情况下取dij的倒数；α、β分别表示信息剩余量和启发信息的重要程度；tabuk表示禁忌表.

(1)将每条路径上所存在的信息素初始化为一个非常小的常数，把蚁群中的m只蚂蚁随机放置在n个节点上，并将出发节点设置到tabuk表中.

(2)每个节点上的蚂蚁按照公式(1)选择下一个节点，并对tabuk表进行更新.

(3)当每只蚂蚁完成一个节点到下一个节点的路径时，按照下式更改该段路径的信息素：

(2)

(4)当所有蚂蚁走完所有节点后，计算最优路径长度并保留.

lmin=minlk,k={1,2,3,…,m}

(3)

其中：lk表示第k只蚂蚁所走路径的长度；m表示蚁群蚂蚁的总数.

(5)当所有蚂蚁走完所有节点后，利用下式更新最优路径上的信息素.

(4)

其中：α表示全局信息素挥发系数；lk表示最优路径的总长度.

(6)假如所设置的迭代次数没有完成，对禁忌表进行清空，对上述步骤重新进行循环.

综合上述，标准蚁群优化算法具有较好的并行分布性、扩展性、易实现性、强鲁棒性，特别是在动态环境下也具有较高的灵活性和健壮性[8].但是，此算法在对大规模的优化问题进行求解时也暴露出它先天性不足的一面，如收敛速度慢、容易陷入局部最优解.

2 对云环境下蚁群优化算法的改进

改进标准蚁群算法的思想是在原有标准算法的基础上将GA算法融入到标准算法的每一次迭代中，将标准优化算法每一次迭代产生的解和全局最优解作为遗传算法的初始种群，每一次的初始种群经过GA的若干次选择、交叉、变异和群体更新后，形成一组新解，然后对比遗传算法产生的解群体最优值和标准蚁群算法的全局最优值，比较出来的最优值就是改进算法的新的全局最优解，最后完成信息素的更新.另外，由于遗传算法变异机制的存在，有效的避免了标准蚁群优化算法易于陷入局部最优的不足[9].使用经过改进的蚁群优化算法，可以使云计算服务在资源发现、资源匹配、任务调度和产生及任务执行方面的效率获得大幅度的提高.基于云计算的特性，笔者对解决TSP和云环境资源调度问题的特性差异进行了比较分析，主要表现在以下方面[10]：

(1)在TSP问题中，节点之间的的路径是可达的并具有不同的长度；而云计算环境中资源的拓扑结构存在着很大的随机性，所以要利用云环境下资源活动的相互作用进行模拟拓扑结构.

(2)在TSP问题中，节点之间的距离确定着信息素的强度；而在云计算中的信息素必须对资源的计算与通信能力的相关参数进行表示.

(3)在云计算环境中，蚁群算法的启发信息需要以资源的计算和通信能力等固有的属性进行表示.

因此，按照当前资源的信息量需要对云计算环境下现有资源下一任务的概率计算方法做相应的调整：

(5)

其中：τj(t)表示t时刻资源信息素的强度；资源的固有属性由ηi表示，ηj=τj(0)；α和β分别表示信息素和资源固有属性的重要程度；蚂蚁路径变异的个数可由随机数产生.

假设云计算环境下的任务目标是将M个任务分配到N个资源上，利用改进的蚁群优化算法计算每个资源上任务的最短平均执行时间，完成系统资源的最优化，也就是求下面函数的最小值：

(6)

改进的蚁群优化算法实现流程如图1所示.

图1 改进蚁群优化算法实现流程

3 仿真实验及结果分析

为了验证改进蚁群优化算法的有效性，笔者对云计算仿真平台CloudSim 2.1进行了扩展，并重写了Cloudlet等类.在仿真实验过程中，遗传算法中的选择、交叉和变异策略分别采用轮盘赌选择、顺序交叉和进化变异策略，将云计算任务量参数设置为30，信息素固有属性重要程度α和资源固有属性的重要程度β分别设置为1和2，迭代次数为200，交叉概率和变异概率分别为0.8、0.1，其最优解为422.83，将达到最大迭代次数作为停止条件，分别利用标准的蚁群优化算法和改进算法进行30次独立重复实验，两种算法找到最优解的实验结果如表1所示.

从表1中我们不难得出，在两种算法分别进行30次重复实验的条件下，标准的蚁群优化算法7次找到最优解，而改进的蚁群优化算法找到最优解的次数竟然达到16次，比标准算法寻优能力提高了30%，从而证实了改进蚁群优化算法的寻优能力.

表2为在给定目标解为420的前提下，分别利用两种算法进行30次独立实验，当第一次达到目标解时，所需要的迭代次数和运行时间的平均值.

通过对表2实验结果的分析表明，两种算法以第一次达到给定目标解为结束条件，分别经过30次实验，所需运行时间的平均值分别为13.87 s和8.96 s，从实验数据上有力的说明了改进的蚁群优化算法在达到目标值的速度上有了很高的提升.

表1 两种算法寻找最优解能力的实验结果

表2 两种算法达到目标解系统运行效率的实验结果

4 结束语

笔者针对标准蚁群优化算法在解决大规模优化问题时存在的缺陷，结合遗传算法全局速度快和云环境下资源任务的特殊性，将遗传算法融入到标准蚁群优化算法每一次迭代中，使标准蚁群优化算法在收敛速度和寻优能力方面有了大幅度的提升，仿真实验结果进一步证明了改进算法的有效性.

参考文献

[1] Sims K.IBM introduces ready-to-use cloud computing collaboration services get clients started with cloud computing[EB/OL].2007：http://www-03.ibm.com/press/us/en/pressrelease/22613.wss.

[2] 陈 康,郑纬民.云计算:系统实例与研究现状[J].软件学报,2009,20(5):1 337-1 348.

[3] 《虚拟化与云计算》小组.虚拟化与云计算[M].北京:电子工业出版社, 2009.

[4] 吴庆洪,张纪会,徐心和. 具有变异特征的蚁群算法[J].计算机研究与发展, 1999, 36(10): 1 240-1 245

[5] 李庆玉,徐敏强,往日新,等.基于蚁群算法的航天器观测动态调度研究[J].计算机测量与控制, 2009, 17(5): 822-825.

[6] 张素兵,刘泽民.基于蚂蚁算法的时延受限分布式多播路由研究[J].通信学报,2001,22(3):70-74.

[7] Marco Dorigo, Thomas Stutzle. Ant Colony Optimization[M]. Cambridge, Masschusetts London, England. MIT Press, 2004.

[8] Verbeeek K, Nowe A.Colonies of learning automata[J]. IEEE Transac-tions on Systems,Man,and Cybernetics:Part B, 2002,32(6):772-780.

[9] Ding Jian-li, Chen Zeng-qiang, Yuan Zhu-zhi. On the combination of genetic algorithm and ant algorithm[J]. Journal of Computer Re-search and Development,2003,40(9):1 351-1 356．

[10] 张 青.网格环境下任务调度算法的应用研究[D].大连:大连海事大学硕士学位论文, 2009.