改进学习型遗传算法求解柔性车间调度问题*
时间：2023-06-25 12:40:04 来源：雅意学习网 本文已影响 人 
张 亮，毛剑琳，王妮娅，李睿祺
(昆明理工大学a.信息工程与自动化学院；
b.机电工程学院，昆明 650500)
柔性作业车间调度问题(flexible job-shop scheduling problem，FJSP)是对传统作业车间调度问题(job-shop scheduling problem，JSP)的延伸。由于柔性作业车间调度问题减少了机器约束，增加了不确定性，目前已被说明是NP-Hard问题[1]。目前求解柔性作业车间的调度问题的算法主要有粒子群算法，禁忌搜索算法，遗传算法等。
遗传算法具有鲁棒性强、算法易设计、全局搜索能力强等优点，因此许多学者用来求解FJSP。张国辉等[2]设计了一种全局搜索、局部搜索和随机产生相结合的初始化种群方法。该方法有效的提高了初始种群的质量及收敛速度。徐文星等[3]进一步提出了一种基于关键工序的全局随机选择初始化的方法，并加入了再激活机制避免了遗传算法陷入局部最优而停滞。李尚函等[4]采用了超启发式遗传算法有效的提高了局部搜索能力。张立果等[5]采用两级交叉的方式，并将双层遗传应用在多目标问题中，该方法提升了遗传算法的局部搜索能力但收敛速度有所下降。GU、王玉芳等[6-8]在遗传算法加入变邻域搜索(variable neighborhood search，VNS)，该算法加入邻域搜索以弥补遗传算法的局部搜索能力。NING等[9]提出了一种改进的双链量子遗传算法求解FJSP，该算法采用了双链编码构成种群，后期采用量子粒子群来保证种群的多样性。WANG等[10]提出了一种基于协同进化算法的多种群协同遗传算法，该算法协同探索了机器选择和工序安排的解空间，为解决包含多个子目标的问题提供了一种新的思路。
近年来学习型智能优化算法得到了学者的关注，陈英武等[11]采用学习型蚁群算法求解多星任务规划问题。邢立宁等[12]采用学习型遗传算法求解双层有能力约束的弧路径优化问题。胡蓉等[13]采用学习型蚁群算法求解绿色多车场车辆路径问题。上述文献表明学习型智能优化算法可以有效地求解实际问题。
由于传统的遗传算法在求解柔性车间调度问题时存在搜索效率低，易过早收敛等问题，本文提出了一种基于关键机器的学习型遗传算法。以知识体的形式在迭代的过程中不断向最优个体学习，同时利用知识体来生成新的个体来替代原始种群中适应度值差的个体，并设计了三种邻域结构，在知识体更新以及邻域搜索中引入关键机器的概念，以此来对解空间进行有效的搜索。
n个工件J={J1,J2,J3,…,Jn}需要在m台机器M={M1,M2,M3,…,Mm}上加工。每一个工件Ji由多道工序{Oi1,Oi2,Oi3,…,Ois}组成。s表示工件Ji的总工序数。每一道工序Oij(i=1,2,…,n；
j=1,2,…,s)必须在给定的机器集中选择Mij⊆M。在不同机器上的加工时间可以不同。因此FJSP问题主要包含两个子问题：机器选择和工序排序。
在建立问题模型之前，根据实际情况本文做出以下假设：
(1)所有的机器和工件在0时刻都是可用的。
(2)不同工件的工序之间没有优先级的约束。
本文选取“最大完工时间CT最小”作为优化目标，如式(1)所示：
(1)
(2)
(3)
Si(j+1)>Fij,∀i,j
(4)
式(2)表示每道工序只能被一台机器加工一次；
式(3)表示工件一旦开始就不能被打断；
式(4)表示工件i的第j+1道工序的开始时间不能早于第j道工序的开始时间；
同一台机器在同一时间只能加工一道工序。
为了更好地利用问题本身的特征，引入关键机器的概念。针对遗传算法求解FJSP设计了知识模型，利用该模型对遗传算法进行引导。最后将遗传算法的全局搜索能力与变邻域算法的局部搜索能力相结合，对遗传的优秀个体进行变邻域搜索。提出了基于关键机器的学习型遗传算法。
2.1 染色体的编码与解码
本文采用集成整数编码方式，每一个染色体有两部分组成。因此染色体长度为所有工序总数的两倍。表1为随机生成的调度案例。
图1所示为表1染色体编码示例图，在OS部分基因位的值代表工件号，工件号以出现的次数则为该工件的工序号。如在图1中OS的第4个基因位为数字2，2是第二次出现，该位置2则表示为工件2的第2道工序。在MS部分基因位按照工件工序的大小依次排列，在图2中6个位置则依次为O11、O12、O13、O21、O22、O23。基因位的值则表示在可选机器集中的序号。解码方式则采用文献[14]的插入式贪婪解码。
图1 FJSP染色体编码示例图
表1 2×3随机生成柔性车间调度方案
2.2 基于关键机器的学习型遗传算法的实现
由于算法在搜索过程中得到的解了隐含问题的内在特征和求解经验，故采用学习型思想对遗传算法的迭代进行引导，其核心思想就是不断获取优秀个体的知识并不断的对迭代过程进行引导。通过知识体存储优秀个体的知识，然后再利用知识体中的知识生成新的染色体替代原来适应度值差的染色体，完成对遗传算法的引导过程，从而提高遗传算法的搜索效率。
2.2.1 改进遗传算法
本文采用遗传算法对问题进行求解，并采用保留精英种群的策略。遗传部分设计如下：种群规模为NP。选择算子采用轮盘赌的方式。交叉算子将NP平均分为两个子种群。第一个子种群内个体相互交叉；
第二个种群则与第一个种群交叉，每两个父代交叉产生一个子代。精英种群采用种群内的交叉的方式。工序排序部分(OS)采用POX交叉方式，机器选择(MS)部分采用单点交叉的方式。工序排序(OS)部分的变异算子选取n个基因位置(n大于0小于OS部分编码长度的1/4)，翻转其顺序。机器选择(MS)部分随机选择m个基因位(m大于0小于MS部分编码长度的1/4)，从可选机器集中从新随机安排它们的加工机器。
文献[4]表明随着迭代次数的增加遗传算法的种群多样性会降低，进一步导致遗传算法的“早熟收敛”，并设计了一种是自适应算子使得变异概率随着迭代次数的增加而变大从而帮助算法跳出局部最优。但是他所设计的自适应因子与迭代次数呈线性关系，这样会使算法最初的变异概率过小，且增长过慢，本文采用非线性映射来动态调整变异因子。采用正玄曲线在[0,π/2]上非线性递增将遗传的迭代次数映射到到[0,π/2]区间,其变异概率p的表达式为：
(5)
2.2.2 关键机器的定义及判断
本文提出了一种关键机器的概念。在柔性作业车间调度中，某一工序可选机器唯一，其加工耗时为该机器的不可调度时间，该机器记为Mk(k=1,2,…,m)，时间记为tijk(i表示工件号，j表示工序号，k表示机器号)。计算每台机器上的不可调度时间，机器Mk的不可调度时间计算表达式为：
(6)
本文定义拥有不可调度时间的机器为关键机器即本文的目标为最小化最大完工时间，要想完工时间最短所有机器的加工时间应该趋于平衡，所以工序应当优先分配给非关键机器或者不可调度时间短的机器，这样所有机器上的加工时间才会趋于平衡。
2.2.3 工序-机器选择知识体的构造及学习更新
图2 表1中工序1.1知识体示例
表1中工序1.1的可选机器有两个，因此其对应知识体长度为6。5，6位的数值为可选机器，即工序1.1可以在机器1和机器2上加工。1，2数值则用来记录知识，其初始值为对应5，6位置在可选机器上加工时间的倒数。3，4位分别表示选中5，6位置机器的概率，其数值计算规则如下，假设可选机器集长度为N，则概率分布部分从N+1开始。则cell{j}(N+i)的数值为式(7)所示(j当前知识体(cell)在知识体结构中的位置索引)。
(7)
知识体的更新是从优秀个体中获取经验的过程，将优秀个体的经验以知识体的结构进行存储，并利用以获取的知识引导种群的迭代。
每进行一次迭代，判断出当前最优个体，根据其染色体机器选择(MS)部分的基因数值对知识体更新，判断每一道工序所选择的机器，并对知识主体部分对应机器的数值进行更新。如果当前机器选择不是关键机器KM则更新规则如式(8)所示，否则保持原数值不变。式中，Q为学习率，由于学习的为优秀个体Q应大于1这样才能使优秀个体部分的经验数值不断变大。更新完知识主体部分数值后，再根据知识主体中的数值从新计算概率分布部分的数值。工序-知识体的学习更新表达式为：
cell{j}(i)=cell{j}(i)×Q
(8)
2.2.4 工序-机器选择知识体对改进遗传算法的引导
过程
已知知识体中概率分布部分的总和为1，把所有机器被选中概率连续的分布在[0,1]的区间内，在生成新的种群时，本文采用随机生成一个[0,1]的随机数r，判断r所在的区间来确定工序所选择机器。这样就生成了染色中机器选择(MS)部分的基因。工序排序(OS)部分的基因有两种生成方式，一部分个体继承种群中优秀个体的基因，另一部分个体则随机生成，这样既能保证种群的多样性又能保留优秀个体的基因。新生成的个体来替换原有种群中适应度值差的个体。知识体得以表达，学习型完成对遗传算法的引导过程。
2.2.5 变邻域搜索
变邻域搜索通过调整邻域结构来增加搜索范围，进而得到局部最优。本文应用了文献[16]的两种邻域机构(邻域结构1,2)。并基于调整调整工序顺序的思想设计了邻域结构3和4，基于关键机器的思想设计了邻域结构5。
结构1：N1调整机器选择，随机选择染色体中MS若干基因，从可选机器集中随机再选择一台对其进行加工。
结构2：N2随机选取两个工件，让他们在OS中的位置互换。
结构3：N3随机选取染色体中OS部分的一段基因，随机打乱其顺序。
结构4：N4随机选取染色体中OS部分的两个基因，将一个插入到另外一个旁边。
结构5：N5选取关键机器上的工序更换其加工机器。
每一次迭代对种群中的优秀个体进行变邻域搜索。如果个体在变邻域后被改进，则保留改进，否则保持变邻域之前的结构。
2.3 算法整体流程框架
算法的整体流程框架图如图3所示。
图3 算法整体流程框架图
上述算法采用MATLAB2020B进行编程，操作系统为Windows10，11th Gen Intel(R) Core(TM) i7-11700KF@3.60 GHz，内存32 GB，64位操作系统上运行。算法参数设置为：种群规模NP=100，最大迭代次数200代；
知识体每次生成个体数为20；
交叉概率0.9，w取0.7。
3.1 学习型思想对算法的改进效果
为了说明学习型能够有效对遗传算法进行引导，本文以MK03为例，分别使用本文算法和去除算法中的学习型进行对比实验，图4为两种算法的迭代曲线由图可不加学习型算法在150代左右才收敛，加入学习型滞后算法在40代左右就收敛了，因此知识体能学习到优秀个体的知识，并对遗传算法进行了有效的引导，提高算法的搜索效率。
图4 去除学习型前后迭代曲线对比
3.2 算法对比
为了说明本文所提出的基于关键机器的学习型遗传算法在求解FJSP问题的性能，将其应用于Benchmark算例中的MK01-MK10基准算例以及Kacem算例，分别运行20次，取最优解。
Kacem算例与ZIAEE等[17]提出的基于结构的启发式算法(heuristic)、NOUIRI等[18]提出的分布式粒子群算法(distributed particle swarm optimization，DPSO)、姜天华[19]的灰狼算法(grey wolf optimization，GWO)进行对比。
表2为Kacem算例对比结果，粗体为相同算例中的最优解。可以看出本文算法在求解Kacem算例时具有较为优秀的求解能力。
表2 Kacem算例对比
MK算例与姜天华等[19-20]提出的灰狼优化算法(grey wolf optimization，GWO)以及混合灰狼优化算法(hybrid grey wolf optimization，HGWO)、PRASERT等[21]提出的改进微分进化算法(improved differential evolution，IDE)、ZHANG等[22]提出的混合量子粒子群优化(hybrid quantum particle swarm optimization，HQPSO)进行对比。
表3为MK算例对比结果，粗体为相同算例中的最优解，图5为5种算法取得最优解个数的折线图。由图5可以发现，在Benchmark的10个基准算例中，GWO算法有3个取得了最优解，HGWO、IDE、HQPSO有4个算例取得了最优解本文所使用的算法有8个都取得了最优解或者优于其他算法。由表3可知除了MK10算例效果不理想以外，MK05和MK06虽然不是最优解，也接近最优解。在整体求解的数量上也优于其他4种算法。
表3 Benchmark算例对比
续表
图5 表3算法取得最优解个数折线图
图6中每一个小方块为一道工序，其中y轴为该工序选择加工的机器，x轴的长度代表加工时间，图6为MK04算例在最大完工时间为64下的一个调度方案。由实验结果可以说明本文算法的可行性，该算法具有较强的搜索能力，能够有效的求解FJSP。
图6 MK04(Makespan=64)调度甘特图
本文所提出的基于关键机器的学习型遗传算法在以最小化最大完工时间为目标求解FJSP问题时取得不错的效果，说明了该方法的可行性。本文首先提出了关键机器的概念，并基于关键机器进行知识体的更新以及变邻域搜索，针对遗传算法求解FJSP编码设计了知识体，实现学习型对遗传算法的引导过程，并设计了5种邻域结构，提高算法的局部搜索能力。在未来的研究中可以考虑使用学习型对其他智能优化算法的迭代进行引导，并将该算法运用到求解多目标柔性车间调度问题的研究中去。
猜你喜欢算例邻域学习型稀疏图平方图的染色数上界吉林大学学报（理学版）(2020年3期)2020-05-29做学习型父母 和孩子共成长中华家教(2018年10期)2018-10-30基于邻域竞赛的多目标优化算法自动化学报(2018年7期)2018-08-20关于-型邻域空间周口师范学院学报(2016年5期)2016-10-17基于振荡能量的低频振荡分析与振荡源定位（二）振荡源定位方法与算例中国学术期刊文摘(2016年2期)2016-02-13互补问题算例分析新乡学院学报(2015年6期)2015-11-06建设学习型党组织的实践与思考学习月刊(2015年6期)2015-07-09基于CYMDIST的配电网运行优化技术及算例分析电网与清洁能源(2015年2期)2015-02-28创建学习型教师团队当代教育实践与教学研究(2015年2期)2015-02-27燃煤PM10湍流聚并GDE方程算法及算例分析电力工程技术(2014年5期)2014-03-20
