第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·
·546· 智能系统学报 第14卷 2.4染色体重组 9,1,7}及{7,4,3,8}，选择长度较长的片段进行 为了进一步提高算法搜索到最优解的机会， 重组，过程如图13所示。 对每一代染色体进行重组。首先随机选择N个 切点，将一条完整的染色体分割成N+1个片段， 再从这些片段中选择出长度最长的片段进行重 G52610917438 组。以工件数为10切点数为2为例，如图12，切 图12切割人工染色体 割完成后的段数为3段，分别为{5,2}、{2,6,10， Fig.12 Cutting an artificial chromosome 计算合 并概率 438 5→2=CP256=CP650=CP1 5→9=CP。5→1=CP,5→7=CP, 选择 工件9 Y比较概率 59 ■438 CP>CP>CP>CP2>CP>CPo ,计算合 Y并概率 92=CP2 96=CP6 910=CP1o 比较概率 9→1=CP CP>CP>CP>CP>CP 97=CP, 选择 592 438 5971620438 图13人工染色体重组 Fig.13 Artificial chromosome reorganization 2.5留存优势解 机选择两条染色体，比较适应度，选择适应度较大 将重组后的GA最新子代山和人工染色体 的染色体放入染色体库，适应度较小的染色体放回 C,放入选择池，使用二元竞赛法选择出优秀染色 选择池继续筛选，反复执行上述步骤，直到染色体 体作为子代进入下一代进化。首先，从选择池中随 库中染色体的数量满足设定的群体大小，如图14。 选择池 C45316289710 c17410628935 c61597438210 染色体库 45316289710 C✉95261710438 C95261710438 c2691038547 C26910138547 412345678910 17426105938 417426105938 596724830 459617248310 445136210978 26109685341 图14留存优势解 Fig.14 Retention of advantage solution
2.4 染色体重组 N N +1 为了进一步提高算法搜索到最优解的机会， 对每一代染色体进行重组。首先随机选择 个 切点，将一条完整的染色体分割成 个片段， 再从这些片段中选择出长度最长的片段进行重 组。以工件数为 10 切点数为 2 为例，如图 12，切 割完成后的段数为 3 段，分别为{5，2}、{2，6，10， 9，1，7}及{7，4，3，8}，选择长度较长的片段进行 重组，过程如图 13 所示。 C1 5 2 6 10 9 1 7 4 3 8 图 12 切割人工染色体 Fig. 12 Cutting an artificial chromosome 5 4 3 8 5 9 4 3 8 5 9 2 4 3 8 5 9 7 1 6 2 10 4 3 8 ……………… 5 2=CP2 5 9=CP9 5 6=CP6 5 1=CP1 5 10=CP10 5 7=CP7 计算合 并概率 CP9>CP1>CP6>CP2>CP7>CP10 选择 工件 9 9 2=CP2 9 6=CP6 9 10=CP10 9 1=CP1 9 7=CP7 计算合 并概率 CP2>CP1>CP6>CP10>CP7 选择 工件 2 比较概率 比较概率 图 13 人工染色体重组 Fig. 13 Artificial chromosome reorganization 2.5 留存优势解 将重组后的 GA 最新子代 µi 和人工染色体 Ci 放入选择池，使用二元竞赛法[17]选择出优秀染色 体作为子代进入下一代进化。首先，从选择池中随 机选择两条染色体，比较适应度，选择适应度较大 的染色体放入染色体库，适应度较小的染色体放回 选择池继续筛选，反复执行上述步骤，直到染色体 库中染色体的数量满足设定的群体大小，如图 14。 4 5 3 1 6 2 8 9 7 10 1 7 4 10 6 2 8 9 3 5 6 1 5 9 7 4 3 8 2 10 9 5 2 6 1 7 10 4 3 8 2 6 9 10 1 3 8 5 4 7 1 2 3 4 5 6 7 8 9 10 1 7 4 2 6 10 5 9 3 8 5 9 6 1 7 2 4 8 3 10 4 5 1 3 6 2 10 9 7 8 2 6 10 9 6 8 5 3 4 1 C1 C2 C3 C4 C5 μ1 μ2 μ3 μ4 μ5 4 5 3 1 6 2 8 9 7 10 9 5 2 6 1 7 10 4 3 8 2 6 9 10 1 3 8 5 4 7 1 7 4 2 6 10 5 9 3 8 5 9 6 1 7 2 4 8 3 10 C1 C4 C5 μ2 μ3 选择池 染色体库 图 14 留存优势解 Fig. 14 Retention of advantage solution ·546· 智 能 系 统 学 报 第 14 卷
第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·
·550· 智能系统学报 第14卷 PEI Xiaobing,ZHAO Heng.Permutation flow shop algorithm for machine scheduling problems[J].Annals of scheduling problem based on hybrid binary distribution operations research,2010,180(1):197-211. estimation algorithm[J].China mechanical engineering, [20]HSU C Y,CHANG P C,CHEN M H.A linkage mining 2017,28(22:2752-2759. in block-based evolutionary algorithm for permutation [16]张敏，汪洋，方侃.基于改进区块进化算法求解置换流 flowshop scheduling problem[J].Computers industrial 水车间问题[J].计算机集成制造系统，2018,24(5)： engineering,2015,83:159-171. 1207-1216. 作者简介： ZHANG Min,WANG Yang,FANG Kan.Improved 裴小兵，男.1965生，教授，博士 block-based evolutionary algorithm for solving permuta- 主要研究方向为生产调度、精益生 tion flowshop scheduling problem[J].Computer integ- 产。发表学术论文14篇。 rated manufacturing systems,2018,24(5):1207-1216. [17]CHANG P C,CHEN Menghui.A block based estimation of distribution algorithm using bivariate model for scheduling problems[J].Soft computing,2014,18(6): 1177-1188 张春花，女，1992生，硕士研究 [18]MILLER B L,GOLDBERG D E.Genetic algorithms, 生，主要研究方向为生产调度、智能 算法。 tournament selection,and the effects of noise[J].Com- plex systems,1995,93):193-212. [19]CHANG P C,CHEN S H.FAN C Y,et al.Generating ar- tificial chromosomes with probability control in genetic
PEI Xiaobing, ZHAO Heng. Permutation flow shop scheduling problem based on hybrid binary distribution estimation algorithm[J]. China mechanical engineering, 2017, 28(22): 2752–2759. 张敏, 汪洋, 方侃. 基于改进区块进化算法求解置换流 水车间问题[J]. 计算机集成制造系统, 2018, 24(5): 1207–1216. ZHANG Min, WANG Yang, FANG Kan. Improved block-based evolutionary algorithm for solving permutation flowshop scheduling problem[J]. Computer integrated manufacturing systems, 2018, 24(5): 1207–1216. [16] CHANG P C, CHEN Menghui. A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft computing, 2014, 18(6): 1177–1188. [17] MILLER B L, GOLDBERG D E. Genetic algorithms, tournament selection, and the effects of noise[J]. Complex systems, 1995, 9(3): 193–212. [18] CHANG P C, CHEN S H, FAN C Y, et al. Generating artificial chromosomes with probability control in genetic [19] algorithm for machine scheduling problems[J]. Annals of operations research, 2010, 180(1): 197–211. HSU C Y, CHANG P C, CHEN M H. A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem[J]. Computers & industrial engineering, 2015, 83: 159–171. [20] 作者简介： 裴小兵，男，1965 生，教授，博士， 主要研究方向为生产调度、精益生 产。发表学术论文 14 篇。 张春花，女，1992 生，硕士研究 生，主要研究方向为生产调度、智能 算法。 ·550· 智 能 系 统 学 报 第 14 卷
