遗传算法是近年兴起的一种用于解决优化问题的并行寻优算法,已被用于分布式系统的任务调度中。经研究表明遗传算法比启发式算法有较大的优越性。本文提出了一种用广义遗传算法解决任务调度的方法,具体内容有: 1.设计了任务分布的问题模型,设计了一种新的编码方式,即“一维分离编码”方式。其中,每个个体由左子串和右子串两部分构成。左子串描述任务分配的情况,右子串描述任务的调度顺序。左、右子串因任务分配和任务排列的要求不同而执行不同的杂交和变异操作,使搜索空间扩大到整个解空间上。此外,在任务调度中,让上一代母体中具有较高适应值的染色体(即最佳和次佳个体)直接进入下一代参与进化,而不是通过轮盘赌的形式进入下一代,以加快算法的收敛过程。 2.设计了任务调度问题的数学模型和针对该调度问题的广义遗传算法的马尔可夫链模型。 3.在单机系统中,利用VC++语言搭建了一个模拟局部任务调度的仿真系统LD。 仿真结果表明,与在这一问题上常采用的二维编码的遗传算法相比,本算法能得到更好的解;与不采用广义遗传算法而代之以精英策略的遗传算法相比,本算法具有更快的收敛速度,具有较大的优越性,适合处理一定规模的调度问题。