快速混合粒子群优化算法应用研究

康鲲鹏

（商丘师范学院 计算机与信息技术学院，河南 商丘 476000）

为了提高生产效率，分配给一个流水车间单元的作业在不同条件下（如：机器的性能和配置），基于相似需求会被按类分成几组。这种课题被称为组调度（GS）。在组调度（GS）中，属于一个组的作业将会被连续处理而不会被其他组的作业打断。一般来说，每个机器的主要配置是用来在组之间实现处理转换的，当然也需要附带配置以便实现同组作业处理间的转换。如果为处理一组作业而配置各机器的时间依赖于每台机器对前一个组的处理，那么我们称这个问题为流水车间序列依赖组调度（FSDGS）问题。

以往人们研究了FSDGS问题时，他们设计了几个最小化最大完工时间（makespan）为性能衡量标准的元启发式算法，而且还设计了一个界定下界的方法来评估这几个元启发式算法的性能。由Kennedy和Eberhart[1]共同提出的一种新型进化技术—粒子群优化（PSO），获得了较多关注并被广泛应用于各个领域，尤其是对于连续优化问题。通过比较，PSO算法比已有的元启发式算法具有较大优越性。

基于当前FSDGS问题有限的研究成果和PSO算法在常规调度问题上具有潜力的性能以及在不同调度问题领域PSO算法逐渐普及的应用，使得我们为以最小化总流动时间为基准的FSDGS问题开发一种新型的PSO算法具有非凡的意义。

1 流水车间组调度问题

研究的问题可以借助Pinedo[2]研究结果中的符号Fm|fm ls，Splk，prmu|∑Cj。 Pinedo 在研究过程中对这些符号的解释和假设如下：

1）将g组作业赋予一个拥有m台机器的流水车间单元（Fm）。在这项研究中，Gp代表组P。

2）每一组（p=1，2，…，g）包含 bp个作业（ fm ls）。 研究中，Jpj代表组 p（p=1，2，…，g）中第 j个作业（ j=1，2，…，bp），组中作业的个数可以不同。

3）组（l）在机器（k）上的配置时间依赖于该机器上紧接在前被处理的组（p），即序列依赖于配置时间（Splk）。

4）所有的作业和组在所有的机器处理序列相同。（置换调度（prmu））

5）组中的每一个作业不需要独立的配置时间。如果需要的话，可以假设每个作业的运行时间包含了配置时间。

6）每台机器只需要在处理第一个组时配置一次。

7）同属于一个组的作业处理时不会被其他组的作业打断（成组技术）。

8）每个作业在每台机器上的运行时间与其他作业的运行时间是无关的。

1.1 解的表达式

解决组调度问题需要两个步骤：第一步，为每一组的作业寻找一个序列。第二步，为所有的组寻找一个序列。研究中，g+1个向量构成一个可行性解，前g向量表示组中作业的序列。最后一个向量对应组的序列。因为这两中类型的向量相互作用，所以这g+1个向量必须同步考虑。由于每个组中作业的个数是不相等的（如：bp≠bq），组调度问题的解可以用一个伪矩阵来表示。这种矩阵的特点是每行或者每列的元素可以不相等[3]。在伪矩阵中，前g行与各组中作业的序列有关，第g+1行（也就是最后一行）对应组的序列。例如，假设有3个组，每组中分别有3个、两个和4个作业，将这3个组逐个分配给拥有3台机器一个的车间单元来处理，则组中的作业可表示为：

G3（J33-J32-J34-J31）-G1（J12-J11-J13）-G2（J21-J22）

而组处理的序列所构成的伪矩阵可表示成下面的形式：

为了将PSO算法应用于当前问题，应将上面矩阵中的元素转换为整数。式（2）用来完成这种转换操作：

其中，bp是组 p（p=1，2，…，g）中作业的个数且 b0=0。 这种映像形式的转换可将式（1）中的伪矩阵转化为下面的伪矩阵：

