作业车间调度问题(JSP, Job shop scheduling problem)是作业车间系统生产管理的核心部分，在实现制造过程智能化的过程中发挥着重要作用。多目标柔性作业车间调度问题(MO-FJSP, multi-objective flexible job-shop scheduling problem)同时对多个性能指标进行优化，在解决工序排序问题时考虑了工序加工机器选择问题，更加贴近于实际生产环境，因而受到了诸多学者的广泛关注^[1-4]。

MO-FJSP是更为复杂的NP-hard问题^[5]。Deb等^[6]引入快速非支配排序和拥挤距离计算提出了NSGA-Ⅱ算法，被广泛应用于多目标优化问题求解，但也存在易于早熟和多样性不足等问题，许多学者对该算法做出了改进。Seng等^[7]通过计算拥挤度和非支配水平来优化新的种群选择，提出一种基于改进NSGA-Ⅱ的柔性车间作业低碳调度方法。缪嘉成等^[8]针对RV减速器结构优化问题，提出一种离散变量的编码方案改进NSGA-Ⅱ。陈辅斌等^[9]利用免疫平衡原理改进NSGA-Ⅱ算法的选择策略和精英保留策略，提高了算法的优化性能。胡成玉等^[10]提出一种改进拥挤距离和自适应交叉变异的NSGA-Ⅱ算法求解分布式数据中心负载调度问题，提升了算法收敛速度和精度。以上研究对NSGA-Ⅱ算法的改进大都采用单一种群的遗传操作模式，进化过程中缺乏激烈竞争关系，难以进化出适应性较强的个体。多种群进化策略可以有效改善算法对解空间的探索能力和开发能力，提高解的多样性和分布均匀性。程子安等^[11]提出一种改进的双种群混合遗传算法求解柔性作业车间调度问题，两个种群采用不同的交叉与变异算子以提高种群多样性，然而种群比例参数由人为设定，降低了算法的灵活性。近年来，许多研究将强化学习与智能算法结合应用于实际问题求解，Chen等^[12]利用强化学习技术保持遗传算法中种群的多样性，防止GA过早收敛，提出一种基于强化学习的最优RS算法。王晓燕等^[13]提出一种基于强化学习的多策略选择遗传算法将种群划分为3个子种群分别进化，提高收敛速度的同时改善了全局收敛问题，但仅优化单个目标。封硕等^[14]将支持强化学习RNSGA-Ⅱ算法应用于无人机多目标三维航迹规划规划问题，通过动态优化种群间迁徙参数保持种群多样性，提高了收敛速度和收敛精度，但遗传操作方式单一减小了局部搜索空间。

根据上述研究内容的优势与不足，提出一种基于强化学习的改进NSGA-Ⅱ算法用于求解多目标柔性车间调度问题。首先，根据性别判定法和种群比例参数将种群划分为两个不同的种群，并为每个种群分配不同的进化目标与遗传操作，增强算法全局与局部搜索能力。迭代过程中运用强化学习机制动态调整种群比例参数，自主保持种群多样性及分布均匀性在合理范围，有效改善了算法寻优能力与收敛性能。通过对标准算例实验仿真，验证了RLNSGA-Ⅱ在求解多目标柔性车间调度问题上可以获得较优的Petro解集。

1 多目标柔性作业车间调度模型

MO-FJSP需解决n个工件{J₁, J₂, …, J_n}的加工机器分配以及在m台机器{M₁, M₂, …, M_k}(k∈{1, 2, …, m})上的加工顺序问题。其中，每个工件J_i(i∈{1, 2, …, n})有p_i道工序，工序O_ij(j∈{1, 2, …, p_i}) 的加工时间由所选机器性能决定。调度的目标是在满足加工约束条件下使所期望的多个性能指标得到优化。

调度模型考虑生产效率和设备利用率两个方面，针对最大完工时间(C_m)、机器总负荷(W_t)以及瓶颈机器负荷(W_m)3个指标同时进行优化，调度优化目标集可以表示为min(C_m, W_t, W_m)，其中最小化最大完工时间是为了提高生产效率，而降低机器负荷可以提高机器利用率及机器寿命。目标函数的计算公式如下。

1) 最大完工时间。

$\min C_{\mathrm{m}}=\max \limits_{1 \leqslant i \leqslant n}\left(\min \limits_{i \leqslant j \leqslant p_i} C_{i j}\right) 。$

(1)

2) 机器总负荷。

$\min W_{\mathrm{t}}=\sum\limits_{i=1}^n \sum\limits_{j=1}^{p_i} \sum\limits_{k=1}^m T_{i j}^k 。$

(2)

3) 瓶颈机器负荷。

$\min W_{\mathrm{m}}=\max \limits_{1 \leqslant k \leqslant m} \sum\limits_{i=1}^n \sum\limits_{j=1}^{p_i} T_{i j}^k 。$

