求解PFSP问题的多粒子群协同学习算法

秦志伟，黄友锐，徐善永

(安徽理工大学电气与信息工程学院，安徽 淮南 232001)

置换流水车间调度问题(Permutation Flow Shop Scheduling Problem，PFSP) 是在流水车间调度的特例，即增加了每台机器上所有作业的加工顺序都相同这一约束。但当机器数大于等于3时，置换流水车间调度问题还是属于典型的 NP 问题[1]117。该调度问题被广泛用于指导实际生产，可以有效提高企业生产效率与设备利用率。因此研究高效的求解算法具有重要的理论和工程意义。

粒子群算法[2](Particle Swarm Optimization，PSO)因为其通用性好、参数少、易实现等优点，被广泛应用于模式识别、神经网络、生产调度等领域，PSO求解流水调度问题也成了研究的热点。文献[3]设计了一个基于随机键最小位置值(Smallest position value，SPV)的规则，使得算法中的粒子由连续空间映射到离散空间。文献[4]提出了一种混合粒子群算法来求解最小化中间存储有限的调度问题的makespan，并在初始化中使用了启发式规则，还加入了局部搜索以及模拟退火的思想，通过仿真表明此算法的有效性。文献[5]将启发式信息和激素调节机制结合，对粒子飞行方程进行改进，为解决PFSP提供了一个新的思路。文献[6]将粒子群算法与迭代贪心算法混合，用来求解PFSP中的makespan，取得了很好的效果。文献[7]将假设检验、模拟退火结合粒子群，用于解决分布式置换流水车间调度。文献[8]提出一种基于Taguchi的粒子群算法并将其用于多目标置换车间调度。

针对粒子之间信息交流不足、高维求解困难等的缺点，本文在协同粒子群算法(Cooperative Particle Swarm Optimization，CPSO)[9]的基础上，将一种多粒子群协同学习算法(MPSO-CL)用于置换流水车间调度。该算法引入了精英策略，通过不同规模Taillard系列基准实例的仿真分析，验证该算法在求解PFSP的有效性与可行性。

1 相关问题数学描述

1.1 PFSP数学描述

PFSP的总体目标就是合理地安排工件在每台机器上的加工顺序，使所有工件最大完工时间(Makespan)最短。在研究该类调度问题时经常作以下假设：n个工件以相同的顺序在m台机器上加工；每台机器上所有工件的顺序是一样的；每个工件在同一时刻只能在一台机器上进行加工；每台机器同一时刻只能处理一个工件；工件在上一个机器加工完成后，立即送到下一台机器加工；每台机器加工工件的过程不允许中断[10]。

令π={π1，π2，…，πn}为一个排序，Pπ，j和Cπ，j分别为πi在机器j上的加工时间和完成时间，则PFSP数学描述如下

min∶Cmax(π)

(1)

(2)

式中：Cmax(π)为最大完成时间。

1.2 协同粒子群算法数学描述

(3)

xi=xi+vi

(4)

式中：w(w≥0)为惯性权重，c1和c2为正的学习因子，r1、r2是[0，1]区间内均匀分布的随机数。

第j个子群粒子个体最优位置更新公式如下

(1≤j≤k) (5)

第j个子群的全局最优位置更新公式如下

(1≤i≤s，1≤j≤k) (6)

2 多粒子群协同学习算法

2.1 多粒子群协同学习算法模型

本文在文献[11]的模型基础上重新定义了学习交流机制，引入了综合学习策略和精英策略，提出了一种经验指导的精英学习策略，其框架如图1所示。

图1 多粒子群协同学习算法模型

定义1精英库种群Z0(t)=(P1Y1，P1Y2，…，PjYi)，PjYi表示第j个子种群的第i个代表。精英库种群Z0是由按照Pareto 的精英理论中的 80/20 法则从普通种群中筛选组建成的，它保存了各普通种群在进化过程中产生的优良基因。利用综合学习策略使精英库种群内部个体相互学习，保持其种群多样性，防止出现早熟收敛现象。

定义2普通种群Z(t)=(P1，P2，…，PI)，其中I∈Z+，其中ZI(t)表示第I个子种群。在进化过程，每一个普通种群中的个体都有概率向精英中的最好个体学习，否则只能学习自己的历史经验。同时隔代引进若干个精英库种群的个体指导普通种群进化，同时淘汰其适应度最差的个体，实现了种群间的信息共享交流。

2.2 改进的综合学习策略

精英库种群采用综合学习粒子群算法(CLPSO)[12]更新，其速度更新公式如下

vid=wvid+c3r3(Pbestfi(d)-xid)

(7)

式中：fi=[fi(1)，fi(2)，…，fi(D)]表示粒子i学习的Pbest向量。通过选择概率Pc来决定精英是否需要综合学习，在[0，1]之间产生一个随机数k1，当k1

CLPSO算法由于速度更新中采用的是较优的粒子，算法后期收敛速度变慢，甚至停滞。

所以在速度公式上加入柯西扰动项

vid=wvid+c3r3(Pbestfi(d)-xid)+

(8)

同时设置并设置进化停滞阀值Tn

(9)

每当CLPSO更新最优不变，flag就会加1，当达到预设阀值，就会产生一个扰动，使精英库粒子摆脱停滞状态，在新的邻域里更好地寻优。

2.3 经验指导的精英学习

