基于遗传算法的云计算任务调度研究(3)
时间:2017-02-27 13:17 来源:毕业论文 作者:毕业论文 点击:次
其中，ctij在前面已经介绍过，表示第j个任务在服务器i上的执行时间，x表示在服务器i上有x个任务。那么适应度值越低的个体，意着当前基因完成所有的任务花费的时间也是越少的。 3.3.2基因编码 本论文中所采用的实例是如何把M个任务调度到N台异构的服务器上，假设M个任务分别编号为M1,M2,...Mm，N台服务器编号为N1,N2,...Nn，将任务访问顺序与服务器编号联系起来就可以构成一个表示任务分配情况的个体，则个体X可以表示为：X：[Mi,Mj,...,Mk]，其中的i，j均为（N1,N2,...Nn）之间的随机数，k为个体长度n。 3.3.3种群初始化 （1）初始化N个任务和M台服务器，并使用随机函数初始化N个任务的数据量及M台服务器的计算能力； （2）初始种群数目设定为50，然后把N个任务随机地分配到M台服务器上。 3.3.4选择算子设计 选择操作是建立在对个体的适应度进行评价的基础之上。避免基因缺失、提高计算效率及全局收敛性是选择操作的主要目的[12]。在本论文中，采用了轮盘赌选择算法。轮盘赌选择是从群体中选择一些个体的方法，设P(i)（i=1..n）为n个个体被选择的概率，在轮盘上表示为所占扇区的面积百分比，这里显然sum(P)=1 ，那么个体被选中的机率和它们的适应度分数成比例，染色体的适应度分数越高，被选中的概率也越大。这并不能保证适应度分数最高的个体一定能选入下一代，仅仅说明它被选中的概率最大。 3.3.5交叉算子设计 遗传算法的交叉算子是模仿自然界有性繁殖的基因重组过程[13]，经过该过程，群体的品质会有所提高。直观来说，选择算法将原有的优良基因遗传给了下一代个体，而交叉算子则可以产生包含更多优良基因的新个体。本文采用了常见的两点交叉具体交叉步骤如下： Step1：对由选择算子选出的两个父个体u1和u2。 Step2：随机生成两个交叉点p1和p2。 Step3：在交叉生成的子个体中，在p1之前及p2之后的基因由u1得到，而在p1和p2之间的基因由u2得到。 3.3.6变异算子设计 在GA进化过程中，变异操作主要是为了保证群体具有一定程度的多样性。本论文中主要采用自适应变异算子来进行变异操作[14]。对于当前群体，适应度值较好个体的应该适当保留，减少其突变概率，防止过大的变异概率破坏最优值附近的解，反之，适应度值较差的个体应该尽量让其突变，以获取最优解或者近似最优解。本论文中对适应度值较好的个体采用0.01的突变概率，而对适应度值较差的个体则采用0.9的突变概率。 3.3.7模拟退火局部优化 模拟退火实质上就是在解空间内对个体做一次变异操作。经过复制、交叉、变异之后我们可以得到150个新产生的个体，然后按照精英保留策略从中选择50个最优的个体，然后将这50个个体作为模拟退火的对象，然后循环遍历当前的50个个体，对每个个体作如下操作： Step1：将解空间定义为当前50个个体中最差的个体。 Step2：随机生成当前基因长度范围内的两个点，并将这两个点作为变异位置。 Step3：从变异之前与变异之后的两个个体中选择较好的那个作为当前的新个体。 3.4算法描述 由于基本遗传算法经常出现近亲繁殖，因此容易出现个体早熟的现象，以致算法不能及时跳出局部最优解而收敛到全局最优解，这是基本遗传算法的最大不足之处。这一现象产生的根本原因是，当种群经过一定的迭代进化后，因为优胜劣汰，只有少数优良个体生存了下来，而这些个体通常具有相同或者高度近似的基因，因此很难产生出新的比较优良的个体。本文在研究标准遗传算法的同时还对其进行了改进，标准遗传算法的变异概率一般是固定的，该改进的遗传算法则对其进行了改进，使不同的个体能够根据其适应值大小选择合适的变异概率进行变异。在改进变异算子的同时还加进了模拟退火算法以对遗传算法进行优化[15]，这样不仅可以更快的找到最优解，而且加快了遗传算法的收敛速度。改进遗传算法描述如下： (责任编辑：qin) |