(3)

s.t.

$S_{i j}+T_{i j}^k=C_{i j}, \forall i, j, k 。$

(4)

$C_{i j} \leqslant S_{i(j+1)}, \forall i, j 。$

(5)

$S_{i j}+T_{i j}^k \leqslant S_{h g}+L\left(1-\beta_{i j h g}^k\right), \forall(i, h), (j, g), k 。$

(6)

$\sum\limits_{k=1}^m \alpha_{i j}^k=1, \forall i . j 。$

(7)

$S_{i j} \geqslant 0, C_{i j} \geqslant 0 。$

(8)

式(1)中p_i为工件i的工序数量，C_ij表示工序O_ij的加工结束时间；式(2)中T_ij^k为工序O_ij在机器k上的加工时间；式(4)表示工序加工不允许中断，S_ij表示工序O_ij的加工开始时间；式(5)表示约束工序加工顺序；式(6)为限制机器不可同时加工多道工序，其中β_ijhg^k为决策变量，若工序O_ij先于工序O_hg在设备k上加工，则β_ijhg^k=1，否则β_ijhg^k=0，L为一个足够大的正实数；式(7)表示工序仅能在一台机器上加工，其中α_ij^k为决策变量，若工序O_ij在设备k上加工，则α_ij^k=1，否则α_ij^k=0；式(8)表示所有参数变量必须为非负数。

2 RNSGA-Ⅱ算法求解多目标柔性车间调度问题

NSGA-Ⅱ种群进化过程如图 1所示。首先对种群P_t执行选择、交叉、变异操作形成种群Q_t，并将2个种群合并为种群R_t，然后对种群R_t进行非支配排序形成多个前列面F_i，并从低到高依次加入新一代种群P_t+1，当F_i加入使得种群超出规模大小时，依据拥挤距离从大到小将个体加入新一代种群P_t+1。由于降低了计算复杂度，NSGA-Ⅱ被广泛应用于多目标优化问题。但求解多目标柔性作业车间调度问题时，存在精英选择策略导致种群多样性不足使得算法陷入局部最优解、早熟收敛的问题。因此，笔者通过融合多个多样性度量指标，采用双种群进化策略和强化学习改进NSGA-Ⅱ求解多目标柔性作业车间调度问题。

2.1 双种群进化策略

多目标进化算法大都采用单一进化策略，在一定程度上降低了算法的搜索能力和收敛速度，增加了算法的随机性。采用双种群进化思想可以提高NSGA-Ⅱ进化的方向性和适应性，扩大搜索空间，避免算法陷入局部最优的问题。在进化过程中，根据种群比例参数和性别判定法^[15]将种群拆分为两个种群，并对两个种群采用不同的遗传操作。针对多目标优化问题，采用性别判定法拆分种群的流程如下。

1) 确定染色体种群规模N、测试种群规模S、种群分割比例参数β。

2) 随机生成数量为S的测试种群。

3) 计算染色体种群中个体的繁殖能力，具体过程如下。

For i=1 To N do

  For j=1 To S do

    a)个体i与个体j进行交叉操作后产生后代个体；

    b)如果后代个体支配个体i，则后代个体替换个体i并将个体i的繁殖能力加1；

  End for

End for

4) 评判染色体种群中个体的繁殖能力，具体过程如下。

For i=1 To N do

  If(个体i的繁殖能力大于平均繁殖能力)

    个体i为繁殖个体；

  Else

    个体i为普通个体。

End for

5) 种群分割。选择繁殖个体中繁殖能力较强的N×β个个体形成子种群1，若数量不够，则挑选普通个体中繁殖能力较强的个体补充；剩余个体形成子种群2。

种群1中的个体由于繁殖能力较强，因此对工序排序部分采用普通的POX交叉和插入变异^[16]方式，机器选择部分采用单点交叉和单点变异，从而保持种群的全局优势。而对于种群2，利用普通的遗传操作难以产生新的个体，降低了算法的局部搜索能力，因此对工序排序部分采用改进的POX交叉方式和基因串逆序变异方式，如图 2(a)和(b); 机器选择部分选择均匀交叉和定向变异方式，以提高算法的收敛能力，如图 3(a)和(b)所示。

2.2 多目标问题多样性度量

多目标问题中非劣解集在近似Pareto前沿上分布得越均匀、越离散则表明多样性更好。常用的指标包括^[17]Sigma度量、解间距度量、网格度量、熵度量和个体空间度量等。然而，单一评价指标会导致一定程度的偏差。因此考虑解间距和熵度量值两个指标对多样性进行度量，并结合强化学习动态控制种群比例参数，实现多目标柔性车间调度问题优化求解。

