【机器学习】应用改进区块遗传算法求解置换流水车间调度问题.pdf_大学文库

第14卷第3期智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201801041 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180503.1008.003.html 应用改进区块遗传算法求解置换流水车间调度问题裴小兵，张春花 (天津理工大学管理学院，天津300384) 摘要：针对最小化最大完工时间的置换流水车间调度问题，提出一种将遗传算法与蚊群算法相结合的改进区块遗传算法。算法利用随机机制和改进反向学习机制相结合的方式产生初始解，以兼顾初始种群的多样性和质量。通过若干代简单遗传算法操作产生精英群体，借鉴蚁群算法中利用蚂蚁信息度浓度统计路径和节点信息的思想，对精英群体所携带信息进行统计分析并建立位置信息素矩阵和相依信息素矩阵，根据两矩阵挖掘区块并将区块与非区块组合形成染色体。将染色体进行切段与重组，以提高染色体的质量，使用二元竞赛法保留适应度较高的染色体。算法通过Reeves实例和Taillard实例进行测试，并将结果与其他算法进行比较，验证了该算法的有效性。关键词：生产调度：组合优化：遗传算法：蚁群优化算法：构建区块：人工染色体中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)03-0541-10 中文引用格式：裴小兵，张春花.应用改进区块遗传算法求解置换流水车间调度问题[.智能系统学报，2019,14(3)： 541-550. 英文引用格式：PEI Xiaobing,.ZHANG Chunhua..An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J].CAAI transactions on intelligent systems,2019,14(3):541-550. An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems PEI Xiaobing,ZHANG Chunhua (School of Management,Tianjin University of Technology,Tianjin 300384,China) Abstract:Targeting the permutation flow-shop scheduling problem that minimizes maximum completion times,an im- proved block genetic algorithm combined with an ant colony algorithm is proposed.The algorithm uses a random mech- anism and the improved opposition-based learning mechanism to generate the initial solution.It takes into account the diversity and quality of the initial population.Elite populations are generated through several generations of simple ge- netic algorithm operations.Based on the idea of using ant information density concentration's statistical path and node information in the ant colony algorithm,the information carried by elite groups was counted.Position pheromone and dependent pheromone matrices were established.Mining blocks according to two matrices were developed and blocks were combined with non-blocks to form artificial chromosomes.Chromosomes were cut and recombined to increase chromosome quality.The binary race method was used to retain chromosomes with higher fitness.The algorithm was tested through the Reeves and Taillard instances,and the results were compared with other algorithms to verify effect- iveness of the algorithm. Keywords:production scheduling;combinatorial optimization;genetic algorithms;ant colony optimization;building block;artificial chromosome 收稿日期：2018-01-23.网络出版日期：2018-05-03，置换流水车间调度问题(permutation flow-shop 基金项目：国家创新方法工作专项项目(2017IM060200):天津市哲学社会科学规划项目(TYY17-013). scheduling problem,PFSP)是广泛受到研究的一种通信作者：张春花.E-mail:Zhang_chunhual203@126.com. 组合优化问题，属于NP-hard问题。PFSP的搜索

DOI: 10.11992/tis.201801041 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180503.1008.003.html 应用改进区块遗传算法求解置换流水车间调度问题裴小兵，张春花（天津理工大学管理学院，天津 300384）摘要：针对最小化最大完工时间的置换流水车间调度问题，提出一种将遗传算法与蚁群算法相结合的改进区块遗传算法。算法利用随机机制和改进反向学习机制相结合的方式产生初始解，以兼顾初始种群的多样性和质量。通过若干代简单遗传算法操作产生精英群体，借鉴蚁群算法中利用蚂蚁信息度浓度统计路径和节点信息的思想，对精英群体所携带信息进行统计分析并建立位置信息素矩阵和相依信息素矩阵，根据两矩阵挖掘区块并将区块与非区块组合形成染色体。将染色体进行切段与重组，以提高染色体的质量，使用二元竞赛法保留适应度较高的染色体。算法通过 Reeves 实例和 Taillard 实例进行测试，并将结果与其他算法进行比较，验证了该算法的有效性。关键词：生产调度；组合优化；遗传算法；蚁群优化算法；构建区块；人工染色体中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)03−0541−10 中文引用格式：裴小兵, 张春花. 应用改进区块遗传算法求解置换流水车间调度问题[J]. 智能系统学报, 2019, 14(3): 541–550. 英文引用格式：PEI Xiaobing, ZHANG Chunhua. An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J]. CAAI transactions on intelligent systems, 2019, 14(3): 541–550. An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems PEI Xiaobing，ZHANG Chunhua (School of Management, Tianjin University of Technology, Tianjin 300384, China) Abstract: Targeting the permutation flow-shop scheduling problem that minimizes maximum completion times, an improved block genetic algorithm combined with an ant colony algorithm is proposed. The algorithm uses a random mechanism and the improved opposition-based learning mechanism to generate the initial solution. It takes into account the diversity and quality of the initial population. Elite populations are generated through several generations of simple genetic algorithm operations. Based on the idea of using ant information density concentration’s statistical path and node information in the ant colony algorithm, the information carried by elite groups was counted. Position pheromone and dependent pheromone matrices were established. Mining blocks according to two matrices were developed and blocks were combined with non-blocks to form artificial chromosomes. Chromosomes were cut and recombined to increase chromosome quality. The binary race method was used to retain chromosomes with higher fitness. The algorithm was tested through the Reeves and Taillard instances, and the results were compared with other algorithms to verify effectiveness of the algorithm. Keywords: production scheduling; combinatorial optimization; genetic algorithms; ant colony optimization; building block; artificial chromosome 置换流水车间调度问题 (permutation flow-shop scheduling problem, PFSP) 是广泛受到研究的一种组合优化问题，属于 NP−hard 问题。PFSP 的搜索收稿日期：2018−01−23. 网络出版日期：2018−05−03. 基金项目：国家创新方法工作专项项目 (2017IM060200)；天津市哲学社会科学规划项目 (TJYY17-013). 通信作者：张春花. E-mail: Zhang_chunhua1203@126.com. 第 14 卷第 3 期智能系统学报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019

