第17卷 智能系统学报 ·92· 需求地信息，随机产生固定数量(Popsize)的染色 在11-7、1-(2-12)-10、8-6、4-(9)-144个对应关系； 体，即可作为混合算法的初始种群。Popsize的大 插人点 插入点 小往往决定了算法的搜索性能，一般需根据模型 输入数据的规模进行调整，从而保证种群基因的 父代182996 1321323T3232213 多样性。 父代28 2)适应度函数 对于本文的保障资源供应调度模型，其优化 交叉互换 建立映射关系 预备 1573☒K822941415613 目标是使维修资源供应调度方案的总成本最小， 子代1 132112133212213 28i21049 算法的目标函数即是调度总成本，因此适应度函 预备 31☐413M4281294915085 数可用倒数函数形式表示，即 子代2 31123323I3233212 716212914 冲突检测与修复 fit(i)=1/Cost(i) (15) 式中：Cost()为种群中个体i的目标函数值；it()即 子代17308229446国 132132313232213 个体i的染色体所对应的适应度，t()越大，被选 则的几率就越大。 子代24372612149s085 312312133213212 3)停止准则 图4交叉操作流程示意 对于本文提出的混合算法，其主体结构依旧 Fig.4 Cross-operation flow diagram 是遗传算法，只需设置一个迭代次数的上限Max- ③对交换基因片段后产生的预备子代进行冲 gen,当算法的迭代次数达到该阈值时候，结束程 突检测与修复。以预备子代1为例，交换之后存 序，输出当前的满意解即可。 在重复基因7、1、6、14。而通过映射关系可知， 4)选择操作 这4个重复基因依次与基因11、10、8、14匹配， 首先通过精英保留策略直接保留最优秀的个 按照该映射规则进行替换，预备子代1中的基因 体：根据适应度的大小对当前种群中的个体降序 7、1、6、14被替换为了基因11、10、8、14，从而得 排列，将一定数量的优秀个体直接放入子代种 到了无重复基因的子代1。预备子代2也按照同 群。对于剩下的个体采用轮盘赌策略进行选择， 样的方法根据映射关系进行修复即可。 具体流程为：先通过式(16)计算保留概率P(x,然 编码第二维向量为配送中心信息，不具有唯 后对所有个体的保留概率累加，得到个体的累计 性，允许元素的重复出现。因此本文采用简单 概率分布刻度区间，最后在(0,1]区间内产生 的两点交叉策略，将父代中虚线所指的配送中心 Gap×Popsize个随机数，根据随机数掉落的刻度区 编码片段两两交换即可，如图4中虚线所示。 间确定被选中的染色体。 6)变异操作 fit(x;) P(xi)= (16) 混合算法中变异操作采用简单的两点交换策 Popsize fit(x;) 略，在种群中以一定变异概率随机选择一定数量 的个体进行基因交换，具体步骤十分简单：对选 式中：it(x)表示个体x的适应度；P(x)表示个体 中的个体，随机选择其染色体上的两个基因作为 x的保留概率。 交换点，然后交换它们的位置即可。 5)交叉操作 7)爆炸算子设计 本文对染色体编码中的两个维度采用了不同 在烟花算法中爆炸操作即为一次邻域搜索过 的交叉方法。第一维编码向量是需求地编码的全 程，且适应度值较好的烟花在较小的范围内产生 排列，具有唯一性，简单的交叉方法非常容易产 较多的火花粒子，称为“局部烟花”，适应度值较 生不可行解，因此本文采用的交叉方法为部分匹 差的烟花在较大的范围内产生较少的火花粒子， 配交叉法(partially matching crossover,PMX)。以 称为“全局烟花”。遗传算法种群中适应度最好的 图4为例，其具体步骤如下： 个体含有更为优秀的遗传信息，在很大程度上能 ①随机选择一对染色体（父代1和父代2）， 够引导算法的收敛方向，因此可以看作一个产生 在染色体上再随机选择两个插入点，作为交叉片 “局部烟花”的最佳爆炸点：而适应度最差的个体 段的起止位置： 由于其包含了和优秀个体差异程度最大的遗传信 ②根据插入点的位置，交换两个父代中的基 息，能够使得种群的遗传信息更加多样化，因此 因片段，并根据交换的具体基因建立一个两两映 可以看作产生“全局烟花”的一个较好爆炸点。 射关系集合。例如，在图4交换的基因片段中，存 由于本文染色体中需求地和配送中心两个向需求地信息，随机产生固定数量 (Popsize) 的染色 体，即可作为混合算法的初始种群。Popsize 的大 小往往决定了算法的搜索性能，一般需根据模型 输入数据的规模进行调整，从而保证种群基因的 多样性。 2）适应度函数 对于本文的保障资源供应调度模型，其优化 目标是使维修资源供应调度方案的总成本最小， 算法的目标函数即是调度总成本，因此适应度函 数可用倒数函数形式表示，即 fit(i) = 1/Cost(i) (15) Cost(i) fit(i) fit(i) 式中： 为种群中个体 i 的目标函数值； 即 个体 i 的染色体所对应的适应度， 越大，被选 则的几率就越大。 3）停止准则 对于本文提出的混合算法，其主体结构依旧 是遗传算法，只需设置一个迭代次数的上限 Max￾gen，当算法的迭代次数达到该阈值时候，结束程 序，输出当前的满意解即可。 4）选择操作 P(xi) Gap×Popsize 首先通过精英保留策略直接保留最优秀的个 体：根据适应度的大小对当前种群中的个体降序 排列，将一定数量的优秀个体直接放入子代种 群。对于剩下的个体采用轮盘赌策略进行选择， 具体流程为：先通过式（16）计算保留概率 ，然 后对所有个体的保留概率累加，得到个体的累计 概率分布刻度区间，最后在 (0， 1] 区间内产生 个随机数，根据随机数掉落的刻度区 间确定被选中的染色体。 P(xi) = fit(xj) Popsize ∑ j=1 fit(xj) (16) fit(xi) xi P(xi) xi 式中： 表示个体 的适应度； 表示个体 的保留概率。 5）交叉操作 本文对染色体编码中的两个维度采用了不同 的交叉方法。第一维编码向量是需求地编码的全 排列，具有唯一性，简单的交叉方法非常容易产 生不可行解，因此本文采用的交叉方法为部分匹 配交叉法 (partially matching crossover，PMX)。以 图 4 为例，其具体步骤如下： ①随机选择一对染色体（父代 1 和父代 2）， 在染色体上再随机选择两个插入点，作为交叉片 段的起止位置； ②根据插入点的位置，交换两个父代中的基 因片段，并根据交换的具体基因建立一个两两映 射关系集合。例如，在图 4 交换的基因片段中，存 在 11-7、1-（2-12）-10、8-6、4-（9）-14 4 个对应关系； 1 5 7 3 11 2 8 1210 4 9 1415 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 父代 1 父代 2 3 11 4 13 7 1 6 2 12 9 141510 8 5 3 1 2 3 1 2 1 3 3 2 1 3 2 1 2 1 5 7 3 1415 6 13 1 3 2 1 1 2 1 3 3 2 1 2 2 1 3 3 11 4 13 15 8 5 3 1 2 3 3 2 3 1 3 2 3 3 2 1 2 7 1 6 2 12 9 14 11 2 8 1210 4 9 1 5 7 3 1415 6 13 1 3 2 1 3 2 3 1 3 2 3 2 2 1 3 子代 1 3 11 4 13 1510 8 5 3 1 2 3 1 2 1 3 3 2 1 3 2 1 2 子代 2 1110 8 2 12 9 4 7 2 6 12 1 14 9 11 2 8 1210 4 9 7 1 6 2 12 9 14 交叉互换 建立映射关系 插入点 插入点 10 预备 子代 1 预备 子代 2 冲突检测与修复 图 4 交叉操作流程示意 Fig. 4 Cross-operation flow diagram ③对交换基因片段后产生的预备子代进行冲 突检测与修复。以预备子代 1 为例，交换之后存 在重复基因 7、1、6、14。而通过映射关系可知， 这 4 个重复基因依次与基因 11、10、8、14 匹配， 按照该映射规则进行替换，预备子代 1 中的基因 7、1、6、14 被替换为了基因 11、10、8、14，从而得 到了无重复基因的子代 1。预备子代 2 也按照同 样的方法根据映射关系进行修复即可。 编码第二维向量为配送中心信息，不具有唯 一性，允许元素的重复出现。因此本文采用简单 的两点交叉策略，将父代中虚线所指的配送中心 编码片段两两交换即可，如图 4 中虚线所示。 6）变异操作 混合算法中变异操作采用简单的两点交换策 略，在种群中以一定变异概率随机选择一定数量 的个体进行基因交换，具体步骤十分简单：对选 中的个体，随机选择其染色体上的两个基因作为 交换点，然后交换它们的位置即可。 7）爆炸算子设计 在烟花算法中爆炸操作即为一次邻域搜索过 程，且适应度值较好的烟花在较小的范围内产生 较多的火花粒子，称为“局部烟花”，适应度值较 差的烟花在较大的范围内产生较少的火花粒子， 称为“全局烟花”。遗传算法种群中适应度最好的 个体含有更为优秀的遗传信息，在很大程度上能 够引导算法的收敛方向，因此可以看作一个产生 “局部烟花”的最佳爆炸点；而适应度最差的个体 由于其包含了和优秀个体差异程度最大的遗传信 息，能够使得种群的遗传信息更加多样化，因此 可以看作产生“全局烟花”的一个较好爆炸点。 由于本文染色体中需求地和配送中心两个向 第 17 卷 智 能 系 统 学 报 ·92·