项目调度遗传算法编码方案与算法优化探讨

在确定项目调度遗传算法采用的编码方案后，可以相应设计其他算法组成部分，并针对项目调度的特定问题做专门的设计。现有文献基本上都采用项目调度目标函数构造适应函数，在此不再赘述。此外，各个参数的设定会影响算法效率，也需要加以分析。

1.初始种群

在项目调度研究领域，多数遗传算法采用随机方式产生初始种群。部分学者采用其他方式产生初始种群，以期提高初始种群的质量。例如，Hartmann（1998）采用随机选择的任务优先规则来产生初始种群。Alcaraz和Maroto（2001）则采用偏倚随机抽样产生初始种群。

绝大多数遗传算法只采用一个种群。也有学者采用两个种群，一个种群的个体为正向积极进度计划，另一个种群的个体为右向积极进度计划，并分别采用正向调度和逆向调度技术以提高解的质量（Debels and Vanhoucke，2005，2007）。

2.选择方

各种选择方式在项目调度遗传算法中都得到了应用。多数研究证实排序选择和竞赛选择效果较好。相对而言，二元竞赛选择方法具有一定的优势（Alcaraz and Maroto，2001）。

3.交叉算子

对于项目调度而言，单点交叉、两点交叉及均匀交叉是最常见的几种变异算子。Hartmann（1998）和Hindi等（2002）都采用了上述常见的三类交叉算子。Hartmann（1998）的计算测试结果表明其中两点交叉算子的效果最好。

Goncalves等（2008）采用了参数化均匀交叉（parameterized uniform crossover）算子。首先，限定一个配对染色体必须来自当前种群的精英染色体集合，另一个染色体则不做限制，然后根据随机数决定子代基因是按照精英染色体的等位基因赋值还是按照普通染色体的等位基因赋值。(www.xing528.com)

一些学者设计了较为特殊的交叉算子。例如，Alcaraz和Maroto（2001）基于其染色体表达方式设计了三种新的交叉算子：优先集交叉（precedence set crossover），正向逆向交叉（forward-backward crossover），两点正向逆向交叉（two-point forward-backward crossover）。Valls等（2008）设计了峰交叉（peak crossover）算子，以保留父代中资源需求高峰的模式，并按照配对染色体信息确定其他时段的任务进度计划。这些交叉算子计算较为复杂，但有助于遗传算法搜索最优解。

4.变异算子

在各种常见的变异算子中，反转变异和对换变异适合于除任务列表外的各类染色体表达方式，而均匀变异和非均匀变异较适合于随机键表达方式、移位向量表达方式及直接表达方式。

对于采用任务列表表达方式的染色体，对换变异可能会形成不可行的任务列表。因此，Hartmann（1998）将对换变异做了限制：首先对随机选中的任务，只和列表中下一位任务进行对换；其次，如果对换后的任务列表不可行，则放弃对换。Boctor（1996）采用的方式有所不同：首先，随机选择一个任务，然后将其随机地插入任务列表中，但同时保证该任务在所有紧前任务之后并在所有紧后任务之前。Alcaraz和Maroto（2001）的计算测试表明，Boctor（1996）设计的变异算子显著优于Hartmann（1998）的变异算子。

对于附加基因，如控制正向调度或逆向调度的基因，则可以采用取反的方式进行变异（Alcaraz and Maroto，2001）。

5.参数设定

Hindi等（2002）对种群规模做了研究，认为种群规模在等于任务数量时，算法效果较好。但值得指出的是，其他研究未能进一步证实Hindi等（2002）的结论。一般认为，在限定产生同样多个解的前提下，种群规模对算法效率有显著影响（Hartmann，1997）。

Alcaraz和Maroto（2001）的计算测试表明，交叉概率和变异概率的合理取值取决于项目规模。