·95· 李猛，等：一种面向维修资源配送调度的遗传-烟花混合算法 第1期 为了综合对比算法的求解速度，分别统计 满意解时的平均迭代次数及平均运行时长（单 3种算法在各算例上10次运行结果中初次找到 位：s),如图7所示。 表4目标函数最优值 Table 4 Optimal value of objective function 算例 A A2 A3 Aa As B B2 B3 Ba Bs GA 16072 22130 28327 42640 41351 14636 20484 24930 40823 39215 FWA 15474 21711 27634 41715 40700 13918 19420 23786 39601 38532 混合 14936 21322 27122 40067 39429 13565 19170 22973 38725 37783 表5目标函数平均值 Table 5 Average value of objective function 算例 Al A2 A3 Aa As B B2 B3 Ba Bs GA 16892 22910 29138 43653 42564 15421 21180 26086 41970 40585 FWA 15725 22137 28354 42405 41638 14753 20187 24786 40533 39714 混合 15270 21634 27592 41517 40727 14195 19794 23553 39022 38372 表6目标函数标准差 Table 6 Standard deviation of objective function 算例 A A2 A3 A A B B2 B3 B Bs GA 384.3 339.9 442.6 485.1 552.3 340.7 327.6 532.5 673.4 472.9 FWA 207.4 208.2 337.5 349.2 362 327.7 308.2 411.8 479.2 512.0 混合 229.6 147.4 219.7 459.9294.6 257.2 328.5 272.5 459.3 324.5 3000 法种群中适应度最好的个体其包含更为优秀的遗 新2500 传信息，对其进行爆炸操作能在很大程度上能够 2000 1500 引导算法的收敛方向，而适应度最差的个体由于 1000 包含了和优秀个体差异程度最大的遗传信息，能 500 ◆GA鲁FWA★混合 够使得种群的遗传信息更加丰富，从而扩大了局 0 A B A2 B:A:B,A.B.As B 部搜索的范围。对两种算法进行混合，充分结合 算例 了遗传算法全局搜索能力强和烟花算法局部搜索 图7初次找到满意解的平均迭代次数 能力强的特点，使得混合算法在收敛速度和搜索 Fig.7 Average number of iterations to find a satisfactory 范围上都得到了改善，从而能够以更快的速度得 solution for the first time 到更小成本的调度方案，这对于实际的资源供应 综合求解质量和求解速度的结果来看：混合 算法求解质量是最好的，其收敛速度也快于烟花 调度具有重要的经济效益。 算法和遗传算法，但在运行时间上会略慢于遗传 5结束语 算法，即混合算法在略微增加了一些运算成本的 情况下获得了更好的求解质量。而增加的运算成 本文针对建立的维修资源供应调度模型，本 本可以通过硬件配置进一步缩小，但对于求解质 文提出了一种遗传-烟花混合算法。混合算法在 量，其他两种算法却无法靠简单的硬件升级进行 遗传算法的基础上，引入了烟花爆炸算子，使得 弥补，因此混合算法是3种算法中综合性能最强 种群优秀个体的数量增多，增强了算法的局部寻 的算法。 优能力。通过仿真对比实验，结果表明本文提出 从理论上对实验结果进行分析，由于遗传算 的混合算法可以得到成本更低的调度方案，同时为了综合对比算法的求解速度，分别统计 3 种算法在各算例上 10 次运行结果中初次找到 满意解时的平均迭代次数及平均运行时长（单 位：s），如图 7 所示。 表 4 目标函数最优值 Table 4 Optimal value of objective function 算例 A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 GA 16072 22130 28 327 42 640 41351 14636 20484 24 930 40 823 39215 FWA 15474 21711 27 634 41 715 40700 13918 19420 23 786 39 601 38532 混合 14936 21322 27 122 40 067 39429 13565 19170 22 973 38 725 37783 表 5 目标函数平均值 Table 5 Average value of objective function 算例 A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 GA 16892 22910 29 138 43 653 42564 15421 21180 26 086 41 970 40585 FWA 15725 22137 28 354 42 405 41638 14753 20187 24 786 40 533 39714 混合 15270 21634 27 592 41 517 40727 14195 19794 23 553 39 022 38372 表 6 目标函数标准差 Table 6 Standard deviation of objective function 算例 A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 GA 384.3 339.9 442.6 485.1 552.3 340.7 327.6 532.5 673.4 472.9 FWA 207.4 208.2 337.5 349.2 362 327.7 308.2 411.8 479.2 512.0 混合 229.6 147.4 219.7 459.9 294.6 257.2 328.5 272.5 459.3 324.5 GA FWA 混合 A1 0 500 1 000 1 500 2 000 2 500 3 000 B1 A2 B2 A3 B3 A4 B4 A5 B5 平均迭代次数 算例 图 7 初次找到满意解的平均迭代次数 Fig. 7 Average number of iterations to find a satisfactory solution for the first time 综合求解质量和求解速度的结果来看：混合 算法求解质量是最好的，其收敛速度也快于烟花 算法和遗传算法，但在运行时间上会略慢于遗传 算法，即混合算法在略微增加了一些运算成本的 情况下获得了更好的求解质量。而增加的运算成 本可以通过硬件配置进一步缩小，但对于求解质 量，其他两种算法却无法靠简单的硬件升级进行 弥补，因此混合算法是 3 种算法中综合性能最强 的算法。 从理论上对实验结果进行分析，由于遗传算 法种群中适应度最好的个体其包含更为优秀的遗 传信息，对其进行爆炸操作能在很大程度上能够 引导算法的收敛方向，而适应度最差的个体由于 包含了和优秀个体差异程度最大的遗传信息，能 够使得种群的遗传信息更加丰富，从而扩大了局 部搜索的范围。对两种算法进行混合，充分结合 了遗传算法全局搜索能力强和烟花算法局部搜索 能力强的特点，使得混合算法在收敛速度和搜索 范围上都得到了改善，从而能够以更快的速度得 到更小成本的调度方案，这对于实际的资源供应 调度具有重要的经济效益。 5 结束语 本文针对建立的维修资源供应调度模型，本 文提出了一种遗传–烟花混合算法。混合算法在 遗传算法的基础上，引入了烟花爆炸算子，使得 种群优秀个体的数量增多，增强了算法的局部寻 优能力。通过仿真对比实验，结果表明本文提出 的混合算法可以得到成本更低的调度方案，同时 ·95· 李猛，等：一种面向维修资源配送调度的遗传–烟花混合算法 第 1 期