毕业论文

打赏
当前位置: 毕业论文 > 计算机论文 >

基于负载均衡的资源调度模型及其算法(4)

时间:2017-02-17 12:47来源:毕业论文
3算法设计 遗传算法具有良好的全局搜索能力,可以快速地将解空间中的全体解搜索出,而不会陷入局部最优解的快速下降陷阱;并且利用它的内在并行性


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所示: 基于负载均衡的资源调度模型及其算法(4):http://www.751com.cn/jisuanji/lunwen_3071.html
------分隔线----------------------------
推荐内容