第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·