目录1.摘要2.问题描述3.基于Q学习增强的质量–多样性算法4.结果展示5.参考文献6.代码获取7.算法辅导·应用定制·读者交流1.摘要针对带AGV柔性作业车间调度问题FJSP-AGVs在规模扩大时复杂度急剧上升、传统方法难以有效求解的问题本文提出了一种Q学习区域选择增强的质量–多样性算法Q-QD。与现有仅将机器学习用于启发式规则选择不同Q-QD在自定义特征空间如工件运输时间、机器空闲时间等中利用Q学习进行区域选择引导解的演化并结合基于规则的AGV局部搜索实现对高质量且多样化解的有效挖掘。2.问题描述在FJSP-AGV模型中系统包含m mm台机器和n nn个作业每个作业由若干道工序组成每道工序可在多个候选机器上加工加工时间随所选机器而变化v vv台AGV负责工序间的运输运输时间计入调度过程。假设加工与运输均不可中断初始时刻作业与AGV均位于仓库。目标函数为最小化最大完工时间f ( x ) max i 1 , … , n C i , w i f(x) \max_{i1,\dots,n} C_{i,w_i}f(x)i1,…,nmaxCi,wi其中C i , w i C_{i,w_i}Ci,wi为作业i ii最后一工序的完成时间。约束包括机器容量约束每台机器同一时刻只能加工一道工序∑ i ∈ I ∑ j ∈ J i X i , j , k , t ≤ 1 \sum_{i\in I}\sum_{j\in J_i} X_{i,j,k,t} \leq 1i∈I∑j∈Ji∑Xi,j,k,t≤1工序完成时间定义C i , j ≥ s i , j ∑ k ∑ t T i , j , k X i , j , k , t C_{i,j} \geq s_{i,j} \sum_k \sum_t T_{i,j,k} X_{i,j,k,t}Ci,j≥si,jk∑t∑Ti,j,kXi,j,k,t运输时间的工序顺序约束s i , j ≥ s i , j − 1 ∑ k , k ′ ( T i , j , k T R , i , j − 1 , k ′ , k ) X i , j − 1 , k ′ , t ′ X i , j , k , t s_{i,j} \geq s_{i,j-1} \sum_{k,k} (T_{i,j,k} T_{R,i,j-1,k,k}) X_{i,j-1,k,t} X_{i,j,k,t}si,j≥si,j−1k,k′∑(Ti,j,kTR,i,j−1,k′,k)Xi,j−1,k′,t′Xi,j,k,t3.基于Q学习增强的质量–多样性算法特征空间构建本文构建了一个二维特征空间用于刻画调度解的行为模式特征包括机器空闲次数N I N_INI和 作业转运次数N T N_TNT。其中N I N_INI表示所有机器的总空闲次数反映设备利用率。N T N_TNT表示作业在机器间的总转运次数(含AGV往返)。两者分别衡量加工利用效率与运输效率共同体现机器利用与物流负载之间的权衡关系。在此特征空间上本文提出 Q-QD 算法首先随机生成初始解并构建特征-性能网格在迭代过程中选取优质解通过 Q-learning 进行区域选择生成候选解再结合基于规则的局部搜索(LS-DK)进行强化优化并依据同一特征格内保留更优解的原则更新网格。Q-QD 架构本文采用三向量编码表示调度解包括工序顺序(OS)、机器分配(MA)和AGV选择(AS),通过解码过程确定加工顺序、机器与AGV分配并计算完工时间及其在特征空间中的坐标( N T , N I ) (N_T,N_I)(NT,NI)。算法基于 MAP-Elites 构建二维特征-性能网格在最小化完工时间的同时维护各行为区域的精英解若新解在对应特征单元中性能更优则进行替换。Q-QD 在此框架下引入 Qlearninq 进行区域选择与协同解配对通过交叉、变异及基于领域知识的局部搜索(含AGV扰动)强化优化从而实现解质量提升与特征空间多样性探索的统一。区域选择与成对选择机制利用 Q-learning 在特征空间中进行区域选择以N T N_TNT作业转运次数升序划分行为区域每个区域对应一个动作。当前解作为状态s t s_tst通过ε \varepsilonε-贪婪策略选择动作a t a_tata t { arg max a ∈ A Q ( s t , a ) , τ ≥ ε a random , τ ε a_t \begin{cases} \arg\max_{a\in A} Q(s_t, a), \tau \geq \varepsilon \\ a_{\text{random}}, \tau \varepsilon \end{cases}at{argmaxa∈AQ(st,a),arandom,τ≥ετε其中ε \varepsilonε为贪婪因子。每个动作对应特征空间中的一个区域被选区域内将产生协作解。随后对选中的两个解执行交叉与变异POX 与均匀交叉生成新解并更新状态。Q值更新Q ( s t , a t ) Q ( s t , a t ) α [ r t γ max a ∈ A Q ( s t 1 , a ) − Q ( s t , a t ) ] Q(s_t, a_t) Q(s_t, a_t) \alpha \big[ r_t \gamma \max_{a\in A} Q(s_{t1}, a) - Q(s_t, a_t) \big]Q(st,at)Q(st,at)α[rtγa∈AmaxQ(st1,a)−Q(st,at)]其中α \alphaα为学习率γ \gammaγ为折扣因子r t r_trt为奖励值学习率随迭代动态衰减α α − ( α − 0.01 ) ⋅ i t e r M a x _ I t e r \alpha \alpha - (\alpha - 0.01) \cdot \frac{iter}{Max\_Iter}αα−(α−0.01)⋅Max_Iteriter基于领域知识启发式规则的局部搜索局部搜索方法基于关键路径展开关键路径由决定最大完工时间的加工与AGV运输活动构成。算法优先针对关键路径上的工序进行调整以直接影响 makespan。结合领域知识本文引入基于AGV运输时间的启发式规则从关键路径中选取作业识别运输时间最长的工序并对其对应的机器分配MA、工序顺序OS或AGV分配AS进行定向扰动生成新解。4.结果展示5.参考文献[1] Qin H, Xiang Y, Han Y, et al. A knowledge region selection enhanced quality-diversity algorithm for real-world flexible job shop scheduling with Automated Guided Vehicles transportation[J]. Engineering Applications of Artificial Intelligence, 2026, 164: 113352.6.代码获取xx7.算法辅导·应用定制·读者交流xx