2.2.1 解间距度量(spaceing metric)

设算法搜索到的具有Pareto性的前沿解的个数为|A|，则解间距指标S_p定义为：

$S_{\mathrm{p}}=\sqrt{\frac{1}{|A|-1} \sum\limits_{i=1}^{|A|}\left(\bar{d}-d_i\right)^2},$

(9)

其中

$d_i=\min \left\{\sum\limits_{h=1}^H F_l\left(x_i\right)-F_l\left(x_j\right)\right\}, i=1, 2, \cdots, |A|, j=1, 2, \cdots, |A|,$

(10)

d是解集中个体间距离的均值，H表示目标函数的个数。S_p越小则得到解的分布越均匀，种群多样性越好。

2.2.2 熵度量(Entropy)

设种群X有划分X={X₁, X₂, …, X_Q}, 其中1≤i≤Q, Q为划分数，则

$P_i=\frac{\left|X_i\right|}{N},$

(11)

式中：P_i表示个体i落入第i个划分的概率; |X_i|表示第i个划分的个体数目; N表示整个种群的规模。种群多样性熵的计算公式为

$H=-\sum\limits_{i=1}^Q P_i \log _2 P_{i}。$

(12)

当熵值越大时，种群中个体分布得越离散、越均匀，种群的多样性也越好。

2.3 基于强化学习的比例参数调整策略

强化学习是一种目标驱动的自适应优化控制方法，智能体Agent通过与环境进行交互来调整自己的行动策略。其最终目标是获得最优策略π^*，使得期望累积回报E=[R_s|s_t=s]最大。强化学习的迭代计算公式为

$Q\left(s_t, a_t\right)=Q\left(s_t, a_t\right)+\alpha\left[r_{t+1}+\gamma \max Q\left(s_{t+1}, a_t\right)-Q\left(s_t, a_t\right)\right],$

(13)

式中：α称为学习因子；γ为折扣率；r为获得的即时奖励。

将NSGA-Ⅱ中的种群视为Agent，最终目标是比例参数学习，Agent通过感知种群多样性变化来控制种群比例参数，进而控制种群进化方向，当解间距较初始种群减小而熵度量值增加时，种群比例设置合理。强化学习的状态划分、动作设计以及奖赏机制如下。

2.3.1 状态

状态空间由种群解间距值和熵值的变化划分为9个，具体定义如表 1所示，其中S_p⁰与H₀表示初始种群的解间距与熵，S_p^t、H_t分别表示第t代种群的解间距与熵。

2.3.2 动作

强化学习Agent的动作是对种群比例参数的调整，包含增加、不变、减少3种。计算公式如式(14)所示。

