第17卷 智能系统学报 ·468· 从表1~6可知： 比TGA、MBO&NS、GMBOAL、AGA&LS、ID 1)当p=20%时，对于中小规模问题，在平均 ABC产生了较好的解。 CPU时间75.63s内，由TGA、MBO&NS、 3)当p=60%时，对于中小规模问题，在平均 GMBOAL、AGA&LS、IDABC和GMBOA得到的 CPU时间63.86s内，由TGA、MBO&NS、GMBOAL 平均目标值分别为479.1、478.4、403.2、391.8、412.3、 AGA&LS、IDABC和GMBOA得到的平均目标值 381.5。GMBOA得到的目标值较TGA改进25.86%， 分别为264.2、251.9、212.2、216.8、233.5、207.5。 较MBO&NS改进25.30%，较GMBOAL改进 GMB0A的目标值较TGA改进27.12%，较 6.46%,较AGA&LS改进3.05%，较IDABC改进 MBO&NS改进20.30%，较GMBOAL改进2.39%， 8.91%。 较AGA&LS改进5.09%，较IDABC改进13.43% 对于大规模问题，在平均CPU时间166.81s 对于大规模问题，在平均CPU时间135.28s 内，由TGA、MBO&NS、GMBOAL、AGA&LS、ID- 内，由TGA、MBO&NS、GMBOAL、AGA&LS、ID- ABC和GMBOA得到的平均目标值分别为917.1、 ABC和GMBOA得到的平均目标值分别为 885.0、761.6、738.7、740.9、723.1。GMB0A的目 468.3、439.1、371.4、374.6、376.0、360.8。GMB0A 标值较TGA改进26.68%，较MBO&NS改进 的目标值较TGA改进29.83%，较MBO&NS改进 22.84%,较GMBOAL改进6.05%，较AGA&LS改 21.14%,较GMB0AL改进3.16%，较AGA&LS改 进2.00%，较DABC改进3.34%。 进4.29%、较DABC改进4.97%。 从平均性能来看，对于不同规模问题，在总平 虽然小规模问题20×10、20×15和20×20的 均时间121.22s内，TGA、MBO&NS、GMBOAL、 3个实例中GMBOA的目标值略差于AGA&LS AGA&LS、IDABC和GMBOA的平均目标值分别 或GMBOAL,但随着问题规模的增大，GMBOA 为698.1、681.7、582.4、565.3、576.6、552.3。GMB0A 得到的解的质量一致优于其他5种算法。 的目标值较TGA改进26.27%，较MBO&NS改进 从平均性能来看，对于不同规模问题，在总平 24.07%,较GMB0AL改进6.26%，较AGA&LS改 均时间99.57s内，TGA、MBO&NS、GMBOAL、 进2.53%，较DABC改进6.13%。整体来看，在相 AGA&LS、IDABC和GMBOA的平均目标值分别 同CPU时间内，GMBOA的表现明显优于TGA、 为366.3、345.5、291.8、295.7、304.8、284.2。GMB0A MBO&NS、GMBOAL、AGA&LS、IDABC. 的目标值较TGA改进28.48%，较MBO&NS改进 2)当p=40%时，对于中小规模问题，在平均 20.72%,较GMB0AL改进2.78%，较AGA&LS改 CPU时间70.15s内，由TGA、MBO&NS、GMBOAL、 进4.69%，较IDABC改进9.20%。因此，GMBOA AGA&LS、IDABC和GMBOA得到的平均目标值 表现最好，尤其是对于大规模问题。 分别为368.3、363.1、305.9、303.9、320.1、293.0。 4)综上可知，在相同CPU时间内，虽然当忽 GMB0A的目标值较TGA改进26.12%，较 略工序比例较高时GMBOA求解小规模问题的一 MBO&NS改进23.53%，较GMBOAL改进4.83%， 些实例的表现略差于其他算法，但平均性能均优 较AGA&LS改进3.82%，较DABC改进9.34%。 于TGA、MBO&NS、GMBOAL、AGA&LS、ID 对于大规模问题，在平均CPU时间151.07s ABC。 内，由TGA、MBO&NS、GMBOAL、AGA&LS、ID- 4结束语 ABC和GMBOA得到的平均目标值分别为685.0、 658.2、561.7、551.8、555.8、537.5。GMB0A的目 本文研究了含忽略工序和不相关并行机的混 标值较TGA改进26.74%，较MBO&NS改进 合流水车间调度问题，以最小化最大完工时间为 22.90%,较GMB0AL改进5.04%，较AGA&LS改 目标建立了整数规划模型，进而结合全局搜索、 进3.08%、较DABC改进4.39%。 自适应遗传算法和候鸟优化提出一种遗传候鸟优 从平均性能来看，对于不同规模问题，在总平 化算法以获取近优解。首先，设计基于机器号的 均时间110.61s内，TGA、MBO&NS、GMBOAL、 编码方案，采用全局搜索和随机程序生成初始种 AGA&LS、IDABC和GMBOA的平均目标值分别 群，然后执行随迭代进化过程而调整的自适应交 为526.7、510.7、433.8、427.9、438.0、415.3。GMB0A 叉和变异操作，从而得到改进的GA解，引入基 的目标值较TGA改进26.43%，较MBO&NS改进 于3种邻域结构的候鸟优化算法扩大解的搜索空 23.22%,较GMB0AL改进4.94%，较AGA&LS改 间以更新GA解。大量随机数据的仿真实验证明 进3.45%，较IDABC改进6.87%。因此，GMBOA 所提遗传候鸟优化算法能够在相同的CPU时间从表 1~6 可知： 1）当 p = 20% 时，对于中小规模问题，在平均 C P U 时 间 75.63 s 内 ， 由 TGA 、 MBO&NS 、 GMBOAL、AGA&LS、IDABC 和 GMBOA 得到的 平均目标值分别为 479.1、478.4、403.2、391.8、412.3、 381.5。GMBOA 得到的目标值较 TGA 改进 25.86%， 较 MBO&NS 改进 25.30%，较 GMBOAL 改进 6.46%，较 AGA&LS 改进 3.05%，较 IDABC 改进 8.91%。 对于大规模问题，在平均 CPU 时间 166.81 s 内， 由 TGA、MBO&NS、GMBOAL、AGA&LS、ID￾ABC 和 GMBOA 得到的平均目标值分别为 917.1、 885.0、761.6、738.7、740.9、723.1。GMBOA 的目 标值较 TGA 改进 26.68%，较 MBO&NS 改进 22.84%，较 GMBOAL 改进 6.05%，较 AGA&LS 改 进 2.00%，较 IDABC 改进 3.34%。 从平均性能来看，对于不同规模问题，在总平 均时间 121.22 s 内，TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 的平均目标值分别 为 698.1、681.7、582.4、565.3、576.6、552.3。GMBOA 的目标值较 TGA 改进 26.27%，较 MBO&NS 改进 24.07%，较 GMBOAL 改进 6.26%，较 AGA&LS 改 进 2.53%，较 IDABC 改进 6.13%。整体来看，在相 同 CPU 时间内，GMBOA 的表现明显优于 TGA、 MBO&NS、GMBOAL、AGA&LS、IDABC。 2）当 p = 40% 时，对于中小规模问题，在平均 CPU 时间 70.15 s 内，由 TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 得到的平均目标值 分别为 368.3、363.1、305.9、303.9、320.1、293.0。 GMBO A 的目标值 较 T G A 改 进 26.12% ， 较 MBO&NS 改进 23.53%，较 GMBOAL 改进 4.83%， 较 AGA&LS 改进 3.82%，较 IDABC 改进 9.34%。 对于大规模问题，在平均 CPU 时间 151.07 s 内， 由 TGA、MBO&NS、GMBOAL、AGA&LS、ID￾ABC 和 GMBOA 得到的平均目标值分别为 685.0、 658.2、561.7、551.8、555.8、537.5。GMBOA 的目 标值较 TGA 改进 26.74%，较 MBO&NS 改进 22.90%，较 GMBOAL 改进 5.04%，较 AGA&LS 改 进 3.08%、较 IDABC 改进 4.39%。 从平均性能来看，对于不同规模问题，在总平 均时间 110.61 s 内，TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 的平均目标值分别 为 526.7、510.7、433.8、427.9、438.0、415.3。GMBOA 的目标值较 TGA 改进 26.43%，较 MBO&NS 改进 23.22%，较 GMBOAL 改进 4.94%，较 AGA&LS 改 进 3.45%，较 IDABC 改进 6.87%。因此，GMBOA 比 TGA、MBO&NS、GMBOAL、AGA&LS、ID￾ABC 产生了较好的解。 3）当 p = 60% 时，对于中小规模问题，在平均 CPU 时间 63.86 s 内，由 TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 得到的平均目标值 分别为 264.2、251.9、212.2、216.8、233.5、207.5。 GMBO A 的目标值 较 T G A 改 进 27.12% ， 较 MBO&NS 改进 20.30%，较 GMBOAL 改进 2.39%， 较 AGA&LS 改进 5.09%，较 IDABC 改进 13.43%。 对于大规模问题，在平均 CPU 时间 135.28 s 内， 由 TGA、MBO&NS、GMBOAL、AGA&LS、ID￾A BC 和 GMBO A 得到的平均目标值分别 为 468.3、439.1、371.4、374.6、376.0、360.8。GMBOA 的目标值较 TGA 改进 29.83%，较 MBO&NS 改进 21.14%，较 GMBOAL 改进 3.16%，较 AGA&LS 改 进 4.29%、较 IDABC 改进 4.97%。 虽然小规模问题 20×10、20×15 和 20×20 的 3 个实例中 GMBOA 的目标值略差于 AGA&LS 或 GMBOAL，但随着问题规模的增大，GMBOA 得到的解的质量一致优于其他 5 种算法。 从平均性能来看，对于不同规模问题，在总平 均时间 99.57s 内 ，TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 的平均目标值分别 为 366.3、345.5、291.8、295.7、304.8、284.2。GMBOA 的目标值较 TGA 改进 28.48%，较 MBO&NS 改进 20.72%，较 GMBOAL 改进 2.78%，较 AGA&LS 改 进 4.69%，较 IDABC 改进 9.20%。因此，GMBOA 表现最好，尤其是对于大规模问题。 4）综上可知，在相同 CPU 时间内，虽然当忽 略工序比例较高时 GMBOA 求解小规模问题的一 些实例的表现略差于其他算法，但平均性能均优 于 TGA、MBO&NS、GMBOAL、AGA&LS、ID￾ABC。 4 结束语 本文研究了含忽略工序和不相关并行机的混 合流水车间调度问题，以最小化最大完工时间为 目标建立了整数规划模型，进而结合全局搜索、 自适应遗传算法和候鸟优化提出一种遗传候鸟优 化算法以获取近优解。首先，设计基于机器号的 编码方案，采用全局搜索和随机程序生成初始种 群，然后执行随迭代进化过程而调整的自适应交 叉和变异操作，从而得到改进的 GA 解，引入基 于 3 种邻域结构的候鸟优化算法扩大解的搜索空 间以更新 GA 解。大量随机数据的仿真实验证明 所提遗传候鸟优化算法能够在相同的 CPU 时间 第 17 卷 智 能 系 统 学 报 ·468·