本文在文献[13]468的基础上，提出了一种基于经验指导的精英学习策略来对普通种群中的每个子群个体极值进行局部搜索。当普通种群每次迭代更新个体极值时， 通过Pe进行决策，当大于Pe时，该子群将由精英库种群的历史最优pbeste1来指导学习搜索，否则通过每次迭代更新历史最优pbest1、次优pbest2的差分来指导个体极值来指导学习搜索。历史经验指导的学习公式如下

(10)

式中：r为[-1， 1]之间随机数，控制局部搜索的方向，d(t)为第t代时的缩放因子，控制局部搜索范围。

进化前期，pbest1距最优解一般比较远，这时较大的d(t)进行粗粒度局部搜索， 加快收敛速度； 进化后期， pbest1距最优解一般比较近， 这时通过较小的d(t)进行细粒度搜索， 可以提高解质量。 d(t)的设置给出一种非线性递减的取值。

d(t)=d0·exp(-t/(Gennum-t))

(11)

最后对于学习后的结果进行适应度评价，若适应度好于原有的，则替换原有的最优极值。

(12)

2.4 隔代精英迁移

普通子种群内部进化过程中，每隔两代需要进行一次评价，若每一个子群的全局最优个体的适应度小于等于精英库种群的全局最优时，则从精英库种群中随机引入个体并淘汰该种群中适应度最差个体。

通过隔代精英迁移，普通种群既传承了精英库种群优良的基因模式，加快了其向最优解的收敛性能，又增强了群体的多样性，提高了寻优能力。

2.5 粒子的编码与解码

本文采用了 SPV 法[1]118来对工件的加工顺序进行提取。粒子的每一维表示一个工件，所得到的随机数表示粒子每一维的位置，对粒子每一维的位置进行升序排序，然后将粒子排序好的新位置与原来维数进行映射。

3 算法步骤

Step 1 初始化。设置种群规模psize、迭代次数Gennum、惯性权重w、学习因子c1、c2，综合学习概率Pc、精英学习概率Pe、缩放因子初值d0。

Step 2 按照spv规则，获取每维粒子对应的工件加工序列，并由加工序列对其调度目标进行评价。

Step 3 根据Pareto 的精英理论中的 80/20 法则选择每个子群的20%个体组建精英库种群。

Step 4 对于精英库种群，采用改进综合学习策略。

Step 5 对于普通种群，采用历史经验指导的学习策略。

Step 7 若当前迭代次数为偶数，执行精英迁移策略，否则转到step 8。

Step 8 循环 step 2～step 7，根据式(2)、式(3) 更新普通种群各子群粒子的速率和位置， 根据式(8)、式(3)更新精英库种群的粒子速率和位置。

Step 9 更新迭代次数Gennum，若还在迭代范围内，则转到step 2；否则，停止更新。

Step 10 输入全局最优值和对应调度方案，调度算法运行结束。

4 仿真结果及分析

为了验证算法的有效性，本文选择文献[14]提出的Ta系列的基准问题进行仿真实验。使用 Matlab2015b 软件编程实现，参数设置与文献[13]469相同，分裂因子为5，惯性权重w=0.4，学习因子c1=c2=2，精英库种群综合学习概率Pc=0.3，缩放因子初值d0=40，设置普通种群精英学习概率Pe时，分别使用0.1、0.3、0.5、0.7、0.9值求解Ta系列基准算例Ta11、Ta21、T31、Ta41各10次，将平均值作为各算例的运算结果，再获得所有算例求解结果的平均值并进行比较，结果Pe取0.7较好。种群规模psize=150，迭代次数Gennum=500。设置好参数后，MPSO-CL与PSO、CPSO进行比较，分别将每种算法运行10次，对每种算例运算所得的最好结果加粗显示，得到仿真结果如表2所示。

表2中，最佳相对偏差BRE(Best Relative Error)和平均相对偏差ARE(Average Relative Error)的计算公式如下

(13)

(14)

由表1可知， PSO求解PFSP问题结果最差，CPSO运行结果比PSO有所改进，除了Ta51三种算法，MPSO-CL的结果比PSO、CPSO都好，改进效果很好， Ta01、Ta22、Ta35、T61都寻到了最优结果。从稳定性上可以看出， MPSO-CL的结果相对与其他三个算法比较稳定。在处理大规模调度问题上，PSO与CPSO、MPSO-CL差距很大，说明协同进化算法在解决大规模调度问题的优势，而改进后MPSO-CL比CPSO在精度、稳定性上都有提升。

为了更突出三种算法之间的差异，图2给出了三种算法在求解Ta21、Ta71调度问题上的进化曲线。

图2中，三种算法在执行的初始阶段，PSO收敛速度被远远拉下，是由于CPSO和MPSO-CL都采用了“分而治之”[16]的协同思想；由于采用学习策略局部搜索， MPSO-CL的收敛速度有所下降，但不会陷入停滞，而CPSO易陷入“伪极值点”，却无法跳出。以上说明MPSO-CL求解置换流水车间问题的有效性。

(a) Ta21

(b) Ta71图2 PSO、CPSO和MPSO-CL进化曲线

5 结论

本文针对置换流水车间调度中求解最小化最大完工时间问题进行了研究，提出一种多粒子群协同学习粒子群算法来进行优化。该算法在协同粒子群算法的基础上，将种群分为精英库种群和普通种群，精英种群采用综合学习策略，避免了早熟收敛；普通种群采用一种新的精英学习策略进行局部搜索，提高了解的质量；并且还引入精英迁移策略，增加了种群多样性。通过不同规模Taillard系列基准实例与PSO、CPSO进行仿真比较，结果验证该算法在求解PFSP上的有效性，在大规模调度上取得了不错的效果。