·93· 李猛，等：一种面向维修资源配送调度的遗传-烟花混合算法 第1期 量的生成规则不同，因此爆炸算子也需要对不同 R;=AX fit(x)-fitmin (18) 维度的向量分别进行操作，才能保证生成新个体 的正确性，具体的操作分为图5所示的4种策 ∑it(x)--filn） 略。对于第一维的需求地向量，爆炸算子采用一种 随机混合方案，对每一次的爆炸操作，随机采用单点 式中：Sum为预设的爆炸火花数；A为爆炸半径的 交换、插入与反转3种策略中的一种执行，如图5 基值；t(x)为个体x的适应度；fita与ftmm分别为 中(a)、(b)、(c)所示；而对于第二维的配送中心向 进行爆炸操作的个体中的最大适应度值与最小适 量，由于无需考虑冲突检测，在上述3种策略之 应度值：N为进行爆炸操作的个体的数量。 外，还加入了多点变异策略，如图5(d)。 爆炸半径规定了爆炸操作时进行邻域搜索的 范围，对于本文的自然数编码方案，爆炸半径可 交换点 交换点 以对应为爆炸操作的最大执行次数，即对于烟花 157311282104914563 i,需要随机进行1~R次爆炸操作才可以得到一个 132132313232213 新的火花。 由于在遗传算法阶段进行了相关变异操作， 15792812104314563 为避免不必要的运算，本文爆炸算子没有考虑高 132332313212213 斯变异火花。由于爆炸数量根据个体的适应度计 (a)单点交换 算的，具有一定的不确定性，因此本文对S:设置了 插人点 插人入基因 上下界： 15731128121049145613 Smax:SiS max 132132313232213 Si Smin<Si<Sma (19) 式中：Sax与S分别为的预先设置的最大、最小 15793128121041415613 132313231322213 爆炸火花数量。 (b)单点插入 最后为了保证种群规模不变，规定每次保留 反转点 反转点 S个火花作为爆炸算子产生的新个体，加入遗传 算法的种群中，进行混合算法的下一轮迭代。 157311281210491415613 132132313232213 3.3混合算法流程 混合算法的基本流程如图6所示，分为初始 化、遗传进化和爆炸优化3个阶段。 157941012821131415613 132323132312213 (开始 (c)反转 变异点1 变异点2 变异点3 初始化模型和算法中的各 项参数和变量 (结束 157311281210491415613 构建资源集合、需求地 输出最佳调度方案 132132313232213 点、配送中心及车辆集合 Y L 随机生成初代种群 是否达到终 止条件 15731128121043141563 132332113222213 采用PMX和简单交换对 将爆炸火花粒子加入子代 种群个体进行交叉操作 种群，进人下一轮迭代 (d多点变异 随机选择一定数量的个 图5爆炸算子示意 体，进行变异操作 经爆炸操作得到火花粒子 Fig.5 Flow chart of explosion operator 计算种群中每个个体的适 计算爆炸数量和爆炸半径 爆炸算子中的爆炸数量S:和爆炸半径R:的计 应度，并对其排序 + 算规则为 采用精英保留和轮盘赌选 选择子代种群中适应度最 fitmax-fit(xi) 择进入子代种群中的个体 好和最差的两个个体 S:=Sum· (17) ,(itax-fit(x》 图6遗传-烟花混合算法流程图 Fig.6 Flow chart of genetic-firework hybrid algorithm量的生成规则不同，因此爆炸算子也需要对不同 维度的向量分别进行操作，才能保证生成新个体 的正确性，具体的操作分为图 5 所示的 4 种策 略。对于第一维的需求地向量，爆炸算子采用一种 随机混合方案，对每一次的爆炸操作，随机采用单点 交换、插入与反转 3 种策略中的一种执行，如图 5 中 (a)、(b)、(c) 所示；而对于第二维的配送中心向 量，由于无需考虑冲突检测，在上述 3 种策略之 外，还加入了多点变异策略，如图 5(d)。 插入点 插入基因 1 5 7 9 11 2 8 12 10 4 14 15 6 13 1 3 2 3 3 2 3 1 3 2 2 2 1 3 3 1 1 5 7 3 11 2 8 12 10 4 9 14 15 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 1 5 7 3 11 2 8 12 10 4 9 14 15 6 13 11 12 10 14 15 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 交换点 交换点 1 5 7 9 2 8 4 3 6 1 3 2 3 3 2 3 1 3 2 1 2 2 1 3 1 5 7 3 11 2 8 12 10 4 9 14 15 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 反转点 反转点 1 5 7 9 4 10 12 8 2 11 3 14 15 6 13 1 3 2 3 2 3 1 3 2 3 1 2 2 1 3 1 5 7 3 11 2 8 12 10 4 9 14 15 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 变异点 1 变异点 2 变异点 3 1 5 7 3 11 2 8 12 10 4 3 14 15 6 13 1 3 2 3 3 2 1 1 3 2 2 2 2 1 3 (d) 多点变异 (c) 反转 (b) 单点插入 (a) 单点交换 图 5 爆炸算子示意 Fig. 5 Flow chart of explosion operator 爆炸算子中的爆炸数量 S i和爆炸半径 Ri的计 算规则为 S i = S sum · fitmax −fit(xi) ∑N i=1 (fitmax −fit(xi)) (17) Ri = A× fit(xi)−fitmin ∑N i=1 (fit(xi)−fitmin ) (18) S sum A fit(xi) xi fitmax fitmin N 式中： 为预设的爆炸火花数； 为爆炸半径的 基值； 为个体 的适应度； 与 分别为 进行爆炸操作的个体中的最大适应度值与最小适 应度值； 为进行爆炸操作的个体的数量。 Ri 爆炸半径规定了爆炸操作时进行邻域搜索的 范围，对于本文的自然数编码方案，爆炸半径可 以对应为爆炸操作的最大执行次数，即对于烟花 i，需要随机进行 1~ 次爆炸操作才可以得到一个 新的火花。 S i 由于在遗传算法阶段进行了相关变异操作， 为避免不必要的运算，本文爆炸算子没有考虑高 斯变异火花。由于爆炸数量根据个体的适应度计 算的，具有一定的不确定性，因此本文对 设置了 上下界： Sˆ i =    S max, S i > S max S i , S min < S i < S max S min, S i < S min (19) 式中： S max与 S min分别为的预先设置的最大、最小 爆炸火花数量。 S min 最后为了保证种群规模不变，规定每次保留 个火花作为爆炸算子产生的新个体，加入遗传 算法的种群中，进行混合算法的下一轮迭代。 3.3 混合算法流程 混合算法的基本流程如图 6 所示，分为初始 化、遗传进化和爆炸优化 3 个阶段。 开始 初始化模型和算法中的各 项参数和变量 随机生成初代种群 计算种群中每个个体的适 应度，并对其排序 采用 PMX 和简单交换对 种群个体进行交叉操作 是否达到终 止条件 随机选择一定数量的个 体，进行变异操作 采用精英保留和轮盘赌选 择进入子代种群中的个体 选择子代种群中适应度最 好和最差的两个个体 计算爆炸数量和爆炸半径 经爆炸操作得到火花粒子 将爆炸火花粒子加入子代 种群，进入下一轮迭代 构建资源集合、需求地 点、配送中心及车辆集合 输出最佳调度方案 结束 遗 传 搜 索 阶 段 爆 炸 优 化 阶 段 初 始 化 阶 段 Y N 图 6 遗传–烟花混合算法流程图 Fig. 6 Flow chart of genetic-firework hybrid algorithm ·93· 李猛，等：一种面向维修资源配送调度的遗传–烟花混合算法 第 1 期