１多周期分配的ＶＭＬＢＰ的蚁群算法
蚁群算法（ＡＣＯ）是意大利学者ＤｏｒｉｇｏＭ等研究蚂蚁寻找路径的自然行为，受到自然界中真实蚁群觅食行为的启发，进而提出的一种路径搜索算法［５－６］．大量的研究发现，蚁群在觅食过程中通过释放信息素、感知信息素的强度来进行交流，从而选择最短搜索食物．蚁群算法是启发式算法，以其鲁棒性强、全局寻优能力强的特点在优化问题中得到广泛的应用．因此针对多周期分配的虚拟机负载均衡问题，本文提出了一种改进的蚁群算法作为求解方法．
１．１对下一个节点的概率选择
仿效自然界的蚁群行为，蚁群算法中人工蚂蚁的行为可以描述如下：多只蚂蚁在相邻的节点间移动，从而协作异步地得到问题的解［７］．在基本的蚁群算法中，每只蚂蚁会根据路径上的信息素，依据一定的概率选择下一个节点，距离越近的点被选择的可能性越大．本文中根据所要达到的优化目标，将概率选择公式中的距离替换为下一个任务的所需服务时间与任务分配周期的比，通过计算概率来选择下一个需要分配的任务，则可知蚂蚁对任务的选择概率应满足以下条件：（１）路径上信息素强度越强，蚂蚁到达的概率越大；（２）所需服务时间与任务分配周期越接近，蚂蚁选择到达的概率越大．
１．２算法描述
基于上述改进，可得多周期分配的ＶＭＬＢＰ蚁群算法流程如下：步骤１初始化各参数，设定最大循环次数Ｎ，计算η（ｉ，ｊ）并存放于相应的数组中；步骤２初始化任务信息，创建空路径，随机选取一个任务为初始点，令当前点为ｉ；步骤３以当前任务ｉ为出发点，根据式（８）计算转移概率，选取下一个任务ｊ，在路径中添加任务ｊ；步骤４重复步骤３，若已遍历所有的任务，则ｋ＝ｋ＋１，若ｋ＜ｋ＋１，则转步骤２，否则转入步骤５；步骤５每只蚂蚁得到一条以初始分配时刻为起点的路经，每条路经就相当于所有虚拟机分配到的任务的排序，取路径中的每ｍ个任务为一次分配的任务，分配次数ｌ＝１，分配时间为０，开始时间为０，等待时间为０，计算完成时间、空闲时间；步骤６ｌ＝ｌ＋１，分配时间为（ｌ－１）•Ｄ，计算等待时间、开始时间、服务时间、完成时间，若完成时间小于下一次任务分配时间ｌ•Ｄ，则计算空闲时间，否则空闲时间为０；步骤７重复步骤６，若ｌ＝Ｌ，分配时间为（ｌ－１）•Ｄ，计算等待时间、开始时间、服务时间、完成时间，记录每个任务的完成时间，若大于最大服务时间Ｔ，转到步骤２；步骤８计算每条路径上最后一次分配的ｍ个任务完成时间的方差，并保存方差最小的路径，在该路径上进行信息素更新；步骤９判断循环次数ｎ是否达到Ｎ，若ｎ＞Ｎ，则终止运算，输出上一步迭代的最优结果，否则转到步骤２．
２实验结果与分析
本文提出的改进的蚁群算法采用Ｃ＋＋语言在ＷｉｎｄｏｗｓＸＰ（Ｐ４２．８ＧＨｚ，１ＧＢ）平台上编程实现，为了验证算法的性能和有效性，随机选取一个任务为初始点，构造一个包含９个任务的分配网络（设分配周期Ｄ＝８０单位时间，虚拟机数量ｍ＝３，分配次数ｌ＝３，虚拟机最大服务时间Ｔ＝３００单位时间），然后利用此数据对算法进行测试．在蚁群算法中设定残留信息的相对重要程度α＝１、预见值的相对重要程度β＝２和信息素的挥发系数ρ＝０．５，运用１０只蚂蚁，迭代１００次获取结果的最优值．为了进一步分析算法执行的稳定性，本文选择遗传算法进行比较，相关参数设置如下：种群大小ｐｏｐｓｉｚｅ＝５，交叉率ｐｃ＝０．１，变异率ｐｍ＝０．０１，最大世代数ｇｅｎｅｒａｔｉｏｎ＝１００，并将得出的结果与蚁群算法得到的结果进行比较，可见表１．由表１可见，在１０组数据上蚁群算法得到的结果的平均值更小，且执行时间的平均值更小．比较表１的第２列和第４列可以看出，在目标函数值相同时，蚁群算法的执行时间更短．由此可见，相对于遗传算法，蚁群算法的平均性能更优，即考虑了时间因素的改进蚁群算法具有更好的全局寻优能力，更易于找到较优的解．由表１的第３列可以看出，１０组实验数据算法执行时间均在０．０５ｓ以内，总的平均执行时间为０．０３７ｓ．由此可见，本文提出的改进蚁群算法可以用于求解云计算环境下的虚拟机负载均衡问题，且可在较短的时间内取得满意的结果．残留信息的相对重要程度α、预见值的相对重要程度β和信息素的挥发系数ρ，体现了相关信息痕迹、预见度及挥发对蚂蚁决策的相对影响．为了进一步分析各参数对解的影响，我们选用不同的α、β、ρ取值．实验表明，α、β、ρ的取值变化均会影响问题的求解结果，多次运行后得出本文的最佳参数设定为α＝１，β＝２，ρ＝０．５，此时得到的实验结果最优，且收敛速度最快，具有较强的全局寻优能力．实验结果表明本文针对云计算环境下的虚拟机负载均衡问题建立的模型是可解的，算法是有效的．由表１可以看到由改进的蚁群算法得到的结果更优，而且具有更快的收敛速度，算法的性能更优．
３结束语
本文对云计算环境下的虚拟机负载均衡问题进行了研究，建立了数学模型，并针对其中特定约束条件进行了研究，最后通过蚁群算法进行了求解，对指导现实生活中的实际情况具有一定的理论意义．
作者：马华伟 吴晓莉 单位：合肥工业大学管理学院
相关专题：大金 臭氧超标 供应链管理存在的问题
