一种基于目标重要性分解的模因演化多目标优化调度方法
一种基于目标重要性分解的模因演化多目标优化调度方法
【技术领域】
[0001] 本发明涉及一种多目标优化调度方法，特别是关于一种在计算机应用技术领域和 生产调度领域中应用的基于目标重要性分解的模因演化多目标优化调度方法。
【背景技术】
[0002] 第二代非支配遗传算法（Nondominated Sorting Genetic Algorithm II，NSGA_ II)首先随机生成含有N个个体的初始种群，其中N是种群大小。接下来，算法进行迭代直至 终止条件满足。在第t代，算法在当前种群Pt的基础上，通过随机选择，模拟两点交叉 (Simulated Binary Crossover，SBX)和多项式变异产生子代种群QtIt和Qt的大小均为N。 因此，两个种群Pt和Qt合并会形成种群大小为2N的新的种群Rt = PtUQt。为了从种群Rt中 选择最好的N个解进入下一代，首先利用基于Pareto支配的非支配排序将Rt分为若干不同 的非支配层(F1，F2等等）。然后，算法构建一个新的种群St，构建方法是从F1开始，逐次将各 非支配层的解加入到St，直至St的大小等于N，或首次大于N。假设最后可以接受的非支配层 是1层，那么在1+1层以及之后的那些解就被丢弃掉了，且St\Fl中的解已经确定被选择作为 Pt+Ι中的解。Pt+Ι中余下的个体需要从F1中选取，选择的依据是要使种群在目标空间中具 有理想的多样性。在NSGA-II中，F1中具有较大拥挤距离的解会优先被选择。
[0003]多目标遗传局部搜索(Multiobjective Genetic Local Search,M0GLS)是较早的 蕴含分解思想的多目标进化算法，它最初是用来求解多目标流水车间调度问题。另外从搜 索行为上来看，M0GLS混合了遗传搜索和局部搜索，所以它也可以看作是一种模因演算法。 M0GLS的执行流程简要描述如下。首先，算法初始化一个大小为N的种群，并用一个外部存档 储存所找到的非支配解。之后，算法进行迭代直至终止条件满足。在M0GLS的第t代，首先选 出当前种群Pt中的所有非支配解，并用其更新外部存档。然后算法进入交配选择阶段，需要 选择N-Nel ite对父代个体，每对个体进行交叉和变异操作产生一个子代个体，并将其加入 到Pt+Ι中。在选择每对父代个体时，首先随机产生一个权向量w=(wl，w2,. . .，wm)T，其中Σ ￥1 = 1，111是目标数目，然后对?1：中的每个解1，有加权函数值；^1)=2￥1；^(1)，其中；^是第 i个目标函数，通过该函数值，由基于轮盘赌的比例选择法，可以得到每个个体被选择的概 率P(x)，根据该概率，可以选择两个父代个体。接着，算法采用了一种精英策略，从外部存档 中随机选择Nelite个解加入到Pt+Ι中，那么现在Pt+Ι中解的个数已达到种群大小。之后，算 法进入局部搜索过程，该过程总共执行N次，每次选择当前种群Pt+Ι中的一个个体以概率 pLS进行局部改进，选择方法如下：随机产生一个权向量w=(wl，w2,. . .，wm)T，其中2wi = 1，然后依据函数值f(x)= fi(x)使用无放回锦标赛选择从Pt+Ι中选择一个个体。如果 局部搜索被执行，改进后的个体将作为下一代种群中的个体，否则原来个体将进入下一代 种群。另外，在局部搜索中，算法设置了一个参数k，每次只随机检测当前解的k个邻域，k较 小时局部搜索很快就会终止，否则局部搜索会检测很多解，通过该参数可以调整局部搜索 在M0GLS中所花费的计算开销。
[0004] NSGA-II在求解多目标柔性作业车间调度问题往往没有充分利用问题相关的知 识，局部搜索的探索能力有限;MOGLS重在解决如何在多目标优化中选择解进行局部搜索， 以及如何对局部搜索中的解进行评价的问题，但是全局搜索能力欠缺。
[0005] 另外，这两种经典算法共同的缺陷:第一，并没有充分利用问题相关知识;第二，并 没有考虑问题的多个目标之间重要性的区别以及它们之间的相关性。
【发明内容】
[0006] 针对上述问题，本发明的目的是提供一种基于目标重要性分解的模因演化多目标 优化调度方法，该方法可以对多目标柔性作业车间系统进行有效的调度，且调度效果优于 目前已有的先进算法。
[0007] 为实现上述目的，本发明采取以下技术方案:一种基于目标重要性分解的模因演 化多目标优化调度方法，其特征在于，所述方法步骤如下：1)随机产生一个大小为N的初始 种群Ρο; 2)在算法每一代中，先由当前种群Pt通过二元锦标赛选择，遗传算子产生一个子代 种群Qt;3)利用局部搜索策略对子代种群Q t进行精细搜索以得到一个改善的种群以*;4)将 当前种群Pt、子代种群Qt和改善的种群Q、合并生成一个种群Rt，对种群Rt中目标大小完全相 同的个体进行变异操作;5)利用NSGA-II中的快速非支配排序与拥挤距离方法对种群R t中 的个体进行排序，以选择最好的N个解作为下一代种群Pt+1。
[0008] 进一步，所述步骤2)中，利用遗传算子产生子代种群，即利用遗传搜索产生子代种 群，其包括染色体编码、染色体解码和遗传操作：（1)染色体编码：（a)给定每个操作一个固 定的ID: j，其中j = l，2, . . .，d，d= Σγη;在编号之后，一个操作也可以用固定ID号进行指 代；（13)机器分配向量表示为11=[111，112，一11(]]，且11」满足1<11」<1」，其中1」是供操作」执行的 机器数目；（c)进一步将操作j的可用机器按操作j在其上的处理时间进行非递减的排序:如 果两台机器在执行操作j时需要相同的处理时间，那么具有较小ID号的机器排在前列；（d) 操作序列向量表示为V = [ VI，V2，…Vd]，其中操作ID号在这个向量中的出现顺序表示该操作 的调度优先顺序，操作有最高优先权的被首先调度；（2)染色体解码:按向量V中的操作排列 顺序，逐个将每个操作分配到指定的机器上，并且在该机器上为其分配一段处理时间：从机 器分配向量u中获取它所选择的处理机器，然后从0时刻开始往后顺序扫描该机器上已安排 操作之间的空闲时隙直到一个可用的空闲时隙被找到，以安排该操作；（3)遗传操作用来生 成子代个体，它包括交叉和变异。
[0009] 进一步，所述步骤(2)中，可用的空闲时隙寻找方法如下：设表示一个操作 在调度中的开始执行时刻，Ci,j表示它的完成时刻;如果在机器Mk上的一个空闲时隙[SX，EX] 对于操作是可用的，那必须满足如下约束条件：
[0010]
[0011] 当操作〇1」被分配到可用的空闲时隙后，它的开始时刻就被设置为max{Sx， Cl,H}， j 2 2或者Sx，j = 1;如果在机器Mk上对于操作不存在这样的时隙，那么操作将被安排 到机器Mk的时间末端上。
[0012] 进一步，所述步骤(3)中，交叉是对一对染色体进行操作，对染色体中的两个向量u 和v，交叉操作是分别独立执行的:对于向量u上的交叉操作，首先在其中随机选择一些交叉 位置，然后通过交换两个父代染色体相应位置上的基因信息以得到两个子代个体的向量U 表示;对于向量V上的交叉操作，采用一个改进的序列交叉方式，具体方法为:首先，在向量V 中随机选择两个交叉点，将第一个父代个体中在这两个交叉点之间的所有操作复制到第一 子代个体的相应位置;然后，对于余下的操作，按照第二个父代个体中这些操作出现的优先 顺序逐个将它们填补到第一个子代个体的向量V中的空余部分;对于第二个子代个体，对称 地由在第二个父代个体中选择交叉点的方式得到;最后，对交叉后得到的向量V进一步做修 补策略，以调整同一个作业内的操作的相对顺序。
[0013] 进一步，所述步骤(3)中，变异只针对于单个个体，变异操作包含两个独立的部分： 对于向量U，任意选择一个操作然后改变该操作的机器分配;对于向量V，在不违反同一作业 内操作优先顺序的前提下，将一个操作插入到向量V的另一个位置上，其中操作和位置都是 随机选择的。
[0014] 进一步，所述步骤3)中，利用局部搜索策略对子代种群进行局部搜索分为两个部 分：⑴子代种群中的个体选择:首先，定义聚合函数:f (1，1)=11：^(1)+\2€2(1)+13；^(1)，其 中λ = [λ:，λ2，λ3 ]是一个权向量，f i (X)、f 2 (X)和f 3 (X)分别设置为MO-FJSP问题的3个优化目 标，即完工时间，总负载和关键负载;然后，生成一组满足约束条件且在目标空间中均匀分 布的权向量;约束条件为. . .，z}，i = l，2,3,权向量的个数为（（z+ 2)(z+l))/2;当选择一个个体进行局部搜索时，先从这些权向量中随机选择一个，然后以这 个权值向量确定的聚合函数f (X，λ)为比较指标，通过无放回的锦标赛选择方式选择一个精 英解，最后对该解进行局部搜索以得到一个或一组改进的解;最后，引入一个局部搜索的概 率Pis，在子代种群中将有个解被选择以执行进一步的局部搜索；（2)选择了某个个 体，通过局部搜索对该个体进行精炼以得到更高质量的个体，即针对个体的局部搜索:①在 局部搜索中，一个调度解G的邻域解是通过移动某个操作来得到的：设定调度解G的邻域解 G'是可接受的当且仅当Cmax(G);假设调度解G中的关键 操作coi将被移动，将关键 操作coi从G中删除得到首先，先移除以 c〇i为起点和以关键操作c〇i为终点的非连接 弧;然后用一条指向SM(G，coi)的非连接弧连接PM(G，coi)和SM(G，coi);最后将节点coi的 权重设置为〇;②删除coi之后，在GT中重新选择一个可行的位置，将关键操作 coi重新插入， 以得到可行调度V且UaXG' H Cmax(G);③将coi插入到某台机器Mk上，将插入位置仅限制 在可行的位置上方法如下：当在调度GT中，为操作coi重新分配机器M k上的某个位置时，只 需顺序检测集合γ k中的位置，一旦某个位置满足约束条件，立即将coi插入到这个位置上， 得到邻域调度解V，它替换G成为新的当前调度解，也是下一轮局部迭代的初始解;其中，集 合Yk示在中所有操作之前且在ΨιΛΦ??中所有操作之后的位置的集合，和Ψι<是 操作集合? k的两个子序列;④将在调度G「中将操作coi插入位置γ的过程看作一个动作， 并表示为coi~Mk;设供(G) = ? α."?/Α / = 1,2, ... ,/κ?Α e VkW ，该集合包含了所有 Slcoi个可能的动作，其中每个动作都有希望生成当前解G的一个可接受的邻域解；（3)接 受准则:采用Best准则和Pareto准则两种不同的接受准则确定哪些将被作为改进的解添加 到改进的种群中。
[0015] 进一步，所述步骤(2)②中，如果该位置对于coi来说是可以插入的，那么必须满足 下式：
[0016]
[0017] 式中，￡Γ((7,. ，⑶表示最早完成时间，即在调度Gf中，操作；ΡΜ(βΜν)的最 早完成时间；aGJG))表示最迟开始时间，即在以完工时间为C max(G)的前提下，调 度GT中，操作v的最迟开始时间;Ρ。。^表示操作coi在机器Mk上的加工时间。
[0018] 进一步，所述步骤(3)中，Best准则选择局部搜索路径上具有最小f(G，A)值的调度 解作为最终改进的解。
[0019] 进一步，所述步骤(3)中，Pareto准则是在每一代中，收集所有局部搜索路径上的 解，当中的非支配解构成了改进的种群。
[0020] 本发明由于采取以上技术方案，其具有以下优点：本发明可以完成柔性作业车间 系统作业数目、机器数目、操作数目、每个操作可用机器情况等基本参数的设置，而且可以 根据不同的设备场景和工艺需求，针对每个作业灵活配置各种各样的加工路径。利用所提 出的模因演算法，可以对配置好的优化目标为完工时间、总负载、关键负载的柔性作业车间 系统进行有效的调度，且调度效果明显优于目前已有的先进算法。本发明可以广泛在计算 机应用技术领域和生产调度领域中应用。
【附图说明】
[0021] 图1是本发明的染色体所对应的甘特图示意图。
【具体实施方式】
[0022] 为了解决半导体生产、汽车装配、纺织等工业生产中所涉及的关键多目标调度问 题，即多目标柔性作业车间调度问题，本发明提供一种基于目标重要性分解的模因演化多 目标优化调度方法，即多目标模因演算法。该方法首先提出一个求解M0-FJSP(多目标柔性 作业车间调度问题）的基于关键操作的与问题相关的局部搜索算子，该算子强调了对问题 解空间的开发能力。在该局部搜索中，使用了一种分层策略来处理三个目标。即，主要考虑 完工时间的最小化，对其它两个目标的考虑则体现在尝试所有可能产生可接受邻域解的动 作的顺序上。第二，通过良好设计的染色体表示、染色体解码和遗传算子，开发了针对M0-FJSP的基于NSGA-II(第二代非支配遗传算法）的遗传搜索，它主要强调对问题解空间的探 索能力。第三，采用了与M0GLS(多目标遗传局部搜索）中类似的机制从种群中选择解进行局 部搜索，有利于在MAs(模因演算法）中平衡局部搜索和遗传搜索。下面结合附图和实施例对 本发明进行详细的描述。
[0023]本发明的基于目标重要性分解的模因演化多目标优化调度方法，基于Eclipse开 发平台，可以为不同配置的多目标柔性作业车间调度系统提供统一的、有效的调度接口，其 步骤如下：
[0024] 1)随机产生一个大小为N的初始种群Po。
[0025] 2)在算法每一代中，先由当前种群Pt通过二元锦标赛选择，遗传算子(包括交叉和 变异)产生一个子代种群Qt。
[0026] 3)利用局部搜索策略对子代种群Qt进行精细搜索以得到一个改善的种群Q\。
[0027] 4)将当前种群Pt、子代种群Qt和改善的种群V t合并生成一个种群Rt，由于种群Rt可 能会含有一些目标大小完全相同的个体，这样会影响搜索质量，因此，对种群Rt中目标大小 完全相同的个体进行变异操作。
[0028] 5)利用NSGA-II中的快速非支配排序与拥挤距离方法对种群Rt中的个体进行排 序，以选择最好的N个解作为下一代种群P t+1。
[0029] 上述步骤2)中，利用遗传算子产生子代种群，即利用遗传搜索产生子代种群，遗传 搜索在模因演算法中主要负责对问题解空间的全局搜索，该遗传搜索包括染色体编码、染 色体解码和遗传操作，具体方法如下：
[0030] (1)染色体编码:对于FJSP(柔性作业车间调度问题）问题，一个解由两部分组成： 第一部分是操作在机器上的分配;第二部分是每台机器上操作的处理序列。因此，本发明的 模因演算法中一个染色体由两个向量组成:第一个向量是机器选择向量，第二个向量是操 作排序向量。这两个向量分别对应于FJSP问题的两个子问题。
[0031] (a)给定每个操作一个固定的ID: j，其中j = l，2, · · .，d，d= Σγη。这就意味着作业 Ji包含操作1，. . .，m，作业J2包含操作ni+1，. . .，ηι+η2,以此类推。在编号之后，一个操作也 可以用固定ID号进行指代，如在表1.1中，操作〇2,2也可以称作操作4,表中Mk为第k个机器。 [0032] 表1 M0-FJSP问题样例的处理时间表
[0033
[0034] (b)机器分配向量可以表示为u = [m，u2，…叫]。这是一个包含d个整数值的数组， 且元素叫满足1 < d，其中1」是可供操作j执行的机器数目。
[0035] (c)再进一步将操作j的可用机器，按操作j在其上的处理时间进行非递减的排序。 如果两台机器在执行操作j时需要相同的处理时间，那么具有较小ID号的机器排在前列，这 样，在机器分配向量中W意味着操作j选择了在排序后的可用机器序列中的第台机器，也 即具有第叫小处理时间的机器。
[0036] (d)操作序列向量可以表示为v= [V1，v2, ···~]。它是一个所有操作ID号的一个全 排列，其中操作ID号在这个向量中的出现顺序表示该操作的调度优先顺序。例如，对于在表 中的问题，一个可能的操作序列向量可以表示为^=[6，1，7,3,4,2,5]。这个向量可以直接 转换为操作的优先顺序列表:〇3,1>〇1,1>〇3,2>〇2,1>〇2,2>〇1,2>〇2,3。操作〇3,1有最高的优 先权并被首先调度，然后是操作Oi, i，以此类推。
[0037] (2)染色体解码:染色体解码就是按向量v中的操作排列顺序，逐个将每个操作分 配到指定的机器上（由机器分配向量U确定），并且在该机器上为其分配一段处理时间。具体 方法为:从机器分配向量U中获取它所选择的处理机器，然后可以从0时刻开始往后顺序扫 描该机器上已安排操作之间的空闲时隙直到一个可用的空闲时隙被找到，以安排该操作。
[0038] 其中，可用的空闲时隙寻找方法如下：设表示一个操作0^在调度中的开始执 行时刻，Ci,j表示它的完成时刻。因为一个操作只能在它所属作业内的上一个操作执行完成 后才能执行，所以如果在机器M k上的一个空闲时隙[SX，EX]对于操作是可用的，那必须满 足如下约束条件：
[0039]
[0040]式中，Sx表示时隙的开始时间;Ex表示时隙的结束时间；(^^表示操作的完成 时刻，Pi, j,k表不操作Oi, j在机器Mk上的加工时间。
[0041] 当操作0^被分配到可用的空闲时隙后，它的开始时刻就被设置为maX{Sx，cm}， j 2 2或者Sx，j = 1。如果在机器Mk上对于操作不存在这样的时隙，那么操作将被安排 到机器Mk的时间末端上。通过这种解码方式产生的调度解可以保证是活动调度解。例如，对 于表1中的问题，一个可行的染色体为11=[1，1，1，1，1，2，1]和￥=[6，1，7,3,4,2,5]，那么通 过上述解码方式可以得到以甘特图描述的活动调度解。
[0042] 由此可见，在该解码方式中，一个操作在被调度时，允许其在所分配的机器上搜索 最早的可用空闲时隙。因此对于被分配在同一台机器上的操作^和^，有可能出现如下情 形:在解码得到的调度方案中Vi在vj之前被执行，但是在向量v中，Vj实际出现在Vi之前。为 了在遗传搜索中更好地继承高质量的操作序列信息，在染色体涉及遗传操作之前，本发明 对染色体中的向量 v进行重排，具体做法是根据操作在解码后所得调度中的开始时刻，对所 有操作进行非递减的排序，所得到的操作序列就是调整后的向量V。
[0043] (3)遗传操作:遗传操作用来生成子代个体，它包括交叉和变异。
[0044] (a)交叉是对一对染色体进行操作，而变异只针对于单个个体。对染色体中的两个 向量，交叉操作是分别独立执行的：
[0045] 对于向量u上的交叉操作，首先在其中随机选择一些交叉位置，然后通过交换两个 父代染色体相应位置上的基因信息以得到两个子代个体的向量u表示。
[0046] 对于向量v上的交叉操作，采用一个改进的序列交叉方式，具体方法为：
[0047] 首先，在向量v中随机选择两个交叉点，将第一个父代个体中在这两个交叉点之间 的所有操作复制到第一子代个体的相应位置。
[0048] 然后，对于余下的操作，按照第二个父代个体中这些操作出现的优先顺序逐个将 它们填补到第一个子代个体的向量v中的空余部分。对于第二个子代个体，可以对称地由在 第二个父代个体中选择交叉点的方式得到。
[0049] 最后，对交叉后得到的向量v进一步做修补策略，以调整同一个作业内的操作的相 对顺序，从而保证可行性。这是由于作业内操作之间的约束，这种方式所得到的操作序列并 不一定是可行的。
[0050] 修补策略方法为：
[0051] 首先，将操作序列向量中的元素[(^^…^初始化^吏各元素均为⑴其中^表 示第η个位置上的操作ID号；
[0052] 然后，对需要修补的向量v从左往右依次读取各位的元素 Vi，计算操作Vi所属的作 业Jk，则qk递增1，获得操作的固定ID号op;
[0053] 最后，将元素^重新赋值为op，完成修补。
[0054] (b)变异操作与交叉操作相同，也包含两个独立的部分:对于向量u，任意选择一个 操作然后改变该操作的机器分配;对于向量V，在不违反同一作业内操作优先顺序的前提 下，将一个操作插入到向量V的另一个位置上，其中操作和位置都是随机选择的。
[0055]上述步骤3)中，利用局部搜索策略对子代种群进行局部搜索分为两个部分：
[0056] (1)子代种群中的个体选择：
[0057]首先，定义如下聚合函数:f(x，A) 。其中λ = [λ^λζ,λ：^ 是一个权向量，fi (x)、f 2(x)和f 3(x)分别设置为M0-FJSP问题的3个优化目标，即完工时间， 总负载和关键负载。
[0058]然后，生成一组满足约束条件且在目标空间中均匀分布的权向量。其中，约束条件 为：
[0059] λι+λ2+λ3 = ζ ,λι^ {0,1,.,.,ζ},1 = 1,2,3 (2)
[0060] 因此，权向量的个数为（（z+2)(z+l))/2，z为预先设定参数。在本实施例中，个数z 设置为23，那么对含有3个优化目标的问题将会生成300个权向量。
[0061] 当选择一个个体进行局部搜索时，首先从这些权向量中随机选择一个，然后以这 个权值向量确定的聚合函数f (X，λ)为比较指标，通过无放回的锦标赛选择方式选择一个精 英解，最后对该解进行局部搜索以得到一个或一组改进的解。
[0062] 最后，引入一个局部搜索的概率Pls，那么在子代种群中将有6」个解被选择 以执行进一步的局部搜索。换言之，"选择精英解并应用局部搜索"的操作被重复了 L#x4」次。
[0063] (2)选择了某个个体，通过局部搜索对该个体进行精炼以得到更高质量的个体，即 针对个体的局部搜索:本发明的局部搜索实际上不直接针对染色体，而是针对该染色体解 码后的调度解，这样有利于引入与问题相关的知识。
[0064] ①在局部搜索中，一个调度解G的邻域解是通过移动某个操作来得到的。因为完工 时间这个目标相对于其它两个目标较难以优化，设定调度解G的邻域解G'是可接受的当且 仅当C max(G)）、Cmax(G)分别表示邻域解G'和调度解G的完工时间；为了使 移动更有针对性、更加高效，这里引入如下定理：
[0065]定理1:在调度解G中，若通过移动某个操作〇u〈x(G)得到一个新解G'，那么Cmax (G7 H Cmax(G)，X(G)表示调度解G中关键操作的集合。
[0066]从定理1中可以得出，只有移动关键操作才能减小完工时间。所以在本发明的局部 搜索中，只考虑移动关键操作。
[0067]在当前调度解G中移动一个关键操作使得到的邻域解G'是可行的且满足) < Cmax(G)，假设调度解G中的关键操作coi将被移动，将关键操作coi从调度解G中删除得到 G，其方法为:首先，先移除以coi为起点和以关键操作coi为终点的非连接弧;然后用一条 指向SM(G，coi)的非连接弧连接PM(G，coi)和SM(G，coi);最后将节点coi的权重设置为0。其 中，SM(G，coi)表示调度解G中，与关键操作coi在同一台机器上的关键操作coi的后一个操 作;PM(G，coi)表示解调度解G中，与关键操作coi在同一台机器上的关键操作coi的前一个 操作。
[0068] ②删除coi之后，在中重新选择一个可行的位置，将关键操作coi重新插入，以得 到可行调度亇且(^Χ(Κ H Uax(G)。如果中存在这样的位置，假设该位置位于机器Mk上的 操作v之前，那么coi的开始时刻不得早于，/^/(6·:. .v〇)，且在完工时间不大于Cmax(G) 的限制下coi的完成时刻不得迟于i胃(C?)) :。另外，coi还必须遵循同一个作业内 的操作优先约束关系。因此，如果该位置对于coi来说是可以插入的，那么必须满足如下不 等式：
[0069]
[0070] 式中，￡〇(σ「，ΡΜ(6Γ,ν))表示最早完成时间，即在调度GT中，操作PM(G「，V)的最 早完成时间；"'设表示最迟开始时间，即在以完工时间为C max(G)的前提下，调 度g中，操作v的最迟开始时间;POT1, k表示操作coi在机器Mk上的加工时间。
[0071] 因此，可以保证如下情形不会发生：在下一轮局部迭代的过程中coi将再次被移 动，局部搜索的当前解又回到初始解G，这样就可以尽可能地避免循环搜索。
[0072] ③即使在满足式(3)的条件下，将coi插入v之前，也不能确保所得到的调度解V是 无环的。因此，将coi插入到某台机器M k上，将所考虑的插入位置仅限制在可行的位置上方 法如下：
[0073] 设在调度G,中在机器Mk上执行的操作集合，且这个集合是有序的，其中包含 的操作按最早开始时刻递增的顺序进行了排序(注意再设〇1^和*15是01{的两个 子序列，且它们满足如下条件：
[0074]
[0075]
[0076] 设γ k表示在Φ k\Ψk中所有操作之前且在Ψk\ Φk中所有操作之后的位置的集合， 则可以得到如下定理：
[0077] 定理2:在调度中，将操作coi插入到一个位置γ e yk上总能得到一个可行的调 度解，且在集合Tk中存在一个最优位置，即在机器Mk的其它任何位置上插入coi都不能得到 具有更小完工时间的调度。
[0078] 推论1:在调度Gf中，如果将操作coi插入到机器Mk上的某个位置，可以得到一个可 行调度V且满足(^ Χ(Κ H Cmax(G)，那么集合γ k中也一定存在这样的位置。
[0079] 由推论1，当在调度中，为操作coi重新分配机器Mk上的某个位置时，只需顺序检 测Yk中的位置，一旦某个位置满足约束(3)，立即将coi插入到这个位置上，得到邻域调度 解V，它替换G成为新的当前调度解，也是下一轮局部迭代的初始解。
[0080] 由此可见，在本发明的局部搜索中实际使用了"首次接受"的方式，即接受第一个 可接受的邻域解作为当前解。这是因为如果考虑所有关键操作的所有可行的移动，计算开 销相当大。
[0081] ④将在调度GT中将操作c〇i插入位置γ的过程看作一个动作，并表示为c〇i~Mk。 设#G) = {m/、，Μ,、/ =丨，2,...e Mro/ }，该集合包含了所有Σ 1 coi个可能的动 作，其中每个动作都有希望生成当前调度解G的一个可接受的邻域解。
[0082] 在本专利的局部搜索中，对总负载和关键负载这两个优化目标的考虑，体现在局 部搜索以何种顺序逐个尝试识(C?)中的动作。为炉(G)中的每个动作coi~M k定义两个指标：
[0083] At(COi^^Mk)-Pcoi, k-Pcoi, u(coi, G) (6)
[0084] Δ c(coi~Mk) =Wk(G)+pc〇i，k (7)
[0085] 式中，WcoiA)表示调度G中的操作coi所选择的机器ID号。
[0086] 显然，At和Ac分别考虑了总负载和关键负载这两个优化目标。基于这两个指标， 可以对舛G)中的动作按△ t的大小进行非递减的排序。如果两个动作具有相同的△ t值，具 有较小A c值的动作排在前列。在局部搜索的一轮迭代中，0G)中的动作根据排序后的顺 序逐个被尝试，直至生成当前调度解G的一个可接受的邻域解。
[0087] (3)接受准则：针对在局部搜索路径上产生的邻域解，本发明采用Best准则和 Pareto准则两种不同的接受 准则确定哪些将被作为改进的解添加到改进的种群中。
[0088] Best准则选择局部搜索路径上具有最小f(G，A)值的调度解作为最终改进的解。 [0089] Pareto准则是在每一代中，收集所有局部搜索路径上的解，当中的非支配解构成 了改进的种群。
[0090]上述各实施例仅用于说明本发明，各个步骤都是可以有所变化的，在本发明技术 方案的基础上，凡根据本发明原理对个别步骤进行的改进和等同变换，均不应排除在本发 明的保护范围之外。
【主权项】
1. 一种基于目标重要性分解的模因演化多目标优化调度方法，其特征在于，所述方法 步骤如下： 1) 随机产生一个大小为N的初始种群P0; 2) 在算法每一代中，先由当前种群Pt通过二元锦标赛选择，遗传算子产生一个子代种群 Qt ； 3) 利用局部搜索策略对子代种群Qt进行精细搜索以得到一个改善的种群Vt; 4) 将当前种群Pt、子代种群Qt和改善的种群合并生成一个种群Rt，对种群Rt中目标大 小完全相同的个体进行变异操作； 5) 利用NSGA-II中的快速非支配排序与拥挤距离方法对种群Rt中的个体进行排序，以选 择最好的N个解作为下一代种群P t+1。2. 如权利要求1所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤2)中，利用遗传算子产生子代种群，即利用遗传搜索产生子代种群，其 包括染色体编码、染色体解码和遗传操作： (1) 染色体编码： (a)给定每个操作一个固定的ID: j，其中j = l，2,. . .，d，d= Σγη;在编号之后，一个操作 也可以用固定ID号进行指代； (13)机器分配向量表示为11=[111，112，'"11(]]，且11」满足1<11」<1」，其中1」是供操作」执行的 机器数目； (C)进一步将操作j的可用机器按操作j在其上的处理时间进行非递减的排序：如果两 台机器在执行操作j时需要相同的处理时间，那么具有较小ID号的机器排在前列； (d)操作序列向量表示为V = [VI，V2，···Vd]，其中操作ID号在这个向量中的出现顺序表 示该操作的调度优先顺序，操作有最高优先权的被首先调度； (2) 染色体解码:按向量V中的操作排列顺序，逐个将每个操作分配到指定的机器上，并 且在该机器上为其分配一段处理时间：从机器分配向量u中获取它所选择的处理机器，然后 从〇时刻开始往后顺序扫描该机器上已安排操作之间的空闲时隙直到一个可用的空闲时隙 被找到，以安排该操作； (3) 遗传操作用来生成子代个体，它包括交叉和变异。3. 如权利要求2所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(2)中，可用的空闲时隙寻找方法如下:设表示一个操作在调度 中的开始执行时刻，Ci, j表不它的完成时刻；如果在机器Mk上的一个空闲时隙[Sx，Ex ]对于操 作是可用的，那必须满足如下约束条件：当操作被分配到可用的空闲时隙后，它的开始时刻就被设置为maX{Sx，cm}，j 2 2 或者Sx，j = I;如果在机器Mk上对于操作不存在这样的时隙，那么操作将被安排到机 器Mk的时间末端上。4. 如权利要求2所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(3)中，交叉是对一对染色体进行操作，对染色体中的两个向量u和V，交 叉操作是分别独立执行的： 对于向量U上的交叉操作，首先在其中随机选择一些交叉位置，然后通过交换两个父代 染色体相应位置上的基因信息以得到两个子代个体的向量U表示； 对于向量V上的交叉操作，采用一个改进的序列交叉方式，具体方法为： 首先，在向量V中随机选择两个交叉点，将第一个父代个体中在这两个交叉点之间的所 有操作复制到第一子代个体的相应位置； 然后，对于余下的操作，按照第二个父代个体中这些操作出现的优先顺序逐个将它们 填补到第一个子代个体的向量￥中的空余部分;对于第二个子代个体，对称地由在第二个父 代个体中选择交叉点的方式得到； 最后，对交叉后得到的向量V进一步做修补策略，以调整同一个作业内的操作的相对顺 序。5. 如权利要求2所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(3)中，变异只针对于单个个体，变异操作包含两个独立的部分:对于向 量u，任意选择一个操作然后改变该操作的机器分配;对于向量V，在不违反同一作业内操作 优先顺序的前提下，将一个操作插入到向量V的另一个位置上，其中操作和位置都是随机选 择的。6. 如权利要求1至5任一项所述的一种基于目标重要性分解的模因演化多目标优化调 度方法，其特征在于:所述步骤3)中，利用局部搜索策略对子代种群进行局部搜索分为两个 部分： (1) 子代种群中的个体选择： 首先，定义聚合函数:；^(1，人）=人1；^(1)+\2€2(1)+人3；^(1)，其中\=|> 1，\2，人3]是一个权 向量，fi (X)、f2(X)和f 3(X)分别设置为MO-FJSP问题的3个优化目标，即完工时间，总负载和 关键负载； 然后，生成一组满足约束条件且在目标空间中均匀分布的权向量;约束条件为： λι+λ2+λ3 = ζ, λ?^{〇,1,...,z},1 = 1,2,3 权向量的个数为（（z+2)(z+1) )/2;当选择一个个体进行局部搜索时，先从这些权向量 中随机选择一个，然后以这个权值向量确定的聚合函数?·(χ，λ)为比较指标，通过无放回的 锦标赛选择方式选择一个精英解，最后对该解进行局部搜索以得到一个或一组改进的解； 最后，引入一个局部搜索的概率Pis，在子代种群中将有个解被选择以执行进一 步的局部搜索； (2) 选择了某个个体，通过局部搜索对该个体进行精炼以得到更高质量的个体，即针对 个体的局部搜索： ① 在局部搜索中，一个调度解G的邻域解是通过移动某个操作来得到的：设定调度解G 的邻域解G'是可接受的当且仅当UaXV H Cmax(G);假设调度解G中的关键操作coi将被移 动，将关键操作Coi从G中删除得到Gi :首先，先移除以C0i为起点和以关键操作C0i为终点 的非连接弧;然后用一条指向SM(G，coi)的非连接弧连接PM(G，coi)和SM(G，coi);最后将节 点coi的权重设置为0; ② 删除coi之后，在兔中重新选择一个可行的位置，将关键操作coi重新插入，以得到可 行调度G7且）< Cmax(G); ③ 将coi插入到某台机器Mk上，将插入位置仅限制在可行的位置上方法如下：当在调度 稼中，为操作coi重新分配机器M k上的某个位置时，只需顺序检测集合的位置，一旦某 个位置满足约束条件，立即将coi插入到这个位置上，得到邻域调度解V，它替换G成为新的 当前调度解，也是下一轮局部迭代的初始解;其中，集合Yk示在?k\Wk中所有操作之前且 在ΨιΛ 中所有操作之后的位置的集合，Φk和Wk是操作集合Θ k的两个子序列； ④ 将在调度GT中将操作COi插入位置γ的过程看作一个动作，并表示为COi~Mk;设该集合包含了所有Σ Icoi个可能的动作， 其中每个动作都有希望生成当前解G的一个可接受的邻域解； (3)接受准则：采用Best准则和Pareto准则两种不同的接受准则确定哪些将被作为改 进的解添加到改进的种群中。7. 如权利要求6所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(2)②中，如果该位置对于coi来说是可以插入的，那么必须满足下式：式中，PM(Gf5V))表示最早完成时间，即在调度G,中，操作PM(GpV)的最早完 成时间；LS(G, ,r,C_(G))表示最迟开始时间，即在以完工时间为Cmax(G)的前提下，调度 中，操作V的最迟开始时间;Pc^k表示操作coi在机器M k上的加工时间。8. 如权利要求6所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(3)中，Best准则选择局部搜索路径上具有最小f(G，A)值的调度解作为 最终改进的解。9. 如权利要求6所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(3)中，Pareto准则是在每一代中，收集所有局部搜索路径上的解，当中 的非支配解构成了改进的种群。
【专利摘要】本发明涉及一种基于目标重要性分解的模因演化多目标优化调度方法，其步骤为：随机产生一个大小为N的初始种群；在算法每一代中，先由当前种群通过二元锦标赛选择，遗传算子产生一个子代种群；利用局部搜索策略对子代种群进行精细搜索以得到一个改善的种群；将当前种群、子代种群和改善的种群合并生成一个种群，对种群中目标大小完全相同的个体进行变异操作；利用NSGA-II中的快速非支配排序与拥挤距离方法对种群中的个体进行排序，以选择最好的N个解作为下一代种群。本发明可以对多目标柔性作业车间系统进行有效的调度，且调度效果优于目前已有的先进算法，可以广泛在计算机应用技术领域和生产调度领域中应用。
【IPC分类】G06Q50/04, G06N3/12
【公开号】CN105488568
【申请号】CN201510856926
【发明人】徐华
【申请人】清华大学
【公开日】2016年4月13日
【申请日】2015年11月30日
【技术领域】
[0001] 本发明涉及一种多目标优化调度方法，特别是关于一种在计算机应用技术领域和 生产调度领域中应用的基于目标重要性分解的模因演化多目标优化调度方法。
【背景技术】
[0002] 第二代非支配遗传算法（Nondominated Sorting Genetic Algorithm II，NSGA_ II)首先随机生成含有N个个体的初始种群，其中N是种群大小。接下来，算法进行迭代直至 终止条件满足。在第t代，算法在当前种群Pt的基础上，通过随机选择，模拟两点交叉 (Simulated Binary Crossover，SBX)和多项式变异产生子代种群QtIt和Qt的大小均为N。 因此，两个种群Pt和Qt合并会形成种群大小为2N的新的种群Rt = PtUQt。为了从种群Rt中 选择最好的N个解进入下一代，首先利用基于Pareto支配的非支配排序将Rt分为若干不同 的非支配层(F1，F2等等）。然后，算法构建一个新的种群St，构建方法是从F1开始，逐次将各 非支配层的解加入到St，直至St的大小等于N，或首次大于N。假设最后可以接受的非支配层 是1层，那么在1+1层以及之后的那些解就被丢弃掉了，且St\Fl中的解已经确定被选择作为 Pt+Ι中的解。Pt+Ι中余下的个体需要从F1中选取，选择的依据是要使种群在目标空间中具 有理想的多样性。在NSGA-II中，F1中具有较大拥挤距离的解会优先被选择。
[0003]多目标遗传局部搜索(Multiobjective Genetic Local Search,M0GLS)是较早的 蕴含分解思想的多目标进化算法，它最初是用来求解多目标流水车间调度问题。另外从搜 索行为上来看，M0GLS混合了遗传搜索和局部搜索，所以它也可以看作是一种模因演算法。 M0GLS的执行流程简要描述如下。首先，算法初始化一个大小为N的种群，并用一个外部存档 储存所找到的非支配解。之后，算法进行迭代直至终止条件满足。在M0GLS的第t代，首先选 出当前种群Pt中的所有非支配解，并用其更新外部存档。然后算法进入交配选择阶段，需要 选择N-Nel ite对父代个体，每对个体进行交叉和变异操作产生一个子代个体，并将其加入 到Pt+Ι中。在选择每对父代个体时，首先随机产生一个权向量w=(wl，w2,. . .，wm)T，其中Σ ￥1 = 1，111是目标数目，然后对?1：中的每个解1，有加权函数值；^1)=2￥1；^(1)，其中；^是第 i个目标函数，通过该函数值，由基于轮盘赌的比例选择法，可以得到每个个体被选择的概 率P(x)，根据该概率，可以选择两个父代个体。接着，算法采用了一种精英策略，从外部存档 中随机选择Nelite个解加入到Pt+Ι中，那么现在Pt+Ι中解的个数已达到种群大小。之后，算 法进入局部搜索过程，该过程总共执行N次，每次选择当前种群Pt+Ι中的一个个体以概率 pLS进行局部改进，选择方法如下：随机产生一个权向量w=(wl，w2,. . .，wm)T，其中2wi = 1，然后依据函数值f(x)= fi(x)使用无放回锦标赛选择从Pt+Ι中选择一个个体。如果 局部搜索被执行，改进后的个体将作为下一代种群中的个体，否则原来个体将进入下一代 种群。另外，在局部搜索中，算法设置了一个参数k，每次只随机检测当前解的k个邻域，k较 小时局部搜索很快就会终止，否则局部搜索会检测很多解，通过该参数可以调整局部搜索 在M0GLS中所花费的计算开销。
[0004] NSGA-II在求解多目标柔性作业车间调度问题往往没有充分利用问题相关的知 识，局部搜索的探索能力有限;MOGLS重在解决如何在多目标优化中选择解进行局部搜索， 以及如何对局部搜索中的解进行评价的问题，但是全局搜索能力欠缺。
[0005] 另外，这两种经典算法共同的缺陷:第一，并没有充分利用问题相关知识;第二，并 没有考虑问题的多个目标之间重要性的区别以及它们之间的相关性。
【发明内容】
[0006] 针对上述问题，本发明的目的是提供一种基于目标重要性分解的模因演化多目标 优化调度方法，该方法可以对多目标柔性作业车间系统进行有效的调度，且调度效果优于 目前已有的先进算法。
[0007] 为实现上述目的，本发明采取以下技术方案:一种基于目标重要性分解的模因演 化多目标优化调度方法，其特征在于，所述方法步骤如下：1)随机产生一个大小为N的初始 种群Ρο; 2)在算法每一代中，先由当前种群Pt通过二元锦标赛选择，遗传算子产生一个子代 种群Qt;3)利用局部搜索策略对子代种群Q t进行精细搜索以得到一个改善的种群以*;4)将 当前种群Pt、子代种群Qt和改善的种群Q、合并生成一个种群Rt，对种群Rt中目标大小完全相 同的个体进行变异操作;5)利用NSGA-II中的快速非支配排序与拥挤距离方法对种群R t中 的个体进行排序，以选择最好的N个解作为下一代种群Pt+1。
[0008] 进一步，所述步骤2)中，利用遗传算子产生子代种群，即利用遗传搜索产生子代种 群，其包括染色体编码、染色体解码和遗传操作：（1)染色体编码：（a)给定每个操作一个固 定的ID: j，其中j = l，2, . . .，d，d= Σγη;在编号之后，一个操作也可以用固定ID号进行指 代；（13)机器分配向量表示为11=[111，112，一11(]]，且11」满足1<11」<1」，其中1」是供操作」执行的 机器数目；（c)进一步将操作j的可用机器按操作j在其上的处理时间进行非递减的排序:如 果两台机器在执行操作j时需要相同的处理时间，那么具有较小ID号的机器排在前列；（d) 操作序列向量表示为V = [ VI，V2，…Vd]，其中操作ID号在这个向量中的出现顺序表示该操作 的调度优先顺序，操作有最高优先权的被首先调度；（2)染色体解码:按向量V中的操作排列 顺序，逐个将每个操作分配到指定的机器上，并且在该机器上为其分配一段处理时间：从机 器分配向量u中获取它所选择的处理机器，然后从0时刻开始往后顺序扫描该机器上已安排 操作之间的空闲时隙直到一个可用的空闲时隙被找到，以安排该操作；（3)遗传操作用来生 成子代个体，它包括交叉和变异。
[0009] 进一步，所述步骤(2)中，可用的空闲时隙寻找方法如下：设表示一个操作 在调度中的开始执行时刻，Ci,j表示它的完成时刻;如果在机器Mk上的一个空闲时隙[SX，EX] 对于操作是可用的，那必须满足如下约束条件：
[0010]
[0011] 当操作〇1」被分配到可用的空闲时隙后，它的开始时刻就被设置为max{Sx， Cl,H}， j 2 2或者Sx，j = 1;如果在机器Mk上对于操作不存在这样的时隙，那么操作将被安排 到机器Mk的时间末端上。
[0012] 进一步，所述步骤(3)中，交叉是对一对染色体进行操作，对染色体中的两个向量u 和v，交叉操作是分别独立执行的:对于向量u上的交叉操作，首先在其中随机选择一些交叉 位置，然后通过交换两个父代染色体相应位置上的基因信息以得到两个子代个体的向量U 表示;对于向量V上的交叉操作，采用一个改进的序列交叉方式，具体方法为:首先，在向量V 中随机选择两个交叉点，将第一个父代个体中在这两个交叉点之间的所有操作复制到第一 子代个体的相应位置;然后，对于余下的操作，按照第二个父代个体中这些操作出现的优先 顺序逐个将它们填补到第一个子代个体的向量V中的空余部分;对于第二个子代个体，对称 地由在第二个父代个体中选择交叉点的方式得到;最后，对交叉后得到的向量V进一步做修 补策略，以调整同一个作业内的操作的相对顺序。
[0013] 进一步，所述步骤(3)中，变异只针对于单个个体，变异操作包含两个独立的部分： 对于向量U，任意选择一个操作然后改变该操作的机器分配;对于向量V，在不违反同一作业 内操作优先顺序的前提下，将一个操作插入到向量V的另一个位置上，其中操作和位置都是 随机选择的。
[0014] 进一步，所述步骤3)中，利用局部搜索策略对子代种群进行局部搜索分为两个部 分：⑴子代种群中的个体选择:首先，定义聚合函数:f (1，1)=11：^(1)+\2€2(1)+13；^(1)，其 中λ = [λ:，λ2，λ3 ]是一个权向量，f i (X)、f 2 (X)和f 3 (X)分别设置为MO-FJSP问题的3个优化目 标，即完工时间，总负载和关键负载;然后，生成一组满足约束条件且在目标空间中均匀分 布的权向量;约束条件为. . .，z}，i = l，2,3,权向量的个数为（（z+ 2)(z+l))/2;当选择一个个体进行局部搜索时，先从这些权向量中随机选择一个，然后以这 个权值向量确定的聚合函数f (X，λ)为比较指标，通过无放回的锦标赛选择方式选择一个精 英解，最后对该解进行局部搜索以得到一个或一组改进的解;最后，引入一个局部搜索的概 率Pis，在子代种群中将有个解被选择以执行进一步的局部搜索；（2)选择了某个个 体，通过局部搜索对该个体进行精炼以得到更高质量的个体，即针对个体的局部搜索:①在 局部搜索中，一个调度解G的邻域解是通过移动某个操作来得到的：设定调度解G的邻域解 G'是可接受的当且仅当Cmax(G);假设调度解G中的关键 操作coi将被移动，将关键 操作coi从G中删除得到首先，先移除以 c〇i为起点和以关键操作c〇i为终点的非连接 弧;然后用一条指向SM(G，coi)的非连接弧连接PM(G，coi)和SM(G，coi);最后将节点coi的 权重设置为〇;②删除coi之后，在GT中重新选择一个可行的位置，将关键操作 coi重新插入， 以得到可行调度V且UaXG' H Cmax(G);③将coi插入到某台机器Mk上，将插入位置仅限制 在可行的位置上方法如下：当在调度GT中，为操作coi重新分配机器M k上的某个位置时，只 需顺序检测集合γ k中的位置，一旦某个位置满足约束条件，立即将coi插入到这个位置上， 得到邻域调度解V，它替换G成为新的当前调度解，也是下一轮局部迭代的初始解;其中，集 合Yk示在中所有操作之前且在ΨιΛΦ??中所有操作之后的位置的集合，和Ψι<是 操作集合? k的两个子序列;④将在调度G「中将操作coi插入位置γ的过程看作一个动作， 并表示为coi~Mk;设供(G) = ? α."?/Α / = 1,2, ... ,/κ?Α e VkW ，该集合包含了所有 Slcoi个可能的动作，其中每个动作都有希望生成当前解G的一个可接受的邻域解；（3)接 受准则:采用Best准则和Pareto准则两种不同的接受准则确定哪些将被作为改进的解添加 到改进的种群中。
[0015] 进一步，所述步骤(2)②中，如果该位置对于coi来说是可以插入的，那么必须满足 下式：
[0016]
[0017] 式中，￡Γ((7,. ，⑶表示最早完成时间，即在调度Gf中，操作；ΡΜ(βΜν)的最 早完成时间；aGJG))表示最迟开始时间，即在以完工时间为C max(G)的前提下，调 度GT中，操作v的最迟开始时间;Ρ。。^表示操作coi在机器Mk上的加工时间。
[0018] 进一步，所述步骤(3)中，Best准则选择局部搜索路径上具有最小f(G，A)值的调度 解作为最终改进的解。
[0019] 进一步，所述步骤(3)中，Pareto准则是在每一代中，收集所有局部搜索路径上的 解，当中的非支配解构成了改进的种群。
[0020] 本发明由于采取以上技术方案，其具有以下优点：本发明可以完成柔性作业车间 系统作业数目、机器数目、操作数目、每个操作可用机器情况等基本参数的设置，而且可以 根据不同的设备场景和工艺需求，针对每个作业灵活配置各种各样的加工路径。利用所提 出的模因演算法，可以对配置好的优化目标为完工时间、总负载、关键负载的柔性作业车间 系统进行有效的调度，且调度效果明显优于目前已有的先进算法。本发明可以广泛在计算 机应用技术领域和生产调度领域中应用。
【附图说明】
[0021] 图1是本发明的染色体所对应的甘特图示意图。
【具体实施方式】
[0022] 为了解决半导体生产、汽车装配、纺织等工业生产中所涉及的关键多目标调度问 题，即多目标柔性作业车间调度问题，本发明提供一种基于目标重要性分解的模因演化多 目标优化调度方法，即多目标模因演算法。该方法首先提出一个求解M0-FJSP(多目标柔性 作业车间调度问题）的基于关键操作的与问题相关的局部搜索算子，该算子强调了对问题 解空间的开发能力。在该局部搜索中，使用了一种分层策略来处理三个目标。即，主要考虑 完工时间的最小化，对其它两个目标的考虑则体现在尝试所有可能产生可接受邻域解的动 作的顺序上。第二，通过良好设计的染色体表示、染色体解码和遗传算子，开发了针对M0-FJSP的基于NSGA-II(第二代非支配遗传算法）的遗传搜索，它主要强调对问题解空间的探 索能力。第三，采用了与M0GLS(多目标遗传局部搜索）中类似的机制从种群中选择解进行局 部搜索，有利于在MAs(模因演算法）中平衡局部搜索和遗传搜索。下面结合附图和实施例对 本发明进行详细的描述。
[0023]本发明的基于目标重要性分解的模因演化多目标优化调度方法，基于Eclipse开 发平台，可以为不同配置的多目标柔性作业车间调度系统提供统一的、有效的调度接口，其 步骤如下：
[0024] 1)随机产生一个大小为N的初始种群Po。
[0025] 2)在算法每一代中，先由当前种群Pt通过二元锦标赛选择，遗传算子(包括交叉和 变异)产生一个子代种群Qt。
[0026] 3)利用局部搜索策略对子代种群Qt进行精细搜索以得到一个改善的种群Q\。
[0027] 4)将当前种群Pt、子代种群Qt和改善的种群V t合并生成一个种群Rt，由于种群Rt可 能会含有一些目标大小完全相同的个体，这样会影响搜索质量，因此，对种群Rt中目标大小 完全相同的个体进行变异操作。
[0028] 5)利用NSGA-II中的快速非支配排序与拥挤距离方法对种群Rt中的个体进行排 序，以选择最好的N个解作为下一代种群P t+1。
[0029] 上述步骤2)中，利用遗传算子产生子代种群，即利用遗传搜索产生子代种群，遗传 搜索在模因演算法中主要负责对问题解空间的全局搜索，该遗传搜索包括染色体编码、染 色体解码和遗传操作，具体方法如下：
[0030] (1)染色体编码:对于FJSP(柔性作业车间调度问题）问题，一个解由两部分组成： 第一部分是操作在机器上的分配;第二部分是每台机器上操作的处理序列。因此，本发明的 模因演算法中一个染色体由两个向量组成:第一个向量是机器选择向量，第二个向量是操 作排序向量。这两个向量分别对应于FJSP问题的两个子问题。
[0031] (a)给定每个操作一个固定的ID: j，其中j = l，2, · · .，d，d= Σγη。这就意味着作业 Ji包含操作1，. . .，m，作业J2包含操作ni+1，. . .，ηι+η2,以此类推。在编号之后，一个操作也 可以用固定ID号进行指代，如在表1.1中，操作〇2,2也可以称作操作4,表中Mk为第k个机器。 [0032] 表1 M0-FJSP问题样例的处理时间表
[0033
[0034] (b)机器分配向量可以表示为u = [m，u2，…叫]。这是一个包含d个整数值的数组， 且元素叫满足1 < d，其中1」是可供操作j执行的机器数目。
[0035] (c)再进一步将操作j的可用机器，按操作j在其上的处理时间进行非递减的排序。 如果两台机器在执行操作j时需要相同的处理时间，那么具有较小ID号的机器排在前列，这 样，在机器分配向量中W意味着操作j选择了在排序后的可用机器序列中的第台机器，也 即具有第叫小处理时间的机器。
[0036] (d)操作序列向量可以表示为v= [V1，v2, ···~]。它是一个所有操作ID号的一个全 排列，其中操作ID号在这个向量中的出现顺序表示该操作的调度优先顺序。例如，对于在表 中的问题，一个可能的操作序列向量可以表示为^=[6，1，7,3,4,2,5]。这个向量可以直接 转换为操作的优先顺序列表:〇3,1>〇1,1>〇3,2>〇2,1>〇2,2>〇1,2>〇2,3。操作〇3,1有最高的优 先权并被首先调度，然后是操作Oi, i，以此类推。
[0037] (2)染色体解码:染色体解码就是按向量v中的操作排列顺序，逐个将每个操作分 配到指定的机器上（由机器分配向量U确定），并且在该机器上为其分配一段处理时间。具体 方法为:从机器分配向量U中获取它所选择的处理机器，然后可以从0时刻开始往后顺序扫 描该机器上已安排操作之间的空闲时隙直到一个可用的空闲时隙被找到，以安排该操作。
[0038] 其中，可用的空闲时隙寻找方法如下：设表示一个操作0^在调度中的开始执 行时刻，Ci,j表示它的完成时刻。因为一个操作只能在它所属作业内的上一个操作执行完成 后才能执行，所以如果在机器M k上的一个空闲时隙[SX，EX]对于操作是可用的，那必须满 足如下约束条件：
[0039]
[0040]式中，Sx表示时隙的开始时间;Ex表示时隙的结束时间；(^^表示操作的完成 时刻，Pi, j,k表不操作Oi, j在机器Mk上的加工时间。
[0041] 当操作0^被分配到可用的空闲时隙后，它的开始时刻就被设置为maX{Sx，cm}， j 2 2或者Sx，j = 1。如果在机器Mk上对于操作不存在这样的时隙，那么操作将被安排 到机器Mk的时间末端上。通过这种解码方式产生的调度解可以保证是活动调度解。例如，对 于表1中的问题，一个可行的染色体为11=[1，1，1，1，1，2，1]和￥=[6，1，7,3,4,2,5]，那么通 过上述解码方式可以得到以甘特图描述的活动调度解。
[0042] 由此可见，在该解码方式中，一个操作在被调度时，允许其在所分配的机器上搜索 最早的可用空闲时隙。因此对于被分配在同一台机器上的操作^和^，有可能出现如下情 形:在解码得到的调度方案中Vi在vj之前被执行，但是在向量v中，Vj实际出现在Vi之前。为 了在遗传搜索中更好地继承高质量的操作序列信息，在染色体涉及遗传操作之前，本发明 对染色体中的向量 v进行重排，具体做法是根据操作在解码后所得调度中的开始时刻，对所 有操作进行非递减的排序，所得到的操作序列就是调整后的向量V。
[0043] (3)遗传操作:遗传操作用来生成子代个体，它包括交叉和变异。
[0044] (a)交叉是对一对染色体进行操作，而变异只针对于单个个体。对染色体中的两个 向量，交叉操作是分别独立执行的：
[0045] 对于向量u上的交叉操作，首先在其中随机选择一些交叉位置，然后通过交换两个 父代染色体相应位置上的基因信息以得到两个子代个体的向量u表示。
[0046] 对于向量v上的交叉操作，采用一个改进的序列交叉方式，具体方法为：
[0047] 首先，在向量v中随机选择两个交叉点，将第一个父代个体中在这两个交叉点之间 的所有操作复制到第一子代个体的相应位置。
[0048] 然后，对于余下的操作，按照第二个父代个体中这些操作出现的优先顺序逐个将 它们填补到第一个子代个体的向量v中的空余部分。对于第二个子代个体，可以对称地由在 第二个父代个体中选择交叉点的方式得到。
[0049] 最后，对交叉后得到的向量v进一步做修补策略，以调整同一个作业内的操作的相 对顺序，从而保证可行性。这是由于作业内操作之间的约束，这种方式所得到的操作序列并 不一定是可行的。
[0050] 修补策略方法为：
[0051] 首先，将操作序列向量中的元素[(^^…^初始化^吏各元素均为⑴其中^表 示第η个位置上的操作ID号；
[0052] 然后，对需要修补的向量v从左往右依次读取各位的元素 Vi，计算操作Vi所属的作 业Jk，则qk递增1，获得操作的固定ID号op;
[0053] 最后，将元素^重新赋值为op，完成修补。
[0054] (b)变异操作与交叉操作相同，也包含两个独立的部分:对于向量u，任意选择一个 操作然后改变该操作的机器分配;对于向量V，在不违反同一作业内操作优先顺序的前提 下，将一个操作插入到向量V的另一个位置上，其中操作和位置都是随机选择的。
[0055]上述步骤3)中，利用局部搜索策略对子代种群进行局部搜索分为两个部分：
[0056] (1)子代种群中的个体选择：
[0057]首先，定义如下聚合函数:f(x，A) 。其中λ = [λ^λζ,λ：^ 是一个权向量，fi (x)、f 2(x)和f 3(x)分别设置为M0-FJSP问题的3个优化目标，即完工时间， 总负载和关键负载。
[0058]然后，生成一组满足约束条件且在目标空间中均匀分布的权向量。其中，约束条件 为：
[0059] λι+λ2+λ3 = ζ ,λι^ {0,1,.,.,ζ},1 = 1,2,3 (2)
[0060] 因此，权向量的个数为（（z+2)(z+l))/2，z为预先设定参数。在本实施例中，个数z 设置为23，那么对含有3个优化目标的问题将会生成300个权向量。
[0061] 当选择一个个体进行局部搜索时，首先从这些权向量中随机选择一个，然后以这 个权值向量确定的聚合函数f (X，λ)为比较指标，通过无放回的锦标赛选择方式选择一个精 英解，最后对该解进行局部搜索以得到一个或一组改进的解。
[0062] 最后，引入一个局部搜索的概率Pls，那么在子代种群中将有6」个解被选择 以执行进一步的局部搜索。换言之，"选择精英解并应用局部搜索"的操作被重复了 L#x4」次。
[0063] (2)选择了某个个体，通过局部搜索对该个体进行精炼以得到更高质量的个体，即 针对个体的局部搜索:本发明的局部搜索实际上不直接针对染色体，而是针对该染色体解 码后的调度解，这样有利于引入与问题相关的知识。
[0064] ①在局部搜索中，一个调度解G的邻域解是通过移动某个操作来得到的。因为完工 时间这个目标相对于其它两个目标较难以优化，设定调度解G的邻域解G'是可接受的当且 仅当C max(G)）、Cmax(G)分别表示邻域解G'和调度解G的完工时间；为了使 移动更有针对性、更加高效，这里引入如下定理：
[0065]定理1:在调度解G中，若通过移动某个操作〇u〈x(G)得到一个新解G'，那么Cmax (G7 H Cmax(G)，X(G)表示调度解G中关键操作的集合。
[0066]从定理1中可以得出，只有移动关键操作才能减小完工时间。所以在本发明的局部 搜索中，只考虑移动关键操作。
[0067]在当前调度解G中移动一个关键操作使得到的邻域解G'是可行的且满足) < Cmax(G)，假设调度解G中的关键操作coi将被移动，将关键操作coi从调度解G中删除得到 G，其方法为:首先，先移除以coi为起点和以关键操作coi为终点的非连接弧;然后用一条 指向SM(G，coi)的非连接弧连接PM(G，coi)和SM(G，coi);最后将节点coi的权重设置为0。其 中，SM(G，coi)表示调度解G中，与关键操作coi在同一台机器上的关键操作coi的后一个操 作;PM(G，coi)表示解调度解G中，与关键操作coi在同一台机器上的关键操作coi的前一个 操作。
[0068] ②删除coi之后，在中重新选择一个可行的位置，将关键操作coi重新插入，以得 到可行调度亇且(^Χ(Κ H Uax(G)。如果中存在这样的位置，假设该位置位于机器Mk上的 操作v之前，那么coi的开始时刻不得早于，/^/(6·:. .v〇)，且在完工时间不大于Cmax(G) 的限制下coi的完成时刻不得迟于i胃(C?)) :。另外，coi还必须遵循同一个作业内 的操作优先约束关系。因此，如果该位置对于coi来说是可以插入的，那么必须满足如下不 等式：
[0069]
[0070] 式中，￡〇(σ「，ΡΜ(6Γ,ν))表示最早完成时间，即在调度GT中，操作PM(G「，V)的最 早完成时间；"'设表示最迟开始时间，即在以完工时间为C max(G)的前提下，调 度g中，操作v的最迟开始时间;POT1, k表示操作coi在机器Mk上的加工时间。
[0071] 因此，可以保证如下情形不会发生：在下一轮局部迭代的过程中coi将再次被移 动，局部搜索的当前解又回到初始解G，这样就可以尽可能地避免循环搜索。
[0072] ③即使在满足式(3)的条件下，将coi插入v之前，也不能确保所得到的调度解V是 无环的。因此，将coi插入到某台机器M k上，将所考虑的插入位置仅限制在可行的位置上方 法如下：
[0073] 设在调度G,中在机器Mk上执行的操作集合，且这个集合是有序的，其中包含 的操作按最早开始时刻递增的顺序进行了排序(注意再设〇1^和*15是01{的两个 子序列，且它们满足如下条件：
[0074]
[0075]
[0076] 设γ k表示在Φ k\Ψk中所有操作之前且在Ψk\ Φk中所有操作之后的位置的集合， 则可以得到如下定理：
[0077] 定理2:在调度中，将操作coi插入到一个位置γ e yk上总能得到一个可行的调 度解，且在集合Tk中存在一个最优位置，即在机器Mk的其它任何位置上插入coi都不能得到 具有更小完工时间的调度。
[0078] 推论1:在调度Gf中，如果将操作coi插入到机器Mk上的某个位置，可以得到一个可 行调度V且满足(^ Χ(Κ H Cmax(G)，那么集合γ k中也一定存在这样的位置。
[0079] 由推论1，当在调度中，为操作coi重新分配机器Mk上的某个位置时，只需顺序检 测Yk中的位置，一旦某个位置满足约束(3)，立即将coi插入到这个位置上，得到邻域调度 解V，它替换G成为新的当前调度解，也是下一轮局部迭代的初始解。
[0080] 由此可见，在本发明的局部搜索中实际使用了"首次接受"的方式，即接受第一个 可接受的邻域解作为当前解。这是因为如果考虑所有关键操作的所有可行的移动，计算开 销相当大。
[0081] ④将在调度GT中将操作c〇i插入位置γ的过程看作一个动作，并表示为c〇i~Mk。 设#G) = {m/、，Μ,、/ =丨，2,...e Mro/ }，该集合包含了所有Σ 1 coi个可能的动 作，其中每个动作都有希望生成当前调度解G的一个可接受的邻域解。
[0082] 在本专利的局部搜索中，对总负载和关键负载这两个优化目标的考虑，体现在局 部搜索以何种顺序逐个尝试识(C?)中的动作。为炉(G)中的每个动作coi~M k定义两个指标：
[0083] At(COi^^Mk)-Pcoi, k-Pcoi, u(coi, G) (6)
[0084] Δ c(coi~Mk) =Wk(G)+pc〇i，k (7)
[0085] 式中，WcoiA)表示调度G中的操作coi所选择的机器ID号。
[0086] 显然，At和Ac分别考虑了总负载和关键负载这两个优化目标。基于这两个指标， 可以对舛G)中的动作按△ t的大小进行非递减的排序。如果两个动作具有相同的△ t值，具 有较小A c值的动作排在前列。在局部搜索的一轮迭代中，0G)中的动作根据排序后的顺 序逐个被尝试，直至生成当前调度解G的一个可接受的邻域解。
[0087] (3)接受准则：针对在局部搜索路径上产生的邻域解，本发明采用Best准则和 Pareto准则两种不同的接受 准则确定哪些将被作为改进的解添加到改进的种群中。
[0088] Best准则选择局部搜索路径上具有最小f(G，A)值的调度解作为最终改进的解。 [0089] Pareto准则是在每一代中，收集所有局部搜索路径上的解，当中的非支配解构成 了改进的种群。
[0090]上述各实施例仅用于说明本发明，各个步骤都是可以有所变化的，在本发明技术 方案的基础上，凡根据本发明原理对个别步骤进行的改进和等同变换，均不应排除在本发 明的保护范围之外。
【主权项】
1. 一种基于目标重要性分解的模因演化多目标优化调度方法，其特征在于，所述方法 步骤如下： 1) 随机产生一个大小为N的初始种群P0; 2) 在算法每一代中，先由当前种群Pt通过二元锦标赛选择，遗传算子产生一个子代种群 Qt ； 3) 利用局部搜索策略对子代种群Qt进行精细搜索以得到一个改善的种群Vt; 4) 将当前种群Pt、子代种群Qt和改善的种群合并生成一个种群Rt，对种群Rt中目标大 小完全相同的个体进行变异操作； 5) 利用NSGA-II中的快速非支配排序与拥挤距离方法对种群Rt中的个体进行排序，以选 择最好的N个解作为下一代种群P t+1。2. 如权利要求1所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤2)中，利用遗传算子产生子代种群，即利用遗传搜索产生子代种群，其 包括染色体编码、染色体解码和遗传操作： (1) 染色体编码： (a)给定每个操作一个固定的ID: j，其中j = l，2,. . .，d，d= Σγη;在编号之后，一个操作 也可以用固定ID号进行指代； (13)机器分配向量表示为11=[111，112，'"11(]]，且11」满足1<11」<1」，其中1」是供操作」执行的 机器数目； (C)进一步将操作j的可用机器按操作j在其上的处理时间进行非递减的排序：如果两 台机器在执行操作j时需要相同的处理时间，那么具有较小ID号的机器排在前列； (d)操作序列向量表示为V = [VI，V2，···Vd]，其中操作ID号在这个向量中的出现顺序表 示该操作的调度优先顺序，操作有最高优先权的被首先调度； (2) 染色体解码:按向量V中的操作排列顺序，逐个将每个操作分配到指定的机器上，并 且在该机器上为其分配一段处理时间：从机器分配向量u中获取它所选择的处理机器，然后 从〇时刻开始往后顺序扫描该机器上已安排操作之间的空闲时隙直到一个可用的空闲时隙 被找到，以安排该操作； (3) 遗传操作用来生成子代个体，它包括交叉和变异。3. 如权利要求2所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(2)中，可用的空闲时隙寻找方法如下:设表示一个操作在调度 中的开始执行时刻，Ci, j表不它的完成时刻；如果在机器Mk上的一个空闲时隙[Sx，Ex ]对于操 作是可用的，那必须满足如下约束条件：当操作被分配到可用的空闲时隙后，它的开始时刻就被设置为maX{Sx，cm}，j 2 2 或者Sx，j = I;如果在机器Mk上对于操作不存在这样的时隙，那么操作将被安排到机 器Mk的时间末端上。4. 如权利要求2所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(3)中，交叉是对一对染色体进行操作，对染色体中的两个向量u和V，交 叉操作是分别独立执行的： 对于向量U上的交叉操作，首先在其中随机选择一些交叉位置，然后通过交换两个父代 染色体相应位置上的基因信息以得到两个子代个体的向量U表示； 对于向量V上的交叉操作，采用一个改进的序列交叉方式，具体方法为： 首先，在向量V中随机选择两个交叉点，将第一个父代个体中在这两个交叉点之间的所 有操作复制到第一子代个体的相应位置； 然后，对于余下的操作，按照第二个父代个体中这些操作出现的优先顺序逐个将它们 填补到第一个子代个体的向量￥中的空余部分;对于第二个子代个体，对称地由在第二个父 代个体中选择交叉点的方式得到； 最后，对交叉后得到的向量V进一步做修补策略，以调整同一个作业内的操作的相对顺 序。5. 如权利要求2所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(3)中，变异只针对于单个个体，变异操作包含两个独立的部分:对于向 量u，任意选择一个操作然后改变该操作的机器分配;对于向量V，在不违反同一作业内操作 优先顺序的前提下，将一个操作插入到向量V的另一个位置上，其中操作和位置都是随机选 择的。6. 如权利要求1至5任一项所述的一种基于目标重要性分解的模因演化多目标优化调 度方法，其特征在于:所述步骤3)中，利用局部搜索策略对子代种群进行局部搜索分为两个 部分： (1) 子代种群中的个体选择： 首先，定义聚合函数:；^(1，人）=人1；^(1)+\2€2(1)+人3；^(1)，其中\=|> 1，\2，人3]是一个权 向量，fi (X)、f2(X)和f 3(X)分别设置为MO-FJSP问题的3个优化目标，即完工时间，总负载和 关键负载； 然后，生成一组满足约束条件且在目标空间中均匀分布的权向量;约束条件为： λι+λ2+λ3 = ζ, λ?^{〇,1,...,z},1 = 1,2,3 权向量的个数为（（z+2)(z+1) )/2;当选择一个个体进行局部搜索时，先从这些权向量 中随机选择一个，然后以这个权值向量确定的聚合函数?·(χ，λ)为比较指标，通过无放回的 锦标赛选择方式选择一个精英解，最后对该解进行局部搜索以得到一个或一组改进的解； 最后，引入一个局部搜索的概率Pis，在子代种群中将有个解被选择以执行进一 步的局部搜索； (2) 选择了某个个体，通过局部搜索对该个体进行精炼以得到更高质量的个体，即针对 个体的局部搜索： ① 在局部搜索中，一个调度解G的邻域解是通过移动某个操作来得到的：设定调度解G 的邻域解G'是可接受的当且仅当UaXV H Cmax(G);假设调度解G中的关键操作coi将被移 动，将关键操作Coi从G中删除得到Gi :首先，先移除以C0i为起点和以关键操作C0i为终点 的非连接弧;然后用一条指向SM(G，coi)的非连接弧连接PM(G，coi)和SM(G，coi);最后将节 点coi的权重设置为0; ② 删除coi之后，在兔中重新选择一个可行的位置，将关键操作coi重新插入，以得到可 行调度G7且）< Cmax(G); ③ 将coi插入到某台机器Mk上，将插入位置仅限制在可行的位置上方法如下：当在调度 稼中，为操作coi重新分配机器M k上的某个位置时，只需顺序检测集合的位置，一旦某 个位置满足约束条件，立即将coi插入到这个位置上，得到邻域调度解V，它替换G成为新的 当前调度解，也是下一轮局部迭代的初始解;其中，集合Yk示在?k\Wk中所有操作之前且 在ΨιΛ 中所有操作之后的位置的集合，Φk和Wk是操作集合Θ k的两个子序列； ④ 将在调度GT中将操作COi插入位置γ的过程看作一个动作，并表示为COi~Mk;设该集合包含了所有Σ Icoi个可能的动作， 其中每个动作都有希望生成当前解G的一个可接受的邻域解； (3)接受准则：采用Best准则和Pareto准则两种不同的接受准则确定哪些将被作为改 进的解添加到改进的种群中。7. 如权利要求6所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(2)②中，如果该位置对于coi来说是可以插入的，那么必须满足下式：式中，PM(Gf5V))表示最早完成时间，即在调度G,中，操作PM(GpV)的最早完 成时间；LS(G, ,r,C_(G))表示最迟开始时间，即在以完工时间为Cmax(G)的前提下，调度 中，操作V的最迟开始时间;Pc^k表示操作coi在机器M k上的加工时间。8. 如权利要求6所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(3)中，Best准则选择局部搜索路径上具有最小f(G，A)值的调度解作为 最终改进的解。9. 如权利要求6所述的一种基于目标重要性分解的模因演化多目标优化调度方法，其 特征在于:所述步骤(3)中，Pareto准则是在每一代中，收集所有局部搜索路径上的解，当中 的非支配解构成了改进的种群。
【专利摘要】本发明涉及一种基于目标重要性分解的模因演化多目标优化调度方法，其步骤为：随机产生一个大小为N的初始种群；在算法每一代中，先由当前种群通过二元锦标赛选择，遗传算子产生一个子代种群；利用局部搜索策略对子代种群进行精细搜索以得到一个改善的种群；将当前种群、子代种群和改善的种群合并生成一个种群，对种群中目标大小完全相同的个体进行变异操作；利用NSGA-II中的快速非支配排序与拥挤距离方法对种群中的个体进行排序，以选择最好的N个解作为下一代种群。本发明可以对多目标柔性作业车间系统进行有效的调度，且调度效果优于目前已有的先进算法，可以广泛在计算机应用技术领域和生产调度领域中应用。
【IPC分类】G06Q50/04, G06N3/12
【公开号】CN105488568
【申请号】CN201510856926
【发明人】徐华
【申请人】清华大学
【公开日】2016年4月13日
【申请日】2015年11月30日
最新回复(0)