基于这个新得到的伪矩阵，上例中每台机器上作业处理的顺序就变成的下面的形式：

2 标准粒子群优化

PSO是一种重在协作的迭代方法。PSO的整体称之为群，PSO整体中的每个个体称为粒子[4-5]。由当前位置及速度来确定的每个粒子，都是PSO中的一个潜在解。粒子在多维搜索空间中飞行从而使位置发生改变。将一个新位置和新速度值赋予某个粒子从而使其得到一个新位置。在搜索的过程中，每个粒子不断变换位置。位置值是通过计算位置目标函数值获得，上个阶段每个粒子获得的最佳位置被称为该粒子的最优值（p-best）。而所有粒子获得的最佳位置称为搜索的全局最优值（g-best）。 每个粒子都是基于其以前位置、（p-best）和搜索的（g-best）得到当前新位置值和速度的。

考虑一个d维的搜索空间，假设初始解（群的大小）的个数是 S。 此时，第 i（i=1，2，…，S）个粒子的参数由位置向量 xi=（xi1，xi2，…，xid）和速度向量 vi=（vi1，vi2，…，vid）构成。 定义第 i个粒子的 p-best为 yi=（yi1，yi2，…，yid），全局最优值 g-best为每个粒子的位置和速度参数更新可以通过对下面公式（5）和（6）的计算得到：

其中w是惯性权重，用来控制该粒子以前的速度值对当前的影响，c1和c2称为置信系数或者加速系数，r1和r2是在区间（0，1）上独立均匀分布的随机变量，i=1，2，…，S 且 j=1，2，…，d。

在PSO算法中，等式（5）用来根据粒子以前的速度和它们当前位置与p-best、g-best的距离计算其新速度。通常，为了控制粒子极端漫游而逸出搜索空间，应为新速度定义一个最大值（vmax）和一个最小值（vmin）。这种情况下，粒子的速度可以被约束在区间[vmin，vmax]上。根据等式（6），粒子从一个位置移动到一个新位置，不断重复这个过程，直到满足一个事先设定的停止标准。

在标准PSO算法中，解用向量来表示。本文中，我们把组调度（GS）问题中的每个可行性解都用一个伪矩阵来表示[6]。因此为了能用PSO算法来解决现在研究的GS问题，须将标准PSO算法作如下扩展：

设Xi是GS问题的一个可行性解，就像PSO搜索空间的一个粒子。Xi可以用一个（g+1）×h的伪矩阵来表示，前g行表示各组中作业的序列，最后一行表示组的序列。h的值等于组中作业的最大数和组的个数。则粒子Xi和其速度Vi可以分别用下面的矩阵表示：

与标准PSO相似，粒子的速度的更新可以基于下面的公式计算得到：

其中Yi是第 i个粒子的 p-best的值， 而Yˆ是 g-best。 k，j和 i的取值范围分别是 k=1，2，…，h，j=1，2，…，g，i=1，2，…，S，其他操作和标准PSO算法类似。

3 混合PSO算法

PSO算法多用于连续优化问题，而GS是一个离散问题（最优解是组的序列，组中作业调度其实也是个离散问题），因此需要对标准PSO算法作一些调整使之适合解决这样的离散问题。为此，课题组设计了一个基于排序值（Ranked Order Value，ROV）规则的新的编码方案。这个ROV规则可以将粒子连续的位置转化为作业和组序列。课题组还设计了一种被称为个体增益（IE）的邻域搜索策略，它由PSO构成，目的是提高了搜索能力并在搜索空间深度和广度方面做出平衡，这种算法被称为PSOIE。下面就来介绍这种基于扩展PSO算法，用来解决FSDGS问题的元启发式算法。

3.1 排序值规则

