论文部分内容阅读
智能优化算法是近几年发展的一类仿生算法,具有自组织、自学习、自适应、多点并行及有指导搜索等特点,已被广泛应用于工程技术、非线性优化、结构性设计、并行计算和社会科学等领域。本文利用智能优化算法能够较好地解决复杂问题的优点,研究网络计算中任务分配与调度(Task Matching and Scheduling)问题。任务分配与调度是充分利用网络计算潜力的关键技术,也是NP-hard问题,该问题的解决对于高性能计算的应用与发展具有十分重要的意义。针对智能优化算法的普适性和具体问题的特殊性,提出算法的改进策略和具体操作算子的设计;基于进化算法的共性,对进化算法用于调度问题的算法设计进行深入研究。主要研究内容如下:(1)针对蚁群优化(Ant Colony Optimization,ACO)算法擅长解决离散问题,但信息素设计比较困难的特点,提出利用调度任务图静态和动态属性作为启发信息的策略,设计了相关算法,实验证明了该算法的优良性能。通过分析算法的性能,研究了启发信息的选取原则和实施方案。在此基础上设计了并行蚁群调度算法,并在MPICH支撑平台上实现,研究了不同并行方式对调度性能的影响,以及并行群体中信息交换策略和信息交换频率的难题,进一步提高了算法的性能和速度。(2)分析进化算法在优化问题中的应用特点,提出了调度问题解空间的不同编码方式和解码方法,研究了算法搜索过程中有效的进化操作。以微分算法为例,对两种调度编码方式分别设计同构系统调度算法,并比较两种方式的调度性能。在算法实现过程中,根据问题设计特殊的交叉、变异算子,并通过随机拓扑排序方法获得初始群体,综合局部搜索策略,加速算法收敛,提高运行质量和全局搜索能力。实验表明,两种编码方式都能有效解决调度问题,且基于任务排列的方式优于基于任务优先级的方式。(3)针对任务排列编码方式较优的特点,提出了基于粒子群优化(Particle Swarm Optimization,PSO)算法的异构调度算法,设计具有问题特征的进化算子,保证算法能在可接受的时间内提供高质量的解,避免了现有算法中采用平均值而导致调度不合理的缺点。量子行为粒子群优化算法是对标准PSO的一种改进,参数少,理论上能保证解全局收敛。针对任务优先级编码方式容易实现的特点,综合调度问题的空间信息,设计了混合量子行为粒子群的调度算法,研究提高算法性能的策略,实验验证了算法的有效性。(4)针对网格任务调度难点,分析网格异构环境中任务分配与调度的关键问题,研究了网格计算模型下静态任务分配与调度的算法;同时根据网格环境中资源自治和作业动态变化的特性,设计了动态自适应的禁忌搜索算法,在任务调度过程中,自适应地调整算法参数,实时响应网格的动态变化。最后在GridSim环境中仿真实现,并取得了满意的结果。