编码方案优化：基于任务列表、优先权值和抢占点的多维编码方案

任务列表与优先权值是两种在RCPSP中广泛采用的编码方案。这两种编码方式均采用1_SSGS进行解码（Ballestín et al.，2008），可能存在搜索空间小于解空间的问题，因此补充设计了包含抢占点的编码方案，以便拓展搜索空间。为方便说明各种编码方案，考虑如图9.4所示的项目调度实例，该实例包括5个非虚拟任务。

图9.4　项目调度实例

1.基于任务列表的编码

修改RCPSP的任务列表编码方式，使之适应1_PRCPSP。根据1_PRCPSP的问题描述，每一个非虚拟任务j＝1，2，…，n可以看作两个子任务ja和jb的组合，这样就可以按RCPSP的方式来表示一个项目的任务列表AL，其长度为2n+2。编码时维持任务间的优先关系，如图9.2所示。图9.5给出了图9.4的一个任务列表，其中包括了10个子任务。

图9.5　基于任务列表的编码

在PSO算法中，每个粒子的一个元素表示一个子任务，其位置则对应于SGS中的优先权。因此，我们用整数2j−1来表示任务ja，用2j来表示任务jb，用0表示虚拟的开始任务0，用2n+1来表示虚拟的结束任务n+1。

2.基于优先权值的编码

用一个2n+2维浮点数组来表示1_PRCPSP中各子任务的优先权值（priority value，PV）。子任务的PV值越大就代表该子任务在SGS中的优先权越高。PSO粒子处于一个2n+2维空间，其2n+2个元素代表了项目的2n+2个子任务。其中，第1个位置和第2n+2个位置分别表示虚拟任务0和虚拟任务n+1的优先权值。非虚拟任务j＝1，2，…，n的两个子任务ja和jb，其优先权值分别用数组的第2j个位置和第2j+1个位置来表示。为控制搜索空间，规定优先权值的取值范围为［0，1］。图9.4示例项目的各个子任务PV的一种可能的取值方案如图9.6所示。(www.xing528.com)

图9.6　基于优先权值的编码

3.基于任务列表和抢占点的编码

这是一种二维编码，包括了两个向量。在基于任务列表编码的基础上，引入“抢占点”这一编码维度，构造二维粒子（Ballestín et al.，2008；Zhang et al.，2006）。第一维与基于任务列表的编码方式一样，长度为2n+2；第二维长度为n+2，使用［0，1］区间上的小数pp来表示相应任务第一部分的工期占整个任务工期的比例。若任务j的工期为dj，则其被抢占后第一部分ja的工期为，函数ROUND（∙）表示四舍五入取整；而第二部分jb的工期则为djb=dj−dja。我们将该编码方案称为基于任务列表和抢占点的编码（activity list with preemption point，ALPP）。图9.7给出了ALPP的一个示例，用于展示其具体结构。

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

4.基于优先权值和抢占点的编码

与基于任务列表和抢占点的编码方式类似，基于优先权值和抢占点的编码也是一种二维编码。第一维是优先权值的编码，第二维是抢占点的编码。我们将该方案称为基于优先权值和抢占点的编码（priority value with preemption point，PVPP）。图9.8给出了一个示例。

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