·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。空间中存在诸多局部最优解，且问题复杂度越 高，越容易局部最优化，因此许多学者针对 PF￾SP 特性不断对求解 PFSP 的算法进行优化。求解 PFSP 的算法可分为精确算法和近似算法，精确算 法虽能求出最优解，但时间复杂性较高，随着问 题的规模增大将变得不可行。近似算法对于较大 规模的问题能在可行时间内求出近优解，是研究 PFSP 问题的重要方法。近似算法包括遗传算 法 [1] 、蚁群算法[2] 、模拟退火算法[3]等。 遗传算法 (genetic algorithm, GA) 通过选择、 交叉和变异等操作搜索解空间的最优解，已经成 功应用于解决旅行商问题、车辆路径问题和车间 调度问题等不同领域的组合问题。但是遗传算法 的局部搜索能力较差，在实际应用中容易产生早 熟收敛的问题。怎么运用遗传算法既能保留优良 个体，又能维持群体的多样性，一直是遗传算法 中较难解决的问题。近年来针对 PFSP，不少学者 为提高遗传算法的有效性，将遗传算法与其他算 法相结合对该问题进行求解，取得了不错的效 果。Benbouzid 等 [4]针对 PFSP 提出 VacGA(intro￾duces vaccination into the field of GAs)，将遗传算法 和免疫算法相结合，遗传算法执行全局搜索，人 工免疫系统执行局部搜索，以克服演化过程中遗 传算法局部搜索能力不足的问题。Chen 等 [5]将遗 传算法与广义邻域搜索相结合，提出一种新型混 合遗传算法求解 PFSP。Bessedik 等 [6]提出一种基 于免疫的遗传算法，这种算法分为两种形式：1） 将接种引入到基于免疫理论的遗传算法；2）从免 疫网络理论得到启发，并将其运用到遗传算法 中。Ganguly 等 [7]将贪婪局部搜索算子引入到遗 传算法，有效地解决大范围的排序和调度离散优 化问题。齐学梅等[8]为求解 PFSP 问题，将变邻域 搜索算法与遗传算法相结合，加快了收敛速度。 吴秀丽等[9]将变邻域搜索算法和遗传算法相结合 提出了一种变邻域改进遗传算法求解混合流水车 间调度问题，增强了遗传算法的局部搜索能力。 Chang 等 [10]针对置换流水车间调度问题，提 出一种基于区块的遗传算法 (puzzle-based artifi￾cial chromosome genetic algorithm，p-ACGA)，将遗 传算法和蚁群算法相结合，通过简单遗传算法的 交叉、突变等操作产生精英群体，针对这些精英 群体，利用蚁群算法的信息素浓度对工件与工件 的关系进行统计分析，进而建立信息素相依矩阵 并根据矩阵挖掘区块，利用区块和非区块重组形 成人工染色体，然后将其注入到进化过程中。虽 然 p-ACGA 能够避免局部最优问题，一定程度上 改善了解的质量，加快了进化速度，但是算法在 初始化、信息素分布统计等方面还存在一些不足。 因此本文提出一种改进区块遗传算法 (puzzle￾based improved artificial chromosome genetic al￾gorithm，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 卷