考虑一个流水车间GS问题的可行性解。假设Xi是一个在某连续空间中由作业和组位置的值构成的伪矩阵，且Xi对应现阶段空间的第 i个粒子。 设 Xi1=（Xi11，Xi12，…，Xi1b1）为伪矩阵中对应第一组作业序列的第一行。在ROV规则中，向量Xi1的最小位置值（SPV）首先映射为第一等级。然后，第二SPV值被指定为第二等级。同样的方法，所有位置上的值会被转化成第一组的一个作业序列。以此类推，将这种方法应用到伪矩阵Xi的所有行上。

3.2 领域搜索方案

假设Xi是GS问题的一个解伪矩阵。若与组序列（最后一行）相关向量中任意两个组的位置发生了变化，意味着该GS问题的一个新的解产生了。这个新伪矩阵被称为邻域矩阵。如果新解的目标函数值比当前目标函数值好，接受当前更新，否则另外选择两组[6]。这种方法被称为个体增益，具体应用如下：

为了标明组顺序，设定最后一行有g个位置。假设这些组的初始顺序是任意的，可以通过改变 “b1”和“b2”两个位置上的组顺序来产生一个领域矩阵，其中，1≤b1≤b2且b1≤b2≤g。如图1所示，在这个例子中假设有4个组，X是问题的一个解。 设定组的原始序列是 Xg=（1，3，4，2），且解 X 的目标函数值f=120。解Xg中头两个值进行交换，在这种情况下，新序列就表示成 Xnewg=（3，1，4，2）。 假设新序列的目标函数值是fnew=112。显然，新序列的目标函数比前一个好。因此，新解（Xg=Xnewg且f=fnew）是可以接受的。基于同样的规则，选定第一和第三个交换其位置上的值，迭代方式和结果如图1中所示。

图1 个体增益策略Fig.1 Individual enhancement strategy

很明显邻域矩阵搜索方案并不是直接应用在连续伪矩阵上而是应用在了离散伪矩阵的组序列上。为了做到这一点，连续伪矩阵中，使用个体增益策略交换组中元素位置的组值也应该作相应修正。因此，当邻域矩阵搜索结束时，为得到新连续位置值应该对其加以更新以保证ROV规则生成的序列结果和邻域矩阵搜索得到的结果相同[7]。

为了更利于研究当前的调度问题，本文在个体增益算法和粒子群优化算法的基础上，开发了一种混合算法。在每一个阶段，当PSO产生一个新解，个体增益算法会改进这个解并把它传递到下一阶段的PSO算法中进行处理。

3.3 PSO参数

本文的研究中，在等式（5）上我们设计的3个动态系数和，是经过深思熟虑的，在进化过程中它们呈现非线性的变化趋势[14]。在每个阶段，这3个系数的值可以通过下面几个等式计算得出：

其中ωmax和ωmin分别表示w的最大值和最小值。同样地，cmax1和cmin1分别表示c1的最大值和最小值，cmax2和cmin2分别表示c2的最大值和最小值。参数α是一个常量。I表示当前迭代次数，而max I表示总迭代次数。

初始粒子总数由下面的公式（11）为PSO算法随机生成：

其中Xmin和Xmax分别是连续搜索空间中位置的上下限。公式中的rand是区间（0，1）上的一个随机变量。类似的，粒子的初始速度由下面的公式（12）生成：

其中vmin和vmax和上面的解释类似，而rand是区间（0，1）上的随机变量。

表1 PSOIE算法和Salm asi给定下限的蚁群算法的平均百分比误差对比Tab.1 The average percentage error for the PSOIE algorithm and ant colony algorithm

4 结果和比较

本文将该PSO算法的性能与参考文献上提到的已知性能最好的元启发式搜索算法做了对比，如Salmasi等人提出的ACO算法。比较是基于Salmasi等人设计的流水车间测试问题进行的。这些测试问题产生自3个不同的集合，这3个集合的特点是：一个流水车间单元分别具有2个、3个和6个机器。共有2到16个组，每个组有2到10个作业。