·542· 智能系统学报第14卷空间中存在诸多局部最优解，且问题复杂度越成人工染色体，然后将其注入到进化过程中。虽高，越容易局部最优化，因此许多学者针对PF- 然p-ACGA能够避免局部最优问题，一定程度上 SP特性不断对求解PFSP的算法进行优化。求解改善了解的质量，加快了进化速度，但是算法在 PFSP的算法可分为精确算法和近似算法，精确算初始化、信息素分布统计等方面还存在一些不足。法虽能求出最优解，但时间复杂性较高，随着问因此本文提出一种改进区块遗传算法(puzzle- 题的规模增大将变得不可行。近似算法对于较大 based improved artificial chromosome genetic al- 规模的问题能在可行时间内求出近优解，是研究 gorithm,p-IACGA)。该算法在种群初始化时引入 PFSP问题的重要方法。近似算法包括遗传算反向学习的思想，并对其进行了改进，将其与随法山、蚁群算法回、模拟退火算法等。机机制相结合产生初始解，大大提高了初始解的遗传算法(genetic algorithm,GA)通过选择、多样性和质量；为进一步描述信息素在路径上的交叉和变异等操作搜索解空间的最优解，已经成分布情况，算法考虑了信息素在节点上的分布情功应用于解决旅行商问题、车辆路径问题和车间况，即工件与所在解序列位置的关系，并将其与调度问题等不同领域的组合问题。但是遗传算法 p-ACGA中的统计分析工件与工件的相邻关系相的局部搜索能力较差，在实际应用中容易产生早结合，以全面地描述解的空间分布情况。然后，熟收敛的问题。怎么运用遗传算法既能保留优良根据这两种关系建立相依信息素矩阵和位置信息个体，又能维持群体的多样性，一直是遗传算法中较难解决的问题。近年来针对PFSP,不少学者素矩阵，进而挖掘区块以组合人工染色体。最为提高遗传算法的有效性，将遗传算法与其他算后，引入染色体重组机制，进一步提高解的质量。法相结合对该问题进行求解，取得了不错的效 1置换流水车间生产调度问题描述果。Benbouzid等针对PFSP提出VacGA(intro- duces vaccination into the field of GAs),将遗传算法 PFSP生产调度问题可以描述为：有n个作业和免疫算法相结合，遗传算法执行全局搜索，人以相同的顺序在m台机器上加工。同时，要满足工免疫系统执行局部搜索，以克服演化过程中遗的约束条件包括：1)操作是独立的，可以在零时传算法局部搜索能力不足的问题。Chen等将遗间开始；2)每台机器在同一时间最多加工一个工传算法与广义邻域搜索相结合，提出一种新型混件；3)每一个工件在同一时间只能在一台机器上合遗传算法求解PFSP。Bessedik等I提出一种基加工。用P(i,)表示工件i在机器j上的处理时于免疫的遗传算法，这种算法分为两种形式：1) 间，用（π1,2，…，πm)表示工件序列，用C(π，）表示将接种引入到基于免疫理论的遗传算法；2)从免完成时间的计算，即 C(π1,1)=P(π1,1) 疫网络理论得到启发，并将其运用到遗传算法 C(π，1)=C(π-1,1)P(π，1) 中。Ganguly等将贪婪局部搜索算子引入到遗 C(π，)=C(π1，j-1)+P(π1，j) 传算法，有效地解决大范围的排序和调度离散优 C(π，)=max{C(π-l,j),C(π，j-l)}+p(π，化问题。齐学梅等为求解PFSP问题，将变邻域式中：i=2,3,…,mj=2,3,…,mo 搜索算法与遗传算法相结合，加快了收敛速度。最大完工时间：Cmx(π)=C(π，m)o 吴秀丽等将变邻域搜索算法和遗传算法相结合适应度为：fx)=1/Cmx(π)。提出了一种变邻域改进遗传算法求解混合流水车求解置换流水车间调度问题的改 2 间调度问题，增强了遗传算法的局部搜索能力。进区块遗传算法 Chang等l针对置换流水车间调度问题，提出一种基于区块的遗传算法(puzzle-based artifi- p-IACGA主要分为5部分：产生初始解、挖 cial chromosome genetic algorithm,p-ACGA), 掘区块、构建人工染色体、染色体重组和保留优传算法和蚁群算法相结合，通过简单遗传算法的势解。p-IACGA流程如图1所示，因为染色体携交叉、突变等操作产生精英群体，针对这些精英带的较优信息是逐代积累的，所以为了挖掘出较群体，利用蚁群算法的信息素浓度对工件与工件优人工染色体，每执行（给定的一个数）代遗传的关系进行统计分析，进而建立信息素相依矩阵算法后挖掘一次区块，这样每一轮执行的总代数并根据矩阵挖掘区块，利用区块和非区块重组形是n+1

空间中存在诸多局部最优解，且问题复杂度越高，越容易局部最优化，因此许多学者针对 PFSP 特性不断对求解 PFSP 的算法进行优化。求解 PFSP 的算法可分为精确算法和近似算法，精确算法虽能求出最优解，但时间复杂性较高，随着问题的规模增大将变得不可行。近似算法对于较大规模的问题能在可行时间内求出近优解，是研究 PFSP 问题的重要方法。近似算法包括遗传算法 [1] 、蚁群算法[2] 、模拟退火算法[3]等。遗传算法 (genetic algorithm, GA) 通过选择、交叉和变异等操作搜索解空间的最优解，已经成功应用于解决旅行商问题、车辆路径问题和车间调度问题等不同领域的组合问题。但是遗传算法的局部搜索能力较差，在实际应用中容易产生早熟收敛的问题。怎么运用遗传算法既能保留优良个体，又能维持群体的多样性，一直是遗传算法中较难解决的问题。近年来针对 PFSP，不少学者为提高遗传算法的有效性，将遗传算法与其他算法相结合对该问题进行求解，取得了不错的效果。Benbouzid 等 [4]针对 PFSP 提出 VacGA(introduces vaccination into the field of GAs)，将遗传算法和免疫算法相结合，遗传算法执行全局搜索，人工免疫系统执行局部搜索，以克服演化过程中遗传算法局部搜索能力不足的问题。Chen 等 [5]将遗传算法与广义邻域搜索相结合，提出一种新型混合遗传算法求解 PFSP。Bessedik 等 [6]提出一种基于免疫的遗传算法，这种算法分为两种形式：1）将接种引入到基于免疫理论的遗传算法；2）从免疫网络理论得到启发，并将其运用到遗传算法中。Ganguly 等 [7]将贪婪局部搜索算子引入到遗传算法，有效地解决大范围的排序和调度离散优化问题。齐学梅等[8]为求解 PFSP 问题，将变邻域搜索算法与遗传算法相结合，加快了收敛速度。吴秀丽等[9]将变邻域搜索算法和遗传算法相结合提出了一种变邻域改进遗传算法求解混合流水车间调度问题，增强了遗传算法的局部搜索能力。 Chang 等 [10]针对置换流水车间调度问题，提出一种基于区块的遗传算法 (puzzle-based artificial chromosome genetic algorithm，p-ACGA)，将遗传算法和蚁群算法相结合，通过简单遗传算法的交叉、突变等操作产生精英群体，针对这些精英群体，利用蚁群算法的信息素浓度对工件与工件的关系进行统计分析，进而建立信息素相依矩阵并根据矩阵挖掘区块，利用区块和非区块重组形成人工染色体，然后将其注入到进化过程中。虽然 p-ACGA 能够避免局部最优问题，一定程度上改善了解的质量，加快了进化速度，但是算法在初始化、信息素分布统计等方面还存在一些不足。因此本文提出一种改进区块遗传算法 (puzzlebased improved artificial chromosome genetic algorithm，p-IACGA)。该算法在种群初始化时引入反向学习的思想，并对其进行了改进，将其与随机机制相结合产生初始解，大大提高了初始解的多样性和质量；为进一步描述信息素在路径上的分布情况，算法考虑了信息素在节点上的分布情况，即工件与所在解序列位置的关系，并将其与 p-ACGA 中的统计分析工件与工件的相邻关系相结合，以全面地描述解的空间分布情况。然后，根据这两种关系建立相依信息素矩阵和位置信息素矩阵，进而挖掘区块以组合人工染色体。最后，引入染色体重组机制，进一步提高解的质量。 1 置换流水车间生产调度问题描述 n m P(i, j) i j π1,π2,··· ,πn C(πi , j) PFSP 生产调度问题可以描述为：有个作业以相同的顺序在台机器上加工。同时，要满足的约束条件包括：1) 操作是独立的，可以在零时间开始；2) 每台机器在同一时间最多加工一个工件；3) 每一个工件在同一时间只能在一台机器上加工。用表示工件在机器上的处理时间，用 ( ) 表示工件序列，用表示完成时间的计算，即 C(π1 ,1) = P(π1 ,1) C(πi ,1) = C(πi−1 ,1)P(πi ,1) C(π1 , j) = C(π1 , j−1)+ P(π1 , j) C(πi , j) = max{C(πi−1, j),C(πi , j−1)}+ p(πi , j) 式中： i = 2,3,··· ,n; j = 2,3,··· ,m。 Cmax(π) = C(πi 最大完工时间： ,m)。适应度为： f(x) = 1/Cmax(π)。 2 求解置换流水车间调度问题的改进区块遗传算法 n n+1 p-IACGA 主要分为 5 部分：产生初始解、挖掘区块、构建人工染色体、染色体重组和保留优势解。p-IACGA 流程如图 1 所示，因为染色体携带的较优信息是逐代积累的，所以为了挖掘出较优人工染色体，每执行 (给定的一个数) 代遗传算法后挖掘一次区块，这样每一轮执行的总代数是。 ·542· 智能系统学报第 14 卷

