云计算中负载均衡优化模型及算法研究(4)
Step2：计算个体的适应度 。根据设计的适应度函数计算出每个个体的适应度大小 。
Step3：选择操作。根据个体的适应度，按照一定的概率选择个体。其中，选择算子采用轮盘赌算法，这种算法个体选中的概率与个体的适应度成正比，即适应度越大，选中的概率越大。其中，个体选中的概率 计算公式如下：
（5）
其中，K表示种群的规模。将新的预备种群初始化为空，并把选中的个体加入新的预备种群中。
Step4：交叉操作。将选择操作选出的个体，按照交叉的概率Pc进行两两交叉，采用多点交叉，交叉概率Pc=0.9。
Step5：变异操作。将选择操作选出的个体，按照变异的概率Pm进行随机变异，采用单点变异，变异概率Pm=0.005。
Step6：精英主义选择操作。将选择、交叉、变异等遗传操作产生的所有个体根据个体的适应度择优选出K个体作为下一代种群，保持种群规模不变。
Step7：终止条件判断。根据设置的迭代次数Gen判断是否满足终止条件。如果不满足，则从Step2开始进行向下执行。否则，程序终止，得到较优的个体。
4.实验仿真及结果分析
4.1仿真环境及主要参数介绍
仿真环境用的普通PC测试，算法执行环境用的VC++ 6.0编译器，绘图工具用的数学软件MATLAB。其中，初始虚拟机数T=100，物理机数M=20，种群规模K=50。
4.2仿真结果分析
首先对比改进遗传算法和简单遗传算法（SGA）对实现计算资源的负载均衡效果以及解的收敛性。这里群体规模K=50，虚拟机数T=100，物理机数量M=20，迭代次数Gen=200。交叉概率Pc=0.9，变异概率Pm=0.05，实验结果如下。
图2 改进GA和SGA算法对计算资源的负载均衡对比结果
根据上图仿真的结果，我们可以证明改进GA比SGA有更快的收敛速度、较好的收敛性和较好的负载均衡效果。这是因为GA的潜在并行性很适合处理大规模、并行计算的问题，并且能以很大的概率收敛到最优解。
下面我们用改进GA和Min-Min算法对于同样负载量的虚拟机调度实现负载均衡。参数同图2中设置的参数一样，这里对比了100组测试数据，实验结果如下图。
图3 改进GA和Min-Min算法对100组数据的负载均衡结果
根据仿真的结果，我们可以看出改进的GA明显比Min-Min处理计算资源的负载均衡有很大的优势，并且总是保持着这种优势。因为GA是并行处理的全局随机优化算法，而Min-Min是串行处理的优化算法，执行效率和优化效果不同。对于处理问题的规模也不同，GA适合处理大规模问题，而Min-Min适合中小规模问题。
下面再对比改进GA算法和Min-Min算法对于实现不同数量虚拟机调度的计算资源负载均衡的效果。这里除了虚拟机数量T不同外，其他参数同图2中设置的参数一样，实验结果如下。
图4 改进GA和Min-Min算法对于调度不同数量虚拟机的负载均衡结果
根据上图实验的结果，我们可以看出改进GA对于不同数量的虚拟机调度实现负载均衡都比Min-Min算法有优势，并且优势在逐渐扩大而明显。因为GA很适合处理大规模问题，并具有并行处理的特点，是一种全局优化搜索算法。
根据上面3个仿真实验的结果，我们可以看出改进的GA在多次数据测试、不同数量虚拟机调度的计算资源负载均衡方面都比Min-Min算法有优势。因此，说明了我们设计的改进GA算法对于解决基于任务调度的计算资源负载均衡优化问题是可行的和有效的。