为了比较算法的性能，在本文的PSO算法效果和ACO算法效果间进行了一次由Salmasi等人开发的t-测试。对比分别在2台、3台和6台机器问题间进行，并把每种问题的总流水时间的最小化值作为基准。附件B中是比较的统计结果。2台、3台和6台机器问题下两种算法比较的P-值参数很接近于零（分别是0.001，0.000和0.022）。因此可以推断，基于2台、3台和6台机器问题下两种算法的结果区别明显。就实验的3种问题来说，因为PSO算法的平均目标函数值都小于ACO算法的平均目标函数值，可以得出这样的结论，对于我们要研究的问题，PSO算法的解更加高效。为了做进一步的对比，针对实验问题，表2展示了由Salmasi提出的两种算法基于下限的百分比误差。这个下限可以用下面一个简单的公式计算得到：

（启发式算法的解-下限）/下限

如表2中所示，该PSO算法的百分比误差比ACO算法的百分比误差在3种情况下都低。为了对两种算法性能的做出更贴切的评估，图2展示了该PSO算法最优解所需时间柱状图，图3展示了ACO算法最优解所需时间最优解柱状图。两张图比较显示PSO算法比ACO算法能在更短的时间内趋于最优解。

图2 粒子群优化算法运行时间百分比柱状图Fig.2 Runtime percentage histogram for the particle swarm optimization algorithm

图3 蚁群优化算法运行时间百分比柱状Fig.3 Runtime percentage histogram for the ant colony optimization

5 结 论

文中开发了一种基于PSO的元启发式算法，用来解决Fmlfmls，Splk，Prmu|∑Cj问题。 然后将这种 PSO算法的性能与ACO算法的做了对比，ACO算法是已知文献上提到的最好的元启发式算法。结果表明，成对t-测试时该PSO算法的性能优于ACO算法，并且能够在较短的时间内找到最优解。这种PSO算法可以用来解决带有不同目标函数的FSDGS问题。如果能找到一个更好的邻域矩阵搜索机制的话，我们的算法还有改进的空间。后面的工作我们将致力于此。

[1]Kennedy J，Eberhart R.Particle swarm optimization[C]//Proceeding of IEEE International Conference on Neural Network， 4， Australia，1995:1942-1948.

[2]Schaller G E，Gupta JN D，Vakharia A.Scheduling a flow line manufacturing cell with sequence dependent family setup time[J].European Journal of Operational Research，2000，125（2）:324-329.

[3]Franca P M，Gupta JN D，Mendes P M，et al.Evolutionary algorithms for scheduling a flow shopmanufacturing cellwith sequence dependent family setups [J].Computers and Industrial Engineering，2005，48（3）：491-506.

[4]王江荣.基于粒子群优化算法的直线拟合及应用[J].工业仪表与自动化装置，2013（4）：73-75.WANG Jiang-rong.Straight line fitting based on particle swarm optimization algorithm and application[J].Industrial Instrumentation&Automation,2013（4）：73-75.

[5]杨柳春.基于粒子群优化算法的AR模型参数估计[J].工业仪表与自动化装置，2013（5）：67-69,95.YANG Liu-chun.AR model parameter estimation based on particle swarm optimization algorithm [J]. Industrial Instrumentation&Automation,2013（5）：67-69,95.

[6]Lin SW，Gupta J N D，Ying K C，et al.Using simulated annealing to schedule a flowshop manufacturing cell with sequencedependent family setup times[J]. International Journal of Production Research， 2009，47（12）：3205-3217.

[7]齐学梅，罗永龙.求解流水车间调度问题的混合粒子群算法[J].计算机工程与应用，2012，48（9）:33-39.QI Xue-mei，LUO Yong-long. Hybrid particle swarm optimization algorithm for flow shop scheduling problem[J].Computer Engineering and Application，2012，48（9）:33-9.