第3期裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·543· 开始解并对每条初始解求出它的反向解；然后，将两初始化种群混合在一起形成规模为2N的种群，计算每个解的适应度，并按照适应度大小对解降序排 N 张到挖掘人了 Y 列；最后，选择前N条适应度较大的解作为进化染色体的条件的初始种群。交叉更新信息素矩阵初始解反向解种群大小为N 种群大小为W 突变构建区块 2 2 更新基因库产生子代 3 构建人工染色体混合 N 混合解混合种群种群大小为2W Y 注人人工染色体重组染色体 AA 留存优势解 ny 终止条件 N 』口选择 Y 优秀解种群大小为W 结束 1☐2☐3到图1P-IACGA流程 4□AA□n Fig.1 Flow chart of p-IACGA 2.1改进反向学习法初始化种群图2改进反向学习法 1)反向学习法 Fig.2 Improved opposition-based learning 反向学习法(opposition-.based learning,OBL) 2.2 挖掘区块的主要思想是同时考虑原始解序列和它的反向解在遗传算法中，进化若干代后，大部分染色体序列，以获得当前候选解中的最优解。假设X= 都会携带与较优解相似的一些信息，这些信息具 (x,x2,…,xn)是n维空间中的一个解，其中xeR和有相似性并且这些相似性在大规模的种群中具有 x∈l,小，、4是搜索空间的上、下界。ie{1,2,…,, 一定的可靠性2。在p-ACGA中，使用蚁群优化那么它的反向解是X”=(x,,…,x),其中x=1,+4, 算法(ant colony optimization,ACO)中的蚂蚁信息 OBL优化过程为：素浓度来识别染色体中较好的相似序列并通过区 ①在n维搜索空间中生成初始解X=(x,2,…, 块的方式将它们挖掘出来。 x)和反向解X=(K…,x): 1)建立信息素矩阵 ②求出初始解的适应度fx)和其反向解的适本研究使用相依信息素矩阵和位置信息素矩应度fx),评估两个解的适应度；阵来记录蚂蚁经过的路径信息，其中位置信息素 ③如果fx)≥fx),用x替换x:否则，继续使矩阵记录每个节点（工件在解序列中的位置）的用x。信息素浓度信息，相依信息素矩阵记录两节点间的路径（两工件间的相邻关系）的信息素浓度信通过同时评估这两个解可以获得更好的结果。息。矩阵建立过程如下： 2)应用改进反向学习法进行种群初始化 ①对信息素矩阵进行初始化初始化过程采用随机机制和改进反向学习机从第n代中选择一条最优染色体进行矩阵初制相结合的方式，以兼顾初始解的多样性和质始化。图3为初始相依信息素矩阵生成过程，两量。本研究对反向学习法作了改进以减少优秀解个工件间的初始信息素表示为t(见式(I)。同样的丢失，基本思路就是将所有原始解和所有反向的方法生成初始位置信息素矩阵如图4。解混合在一起形成混合群体，然后从混合群体中 1 选出适应度较高的解，如图2所示。首先利用随 t0二i (1) 机方式产生N(N为给定的初始种群规模)条初始式中L表示完工时间

开始初始化注入人工染色体终止条件达到挖掘人工染色体的条件结束 N Y N Y N 混合种群 Y 更新信息素矩阵构建区块更新基因库构建人工染色体交叉突变产生子代留存优势解重组染色体图 1 p-IACGA 流程 Fig. 1 Flow chart of p-IACGA 2.1 改进反向学习法初始化种群 1) 反向学习法 (x1, x2,··· , xn) n xi ∈R xi ∈[li ,ui] li ui ∀i ∈ {1,2,··· ,n} X ′ = (x ′ 1 , x ′ 2 ,··· , x ′ n ) x ′ i = li +ui− xi 反向学习法 (opposition-based learning，OBL)[11] 的主要思想是同时考虑原始解序列和它的反向解序列，以获得当前候选解中的最优解。假设 X = 是维空间中的一个解，其中和，、是搜索空间的上、下界。，那么它的反向解是，其中。OBL 优化过程为： n X = (x1, x2,··· , xn) X ′ = (x ′ 1 , x ′ 2 ,··· , x ′ n ) ①在维搜索空间中生成初始解和反向解； f(x) f(x ′ ) ②求出初始解的适应度和其反向解的适应度，评估两个解的适应度； f(x ′ ) ⩾ f(x) x ′ x x ③如果，用替换；否则，继续使用。通过同时评估这两个解可以获得更好的结果。 2) 应用改进反向学习法进行种群初始化 N N 初始化过程采用随机机制和改进反向学习机制相结合的方式，以兼顾初始解的多样性和质量。本研究对反向学习法作了改进以减少优秀解的丢失，基本思路就是将所有原始解和所有反向解混合在一起形成混合群体，然后从混合群体中选出适应度较高的解，如图 2 所示。首先利用随机方式产生 ( 为给定的初始种群规模) 条初始 N N 解并对每条初始解求出它的反向解；然后，将两种群混合在一起形成规模为 2 的种群，计算每个解的适应度，并按照适应度大小对解降序排列；最后，选择前条适应度较大的解作为进化的初始种群。 1 3 2 4 n ĂĂ 1′ 3′ 2′ 4′ ĂĂ nÿ 1 2 3 4 ĂĂ n 1′ 2′ 3′ 4′ ĂĂ nÿ 1 2′ 3′ 4′ ĂĂ n 初始解种群大小为N 反向解种群大小为N 混合解种群大小为2N 优秀解种群大小为N 混合选择图 2 改进反向学习法 Fig. 2 Improved opposition-based learning 2.2 挖掘区块在遗传算法中，进化若干代后，大部分染色体都会携带与较优解相似的一些信息，这些信息具有相似性并且这些相似性在大规模的种群中具有一定的可靠性[12]。在 p-IACGA 中，使用蚁群优化算法 (ant colony optimization，ACO) 中的蚂蚁信息素浓度来识别染色体中较好的相似序列并通过区块的方式将它们挖掘出来。 1) 建立信息素矩阵本研究使用相依信息素矩阵和位置信息素矩阵来记录蚂蚁经过的路径信息，其中位置信息素矩阵记录每个节点 (工件在解序列中的位置) 的信息素浓度信息，相依信息素矩阵记录两节点间的路径 (两工件间的相邻关系) 的信息素浓度信息。矩阵建立过程如下： ①对信息素矩阵进行初始化 n τ0 从第代中选择一条最优染色体进行矩阵初始化。图 3 为初始相依信息素矩阵生成过程，两个工件间的初始信息素表示为 (见式 (1))。同样的方法生成初始位置信息素矩阵如图 4。 τ0 = 1 L (1) 式中 L 表示完工时间。第 3 期裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·543·

·544· 智能系统学报第14卷初始4 初始信息素相依矩阵 2)构建区块 4624市选择形成 1 矩阵 To To.. 区块是简短的染色体片段，本研究通过学习 4最优 ☐2455 to-to to To To 链接关系构建区块。首先确定区块的最小长 4.024E56 度，然后随机选择起始位置，最后为各位置选择 Jto ToTo 工序。在区块最小长度内，起始位置采用位置信图3初始相依信息素矩阵息素矩阵中的信息选择工序，如图7，假设P> Fig.3 Initially dependent pheromone matrix P>…>P,选择工件放入起始位置S1。其他初始4 初始信息素相依矩阵位置采用位置信息素矩阵和相依信息素矩阵的合 4624阝选择形成S 并信息，以轮盘赌选择法(roulette wheel section, 4246d53: 最优矩阵国 6666 25西一6-6 RWS)对工序进行筛选，已经人选的工件不再进 4.24356: …… 行筛选，如图8，假设CP2最大，选择工件2放入 6.06 位置S2 图4初始位置信息素矩阵起始位置 Fig.4 The initial position pheromone matrix t f1 ②更新信息素矩阵由遗传算法产生的最新一代的前30%适应 To Ta 度较高的染色体更新信息素矩阵，更新过程如图5，更新公式如式(2)：图7起始位置工序挑选 Fig.7 Starting position process selection Tij(t+1)=(1-p)xTi(t)+pATg(t+1) △rt+1)= ∫1/L,若蚂蚁经过路径(i,) (2) 位置信息素矩阵相依信息素矩阵 0,其他 S S2 S3--Sm JJ2J…J 式中：表示每对相邻工件（伍，）间的信息素浓 fn-- tn …t 度；Tt+l)表示更新的t;p表示信息素的蒸发 t t到速率。初始4 前30%条染色体新相依信息素矩阵 4,回6245D降序4,45362 CP=W(tnltz+tx+...+t))+W"(ta/(ta+ta+..+t)) 兴9 CP=W(il+is+...+i))+W(tl(+i+...+)) 4,②46卫53 CP=W(ta/(a+t+..+r2)+W(《2+i+..tt)》 4.24356 4243▣ JTa Ta Ta..Ty 假设CP>CP>A>Cp, 选择J 图5更新相依信息素矩阵 Fig.5 Update dependent pheromone matrix 图8区块最小长度内其他位置工件选择同理，得到更新的位置信息素矩阵如图6。 Fig.8 Workpiece selection at other positions within the 更新公式如式(3)： block's minimum length T(t+1)=(1-p)xT()+pAT(+1) 当出现两个或多个较大值时随机选择。位置信 ∫1/L,若蚂蚁经过的第m个节点为节点i △rt+1)=0,其他息素浓度概率计算公式为 (3) m=1,2,…,n ∑tm (4) 式中：t为蚂蚁经过的第m个节点为节点i时在 ieun 节点i处释放的信息素。相依信息素浓度概率计算公式为 T Pu-T i,j=1,2,…,n (5) S S S 合并概率计算公式 T. CP,=(W×P)+(W'×Pm,ijm=1,2,…n(6) 式中：i表示工件号；j表示i所连接的上一个工 T 件号；m表示染色体上的工件的位置；n表示染色图6更新的位置信息素矩阵体长度；Pm表示工件i与位置m在位置矩阵的概 Fig.6 Updated positional information matrix 率；P表示相依矩阵中工件j相连于工件i之后

