第17卷 智能系统学报 ·464· 4)计算每个个体的适应度值，使用轮盘赌选 真实验得到最佳的一组设置，即5mas=0.9、专mim=0.5 择法获取适应度值高的个体； 少max=0.2和ψmin=0.02;参考文献[22]，并经过仿真 5)根据交叉概率，从单点交叉和均匀两点交 实验测试GMBOA中的6=31、y=10、Gmx=10 叉2种方式随机选择1种生成新个体： o=3;基于GA的4种算法和IDABC的种群规模 6)根据变异概率山，随机执行基于随机机器 e=100:由于MBO&NS的种群规模必须为奇数， 选择的单点变异或基于机器最短处理时间的多点 所以其种群规模e=101;DABC的参数与文献[30] 变异； 的设置相同，最大迭代数B=100,最大CPU时间 7)若当前迭代得到的最佳解Z≠Z,Z= 为720s:考虑到GA的运行时间较短，将MBO&NS、 min(Z,Z,t=1,A=A+1,转至2)；否则，t=t+1, GMBOAL、AGA&LS、IDABC和GMBOA的停止 执行8)： 时间设为TGA运行100次所需时间。 8)若t=T,执行9)，否则，A=A+1,转至2)： 问题产生如下：n={20,30,40,50,80,100,120,150}, 9)调用候鸟优化算法，若得到的最佳解优于 h={5,10,15,201,m,=5。借鉴Dios等7-1关于忽略 Z,更新Z,否则，保留Z不变；t=1,A=1+1,转至2)。 工序比例的设定，将本文的忽略工序比例分别 取为20%、40%和60%。每个工件在同一道工序 3仿真实验 不同机器上的处理时间P.不同且满足[1,99]之 间的均匀分布。 本文所提的遗传候鸟优化算法将全局搜索、 自适应遗传算法和候鸟优化相结合，为了验证所 3.2数据实验与结果分析 提出的算法性能，从传统算法、与其他算法结合 参数{n,h,p的不同组合产生96组问题规模， 的混合算法、解码规则、已发表的文献的算法 每种规模随机运行10个实例，取10次测试结果 4个角度选择传统遗传算法(traditional genetic al- 的平均值作为对应规模问题的测试结果。 gorithm,TGA),结合3种领域搜索结构候鸟优化 定义相对偏差为 (migrating birds optimization neighborhood R=CIGA-COMOAX100% CGMBOA search,MBO&NS)、基于最长处理时间规则解码 的遗传候鸟优化算法(genetic migrating birds op- R2= CMBO&NS-CGMBOA 100% CGMBOA timization algorithm L,GMBOAL)、结合局域搜索 R3= CGMBOA-CGMB0A×100% 的自适应遗传算法(adaptive genetic algorithm& CGMBOA local search,AGA&LS)与文献[30]的改进人工蜂 R4= CAGALS-COMBOA100% 群算法(improved artificial bee colony,.IDABC)进行 CGMBOA 对比。采用Matlab R20l4b进行编程，在CPU为 R=CIDARC-COMOA 100% CGMBOA Inter Core i5-5200U,内存为4GB,主频2.2GHz的 由于本文所提的算法迭代100次的CPU时 微机上运行。 间略长，为在较短的运行时间内测试所提算法的 3.1参数设置 有效性，兼顾算法对比的公平性，将TGA迭代100 为公平比较TGA、MBO&NS、GMBOAL、 次所需的时间作为对比算法MBO&NS、GMBOAL、 AGA&LS、IDABC和GMBOA这6种算法，TGA AGA&LS、IDABC和所提出算法GMBOA的停止 中的和山的取值通过仿真实验得到最佳的一组 条件，以此对比算法的性能，所以表1~6列出的 设置，即E=0.8和w=0.2;GMBOAL、AGA&LS和 CPU时间为TGA迭代100次的时间。表1~6列 GMBOA中的Eas、专mn、中max和bmn的取值是通过仿 出了5种算法求解不同规模问题的实验结果。 表1忽略工序比例为20%时中小规模问题的测试结果 Table 1 Testing results for small and medium scale problems with the proportion 20%of missing operations nxh TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R%R/%R/%R,/%R/%CPU时间s 20×5 209.9 208.2 184.1 176.5 188.9 172.3 21.82 20.84 6.852.44 9.63 22.01 30×5 280.1 260.3 224.2 218.1 228.4 203.7 37.51 27.79 10.067.07 12.13 25.19 40×5318.6 284.9 261.5 242.4 261.7 232.0 37.3322.8012.724.4812.80 28.84 50×5335.7 335.0 285.0 271.8 296.0 263.2 27.5527.28 8.283.2712.46 31.44 20×10337.3 355.8 299.0 285.8 300.9 277.1 21.7328.40 6.853.14 8.59 44.144）计算每个个体的适应度值，使用轮盘赌选 择法获取适应度值高的个体； 5）根据交叉概率 ξ ，从单点交叉和均匀两点交 叉 2 种方式随机选择 1 种生成新个体； 6）根据变异概率 ψ ，随机执行基于随机机器 选择的单点变异或基于机器最短处理时间的多点 变异； Z λ , Z ∗ Z ∗ = min{Z λ ,Z ∗ } t = 1 λ = λ+1 t = t + 1 7 ）若当前迭代得到的最佳解 ， ， ， ，转至 2）；否则， ， 执行 8）； 8）若 t = T ，执行 9），否则， λ = λ+1 ，转至 2）； Z ∗ Z ∗ Z ∗ t = 1 λ = λ+1 9）调用候鸟优化算法，若得到的最佳解优于 ，更新 ，否则，保留 不变； ， ，转至 2）。 3 仿真实验 本文所提的遗传候鸟优化算法将全局搜索、 自适应遗传算法和候鸟优化相结合，为了验证所 提出的算法性能，从传统算法、与其他算法结合 的混合算法、解码规则、已发表的文献的算法 4 个角度选择传统遗传算法 (traditional genetic al￾gorithm, TGA)，结合 3 种领域搜索结构候鸟优化 算法 (migrating birds optimization & neighborhood search, MBO&NS )、基于最长处理时间规则解码 的遗传候鸟优化算法 (genetic migrating birds op￾timization algorithm L, GMBOAL)、结合局域搜索 的自适应遗传算法 (adaptive genetic algorithm & local search, AGA&LS) 与文献 [30] 的改进人工蜂 群算法 (improved artificial bee colony, IDABC) 进行 对比。采用 Matlab R2014b 进行编程，在 CPU 为 Inter Core i5-5200U，内存为 4 GB，主频 2.2 GHz 的 微机上运行。 3.1 参数设置 ξ ψ ξ = 0.8 ψ = 0.2 ξmax ξmin ψmax ψmin 为公平比较 TGA、MBO&NS、 GMBOAL、 AGA&LS、IDABC 和 GMBOA 这 6 种算法，TGA 中的 和 的取值通过仿真实验得到最佳的一组 设置，即 和 ；GMBOAL、AGA&LS 和 GMBOA 中的 、 、 和 的取值是通过仿 ξmax = 0.9 ξmin = 0.5 ψmax = 0.2 ψmin = 0.02 δ = 31 γ = 10 Gmax = 10 o = 3 e = 100 e = 101 β = 100 真实验得到最佳的一组设置，即 、 、 和 ；参考文献 [22]，并经过仿真 实验测试 GMBOA 中的 、 、 、 ；基于 GA 的 4 种算法和 IDABC 的种群规模 ；由于 MBO&NS 的种群规模必须为奇数， 所以其种群规模 ；IDABC 的参数与文献 [30] 的设置相同，最大迭代数 ，最大 CPU 时间 为 720 s；考虑到 GA 的运行时间较短，将 MBO&NS、 GMBOAL、AGA&LS、IDABC 和 GMBOA 的停止 时间设为 TGA 运行 100 次所需时间。 n = {20,30,40,50,80,100,120,150} h = {5,10,15,20} ms = 5 p Pjks 问题产生如下： ， ， 。借鉴 Dios 等 [7-8] 关于忽略 工序比例的设定，将本文的忽略工序比例 分别 取为 20%、40% 和 60%。每个工件在同一道工序 不同机器上的处理时间 不同且满足 [1, 99] 之 间的均匀分布。 3.2 数据实验与结果分析 参数 {n,h, p} 的不同组合产生 96 组问题规模， 每种规模随机运行 10 个实例，取 10 次测试结果 的平均值作为对应规模问题的测试结果。 定义相对偏差为 R1 = CTGA −CGMBOA CGMBOA ×100% R2 = CMBO& NS −CGMBOA CGMBOA ×100% R3 = CGMBOAL −CGMBOA CGMBOA ×100% R4 = CAGA& LS −CGMBOA CGMBOA ×100% R5 = CIDABC −CGMBOA CGMBOA ×100% 由于本文所提的算法迭代 100 次的 CPU 时 间略长，为在较短的运行时间内测试所提算法的 有效性，兼顾算法对比的公平性，将 TGA 迭代 100 次所需的时间作为对比算法 MBO&NS、GMBOAL、 AGA&LS、IDABC 和所提出算法 GMBOA 的停止 条件，以此对比算法的性能，所以表 1~6 列出的 CPU 时间为 TGA 迭代 100 次的时间。表 1~6 列 出了 5 种算法求解不同规模问题的实验结果。 表 1 忽略工序比例为 20% 时中小规模问题的测试结果 Table 1 Testing results for small and medium scale problems with the proportion 20% of missing operations n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 20×5 209.9 208.2 184.1 176.5 188.9 172.3 21.82 20.84 6.85 2.44 9.63 22.01 30×5 280.1 260.3 224.2 218.1 228.4 203.7 37.51 27.79 10.06 7.07 12.13 25.19 40×5 318.6 284.9 261.5 242.4 261.7 232.0 37.33 22.80 12.72 4.48 12.80 28.84 50×5 335.7 335.0 285.0 271.8 296.0 263.2 27.55 27.28 8.28 3.27 12.46 31.44 20×10 337.3 355.8 299.0 285.8 300.9 277.1 21.73 28.40 6.85 3.14 8.59 44.14 第 17 卷 智 能 系 统 学 报 ·464·