(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211026596.3 (22)申请日 2022.08.25 (71)申请人 河南工业大 学 地址 450001 河南省郑州市高新 技术产业 开发区莲 花街100号 (72)发明人 张闻强　李晨　杨卫东　许德刚　 梁义涛　朱春华　魏蔚　刘刚　 李智　 (74)专利代理 机构 郑州睿信知识产权代理有限 公司 41119 专利代理师 史萌杨 (51)Int.Cl. G06N 3/00(2006.01) G06N 3/12(2006.01) G06F 30/20(2020.01)G06F 111/06(2020.01) (54)发明名称 基于序列差分的多阶段混合多目标进化的 DFFSP方法 (57)摘要 本发明属于流水车间调度技术领域， 具体涉 及一种基于序列差分的多阶段混合多目标进化 的DFFSP方法。 该方法在种群进 化的不同阶段， 采 用不同的策略。 中期差分进化策略是在种群中随 机抽取三个不同的个体， 利用交换序求解出表现 较好的两个个体 之间的差异， 并取一定比例的差 异作用于表现较差的个体， 该策略可以加快种群 中个体的收敛速度， 提高整体的收敛性能。 且在 迭代后期， 所采用的后期差分进化策略是对个体 的选择与进化方向进行了调整， 目的是提高算法 对于Pareto前沿面边缘与局部区域的解的搜索 能力。 两者相结合， 使个体朝着需要的方向去进 化， 以满足算法对收敛性和分布性能的需求， 从 而保证最终得到的解集(即最终的调度解决方案 集)较优。 权利要求书2页 说明书13页 附图5页 CN 115409148 A 2022.11.29 CN 115409148 A 1.一种基于序列差分的多阶段混合多目标进化的DFFSP方法， 其特征在于， 包括如下步 骤： 1)根据车间加工信息， 建立多目标DFFSP模型； 多目标包括第一目标和第二目标， 第一 目标为模糊最大完工时间最短， 第二 目标为最小化所有工件的模糊总流动时间； 初始化当 代种群Pt和当代精英种群At， 种群中的每 个个体均为一种调度 序列； 2)对当代种群Pt进行处理生成当代子种群， 将当代子种群和当代精英种群At混合得到 当代混合种群， 对当代混合种群进行遗传操作生成当代临时种群Pt′； 3)判断当前 所处的迭代阶段： 若处于整体迭代过程的迭代前期， 则将当代临时种群Pt′作为下一代临时种群P ′t+1； 若处于整体迭代过程的迭代中期， 则对当代临时种群Pt′执行中期差分进化策略生成当 代策略临时种群SDDE ‑Pt′， 将当代策略临时种 群SDDE‑Pt′和当代精英种 群At混合得到下一 代临时种群P ′t+1； 所述中期差分进化策略为： 执行如下过程： 从当代临时种群Pt′中随机抽 取三个个体， 使用交换序方法获得PDDR ‑FF值较优的两个个体之间的序列差异， 利用序列差 异对最差的个 体进行调整； 重复上述过程， 直至满足中期差分进化策略迭代终止条件； 若处于整体迭代过程的迭代后期， 则对当代临时种群Pt′执行后期差分进化策略生成当 代策略临时种群SDDE ‑Pt′， 将当代策略临时种 群SDDE‑Pt′和当代精英种 群At混合得到下一 代临时种群P ′t+1； 所述后期差分进化策略为： 执行如下过程： 从当代临时种群Pt′中随机抽 取三个个体且三个个体的PDDR ‑FF值均小于设定值， 使用交换序方法获得PDDR ‑FF值较优的 两个个体之间的序列差异， 利用序列差异对最差的个体进行调整； 重复上述过程， 直至满足 后期差分进化策略迭代终止条件； 其中， 迭代前期、 迭代中期和迭代后期构 成一个整体迭代过程， 且在时间上迭代前期早 于迭代中期， 迭代中期早于迭代后期； P DDR‑FF值为： 式中， eval(k)为个体的PDDR ‑FF值； q(k)为支配k的个体的数量； p(k)为被k所支配的个 体的数量； pSize为种群的大小； 4)从下一代临时种群P ′t+1中挑选出PDDR ‑FF值较优的多个个体作为下一代精英种群 At+1； 判断是否满足整体迭代过程的终止条件： 若不满足， 则从下一代临时种群P ′t+1中选择 多个个体生成下一代种 群Pt+1， 并将下一代精英种群At+1和下一代种 群Pt+1分别作为当代种 群Pt和当代精英种群At， 重复步骤3)～4)进行迭代计算， 直至满足整体迭代终止条件， 从最 终得到的精英种群中挑选出较优调度 序列集作为多目标DF FSP模型的解决方案集。 2.根据权利要求1所述的基于序列差分的多阶段混合多目标进化的DFFSP方法， 其特征 在于， 步骤2)中采用如下方法生成当代子种群： 从当代种群Pt中挑选出第一目标上表现较 优的个体作为第一子种群SP1， 从当代种群Pt中挑选出第二目标上表现较优的个体作为第二 子种群SP2； 将第一子种群S P1和第二子种群S P2混合得到当代子种群。 3.根据权利要求1所述的基于序列差分的多阶段混合多目标进化的DFFSP方法， 其特征 在于， 步骤2)中所述遗传操作包括选择操作， 并使用二元竞争方式作为选择算子 。 4.根据权利要求1所述的基于序列差分的多阶段混合多目标进化的DFFSP方法， 其特征 在于， 在对种群中个体进 行编码时， 采用离散排序编码方法进 行编码， 且包括表示工件序列权　利　要　求　书 1/2 页 2 CN 115409148 A 2的染色体和表示工厂序列的染色体。 5.根据权利要求4所述的基于序列差分的多阶段混合多目标进化的DFFSP方法， 其特征 在于， 步骤2)中所述遗传操作包括交叉操作， 且针对表示工件序列的染色体采用顺序交叉 方式作为交叉算子， 针对表示工厂序列的染色体采用单点交叉 方式作为交叉算子 。 6.根据权利要求4所述的基于序列差分的多阶段混合多目标进化的DFFSP方法， 其特征 在于， 步骤2)中所述遗传操作包括变异操作， 且针对表示工件序列的染色体采用交换变异 方式作为变异算子， 针对表示工厂序列的染色体采用单点变异方式作为变异算子 。 7.根据权利要求1所述的基于序列差分的多阶段混合多目标进化的DFFSP方法， 其特征 在于， 后期差分进化策略中设定值 为1。 8.根据权利要求1～7任一项所述的基于序列差分的多阶段混合多目标进化的DFFSP方 法， 其特征在于， 所述整体迭代终止条件为迭代次数达到整体迭代次数要求， 迭代前期为迭 代次数处于[0,15％*mref]区间内， 迭代中期为迭代次数处于(15％*mref,90％*mref]区间内， 迭代后期为迭代次数m处于(90％*mref,mref]区间内， mref为整体迭代次数要求。 9.根据权利要求1～7任一项所述的基于序列差分的多阶段混合多目标进化的DFFSP方 法， 其特征在于， 中期差分进化策略和后期差分进化策略中， 需对序列差异进行截取操作， 并利用截取后的序列差异对最差的个 体进行调整， 从而得到的新个 体为： S＝S3+F(S1‑S2) 其中， (S1‑S2)表示个体S1和个体S2之间的序列差异， F表示截取比例， S表示对最差的个 体S3进行调整后得到的新个 体。 10.根据权利要求9所述的基于序列差分的多阶段混合多目标进化的DFFSP方法， 其特 征在于， 截取比例为截取 前序列差异总长度的80％。权　利　要　求　书 2/2 页 3 CN 115409148 A 3