1 6 2 4 5 3 2 4 6 1 5 3 1 2 4 3 5 6 选择最优初始 μ μ最优 1 2 4 3 5 6 形成矩阵初始信息素相依矩阵 … J1 J2 J3 … Jj J1 - … J2 - … J3 - … … … … … … Ji … - μ1 μ2 μn τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 … 图 3 初始相依信息素矩阵 Fig. 3 Initially dependent pheromone matrix 1 6 2 4 5 3 2 4 6 1 5 3 1 2 4 3 5 6 选择最优初始 μ μ最优 1 2 4 3 5 6 形成矩阵初始信息素相依矩阵 … S1 S2 S3 Sj J1 J2 J3 Ji μ1 μ2 μn τ ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ τ 0 ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ τ 0 ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 … … … … … … … … … … 图 4 初始位置信息素矩阵 Fig. 4 The initial position pheromone matrix ②更新信息素矩阵由遗传算法产生的最新一代的前 30% 适应度较高的染色体更新信息素矩阵，更新过程如图 5，更新公式如式 (2)： τi j(t+1) = (1−ρ)×τi j(t)+ρ∆τi j(t+1) ∆τi j(t+1) = { 1/L, 若蚂蚁经过路径(i, j) 0, 其他 (2) τi j i, j τi j(t+1) τi j ρ 式中：表示每对相邻工件 ( ) 间的信息素浓度；表示更新的；表示信息素的蒸发速率[12]。 12 τ 新相依信息素矩阵 J1 J2 J3 … Jj J1 - … J2 - … J3 - … … … … … - … Ji … 4 5 3 1 6 2 2 4 6 1 5 3 6 2 4 5 3 1 降序排列更新前 30% 条染色体 1 6 2 4 5 3 2 4 6 1 5 3 1 2 4 3 5 6 初始 μ … … μ1 μ2 μn μ1 μ2 μj τi1 τ31 τ32 τ23 τ13 τ12 τ21 τ3j τ2j τ1j τi2 τi3 τij 图 5 更新相依信息素矩阵 Fig. 5 Update dependent pheromone matrix 同理，得到更新的位置信息素矩阵如图 6。更新公式如式 (3)： τ ′ mi(t+1) = (1−ρ)×τ ′ mi(t)+ρ∆τ ′ mi(t+1) ∆τ ′ mi(t+1) = { 1/L, 若蚂蚁经过的第m个节点为节点i 0, 其他 (3) τ ′ mi m i i 式中：为蚂蚁经过的第个节点为节点时在节点处释放的信息素。 S1 S2 S3 … Sm J1 … J2 … J3 … … … … … … … Ji … τ ′ 11 τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 22 τ ′ 23 τ ′ 31 τ ′ 32 τ ′ 33 τ ′ i1 τ ′ i2 τ ′ i3 τ ′ im τ ′ 3m τ ′ 2m τ ′ 1m 图 6 更新的位置信息素矩阵 Fig. 6 Updated positional information matrix 2) 构建区块 P ′ 11 > P ′ 21 > ··· > P ′ i1 J1 S 1 CP2 J2 S 2 区块是简短的染色体片段，本研究通过学习链接关系[13]构建区块。首先确定区块的最小长度，然后随机选择起始位置，最后为各位置选择工序。在区块最小长度内，起始位置采用位置信息素矩阵中的信息选择工序，如图 7，假设，选择工件放入起始位置。其他位置采用位置信息素矩阵和相依信息素矩阵的合并信息，以轮盘赌选择法 (roulette wheel section， RWS)[13]对工序进行筛选，已经入选的工件不再进行筛选，如图 8，假设最大，选择工件放入位置。 S1 S2 S3 … Sm J1 P ' 11 P ' 12 P ' 13 … P ' 1m J2 P ' 21 P ' 22 P ' 23 … P ' 2m J3 P ' 31 P ' 32 P ' 33 … P ' 3m … … … … … … Ji P ' i1 P ' i2 P ' i3 … P ' im J1 S1 S2 S1 S2 S3 … Sm 起始位置 J1 … J2 … J3 … … … … … … … Ji … τ ′ 11 τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 22 τ ′ 23 τ ′ 31 τ ′ 32 τ ′ 33 τ ′ i1 τ ′ i2 τ ′ i3 τ ′ im τ ′ 3m τ ′ 2m τ ′ 1m 图 7 起始位置工序挑选 Fig. 7 Starting position process selection 位置信息素矩阵 … … … … … … … … … … … J1 J2 J3 … Jj - … - … - … … … … … … … … - CP2=W'* (τ ′ 22/(τ ′ 22+τ ′ 32+…+τ ′ i2 ))+W* (τ ′ 21/(τ ′ 21+τ ′ 31+…+τ ′ i1 )) CP3=W'* (τ ′ 32/(τ ′ 22+τ ′ 32+…+τ ′ i2 ))+W* (τ ′ 31/(τ ′ 21+τ ′ 31+…+τ ′ i1 )) CPi=W'* (τ ′ i2 /(τ ′ 22+τ ′ 32+…+τ ′ i2 ))+W* (τ ′ i1 /(τ ′ 21+τ ′ 31+…+τ ′ i1 )) … J1 J2 S1 S2 相依信息素矩阵假设 CP2>CP3>Ă>Cpi 选择J2 S1 S2 S3 Sm J1 J2 J3 Ji τ ′ 11 τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 22 τ ′ 23 τ ′ 31 τ ′ 32 τ ′ 33 τ ′ i1 τ ′ i2 τ ′ i3 J1 J2 J3 Ji τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 1j τ ′ 2j τ ′ 3j τ ′ 23 τ ′ 31 τ ′ 32 τ ′ i1 τ ′ i2 τ ′ i3 τ ′ im τ ′ 3m τ ′ 2m τ ′ 1m 图 8 区块最小长度内其他位置工件选择 Fig. 8 Workpiece selection at other positions within the block's minimum length 当出现两个或多个较大值时随机选择。位置信息素浓度概率计算公式为 P ′ im = τ ′ mi ∑ i∈uns τ ′ mi i, m = 1,2,··· ,n (4) 相依信息素浓度概率计算公式为 Pi j = τi j ∑ i∈uns τi j , i, j = 1,2,··· ,n (5) 合并概率计算公式 CPi = (W × Pi j)+(W′ × P ′ im), i, j,m = 1,2,··· ,n (6) i j i m n P ′ im i m Pi j j i 式中：表示工件号；表示所连接的上一个工件号；表示染色体上的工件的位置；表示染色体长度；表示工件与位置在位置矩阵的概率；表示相依矩阵中工件相连于工件之后 ·544· 智能系统学报第 14 卷

第3期裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·545· 的概率；CP:表示工件i的合并概率；W与W分别表示区块的长度；P"表示第i条区块的第I个工表示位置矩阵与相依矩阵的权重值，权重值会随件的位置概率；CP表示第i个区块的第1个工件着进化代数的增加不断改变。的合并概率。对最小长度外的位置进行工序选择时设立合位置信息素矩阵相依信息素矩阵并概率最小阈值，作为筛选条件。当工件的合并概率大于最小阈值时，选择该工件，否则停止 ---r 选择工件，本区块完成挖掘，如图9所示。因为当区块包含的工件越多总体概率越低，组合错误的概率越大，区块阈值将会保证区块的质量，同时也将会导致挖掘出的区块长度也有所不同。挖掘的区块均存放在区块资料库中。 CP=W(t/(+…+2)tW(ax+…+r》 CP=Wr2++atW(t+…ta》 3)区块竞争区块竞争就是去除有重复信息的区块。将 CP=W(t/t+…+ra)tW(t(+…tt)》假设CP,>CP>.…>CP选择区块资料库中的区块的工序与位置进行比对，如 J.计算全局合并概率CP 果区块之间出现重复的工序或涵盖的位置重复， CP=W(t/《ti:+i+…+a)tW(t(rtr4t…+r)》则通过比较平均概率的方式进行选择，平均概率若CP大于國值，则选择人.否则结束本区块较大者保留至区块资料库，较小者则删除，举例 S:S:S; 如图10。平均概率的计算公式为 P+CPa 图9区块最小长度外的工件选择 i=2 1=1,2,…,n (7) Fig.9 Selection of workpieces outside the block minimum n 式中：i表示区块号；1表示区块的第1个位置；n length 区块资料库新建区块资料库位置1位置2位置3 位置5位置6位置7 位蜜1位置2位置3 选择 PG=0.66 PcG-0.55 P6=0.66 位置7位置8位置9 位置10位置11位置12 位置5位置6位置7 g P%=0.45 P%=0.42 J P=-0.55 图10区块竞争 Fig.10 Block competition 2.3组合染色体位置顺序（由左到右），利用RWS方法根据合并概本研究利用新建区块资料库中的区块和非区率从剩余的工件中选择合适工件放入其中。例如块资料库中的工件组合出较优染色体。先将区块图11区块资料库中有2个区块，非区块资料库有资料库中的所有区块复制到确定长度的空白染色 2个工件，合并概率CP6大于CP,选择J6放至位体对应位置，对于尚未放入工序的空位置依照其置5，剩下5放至位置9。区块资料库位置1位置2位置3位置4位置5位置6位置7位置8位置9 位置1位置2位置3位置4 位置6位置7位置8 C J: B2 通过RWS选择J6 非区块资料科库 L选择J 图11染色体组合 Fig.11 Chromosome combinations

CPi 的概率；表示工件 i 的合并概率； W′ 与 W 分别表示位置矩阵与相依矩阵的权重值，权重值会随着进化代数的增加不断改变[14]。对最小长度外的位置进行工序选择时设立合并概率最小阈值[15] ，作为筛选条件。当工件的合并概率大于最小阈值时，选择该工件，否则停止选择工件，本区块完成挖掘，如图 9 所示。因为当区块包含的工件越多总体概率越低，组合错误的概率越大，区块阈值将会保证区块的质量，同时也将会导致挖掘出的区块长度也有所不同。挖掘的区块均存放在区块资料库中。 3) 区块竞争区块竞争[16]就是去除有重复信息的区块。将区块资料库中的区块的工序与位置进行比对，如果区块之间出现重复的工序或涵盖的位置重复，则通过比较平均概率的方式进行选择，平均概率较大者保留至区块资料库，较小者则删除，举例如图 10。平均概率的计算公式为 P AVG Bl = P dom B i l + ∑n i=2 CPB i l n , l = 1,2,··· ,n (7) 式中： i 表示区块号； l 表示区块的第 l 个位置；n P dow B i 1 i l CPB i l i l 表示区块的长度；表示第条区块的第个工件的位置概率；表示第个区块的第个工件的合并概率。 2.3 组合染色体本研究利用新建区块资料库中的区块和非区块资料库中的工件组合出较优染色体。先将区块资料库中的所有区块复制到确定长度的空白染色体对应位置，对于尚未放入工序的空位置依照其 CP6 CP5 J6 J5 位置顺序 (由左到右)，利用 RWS 方法根据合并概率从剩余的工件中选择合适工件放入其中。例如图 11 区块资料库中有 2 个区块，非区块资料库有 2 个工件，合并概率大于，选择放至位置 5，剩下放至位置 9。位置信息素矩阵 … … … … … … … … … … … J1 J2 J3 … Jj - … - … - … … … … … … … … - CP2=W'* (τ ′ 32/(τ ′ 32+…+τ ′ i2 ))+W* (τ31/(τ31+…+τi1 )) CP3=W'* (τ ′ 42/(τ ′ 32+…+τ ′ i2 ))+W* (τ41/(τ31+…+τi1 )) CPi=W'* (τ ′ i2 /(τ ′ 32+…+τ ′ i2 ))+W* (τi1 /(τ31+…+τi1 )) CPT=W'* (τ ′ 33/(τ ′ 13+τ ′ 23+…+τ ′ i3 ))+W* (τ32/(τ32+τ42+…+τi1 )) … J1 J2 J3 S1 S2 S3 相依信息素矩阵假设 CP3>CP4>…>CPi选择 J3，计算全局合并概率CPT 若 CPT 大于阈值，则选择 J3，否则结束本区块 S1 S2 S3 Sm J1 J2 J3 Ji τ ′ 11 τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 22 τ ′ 23 τ ′ 31 τ ′ 32 τ ′ 33 τ ′ i1 τ ′ i2 τ ′ i3 J1 J2 J3 Ji τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 1j τ ′ 2j τ ′ 3j τ ′ 23 τ ′ 31 τ ′ 32 τ ′ i1 τ ′ i2 τ ′ i3 τ ′ im τ ′ 3m τ ′ 2m τ ′ 1m 图 9 区块最小长度外的工件选择 Fig. 9 Selection of workpieces outside the block minimum length J1 J2 J3 位置1 位置2 位置3 J13 J9 J7 位置7 位置8 位置9 J8 J12 J11 位置5 位置6 位置7 J1 J5 J6 位置10 位置11 位置12 P AVG=0.45 B1 B2 P AVG=0.66 PB3 AVG B =0.55 1 B 2 B 3 B 4 PB4 AVG=0.42 区块资料库新建区块资料库选择 P AVG=0.55 B1 B3 P AVG=0.66 J1 J2 J3 位置1 位置2 位置3 J8 J12 J11 位置5 位置6 位置7 B 3 B 1 图 10 区块竞争 Fig. 10 Block competition Ci 位置5 Ci 通过 RWS 选择 J6 选择 J5 Ci J1 J2 J3 J4 J8 J7 J9 Ci B1 B2 区块资料库位置1位置2位置3位置4 位置6位置7 位置8 J1 J2 J3 J4 J8 J7 J9 J1 J2 J3 J4 J6 J8 J7 J9 J1 J2 J3 J4 J6 J8 J7 J9 J5 非区块资料库 J5 J6 位置1位置2位置3位置4 位置6位置7位置8位置9 图 11 染色体组合 Fig. 11 Chromosome combinations 第 3 期裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·545·

