基于能效管理的云计算资源调度模型及算法(5)
p[i]=(∞-Ei)/(n*∞-Etotal)；
else
p[i]=(∞-Ei)/(n*∞-Etotal)+p[i-1]；
i++；
}
Step2：随机生成一个随机数tempp，取值范围为（0,1）；
Step3：将该随机数tempp和概率数组p中的概率p[j]一一进行比较，选出第一个大于tempp的概率p[j]；
Step4：将虚拟机装箱集合bin中第j个个体加入到新的虚拟机装箱集合newbin中；
Step5：如果已选择了100个个体，则结束；否则，则跳转到Step2；
3.4.3 交叉算子设计
首先我们将这n个个体分成n/2组，其中0号和1号个体为第1组，2号和3号个体为第2组，4号和5号个体为第3组，……n-2号和n-1号个体为第n/2组。然后针对每一组我们随机生成一个概率，当这个随机生成的概率小于规定的交叉概率时，我们就将该组中的两个个体进行交叉。
Step1：i=0；
Step2：随机生成一个数p，取值范围（0,1）；如果p小于交叉概率，则跳转到Step3；否则，跳转到Step10；
Step3：将要交叉的个体bin[i]和bin[i+1]保存到serverlist1和serverlist2中；
Step4：从serverlist1中随机选择一个物理机server，并将该物理机加入bin[i+1]中，从而产生新的子代编码；
Step5：将bin[i+1]中原有物理机和server进行比较，如果该物理机中有和server中相同虚拟机，则将该物理机删除，并将因物理机删除而产生的未分配的虚拟机保存到VmList2中；
Step6：将VmList2中的虚拟机按照最佳适应算法重新放置。
Step7：从serverlist2中随机选择一个物理机server，并将该物理机加入bin[i]中，从而产生新的子代编码；
Step8：将bin[i]中原有物理机和server进行比较，如果该物理机中有和server中相同虚拟机，则将该物理机删除，并将因物理机删除而产生的未分配的虚拟机保存到VmList1中；
Step9：将VmList1中的虚拟机按照最佳适应算法重新放置。
Step10：判断i是否小于n-1，如果i<n-1,则i++，并跳转到Step2；否则，结束。
3.4.4 变异算子设计
针对每一个个体bin[i]我们随机生成一个概率，当该概率小于规定的变异概率时，我们则对该个体进行变异。在变异时，我们从bin[i]中随机选择一个物理机，并将该物理机删除，然后将因物理机删除而产生的未分配的虚拟机重新分配物理机。
Step1：i=0；
Step2：随机生成一个数p，取值范围（0,1）；
Step3：如果p小于变异概率，则跳转到Step3；否则，跳转到Step5；
Step4：从bin[i]中随机选择一个物理机，并将该物理机删除；
Step5：将因物理机删除而产生的未分配的虚拟机按照最佳适应算法重新分配物理机；
Step6：判断i是否小于n，如果i<n，i++，并跳转到Step2；否则，结束。
3.4.5 算法总体流程
Step 1：种群初始化；
Step 2：计算种群中每个个体的适应度，并保存最好个体；
Step 3：除选择最好的个体外，再选择99个个体；
Step 4：将这100个个体两两分组，在满足交叉条件时，进行交叉；
Step 5：对每一个个体判断是否满足变异条件，满足时进行变异；
Step 6：判断是否满足结束条件，如果满足，则结束，否则跳转到Step 2。
4 仿真环境与结果分析
为了验证在虚拟机放置问题上，遗传算法要优于最佳适应算法。本文在Visual Studio 2005中采用C#语言对这两个算法进行了仿真。
4.1 对遗传算法的收敛性进行验证
在对遗传算法的收敛性验证时，假设虚拟机个数为100，虚拟机类型数组为{20,40,50}（其中20,40,50代表虚拟机CPU的计算能力），虚拟机运行时间数组为{1,2,3}（其中1,2,3表示虚拟机运行了1个，2个，3个时间单位），这样得出整个系统的能耗随着遗传代数的增加的变化情况，如图2所示：