编码方案对遗传算法的影响及其应用探讨

对于遗传算法而言，编码方案，也就是染色体表达（chromosome representation）方式，对于算法效率有相当显著的影响。而整个遗传算法的设计，包括各类遗传算子，也必须针对编码方案进行设计。

对于RCPSP而言，现有文献中主要存在以下五种染色体表达方式。

（1）任务列表表达方式（activity list representation）：项目的进度计划通过一个可行的任务列表来进行表达，缺省采用串行SGS对染色体进行解码。在解码过程中，遵循一般的SGS规则，即每一项任务都在满足紧前关系与资源约束的条件下尽早开始。这是现有文献中被大量采用的染色体表达方式（Alcaraz and Maroto，2001；Hartmann，1998；2002；Hindi et al.，2002；Lova et al.，2009），由于其内嵌了任务之间的紧前关系，也被数值实验证明为一种有效的表达方式（Hartmann and Kolisch，2000；Kolisch and Hartmann，2006）。

（2）任务优先规则表达方式（priority rule representation）：在这种表达方式中，通常事先给定一组任务优先规则，而染色体的每一个基因则表示一个特定的任务优先规则。任务优先规则在不同基因之间允许出现重复。在解码过程中，则采用串行或并行进度生成机制，在每阶段分别采用染色体中指定的优先规则选取任务进行调度。Hartmann（1998）与Ozdamar（1999）都曾经采用这种染色体表达方式构建项目调度遗传算法。

（3）随机键表达方式（random key representation）：在这种表达方式中，遗传算法为每个任务分配一个实数，这些实数构成的向量即为一个染色体。可以采用串行SGS或并行SGS对染色体进行解码。在解码过程中，每一个阶段的可行任务集合中键值最高的任务被选中进行调度，并安排其尽早开始。随机键表达方式在调度领域也得到了广泛应用（Debels and Vanhoucke，2007；Hartmann，1998；Lee and Kim，1996；Mendes et al.，2009；Van Peteghem and Vanhoucke，2010）。此外，由于PSGS有可能将最优解排除在可行解集合之外，一些学者对PSGS的随机键表述方式进行了修正，允许延迟候选任务以使搜索空间不局限于非延迟进度计划集合（Cho and Kim，1997）。

（4）移位向量表达方式（shift vector representation）：在这种表达方式中，染色体是一个移位向量，该向量为每个任务分配一个非负整数。在解码过程中，一个任务的所有紧前任务结束时间的最大值加上其对应的移位值，就是这个任务的开始时间。这种染色体表达方式的解码过程并不考虑资源约束，因此解码所得的项目进度计划不一定满足资源约束，也就是说不一定是可行解。这种表达方式最早由Sampson和Weiss（1993）提出，之后Lambrechts等（2008）对其做了改进，同时考虑紧前关系和资源约束，提出了时间缓冲列表表达方式（buffer list representation）。

（5）直接表达方式（direct representation）：在这种表达方式中，染色体每个基因的值就是所对应的任务的开始时间。因此，这种表达方式不需要解码过程。但是，这种表达方式在项目调度领域应用很少，因为这种表达方式既不考虑紧前关系，也不考虑资源约束，其对应的项目进度计划通常是不可行的。现有文献中，只有极少数遗传算法采用这一编码方案（Toklu，2002）。另外，Thomas和Salh（i1998）提出的禁忌搜索算法也直接在项目进度计划上进行领域搜索。直接表达方式也被称为基因型（genotype），而间接表达方式则被称为表达型（phenotype）。(www.xing528.com)

也可以对上述表达方式加以修饰。例如，可以在染色体尾端增加一个额外的基因，用于表达进度生成机制是采用SSGS还是PSGS（Hartmann，2002），或是采用正向调度还是逆向调度（Alcaraz and Maroto，2001）。

对于更加复杂的项目调度问题，则需要在上述编码方案基础上进行相应调整。例如，对于抢占式RCPSP，可以设计两种新的编码方案：（6）基于任务列表和抢占点的编码；（7）基于优先权值和抢占点的编码。

对于编码方案（6）和（7），为解决抢占点确定问题，需要设计相应的二维编码，在基于任务列表（或优先权值）编码的基础上，引入“抢占点”这一编码维度，构造二维染色体。其中第一维的长度为2n（不考虑虚拟任务j0和jn+1，下同），表示任务列表（或优先权值），其构造方式与基于任务列表（或优先权值）的编码相同。任务列表是项目网络图的一个拓扑排序；优先权值列表使用（0，1）区间上的数值k来表示任务（各部分）的优先权值，k值越大代表该任务（部分）执行的优先权越高。第二维长度为n，采用（0，1）区间上的数值l来表示相应任务第一部分的工期占整项任务工期的比例。若任务j的工期为pj，则其被抢占后第一部分的工期为Round（pjlj）。Round（）表示四舍五入取整。

基于任务列表和抢占点的编码方案如图7.7所示，其中τi∈{a，b}；基于优先权值和抢占点的编码方案见图7.8。由于采用了新的编码方式，在解码时也需要相应调整进度生成机制（寿涌毅等，2014a）。

图7.7　基于任务列表和抢占点的编码

图7.8　基于优先权值和抢占点的编码