第3期裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·547· 3 实验结果分析选择了最佳的、相同的参数配置以保证了算法的可比性。为了评估所提出的算法的性能，本研究将通以SGA、ACGA、P-ACGA、BBEDA、LMB- 过对不同实例进行测试，使用误差率(ER)作为对 BEA和p-IACGA计算Taillard实例，结果如表1 比指标，与其他算法进行比较。误差率是指测试所示。从表1可以看出，ta005、ta010、ta020、ta030 中算法所得最优解与实例已知最优解的差值占实 ta070和ta080这6个实例中的ER值均为0，即找例已知最优解的比例，ER计算公式为到了6个与实例已知解相同的解，多于其他算法 R=C-Lx100% (8) 所能找到的个数。尽管在ta050实例中，BBEDA U 和LMBBEA的ER值为O.85,p-IACGA的ER值式中：U,是实例的已知最优解；Cmx是测试算法的为0.97，前两者的结果优于p-IACGA,但是p-IACGA 最优解。的平均值ER为0.32%，均低于其他算法，表明p 本文所提算法由C++语言编写，程序的运行 IACGA的整体求解问题的性能优于其他算法。同环境为：处理器Intel(R)Core(TM)i5-4005UCPU@ 理，用这些算法计算Reeves实例，结果如表2。通 3.40GHz,内存为4.0GB的计算机。在本文中，过对Reeves的21个实例测试，发现p-IACGA在选择了29个调度问题进行比较，其中21个 Rec01、Rec03、Rec09、Recl1和Rec35实例中ER的 Reeves实例和8个Taillard实例，每个实例独立运值为0，找到了5个与实例已知解相同的解，多于其行30次，并求出ER的平均值。为了达到性能评他算法，且p-IACGA的平均误差率为0.46，均小于价的目的，在SGAI、ACGAU91、P-ACGA1OI 其他算法，充分表明p-IACGA求解PFSP的优良 BBEDAUS)、LMBBEA2OI、p-IACGA的参数设置上性能。表1 Taillard实例测试结果比较 Table 1 Comparison of Taillard instance test results BBEDA LMBBEA SGA ACGA p-ACGA p-IACGA 算例问题规模 U Cma/s ER Cmad/s ER Cmax/s ER Cma/s ER Cads ER Cmax/s ER ta005 20×51235 12350.001235.000.00 2630.551.131840.150.49 1235.000.001235.000.00 ta010 20×5110811080.001108.000.00 2925.121.641894.680.711163.400.05 1108.000.00 ta020 20×10159119890.251591.000.00 5727.602.60 4597.991.891781.920.121591.000.00 ta030 20×20217822870.052286.900.05 8951.583.115466.781.512221.560.02 2178.000.00 ta050 50×10306556700.855670.250.85 19156.255.2515416.954.036773.651.21 4444.250.45 ta060 50×203696177043.7917703.843.7934298.888.2828274.406.6516114.563.3611568.482.13 ta070 100×5532253220.005322.000.00 7823.340.477078.260.33 5428.440.02 5322.000.00 ta080 100×105845 58450.00 5845.000.00 13501.951.3111748.451.01 6604.850.13 5845.000.00 平均值 0.62 0.59 2.97 2.08 0.61 0.32 表2 Reeves实例测试结果比较 Table 2 Comparison of Reeves instance test results BBEDA LMBBEA SGA ACGA p-ACGA p-IACGA 算例问题规模 Cmay/s ER Cmav/s ER Cma/s ER Cmay/s ER Cma/s ER Cma/s ER Rec01 20×5 124712590.011284.410.039926.126.961446.520.161384.170.111247.000.00 Rec03 20×5 110912420.121131.180.02 6044.054.451208.810.091186.630.071109.000.00 Rec05 20×5 124216890.361502.820.21 5986.443.82 1540.080.241589.760.28 1242.000.00 Rec07 20×10 156615660.001566.000.009881.465.31 2364.660.512286.360.461566.000.00 Rec09 20×101371710.25137.000.00 785.014.73 289.071.11146.590.07 137.000.00 Rec11 20×10143114310.001431.000.0012778.837.931631.340.141545.480.081431.000.00 Rec13 20×15 193025860.342277.400.1813452.105.973531.900.832644.100.372219.500.15 Rec15 20×15195022040.132008.500.0310315.504.293354.000.722983.500.531989.000.02 Rec1720×15190223580.241921.020.0113466.166.084907.161.583899.101.052415.540.27

