论文部分内容阅读
高速网络的发展使得将分散的、异构的计算资源有机地整合到一起形成计算网格成为可能。计算网格为解决科学和工程领域一些大规模计算问题提供了理想的平台。由于网格所具有的广域性、动态性、异构性的特点,如何对任务进行调度是一个极具挑战性的问题。与此同时,通过模拟自然生态机制求解复杂优化问题的新型计算智能方法,如遗传算法、免疫算法、蚁群算法、粒子群算法等具有很好的自适应性。尤其是由Eberhart和Kennedy于1995年提出的粒子群优化算法和由Dotigo于1991年提出的蚁群算法,具有NP-hard的组合优化的调度问题成为它们的一个重要研究方向。我们提出把离散粒子群算法用于网格任务调度问题,即为使粒子群算法适用于网格任务调度而对粒子群算法进行离散化,对粒子的位置和速度重新进行定义,并重新设计粒子的位置和速度的变换规则。基于GridSim包,我们设计了一个网格模拟系统,并在网格模拟系统上对提出的离散粒子群算法进行仿真实验,实验表明该算法具有较好的性能,但在算法后期的局部搜索能力差,反馈信息利用不充分。进而我们提出把粒子群算法与蚁群算法进行融合并应用于连续函数优化问题,利用粒子群算法寻优的结果来初始化蚁群算法的信息素,为使蚁群算法适用于求解连续函数优化问题,对蚂蚁寻优思想作了修改和引申,大量在连续空间的典型算例测试结果表明,融合算法比现存的用于连续函数优化的蚁群算法更快地找到更好的结果,该融合算法具有良好的效果。我们进一步将融合算法应用于解决网格任务的调度问题。离散粒子群算法作为融合算法的前期寻优部分,并把其寻优结果转化为蚁群算法的初始信息素,解决了蚁群算法初始信息素匮乏的缺陷,蚁群算法部分的信息素更新通过局部更新和全局更新合理结合来提高蚁群算法的性能,并且用蚁群算法作为融合算法的后期搜索,可有效克服离散粒子群算法后期的局部搜索能力差的缺陷,又充分利用粒子群算法的快速收敛性和蚁群算法的正反馈机制的优点。仿真实验表明本文提出的融合算法在网格调度方面取得较好的效果。