基于负载均衡的资源调度模型及其算法(4)
3算法设计
遗传算法具有良好的全局搜索能力，可以快速地将解空间中的全体解搜索出，而不会陷入局部最优解的快速下降陷阱；并且利用它的内在并行性，可以方便地进行分布式计算，加快求解速度。遗传算法(Genetic Algorithm, GA)[8]因其隐形并行性和全局解空间搜索特点得到学术研究者的青睐。下面就给出遗传算法中各个算子的设计。
3.1选择算子设计
选择操作是建立在评价个体的适应度进行的基础之上。避免基因缺失、提高计算效率及全局收敛性是选择操作的主要目的。本文采用了轮盘赌选择算法。轮盘赌选择是从群体中选择一些个体的方法，设P(i)（i=1..n）为n个个体被选择的概率，在轮盘上表示为所占扇区的面积百分比，这里显然sum(P)=1 ，那么个体被选中的概率和它适应度的值成比例，染色体适应度的值越高，被选中的概率也越大，但这并不能保证适应度的值最高的个体一定能被选择遗传给下一代。
3.2交叉算子设计
遗传算法的交叉算子是模仿自然界生物进化的基因重组过程，经过该过程，群体的品质会有所提高。简单地说，选择算法将原有的优良基因遗传给了下一代个体，而交叉算子则可以产生包含更多优良基因的新个体。假设从Y(g)中选择的两个个体为 和 ，长度均为M。定义两长度为M的数组来表示 和 的基因序列，随机的用0或1来对数组进行初始化，然后设定 的基因为1的位置为交叉位置进行交叉，其具体交叉过程如下所示：
3.3变异算子设计
在GA进化过程中，变异操作主要是为了保证群体具有一定程度的多样性。本文设计一个均匀变异算子，即设 为参加变异的个体，当满足特定概率时，以均匀概率的方式依次从每个任务对应的节点集合中选择一个节点s，替换掉 ，执行n次，得到一个新的个体 。该变异算法设计简单，且可以有效防止算法陷入局部最优。
3.4算法流程
(1) 初始种群：随机产生满足染色体定义的初始种群，种群规模为 ，假设变异概率为 ，交叉概率为 ，个体长度为M，物理机数量为H，进化代数为 。采用直接整数编码的方式，生成规模为 的初始种群，记为 ，当前进化代数g=0；
(2) 交叉：将 复制一份，记为 ，以杂交概率从 中选择部分个体两两进行随机交叉，最后得到的集合记为 ；
(3) 变异：将 复制一份，记为 ，对种群 进行概率为 的随机变异操作，产生变异后代种群记为 ；
(4) 选择：采用设计的轮盘赌[9]选择策略从 中选择N个个体，组成下一代规模为 的种群 ；
(5) 判终止条件：若不满足, 返回步骤(2)重复，直到满足终止条件为止。
4实验仿真与结果分析
本实验所采用的操作系统为Win7 Ultimate，内存大小2GB，处理器型号AMD Turion X2 Dual-Core Mobile RM-75，处理器频率2.2GHz，磁盘容量320GB。算法设计采用C++语言来编程，仿真结果由Matlab[10]绘制而成。
本论文中采用的实例为M台机器，N个任务，因此需要首先初始化N台机器的计算能力以及N个任务的数据量。基本遗传算法主要有下述4个运行参数：种群规模N，即群体中个体的数量，取为40。T：遗传运算的阈值，即遗传代数G，取为150。交叉概率Pc=0.5，变异概率Pm=0.1。这样得出整个系统的负载随着遗传代数增加的变化情况，如图2所示：