3 实验结果分析为了评估所提出的算法的性能，本研究将通过对不同实例进行测试，使用误差率 (ER) 作为对比指标，与其他算法进行比较。误差率是指测试中算法所得最优解与实例已知最优解的差值占实例已知最优解的比例，ER 计算公式为 ERi = Cmax −Ui Ui ×100% (8) 式中： Ui 是实例的已知最优解； Cmax 是测试算法的最优解。本文所提算法由 C++语言编写，程序的运行环境为：处理器 Intel(R) Core(TM) i5-4005U CPU @ 3.40 GHz，内存为 4.0 GB 的计算机。在本文中，选择了 2 9 个调度问题进行比较，其中 2 1 个 Reeves 实例和 8 个 Taillard 实例，每个实例独立运行 30 次，并求出 ER 的平均值。为了达到性能评价的目的，在 SGA[ 1 8 ] 、ACGA[ 1 9 ] 、p-ACGA[ 1 0 ] 、 BBEDA[18] 、LMBBEA[20] 、p-IACGA 的参数设置上选择了最佳的、相同的参数配置以保证了算法的可比性。 Rec Rec Rec Rec Rec 以 SGA、ACGA、p-ACGA、BBEDA、LMBBEA 和 p-IACGA 计算 Taillard 实例，结果如表 1 所示。从表 1 可以看出，ta005、ta010、ta020、ta030、 ta070 和 ta080 这 6 个实例中的 ER 值均为 0，即找到了 6 个与实例已知解相同的解，多于其他算法所能找到的个数。尽管在 ta050 实例中，BBEDA 和 LMBBEA 的 ER 值为 0.85，p-IACGA 的 ER 值为 0.97，前两者的结果优于 p-IACGA，但是 p-IACGA 的平均值 ER 为 0.32%，均低于其他算法，表明 pIACGA 的整体求解问题的性能优于其他算法。同理，用这些算法计算 Reeves 实例，结果如表 2。通过对 Reeves 的 21 个实例测试，发现 p-IACGA 在 01、 03、 09、 11 和 35 实例中 ER 的值为 0，找到了 5 个与实例已知解相同的解，多于其他算法，且 p-IACGA 的平均误差率为 0.46，均小于其他算法，充分表明 p-IACGA 求解 PFSP 的优良性能。表 1 Taillard 实例测试结果比较 Table 1 Comparison of Taillard instance test results 算例问题规模 Ui BBEDA LMBBEA SGA ACGA p-ACGA p-IACGA Cmax/s ER Cmax/s ER Cmax/s ER Cmax/s ER Cmax/s ER Cmax/s ER ta005 20×5 1 235 1 235 0.00 1 235.00 0.00 2 630.55 1.13 1 840.15 0.49 1 235.00 0.00 1 235.00 0.00 ta010 20×5 1 108 1 108 0.00 1 108.00 0.00 2 925.12 1.64 1 894.68 0.71 1 163.40 0.05 1 108.00 0.00 ta020 20×10 1 591 1 989 0.25 1 591.00 0.00 5 727.60 2.60 4 597.99 1.89 1 781.92 0.12 1 591.00 0.00 ta030 20×20 2 178 2 287 0.05 2 286.90 0.05 8 951.58 3.11 5 466.78 1.51 2 221.56 0.02 2 178.00 0.00 ta050 50×10 3 065 5 670 0.85 5 670.25 0.85 19 156.25 5.25 15 416.95 4.03 6 773.65 1.21 4 444.25 0.45 ta060 50×20 3 696 17 704 3.79 17 703.84 3.79 34 298.88 8.28 28 274.40 6.65 16 114.56 3.36 11 568.48 2.13 ta070 100×5 5 322 5 322 0.00 5 322.00 0.00 7 823.34 0.47 7 078.26 0.33 5 428.44 0.02 5 322.00 0.00 ta080 100×10 5 845 5 845 0.00 5 845.00 0.00 13 501.95 1.31 11 748.45 1.01 6 604.85 0.13 5 845.00 0.00 平均值 0.62 0.59 2.97 2.08 0.61 0.32 表 2 Reeves 实例测试结果比较 Table 2 Comparison of Reeves instance test results 算例问题规模 Ui BBEDA LMBBEA SGA ACGA p-ACGA p-IACGA Cmax/s ER Cmax/s ER Cmax/s ER Cmax/s ER Cmax/s ER Cmax/s ER Rec01 20×5 1 247 1 259 0.01 1 284.41 0.03 9 926.12 6.96 1 446.52 0.16 1 384.17 0.11 1 247.00 0.00 Rec03 20×5 1 109 1 242 0.12 1 131.18 0.02 6 044.05 4.45 1 208.81 0.09 1 186.63 0.07 1 109.00 0.00 Rec05 20×5 1 242 1 689 0.36 1 502.82 0.21 5 986.44 3.82 1 540.08 0.24 1 589.76 0.28 1 242.00 0.00 Rec07 20×10 1 566 1 566 0.00 1 566.00 0.00 9 881.46 5.31 2 364.66 0.51 2 286.36 0.46 1 566.00 0.00 Rec09 20×10 137 171 0.25 137.00 0.00 785.01 4.73 289.07 1.11 146.59 0.07 137.00 0.00 Rec11 20×10 1 431 1 431 0.00 1 431.00 0.00 12 778.83 7.93 1 631.34 0.14 1 545.48 0.08 1 431.00 0.00 Rec13 20×15 1 930 2 586 0.34 2 277.40 0.18 13 452.10 5.97 3 531.90 0.83 2 644.10 0.37 2 219.50 0.15 Rec15 20×15 1 950 2 204 0.13 2 008.50 0.03 10 315.50 4.29 3 354.00 0.72 2 983.50 0.53 1 989.00 0.02 Rec17 20×15 1 902 2 358 0.24 1 921.02 0.01 13 466.16 6.08 4 907.16 1.58 3 899.10 1.05 2 415.54 0.27 第 3 期裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·547·

