论文部分内容阅读
网格作为计算机领域的研究热点之一,近年来受到了广泛的关注。网格中的任务调度,对发挥系统的并行性能和保持负载平衡具有举足轻重的作用。如何快速而有效地实现多机系统内的全局任务调度,无论在理论研究还是实际应用中都有十分重大的意义。已有文献证明,由于网格的复杂多变和任务的层出不穷,网格中的任务调度属于NP完全问题,很难用传统的搜索办法在多项式时间内找到最优解。由此人们想到利用现代启发式算法来解决网格中的任务调度问题。
遗传算法是近年兴起的一种用于解决优化问题的启发式算法,被广泛用于解决各类NP问题和任务调度问题,并有仿真实验证明,在处理调度问题时,遗传算法与传统调度算法相比具有较大的优越性。但是经典遗传算法本身也存在一定的缺陷,实时性较差,存在运行随机性和不稳定性,因而吸引了大批学者致力于改进遗传算法的探索和研究中。
在本文中,首先对经典遗传算法,广义遗传算法和并行广义遗传算法进行了数学分析,得到:广义遗传算法比经典遗传算法有更好的收敛性和全局寻优能力:并行广义遗传算法比广义遗传算法有更高的运行效率,更适合在有多处理机的网格系统中处理分布式任务的调度问题。我们提出的任务调度算法以并行广义遗传算法为基础,根据参考文献[4]的研究,本算法采用统一二进制编码。考虑到生物界不变的规律:父代强壮,子嗣必然强壮,我们对广义遗传算法又做了进一步的扩展:利用问题的领域知识,把握最优解在问题空间中的分布,再在这个分布范围内随机设定初始群体,也可以利用其它的寻优算法,生成一些近优解,组成初始群体。而从算法本身而言,则可以通过过量生成初始个体,从中挑选优势个体的方式构成初始群体。通过这样方式生成的初始种群,必然会在今后的进化过程中占据优势,能够更快的收敛到全局最优解,提高任务调度器的实时性。本文在第五章中对此也进行了实验对比,对比结果表明优秀的初始种群的收敛速率更快,算法的全局寻优能力更强。
同时我们利用Matlab的Distributed C0mputing工具箱对并行广义遗传算法进行了仿真。虽然由于试验环境所限,试验结果与数学推导公式略有偏颇,但仍旧可以证明并行广义遗传算法比广义遗传算法有更高的运行效率和实际应用价值。