Solving the JSP problem using a hybrid CHIO algorithm based on quantum computing and Weibull distribution
-
摘要: 针对冠状病毒群免疫优化算法（coronavirus herd immunity optimizer , CHIO）在解决优化问题时存在易陷入局部最优解、收敛速度慢和收敛精度差等问题，文章提出一种量子混合CHIO算法（quantum hybrid coronavirus herd immunity optimizer，QCHIO）。首先，引入量子计算的思想，通过量子相关性实现全局搜索和快速收敛的目标，能够有效避免算法陷入局部最优解的问题。其次，采用威布尔分布算子的大步长和小步长来增加算法的多样性，使算法能够更好地探索搜索空间，增强了算法的全局开发能力。此外，还引入$\beta $-登山算子通过搜索当前最优解的邻域，尝试找到更优的解，从而增加了算法的搜索宽度，改善了解的质量。多邻域搜索则通过搜索全局最优解的多个邻域来增加了算法的收敛精度。为验证其性能，将QCHIO应用到10种标准算例中与其他几种改进算法进行了对比分析，并通过显著性检验证明了QCHIO的优越性。最后将QCHIO应用到某发动机生产调度实例上，进一步证明了QCHIO的可行性和优越性。Abstract: A quantum hybrid coronavirus herd immunity optimizer (QCHIO) algorithm is proposed to address the issues of local optima trapping, slow convergence speed, and poor convergence accuracy in the Coronavirus herd immunity optimizer (CHIO) algorithm. Firstly, the concept of quantum computing is introduced to achieve the goals of global search and fast convergence through quantum correlations, effectively avoiding the problem of the algorithm getting trapped in local optima. Secondly, the algorithm enhances its global exploration capability by utilizing both large and small step sizes of the Weibull distribution operator to increase algorithm diversity and better explore the search space. Additionally, the hill-climbing operator is introduced to search the neighborhood of the current best solution, attempting to find better solutions and thereby increasing the algorithm’s search breadth and improving the quality of solutions. Multi-neighborhood search further enhances the convergence accuracy of the algorithm by searching multiple neighborhoods of the global optimum. To validate its performance, QCHIO is applied to 10 standard test cases and compared with other improved algorithms, demonstrating its superiority through significant testing. Finally, the feasibility and superiority of QCHIO are further demonstrated by applying it to a case of engine production scheduling.
-
表 2 消融实验结果
算法 已知最优解 CHIO QCHIO ICHIO1 ICHIO2 ICHIO3 ICHIO4 算例及规模 best avg best avg best avg best avg best avg best avg FT06(6×6) 55 55 55 55 55 55 55 55 55 55 55 55 55 FT10(10×10) 930 1 023 1 083 966 1 014 979 1 014 996 1 021 986 1 035 967 1 018 FT20(20×5) 1 165 1 338 1 401 1 185 1 253 1 197 1 259 1 198 1 259 1 286 1 322 1 202 1 262 LA01(10×5) 666 666 669 666 666 666 666 666 666 666 666 666 666 LA11(20×5) 1 222 1 222 1 222 1 222 1 222 1 222 1 222 1 222 1 222 1 222 1 222 1 222 1 222 LA16(10×10) 945 986 1 021 956 987 979 990 959 988 973 1 004 967 1 018 LA21(15×10) 1 046 1 218 1 260 1 109 1 160 1 114 1 158 1 141 1 171 1 126 1 185 1 161 1 195 LA26(20×10) 1 218 1 433 1 507 1 275 1 357 1 320 1 358 1 283 1 368 1 334 1 377 1 372 1 411 LA31(30×10) 1 784 2 019 2 079 1 807 1 868 1 824 1 877 1 848 1 883 1 833 1 882 1 950 2 004 LA36(15×15) 1 268 1 519 1 569 1 355 1 434 1 401 1 439 1 398 1 438 1 407 1 464 1 443 1 486 
下载: 导出CSV
表 3 QCHIO与部分改进算法在算例上的对比
（%） 算法对照 相对CHIO 相对ISSA 相对QSTA 相对MGEFO 算例及规模 ∆best ∆avg ∆best ∆avg ∆best ∆avg ∆best ∆avg FT06(6×6) － 0.7 － － － 0.8 － 1.8 FT10(10×10) 5.6 6.4 － 2.1 － 1.2 － 2.6 FT20(20×5) 11.4 10.6 － 3.1 2.0 3.3 2.5 6.6 LA01(10×5) － 0.4 － － － 0.6 － 0.3 LA11(20×5) － － － － － － － － LA16(10×10) 2.7 3.2 － 2.0 － 2.9 1.3 2.1 LA21(15×10) 8.9 7.9 － 1.4 1.9 6.6 0.8 0.6 LA26(20×10) 9.6 10.0 － 1.3 0.7 5.4 2.9 4.2 LA31(30×10) 10.5 10.1 － 0.4 － 4.7 － 0.4 LA36(15×15) 10.8 8.6 － 0.2 0.5 4.7 2.7 2.3
下载: 导出CSV
表 4 QCHIO相对于CHIO、ISSA、QSTA、MGEFO的提升水平
（%） 算法对照 相对CHIO 相对ISSA 相对QSTA 相对MGEFO 算例及规模 ∆best ∆avg ∆best ∆avg ∆best ∆avg ∆best ∆avg FT06(6×6) － 0.7 － － － 0.8 － 1.8 FT10(10×10) 5.6 6.4 － 2.1 － 1.2 － 2.6 FT20(20×5) 11.4 10.6 － 3.1 2.0 3.3 2.5 6.6 LA01(10×5) － 0.4 － － － 0.6 － 0.3 LA11(20×5) － － － － － － － － LA16(10×10) 2.7 3.2 － 2.0 － 2.9 1.3 2.1 LA21(15×10) 8.9 7.9 － 1.4 1.9 6.6 0.8 0.6 LA26(20×10) 9.6 10.0 － 1.3 0.7 5.4 2.9 4.2 LA31(30×10) 10.5 10.1 － 0.4 － 4.7 － 0.4 LA36(15×15) 10.8 8.6 － 0.2 0.5 4.7 2.7 2.3
下载: 导出CSV
表 5 各算法配对t检验结果
算法 平均值差值 差值95% CI 差值标准差 Cohen's d 值 t p QCHIO配对CHIO －84.8 －138.668 ～ －30.932 75.302 1.126 －3.561 0.006** QCHIO配对ISSA －12.5 －21.669 ～ －3.331 12.817 0.975 －3.084 0.013* QCHIO配对QSTA －41.2 －67.533 ～ －14.867 36.811 1.119 －3.539 0.006** QCHIO配对MGEFO －24.7 －45.499 ～ －3.901 29.075 0.85 －2.686 0.025* 其中 *表示 p<0.05 ； **表示 p<0.01
下载: 导出CSV
表 6 各工件加工工艺
工序/工件 工序1 工序2 工序3 工序4 工序5 工序6 气缸体 粗车加工 精车加工 镗床 铣床 钻床 磨床 气缸盖衬垫 粗车加工 精车加工 镗床 钻床 磨床 铣床 轴承座 粗车加工 精车加工 镗床 钻床 铣床 磨床 油底壳 粗车加工 精车加工 铣床 磨床 镗床 钻床 气缸盖 粗车加工 精车加工 钻床 镗床 磨床 铣床 飞轮 粗车加工 精车加工 磨床 钻床 铣床 镗床 曲轮轴架 粗车加工 精车加工 铣床 镗床 钻床 磨床 曲轮轴盖 粗车加工 精车加工 钻床 铣床 磨床 镗床 曲轴 粗车加工 精车加工 镗床 铣床 钻床 磨床 正时带上盖 粗车加工 精车加工 铣床 钻床 磨床 镗床
下载: 导出CSV
表 7 各工件加工时长
min 机床/工件 粗加工车 M1 精加工车 M2 镗床M3 铣床M4 磨床M5 钻床M6 总时长 气缸体 J1 6 12 12 6 4 8 48 气缸盖衬垫J2 4 8 6 5 3 3 29 轴承座J3 3 9 8 7 3 5 35 油底壳J4 6 11 10 8 5 4 44 气缸盖J5 6 10 7 9 4 6 42 飞轮J6 5 11 5 7 8 3 39 曲轮轴架J7 7 13 9 10 4 3 46 曲轮轴盖J8 4 8 8 6 4 3 33 曲轴J9 8 13 10 8 9 4 52 正时带上盖J10 4 7 6 5 3 3 28
下载: 导出CSV
-
[1] Yazdani M,Aleti A,Khalili S M,et al. Optimising the sum of maximum earliness and tardiness of the Job-Shop scheduling problem[J]. Computers & Industrial Engineering,2017,107(5):12-24. [2] 刘丽娜,南新元,石跃飞. 改进麻雀搜索算法求解作业车间调度问题[J]. 计算机应用研究,2021,38(12):3634-3639. [3] 吴贝贝,李喆. 基于量子状态转移算法的作业车间调度问题[J]. 计算机应用与软件,2021,38(7):232-239. [4] 陈斌,马良,刘勇. 一种多策略引导的电磁场优化算法求解作业车间调度问题[J]. 运筹与管理,2021,30(11):84-91. [5] 亓祥波,王宏伟,马志强. 基于交叉选择的变邻域蜂群算法求解置换流水车间调度问题[J]. 制造技术与机床,2023(5):179-187. [6] Al-Betar M A,Alyasseri Z A A,Awadallah M A,et al. Coronavirus herd immunity optimizer (CHIO)[J]. Neural Computing and Applications,2021,33:5011-5042. doi: 10.1007/s00521-020-05296-6 [7] Dalbah L M,Al-Betar M A,Awadallah M A,et al. A modified coronavirus herd immunity optimizer for capacitated vehicle routing problem[J]. Journal of King Saud University-Computer and Information Sciences,2022,34(8):4782-4795. doi: 10.1016/j.jksuci.2021.06.013 [8] Yan C,Razmjooy N. Kidney stone detection using an optimized deep believe network by fractional coronavirus herd immunity optimizer[J]. Biomedical Signal Processing and Control,2023,86:104951. doi: 10.1016/j.bspc.2023.104951 [9] Kumar C,Magdalin Maryb D,Gunasekar T. MOCHIO:a novel multi-objective coronavirus herd immunity optimization algorithm for solving brushless direct current wheel motor design optimization problem[J]. Automatika,2022,63(1):149-170. doi: 10.1080/00051144.2021.2014035 [10] 王永名,尹红丽,秦开大. 作业车间调度理论及其优化方法研究[M]. 北京:科学出版社,2013. [11] 高洪元,刁鸣. 量子群智能及其在通信技术中的应用[M]. 北京:电子工业出版社,2016. [12] Sahoo S K,Sharma S,Saha A K. A novel variant of moth flame optimizer for higher dimensional optimization problems[J]. Journal of Bionic Engineering,2023:1-27. [13] Al-Betar M A. β-Hill climbing:an exploratory local search[J]. Neural Computing and Applications,2017,28(S1):153-168. doi: 10.1007/s00521-016-2328-2 [14] 潘全科,王文宏,朱剑英,等. 基于粒子群优化和变邻域搜索的混合调度算法[J]. 计算机集成制造系统,2007,13(2):323-328. [15] 王宁. 基于改进蚁群算法的Job-shop车间调度研究[D]. 大连:大连海事大学,2021. [16] 魏亮旗. 基于改进人工蜂群算法的车间调度优化的研究与应用[D]. 合肥:安徽大学,2019. -
下载:
点击查看大图
图(5) / 表(8)
计量
- 文章访问数: 72
- HTML全文浏览量: 8
- PDF下载量: 12
- 被引次数: 0