·548· 智能系统学报第14卷续表2 BBEDA LMBBEA SGA ACGA P-ACGA P-IACGA 算例问题规模 U Cma/s ER Cmad/s ER Cmax/s ER Cmad/s ER Cmax/s ER Cmay/s ER Rec1930×10209337460.793202.290.5314797.516.075211.571.494018.560.922741.830.31 Rec21 30×10201749421.45 4659.271.3114260.196.07 5324.881.64 5022.331.49 3388.560.68 Rec2330x10 201131570.572936.060.4617013.067.46 5610.691.79 4122.551.05 2493.640.24 Rec2530×15251353281.124498.270.7920606.607.20 7815.432.116584.061.62 3342.290.33 Rec2730×15237343660.843701.880.5618628.056.855885.041.485362.981.26 3488.310.47 Rec2930×15228742540.863499.110.5321680.768.487181.182.144985.661.18 3201.800.40 Rec3150×10304556330.854841.550.5927465.908.0212149.552.997886.551.59 4019.400.32 Rec3350×10311438930.254079.340.3119057.685.126010.020.935169.240.66 3456.540.11 Rec3550×10327732770.003277.000.0014091.103.303473.620.063309.770.01 3277.000.00 Rec3775×204951242603.9020645.673.1754807.5710.0730349.635.1321437.833.3315447.122.12 Rec39 75×205087194322.8215159.261.9848377.378.5124214.123.7617295.802.4014396.211.83 Rec4175×2096047143.913955.203.1210588.8010.03 5932.805.184233.603.413369.602.51 平均值 0.90 0.66 6.51 1.62 1.04 0.46 为了更直观地比较算法性能，图15给出了关式生成矩阵，提高了区块质量。在进化的后期于p-ACGA和p-IACGA两个算法测试部分Tail- 应用二元竞赛法来寻找具有更优适应值的解，加 lard实例的收敛图。从图l5中可以看出，在相同快了进化速度。的最大迭代次数下，p-IACGA的收敛速度比通过实验数据分析，对于求解PFSP,本文提 p-ACGA更快。在进化初期，算法通过优化初始出的p-IACGA相较于SGA、ACGA、P-ACGA、方法提高初始解的质量，保证进化过程中解的质 BBEDA、LMBBEA和p-IACGA具有较优的求解量；采用节点信息浓度和路径信息度相结合的方性能。 2.1r×10 6.5r×10 -p-ACGA --p-ACGA 1.9 P-IACGA 5.5 一p-IACGA 4.5 3.5 2.5 0.9 07 1.5 0.5 0.5 10012001300140015001 10012001300140015001 迭代次数G 迭代次数G (a)ta0l (b)ta03 11r×10 9-×10 10 p-ACGA p-ACGA -p-ACGA 9 -D-IACGA 6 100120013001 40015001 1001.2001300140015001 迭代次数G 迭代次数G (c)ta05 (d)ta07 图15算例收敛图 Fig.15 Instance convergence diagram

为了更直观地比较算法性能，图 15 给出了关于 p-ACGA 和 p-IACGA 两个算法测试部分 Taillard 实例的收敛图。从图 15 中可以看出，在相同的最大迭代次数下， p-IACGA 的收敛速度比 p-ACGA 更快。在进化初期，算法通过优化初始方法提高初始解的质量，保证进化过程中解的质量；采用节点信息浓度和路径信息度相结合的方式生成矩阵，提高了区块质量。在进化的后期，应用二元竞赛法来寻找具有更优适应值的解，加快了进化速度。通过实验数据分析，对于求解 PFSP，本文提出的 p-IACGA 相较于 SGA、ACGA、p-ACGA、 BBEDA、LMBBEA 和 p-IACGA 具有较优的求解性能。 0.5 0.7 0.9 1.1 1.3 1.5 1.7 1.9 2.1 ×103 ×103 ×103 ×103 1 1 001 2 001 3 001 4 001 5 001 完工时间 Cmax/s 迭代次数 G (a) ta01 (c) ta05 (d) ta07 (b) ta03 p-ACGA p-IACGA 0.5 1.5 2.5 3.5 4.5 5.5 6.5 1 1 001 2 001 3 001 4 001 5 001 完工时间 Cmax/s 迭代次数 G p-ACGA p-IACGA 2 3 4 5 6 7 8 9 10 11 1 1 001 2 001 3 001 4 001 5 001 完工时间 Cmax/s 迭代次数 G p-ACGA p-ACGA 2 3 4 5 6 7 8 9 1 1 001 2 001 3 001 4 001 5 001 完工时间 Cmax/s 迭代次数 G p-ACGA p-IACGA 图 15 算例收敛图 Fig. 15 Instance convergence diagram 续表 2 算例问题规模 Ui BBEDA LMBBEA SGA ACGA p-ACGA p-IACGA Cmax/s ER Cmax/s ER Cmax/s ER Cmax/s ER Cmax/s ER Cmax/s ER Rec19 30×10 2 093 3 746 0.79 3 202.29 0.53 14 797.51 6.07 5 211.57 1.49 4 018.56 0.92 2 741.83 0.31 Rec21 30×10 2 017 4 942 1.45 4 659.27 1.31 14 260.19 6.07 5 324.88 1.64 5 022.33 1.49 3 388.56 0.68 Rec23 30×10 2 011 3 157 0.57 2 936.06 0.46 17 013.06 7.46 5 610.69 1.79 4 122.55 1.05 2 493.64 0.24 Rec25 30×15 2 513 5 328 1.12 4 498.27 0.79 20 606.60 7.20 7 815.43 2.11 6 584.06 1.62 3 342.29 0.33 Rec27 30×15 2 373 4 366 0.84 3 701.88 0.56 18 628.05 6.85 5 885.04 1.48 5 362.98 1.26 3 488.31 0.47 Rec29 30×15 2 287 4 254 0.86 3 499.11 0.53 21 680.76 8.48 7 181.18 2.14 4 985.66 1.18 3 201.80 0.40 Rec31 50×10 3 045 5 633 0.85 4 841.55 0.59 27 465.90 8.02 12 149.55 2.99 7 886.55 1.59 4 019.40 0.32 Rec33 50×10 3 114 3 893 0.25 4 079.34 0.31 19 057.68 5.12 6 010.02 0.93 5 169.24 0.66 3 456.54 0.11 Rec35 50×10 3 277 3 277 0.00 3 277.00 0.00 14 091.10 3.30 3 473.62 0.06 3 309.77 0.01 3 277.00 0.00 Rec37 75×20 4 951 24 260 3.90 20 645.67 3.17 54 807.57 10.07 30 349.63 5.13 21 437.83 3.33 15 447.12 2.12 Rec39 75×20 5 087 19 432 2.82 15 159.26 1.98 48 377.37 8.51 24 214.12 3.76 17 295.80 2.40 14 396.21 1.83 Rec41 75×20 960 4 714 3.91 3 955.20 3.12 10 588.80 10.03 5 932.80 5.18 4 233.60 3.41 3 369.60 2.51 平均值 0.90 0.66 6.51 1.62 1.04 0.46 ·548· 智能系统学报第 14 卷

