基于自适应遗传算法的服务工作流调度问题的研究

摘要

随着互联网普及和计算机技术的发展，作为下一代分布式计算平台，网格计算越来越得到人们的重视。网格计算中的一个重要问题——工作流调度就是一个很有应用前景的技术。工作流调度问题把用户提交的任务分为若干个存在互相依赖关系的子任务，要求工作流管理系统(WfMS)为工作流的所有子任务分配一个服务器，根据用户的喜好最大化某种需求。工作流调度最大的挑战在于在较短的时间内，要为用户随机给定的任务集合分配服务器。不但这些服务器的性质会动态地变化，而且服务器本身也属于不同的系统管理者所有。
　　 本文提出了一种混合自适应遗传算法，用来解决网格环境的工作流调度问题，在最大化某种用户喜好的同时还要求调度满足用户提出的约束条件，比如费用、完成期限等。本文首先简单介绍网格环境的工作流和遗传算法。接着根据用户的三种主要需求建立数学模型，设计相应的适应度函数。然后介绍自适应的遗传算法，算法通过聚类分析提炼出若然干变量，把这些变量融入模糊逻辑的思想指导遗传算法控制参数的更新。同时算法还加入了并行算子，减少算法的计算时间。另外，增加了染色体的寿命属性，使得染色体在后期能通过重调整算子，实现优胜劣汰。最后，通过实验验证了本文提出的自适应遗传算法在求解工作流调度问题上的效率。

目录

文摘

英文文摘

声明

1.绪论

1.1.引言

1.2.选题背景

1.3.主要工作

1.4.研究意义

1.5.论文结构

2.网格工作流

2.1.网格工作流概述

2.2.网格工作流的数学模型

3.标准遗传算法

3.1.起源和基本思想

3.2.基本流程

3.3.初始化

3.4.适应度评价

3.5.选择算子

3.6.交叉算子

3.7.变异算子

3.8.精英化

3.9.结束条件

4.自适应遗传算法

4.1.自适应算法的提出和基本流程

4.2.K均值聚类算法

4.3.调整交叉和变异参数

4.4.并行算子

4.5.重调整算子

5.实验分析

5.1.用函数优化问题测试AGA

5.2.基于工作流问题的参数分析

5.3.改进后的AGA求解不同的工作流问题

6.结论和展望

6.1.遗传算法求工作流问题的讨论

6.2.本文开展的工作

6.3.进一步研究的展望

参考文献

作者简历

致谢