云计算任务优化调度关键技术研究：基于遗传算法的优化求解

根据上述确定的任务调度的时间-费用目标函数，利用遗传算法的快速全局搜索能力，完成优化的前期求解过程。在遗传算法的求解中，对任务调度方案形成的解空间编码字符串进行一系列的改进设计：改进编码设计和操作设计，使其进化产生更好的解，为下一步的蚁群算法设计提供优化的全局搜索转化的信息素初始值。

4.2.2.1改进的遗传算法编码设计

设置编码的假设条件：

（1）资源池中有n个资源可供调度，用户有m个任务（m＜n）；

（2）每个资源可以被分配给任何一个用户进行服务；

（3）在一次调度中，每个资源最多可以被分配一次。

编码表如表4-1所示。在表4-1中，Umn表示资源n被用于用户任务m，例如，有8个资源可供分配，分配给2个用户任务，随机产生的染色体编码为：｛1010000000010000｝，表示资源1、资源3被分配给用户任务1，资源4被分配给用户任务2使用。

表4-1　编码对应表

解码过程：对染色体按照从左到右顺序进行分组，每 8个二进制位设置为一组，表示一个用户任务，并以 1作为起始编号，则｛10100000 00010000｝为用户1分得资源1和资源3，用户2分得资源4。

种群初始化：初始种群是迭代进化的搜索空间，由随机生成的染色体组成。考虑到算法的搜索速度和收敛问题，本书采用的是随机产生的初始种群Pp，在每次迭代过程中，保持种群的大小不变。

适应度函数表明个体或解的优劣性，适应度函数的构造非常重要，针对特征选取问题，适应度函数设置有效性将直接决定遗传算法的搜索方向和进化结果的优劣。

在本书中，由于要求目标函数所求的云资源被分配给用户使用时，产生的效益最大化，则采用如公式（4-21）所示的适应度函数F：

其中，G为目标函数，G'为目标函数下界限的估计值。

4.2.2.2改进的遗传算法操作设计

（1）选择操作

选择或复制操作是决定哪些个体可以进入下一代。本书中采用轮盘赌选择法选择。选择公式：

其中，为个体i被选择的概率，fi为种群个体的适应度，Pp为种群大小。

选择步骤：

①在第g代，根据公式（4-22）计算和；(www.xing528.com)

②产生［0，1］的随机数，求；

③求中最小的k，则第k个个体被选中；

④进行I次第2、3操作，得到I个个体，成为第g=g+1代种群。

（2）交叉操作

交叉操作是遗传算法产生新个体的途径，本书利用种群相关度设计交叉概率。

定义4.6第g代种群的个体i，它的适应度为fig，则第g代种群的相关度：

种群相关度反映了种群个体的相异程度，Dg值大就说明相异个体比较多，可以适当减小交叉算子，节省搜索时间；反之则增大交叉算子。

据此，第g代种群的交叉算子可表示如公式（4-24）所示：

根据公式（4-24），当Dg为0时，为传统遗传算法的固定交叉算子值0.8。随着种群相关度Dg增加，交叉算子相应减小，这样避免当种群的相关性、多样性较强时，盲目加大交叉概率而耗费搜索时间，破坏优异的个体。同时，这样做具有提高全局搜索能力、稳定新个体产生的核心作用。

（3）变异操作

遗传算法中的变异运算是产生新个体的辅助方法，决定了遗传算法的局部搜索能力，同时保持种群的多样性。本书变异算子采用概率计算的形式，进行新个体的突变选择。变异选择步骤：

① 复制要操作的染色体；

②以概率Pm选择在染色体中突变的点；

③ 交换突变点的值；

④ 返回给选择的染色体。

初始种群经过以上三种操作，筛选出适应度较高、数量较稳定的个体群，将其作为新的种群，而对应的优化问题的操作就可以通过这个过程搜索到整个空间，在一定程度上求得全局最优解。但是新的个体适应度值不一定全部都比父代要好，因此在筛选过程中，要同时遵循以下新个体与上一代种群个体替换的原则：

①如果父代个体劣于子代个体，则新种群中使用子代个体；

② 如果父代和子代的个体的适应度值相同，则使用子代的个体，用于增加遗传算法的多样性；

③ 如果子代的适应度值小于父代的个体，则继续使用父代个体。