$\beta(t)=\beta(t-1)+\Delta \varphi, \Delta \varphi=\left\{\begin{array}{r} 0.05, \\ 0.00, \\ -0.05。\end{array}\right.$

(14)

式中β(t)、β(t-1)分别为第t和t-1代种群的分割比例参数。

依据解间距与熵度量值的变化决定Agent的奖赏，目标是学习最优的比例参数β(t)。具体计算公式为

$R=R_{\mathrm{d}}+R_{\mathrm{e}}$

(15)

$R_{\mathrm{d}}=\left\{\begin{array}{r} 0.0, \frac{S_{\mathrm{p}}^t}{S_{\mathrm{p}}^0}=1.0 ,\\ 0.5, \frac{S_{\mathrm{p}}^t}{S_{\mathrm{p}}^0}<1.0, \\ -1.0, \frac{S_{\mathrm{p}}^t}{S_{\mathrm{p}}^0}>1.0。\end{array}\right. \;\;R_{\mathrm{e}}=\left\{\begin{array}{r} 0.0, \frac{H_t}{H_0}=1.0, \\ 0.5, \frac{H_t}{H_0}>1.0 ,\\ -1.0, \frac{H_t}{H_0}<1.0。\end{array}\right.$

(16)

2.4 RNSGA-Ⅱ算法求解MO-FJSP问题流程

RLNSGA-Ⅱ算法求解MO-FJSP的流程如图 4所示。

操作步骤如下：

Step1 输入工件信息，设置算法参数：迭代次数G，初始种群比例参数β，种群规模N，交叉概率P_c，变异概率P_m，强化学习Q值表，学习率α以及折扣率γ。

Step2 产生初始种群，计算初始种群解间距值和熵度量值。染色体编码采用基于工序的实数编码方式，分为工序调度与机器选择两部分。

Step3 对种群进行快速非支配排序和拥挤度计算。

Step4 采用性别判定法按照比例参数β拆分种群，通过双种群进化策略获得新一代种群。

Step5 判断是否达到最大迭代次数，如果是，则结束迭代；否则，执行Step6。

Step6 计算种群的解间距和熵值，获得状态s_t。

Step7 计算奖励值R，根据公式(14)更新Q值表。

Step8 采用ε-贪心策略选择动作a_t，更新种群比例参数, 转到Step3。

3 试验仿真与分析

算法采用C#程序语言在Visual Studio2017软件实现，运行环境为Intel © Core^TMi5-4430 CPU@3.00 GHz。RLNSGA-Ⅱ算法的参数设置如下：种群规模N=100，最大迭代次数G=200, 初始种群比例参数β=0.5, 交叉概率P_c=0.8，变异概率P_m=0.1，强化学习的学习率α=0.9, 折扣因子γ=0.9。

3.1 算例测试

为验证RLNSGA-Ⅱ算法求解的有效性，选取Kacem^[18]等提出的不同规模的标准算例进行测试，用n×m表示一组n个工件与m台机器的算例，每组算例均独立运行10次，并将运行结果与多策略融合的Pareto人工蜂群算法^[19]、改进粒子群算法^[20]、混合人工蜂群算法^[21]、自适应Jaya算法^[22]及基于正态云的状态转移算法^[23]的仿真结果进行对比，比较结果如表 2所示。

通过表 2可知，运用RLNSGA-Ⅱ求解多目标FJSP均可以得到最优组合解，且在总体运行结果和解的多样性上与所提文献中算法的结果基本一致。根据表格中的运算结果，RLNSGA-Ⅱ算法在求解算例4×4和算例10×7时与MSIPABC算法的结果相同，相比于其他几种优化算法Pareto解更多样且在单个目标值上有所突破；而对于算例8×8和算例10×10，RLNSGA-Ⅱ的运行结果与MSIPABC、SAMO-Jaya和CSTA相近，但获得Pareto解的个数多于TL-HGAPOS和HTABC算法, 且与其相比在W_m优化目标上更优，图 5和图 6分别展示了RLNSGA-Ⅱ求解算例8×8和算例10×10运算结果的甘特图；对于算例15×15，RLNSGA-Ⅱ的运算结果接近于其他几种算法求得的最优解，但解的多样性优于MSIPABC、TL-HGAPOS、HTABC和SAMO-Jaya 4种算法的仿真结果。综合上述分析可知，RLNSGA-Ⅱ可有效求解柔性作业车间多目标优化调度问题。

3.2 算法改进性能分析

为了验证各改进部分对NSGA-Ⅱ影响，针对Kacem 8×8算例进行收敛性能及多样性度量指标对比分析。以3个目标函数之和作为适应度值，分别采用NSGA-Ⅱ、只加入双种群进化策略的改进NSGA-Ⅱ及RLNSGA-Ⅱ进行求解，得到收敛性能对比图及多样性度量指标图(如图 7所示)。

由图 7中收敛曲线对比分析可知，采用双种群进化策略改进NSGA-Ⅱ后，可以明显提升算法的收敛速度，克服NSGA-Ⅱ易于局部收敛问题。而RLNSGA-Ⅱ同时引入双种群进化策略和强化学习机制，收敛速度更快，种群适应度值更优。验证了RLNSGA-Ⅱ算法能够有效改善NSGA-Ⅱ的收敛性能。

图 8和图 9分别为算法求解过程中两个多样性度量指标的变化曲线。由图 8可知，采用强化学习对NSGA-Ⅱ改进后，种群的解间距能够快速地降低并保持在较小的范围内，说明RLNSGA-Ⅱ得到的解更加均匀。图 9为熵度量值对比图，相比于NSGA-Ⅱ和改进NSGA-Ⅱ，RLNSGA-Ⅱ在前100次迭代过程中可以更好地保持种群熵度量值在较大的范围；而在后100次迭代过程中，RLNSGA-Ⅱ相比于改进NSGA-Ⅱ在加快收敛的同时仍能有效保持熵度量值，增加解的离散性，验证了RLNSGA-Ⅱ能够较好保持种群的多样性。

4 结束语

针对完工时间、机器总负荷和瓶颈机器负荷3个调度目标，提出了一种基于强化学习的改进NSGA-Ⅱ算法求解MO-FJSP问题。运用性别判定法对种群进行拆分，并采用双种群进化策略改进NSGA-Ⅱ的进化过程，增加算法局部搜索空间和全局搜索能力，改善收敛性能；根据种群解间距和熵值两个度量指标建立状态空间，通过强化学习机制调整种群比例参数，间接调整种群的进化方向，将种群多样性保持在合理范围内，避免了NSGA-Ⅱ易于收敛至第一等级非支配曲面的缺陷。最后，通过仿真基准算例验证了算法求解的有效性和对NSGA-Ⅱ改进的优越性。未来将继续对算法进行优化，进一步研究RLNSGA-Ⅱ用于柔性作业车间多目标动态调度等复杂问题。