第3期裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·549· 4结束语 advanced manufacturing technology,2016,85(9/10/11/12): 2459-2469. 本文针对置换流水车间调度问题，通过对p-ACGA [7]GANGULY S,MUKHERJEE S,BASU D.et al.A novel 改进，提出了p-IACGA。该算法初始化采用随机 strategy adaptive genetic algorithm with greedy local 机制和改进反向学习机制相结合的方式，提高了 search for the permutation flowshop scheduling 初始种群的多样性和质量。进一步考虑了工件与 problem[M]//Swarm,Evolutionary,and Memetic Comput- 所在解序列的位置关系，对节点信息素浓度进行 ing.Berlin,Heidelberg:Springer,2012:687-696. 了分析，通过位置信息素矩阵和相依信息素矩阵 [8]齐学梅，王宏涛，陈付龙，等.求解多目标PFSP的改进遗挖掘区块加快了收敛速度，提高了最终解的质传算法U.计算机工程与应用，2015,51(11)：242-247. 量。该算法保留了传统GA的交叉、变异等操作， QI Xuemei,WANG Hongtao,CHEN Fulong,et al.Im- 通过若干代的GA进化过程产生精英群体，不断 proved genetic algorithm for multi-objective of PFSP[J]. 更新区块，提高了人工染色体的质量和更新速 Computer engineering and applications,2015,51(11): 242-247 度。实验中，通过Taillard和Reeves实例进行测 [9]崔琪，吴秀丽，余建军.变邻域改进遗传算法求解混合流试，以误差率作为比较指标，将结果与其他算法水车间调度问题.计算机集成制造系统，2017,23(9)：比较，验证了p-IACGA的有效性。 1917-1927 未来研究方向可以将所提出的p-IACGA应 CUI Qi,WU Xiuli,YU Jianjun.Improved genetic al- 用于其他组合优化问题，如旅行商问题、车辆路 gorithm variable neighborhood search for solving hybrid 径问题等。也可以通过改进该算法对PFSP的最 flow shop scheduling problem[J].Computer integrated 小化流程时间、最小化延迟时间等其他一个或多 manufacturing systems,2017,23(9):1917-1927 个目标进行研究。 [10]CHANG P C.HUANG W H.WU JL.et al.A block min- 参考文献： ing and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J].Interna- [1]周明，孙树栋遗传算法原理及应用M.北京：国防工业 tional journal of production economics,2013,141(1): 出版社，1999：6. 45-55. [2]夏小云，周育人.蚁群优化算法的理论研究进展.智能 [11]JIN Jian.A hybrid discrete biogeography-based optimiza- 系统学报，2016,11(127-36. tion for the permutation flow shop scheduling problem[J]. XIA Xiaoyun,ZHOU Yuren.Advances in theoretical re- International journal of production research,2016,54(16): search of ant colony optimization[J].CAAI transactions on 4805-4814 intelligent systems,2016,11(1):27-36 [12]DORIGO M.GAMBARDELLA L M.Ant colony sys- [3]李金忠，夏洁武，曾小荟，等.多目标模拟退火算法及其 tem:a cooperative learning approach to the traveling 应用研究进展[J】.计算机工程与科学，2013,35(8)： salesman problem[J].IEEE transactions on evolutionary 77-88. computation,1997,1(1):53-66. LI Jinzhong,XIA Jiewu,ZENG Xiaohui,et al.Survey of [13]陈慧芬.基于链结学习的子群体进化算法求解多目标 multi-objective simulated annealing algorithm and its ap- 调度问题[D].天津：天津理工大学，2017 plications[J].Computer engineering and science,2013, CHEN Huifen.Sub-population evolutionary algorithm 35(8):77-88 based on linkage learning for multi-objective scheduling [4]TAYEB F B S,BESSEDIK M,BENBOUZID M,et al.Re- problem[D].Tianjin:Tianjin University of Technology, search on permutation flow-shop scheduling problem 2017. based on improved genetic immune algorithm with vaccin- [14]裴小兵，陈慧芬，张百栈，等.改善式BVEDA求解多目 ated offspring[J].Procedia computer science,2017,112: 标调度问题[.山东大学学报（工学版），2017,47(4)： 427-436 25-30. [5]CHEN Rongchang,CHEN J,CHEN T S,et al.Synergy of PEI Xiaobing,CHEN Huifen,ZHANG Baizhan,et al.Im- genetic algorithm with extensive neighborhood search for proved bi-variables estimation of distribution algorithms the permutation flowshop scheduling problem[J].Mathem- for multi-objective permutation flow shop scheduling atical problems in engineering,2017,2017:3630869. problem[J].Journal of Shandong University (engineering [6]BESSEDIK M.TAYEB F B S.CHEURFI H,et al.An im- science,2017,47(4):25-30. munity-based hybrid genetic algorithms for permutation [15]裴小兵，赵衡.基于二元分布估计算法的置换流水车间 flowshop scheduling problems[J].International journal of 调度方法.中国机械工程，2017,28(22)：2752-2759

4 结束语本文针对置换流水车间调度问题，通过对p-ACGA 改进，提出了 p-IACGA。该算法初始化采用随机机制和改进反向学习机制相结合的方式，提高了初始种群的多样性和质量。进一步考虑了工件与所在解序列的位置关系，对节点信息素浓度进行了分析，通过位置信息素矩阵和相依信息素矩阵挖掘区块加快了收敛速度，提高了最终解的质量。该算法保留了传统 GA 的交叉、变异等操作，通过若干代的 GA 进化过程产生精英群体，不断更新区块，提高了人工染色体的质量和更新速度。实验中，通过 Taillard 和 Reeves 实例进行测试，以误差率作为比较指标，将结果与其他算法比较，验证了 p-IACGA 的有效性。未来研究方向可以将所提出的 p-IACGA 应用于其他组合优化问题，如旅行商问题、车辆路径问题等。也可以通过改进该算法对 PFSP 的最小化流程时间、最小化延迟时间等其他一个或多个目标进行研究。参考文献：周明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出版社, 1999: 6. [1] 夏小云, 周育人. 蚁群优化算法的理论研究进展[J]. 智能系统学报, 2016, 11(1): 27–36. XIA Xiaoyun, ZHOU Yuren. Advances in theoretical research of ant colony optimization[J]. CAAI transactions on intelligent systems, 2016, 11(1): 27–36. [2] 李金忠, 夏洁武, 曾小荟, 等. 多目标模拟退火算法及其应用研究进展[J]. 计算机工程与科学, 2013, 35(8): 77–88. LI Jinzhong, XIA Jiewu, ZENG Xiaohui, et al. Survey of multi-objective simulated annealing algorithm and its applications[J]. Computer engineering and science, 2013, 35(8): 77–88. [3] TAYEB F B S, BESSEDIK M, BENBOUZID M, et al. Research on permutation flow-shop scheduling problem based on improved genetic immune algorithm with vaccinated offspring[J]. Procedia computer science, 2017, 112: 427–436. [4] CHEN Rongchang, CHEN J, CHEN T S, et al. Synergy of genetic algorithm with extensive neighborhood search for the permutation flowshop scheduling problem[J]. Mathematical problems in engineering, 2017, 2017: 3630869. [5] BESSEDIK M, TAYEB F B S, CHEURFI H, et al. An immunity-based hybrid genetic algorithms for permutation flowshop scheduling problems[J]. International journal of [6] advanced manufacturing technology, 2016, 85(9/10/11/12): 2459–2469. GANGULY S, MUKHERJEE S, BASU D, et al. A novel strategy adaptive genetic algorithm with greedy local search for the permutation flowshop scheduling problem[M]//Swarm, Evolutionary, and Memetic Computing. Berlin, Heidelberg: Springer, 2012: 687–696. [7] 齐学梅, 王宏涛, 陈付龙, 等. 求解多目标 PFSP 的改进遗传算法[J]. 计算机工程与应用, 2015, 51(11): 242–247. QI Xuemei, WANG Hongtao, CHEN Fulong, et al. Improved genetic algorithm for multi-objective of PFSP[J]. Computer engineering and applications, 2015, 51(11): 242–247. [8] 崔琪, 吴秀丽, 余建军. 变邻域改进遗传算法求解混合流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(9): 1917–1927. CUI Qi, WU Xiuli, YU Jianjun. Improved genetic algorithm variable neighborhood search for solving hybrid flow shop scheduling problem[J]. Computer integrated manufacturing systems, 2017, 23(9): 1917–1927. [9] CHANG P C, HUANG W H, WU J L, et al. A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International journal of production economics, 2013, 141(1): 45–55. [10] JIN Jian. A hybrid discrete biogeography-based optimization for the permutation flow shop scheduling problem[J]. International journal of production research, 2016, 54(16): 4805–4814. [11] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE transactions on evolutionary computation, 1997, 1(1): 53–66. [12] 陈慧芬. 基于链结学习的子群体进化算法求解多目标调度问题[D]. 天津: 天津理工大学, 2017. CHEN Huifen. Sub-population evolutionary algorithm based on linkage learning for multi-objective scheduling problem[D]. Tianjin: Tianjin University of Technology, 2017. [13] 裴小兵, 陈慧芬, 张百栈, 等. 改善式 BVEDA 求解多目标调度问题[J]. 山东大学学报(工学版), 2017, 47(4): 25–30. PEI Xiaobing, CHEN Huifen, ZHANG Baizhan, et al. Improved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem[J]. Journal of Shandong University (engineering science), 2017, 47(4): 25–30. [14] 裴小兵, 赵衡. 基于二元分布估计算法的置换流水车间调度方法[J]. 中国机械工程, 2017, 28(22): 2752–2759. [15] 第 3 期裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·549·