论文部分内容阅读
任务分配与调度是网络计算中的一项关键技术,直接影响到整个系统的计算性能。任务分配与调度问题是一类NP问题,经典调度理论一般仅能获得问题的近似最优解。尽管已有用于任务分配与调度的遗传算法的求解质量优于传统方法,但传统单种群遗传算法的效率随任务数增多而下降。本文采用理论分析与仿真实验相结合的方法,研究网络计算中单任务和独立多任务分配与调度的遗传算法。 本文首先针对同构系统中任务分配与调度问题提出一个通用的遗传算法。算法直接采用任务列表编码结构,在此基础上设计出三个专门的遗传算子,即改进的交叉算子、内部交叉算子和具有变异功能的迁移算子。种群初始化技术采用均衡水平分割法,以保证初始个体的有效性和质量。算法主要控制参数的取值通过仿真实验确定。 针对传统单种群遗传算法求解独立多任务分配与调度问题的伸缩性差的缺点,本文基于多物种共同进化的生物学背景,从理论上探讨合作式共同进化计算模型的机理。数学分析表明,对于独立多问题,共同进化算法采用按比例选择策略时,高于平均适应值的模式的逐代递增指数高于传统单种群遗传算法,说明共同进化算法的效率高于传统的单种群遗传算法。对于不可作独立子问题分解的问题,则以基因连锁一般模型—NK模型进行了实例研究。 将合作式共同进化计算模型应用于同构系统中的独立多任务分配与调度问题,提出一个独立多任务分配与调度的共同进化遗传算法,包括子种群中子分配与调度实例组合成总分配与调度实例的启发式合并方法,以及子种群个体的适应值计算方法等。 针对网络异构计算的简化模型和一般模型分别提出任务分配与调度的遗传算法。一般模型中任务分配与调度受到系统多种因素的影响,如任务间的数据逻辑关系、各处理机的计算速度、网络拓扑结构、节点间通信机制以及通信波特率、数据流量大小等等。在考虑上述影响因素的基础上,分别提出单任务分配与调度的遗传算法和独立多任务分配与调度的共同进化算法。 从同构系统到异构计算环境,从单任务到独立多任务,本文提出了针对不同系统环境下任务分配与调度的遗传算法。理论分析与仿真实验均表明,本文所提算法的问题求解性能优于传统调度方法和已有用于任务分配与调度的遗传算法。