遗传算法在分布式系统中的应用

论文摘要

遗传算法(Genetic Algorithm,GA)是一种用于解优化问题的并行寻优算法,目前已被广泛用于各类NP问题的求解中。运用遗传算法解决任务调度与资源映射问题,是分布式系统的重要研究课题。 本文将资源分为计算资源(处理机)与非计算资源两类,重点研究带优先级的独立任务集。我们将任务调度与资源映射结合在一起,建立一个具有资源映射功能的任务调度模型。在此基础上,设计了满足本课题的一个变型的广义遗传算法——MGGA(Modified General Genetic Algorithm),将MGGA应用于静态优化调度中,以便在任务执行前产生一个最好的分配调度策略。尔后,在任务执行期间通过一个动态调整算法对调度结果进行调整。 在MGGA中采用的染色体一改传统的矩阵编码方式,用一种与自然界中生物染色体相吻合的“一维结构体编码”方式,使遗传操作更直观、方便。为了适应这一编码方式,该算法中采用的杂交与变异操作的基本单位是“基因片段”而不是通常所说的基因位。本文通过建立马尔可夫链模型,在对MGGA的收敛性进行分析,得出与广义遗传算法的收敛性相同的结论。 仿真结果表明,与不采用遗传算法优化的静态分配调度算法相比,本算法能得到更好的解。

论文目录

• 第一章 绪论
• 1.1 研究背景
• 1.2 任务分配与调度问题
• 1.3 任务分配与调度常用算法
• 1.4 资源映射问题
• 1.5 本文所做的工作
• 1.6 内容安排
• 第二章 遗传算法
• 2.1 遗传算法简介
• 2.2 标准遗传算法（SGA）
• 2.3 遗传算法的主要参数
• 2.4 广义遗传算法
• 第三章 MGGA算法收敛性分析
• 3.1 遗传算法的数学描述
• 3.2 马尔可夫链的定义及性质
• 3.3 MGGA算法的收敛性分析
• 第四章 遗传算法在分布式系统中的应用
• 4.1 问题描述
• 4.2 相关前期研究进展（SA算法）
• 4.3 动态调整算法DA
• 4.4 MGGA算法的应用
• 4.4.1 编码方式与初始种群的生成
• 4.4.2 适应值函数
• 4.4.3 杂交算子
• 4.4.4 变异算子
• 4.4.5 MGGA算法描述
• 4.4.6 GSA算法描述
• 4.5 实验仿真及结论
• 第五章 总结与展望
• 参考文献
• 攻读学位期间的研究成果
• 致谢
• 学位论文独创性声明、学位论文知识产权权属声明