云计算中负载均衡优化模型及算法研究(3)
Min-Min算法是一种很容易实现的算法，它的执行效率很高。算法的思想是首先选出负载小的任务，并映射到计算能力强的虚拟机上。
Min-Min算法执行过程为：计算每个任务在每台虚拟机上的预计资源占用率，找到每个任务的最小资源占用率及其对应的虚拟机；从中找出资源占用率最小的任务，将该任务调度到对应的虚拟机上；调度完成后，更新该虚拟机的资源占用率并将已调度的任务从集合中删除。重复上面的过程，直到所有的任务都被调度到虚拟机上。
3.2算法设计
3.2.1种群初始化
在遗传算法开始的时候，首先要随机生成K个个体组成初始群体，并进行个体的编码工作，其中编码过程即为将T个虚拟机调度到M台物理机上的分配方案，这里初始生成K个调度方案。这里我们初始化群体大小K=50，物理机器数M=20，虚拟机数T=100。还要初始化每台虚拟机上的负载量大小和每台物理机的计算能力大小。
3.2.2适应度函数设计
由于目标函数是大于0的，且求函数的最小值。因此将目标函数求倒数即可作为适应度函数，即用物理机上计算资源占用率的方差的倒数作为适应度函数。
适应度函数 的公式如下：
（4）
其中，方差 公式： ， ， 。其中， 表示物理机j上的计算资源占用率， 表示虚拟机i上的负载量大小， 表示物理机j的计算能力， 代表所有物理机上计算资源占用率的均值，n代表云计算中物理机的数量。
3.2.3选择算子设计
根据每个个体的适应度，计算出每个个体被选择的概率。这里采用轮盘赌选择算法，该算法中个体的适应度和选择概率成正比，适应度越好，选择的概率就越大。也即物理机计算资源占用率的方差越小，适应度越好，被选择的概率越大。
3.2.4交叉算子设计
对于选择操作选择出的个体随机进行两两配对，交换两个个体的部分基因，从而组成新的染色体（即新的个体）。交叉的目的就是要把优势基因重新组合到一起，优势合并、强强联合，这样新组合的个体优势就更强了，其个体的适应度也就越好，设计的方案也就越优，越接近问题的最优解。交叉概率Pc的选择一般在0.4-0.9之间，通常选择较大的概率。
交叉操作示例如下，交叉位置4，其中Ci代表将虚拟机调度到物理机i上。
父代个体A：C2C9C8|C15C7C14->新个体：C2C9C8C6C2C9
父代个体B：C7C3C17|C6C2C9->新个体：C7C3C17C15C7C14
3.2.5变异算子设计
对于选择操作选择出的个体根据变异概率进行变异，随机确定变异的基因位置，根据变异概率P进行随机变异。交叉操作是进行全局搜索优化，避免陷入局部最优解，确定出最优解的局部范围。而变异操作则是进行局部的搜索优化，进行局部范围的优化，逐步向最优解靠近。变异概率一般选择较小的值，通常取0.001-0.1之间。
变异操作示例如下，变异位置5，由C10变异为C2，其中Ci代表将虚拟机调度到物理机i上。
个体C：C9C13C5C7C10C3->个体C’：C9C13C5C7C2C3
3.2.6精英主义选择算子设计
根据前面选择、交叉、变异等遗传操作所产生的所有个体，依据这些个体的适应度择优选择K个个体，作为下一代种群，以便进行多次迭代操作。
3.3算法步骤
改进的遗传算法的执行流程如下：
Step1：随机生成K个个体，作为初始群体。每个个体即为一个将虚拟机调度到物理机上的分配方案。物理机数M=20，虚拟机数T=100，种群规模K=50。同时初始化每个任务的负载量大小和每台物理机计算能力的大小，以及K个个体的初始化（即任务的调度方案）。