量子鲸鱼优化算法求解作业车间调度问题
|
摘要
为了克服基本鲸鱼优化算法(WOA)在解决作业车间调度问题时存在收敛精度低、容易陷入局部最优的缺陷,利用量子计算与优化思想提出了一种量子鲸鱼优化算法(QWOA),并对其进行了计算复杂度分析、全局收敛性证明及仿真实验。通过对11个作业车间调度问题基准算例的仿真实验发现,与基本鲸鱼优化算法、布谷鸟搜索算法(CS)、灰狼优化算法(GWO)相比,QWOA算法在最小值、平均值、寻优成功率等方面具有较优结果。研究表明,量子鲸鱼优化算法在解决作业车间调度问题时,具有更高的收敛精度和更好的全局搜索能力,且能够跳出局部最优。
To overcome whale optimization algorithm's disadvantages of poor convergence and being easily trapped in local optima in solving Job-Shop scheduling problem,this paper proposed a quantum whale optimization algorithm( QWOA) based on the idea of quantum computation. Then it provided the computational complexity analysis,global convergence proof and simulation experiments of QWOA. Based on a set of 11 JSP benchmark instances,the simulation experiments show that QWOA has better results than whale optimization algorithm( WOA),cuckoo search( CS) and grey wolf optimizer( GWO),in the minimum value,average value and success rate. Finally,this paper concludes that QWOA has the merits of higher convergence accuracy,higher local optima avoidance and better exploration.
To overcome whale optimization algorithm's disadvantages of poor convergence and being easily trapped in local optima in solving Job-Shop scheduling problem,this paper proposed a quantum whale optimization algorithm( QWOA) based on the idea of quantum computation. Then it provided the computational complexity analysis,global convergence proof and simulation experiments of QWOA. Based on a set of 11 JSP benchmark instances,the simulation experiments show that QWOA has better results than whale optimization algorithm( WOA),cuckoo search( CS) and grey wolf optimizer( GWO),in the minimum value,average value and success rate. Finally,this paper concludes that QWOA has the merits of higher convergence accuracy,higher local optima avoidance and better exploration.
引文
[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]Mirjalili S,Lewis A.The whale optimization algorithm[J].Advances in Engineering Software,2016,95(5):51-67.
[3]Trivedi I N,Bhoye M,Bhesdadiya R H,et al.An emission constraint environment dispatch problem solution with microgrid using whale optimization algorithm[C]//Proc of Power Systems Conference.Piscataway,NJ:IEEE Press,2017:1-6.
[4]Prakash D B,Lakshminarayana C.Optimal siting of capacitors in radial distribution network using whale optimization algorithm[J].Alexandria Engineering Journal,2016,56(4):499-509.
[5]Dao T K,Pan T S,Pan J S.A multi-objective optimal mobile robot path planning based on whale optimization algorithm[C]//Proc of the13th IEEE International Conference on Signal Processing.Piscataway,NJ:IEEE Press,2017:337-342.
[6]Kaveh A,Ghazaan M I.Enhanced whale optimization algorithm for sizing optimization of skeletal structures[J].Mechanics Based Design of Structures&Machines,2017,45(3):345-362.
[7]Oliva D,Aziz M A E,Hassanien A E.Parameter estimation of photovoltaic cells using an improved chaotic whale optimization algorithm[J].Applied Energy,2017,200(8):141-154.
[8]Jangir P,Trivedi I N,Jangir N,et al.A novel adaptive whale optimization algorithm for global optimization[J].Indian Journal of Science&Technology,2016,9(38):DOI:10.17485/ijst/2016/v9i38/101939.
[9]Ling Ying,Zhou Yongquan,Luo Qifang.Lévy flight trajectory-based whale optimization algorithm for global optimization[J].IEEE Access,2017,5(99):6168-6186.
[10]钟明辉,龙文.一种随机调整控制参数的鲸鱼优化算法[J].科学技术与工程,2017,17(12):68-73.(Zhong Minghui,Long Wen.Whale optimization algorithm based on stochastic adjustment control parameter[J].Science Technology and Engineering,2017,17(12):68-73.)
[11]刘竹松,李生.正余混沌双弦鲸鱼优化算法[J].计算机工程与应用,2018,54(7):159-163,212.(Liu Zhusong,Li Sheng.Whale optimization algorithm based on chaotic sine cosine operator[J].Computer Engineering and Applications,2018,54(7):159-163,212.)
[12]Cheng T C E,Peng Bo,Lyu Zhipeng.A hybrid evolutionary algorithm to solve the job shop scheduling problem[J].Annals of Operations Research,2016,242(2):223-237.
[13]Dey S,Saha I,Bhattacharyya S,et al.Multi-level thresholding using quantum inspired meta-heuristics[J].Knowledge-Based Systems,2014,67(3):373-400.
[14]高洪元,刁鸣.量子群智能及其在通信技术中的应用[M].北京:电子工业出版社,2016.(Gao Hongyuan,Diao Ming.Quantum swarm intelligence and its application in communication technology[M].Beijing:Publishing House of Electronics Industry,2016.)
[15]Fang Wei,Sun Jun,Chen Huanhuan,et al.A decentralized quantuminspired particle swarm optimization algorithm with cellular structured population[J].Information Sciences,2016,330(C):19-48.
[16]姚远远,叶春明.求解作业车间调度问题的改进混合灰狼优化算法[J].计算机应用研究,2018,35(5):1310-1314.(Yao Yuanyuan,Ye Chunming.Solving Job-Shop scheduling problem using improved hybrid grey wolf optimizer[J].Application Research of Computers,2018,35(5):1310-1314.)
[17]Mirjalili S.How effective is the grey wolf optimizer in training multilayer perceptrons[J].Applied Intelligence,2015,43(1):150-161.
[18]Li Xiangtao,Yin Minghao.Modified cuckoo search algorithm with self adaptive parameter method[J].Information Sciences,2015,298(C):80-97.
[2]Mirjalili S,Lewis A.The whale optimization algorithm[J].Advances in Engineering Software,2016,95(5):51-67.
[3]Trivedi I N,Bhoye M,Bhesdadiya R H,et al.An emission constraint environment dispatch problem solution with microgrid using whale optimization algorithm[C]//Proc of Power Systems Conference.Piscataway,NJ:IEEE Press,2017:1-6.
[4]Prakash D B,Lakshminarayana C.Optimal siting of capacitors in radial distribution network using whale optimization algorithm[J].Alexandria Engineering Journal,2016,56(4):499-509.
[5]Dao T K,Pan T S,Pan J S.A multi-objective optimal mobile robot path planning based on whale optimization algorithm[C]//Proc of the13th IEEE International Conference on Signal Processing.Piscataway,NJ:IEEE Press,2017:337-342.
[6]Kaveh A,Ghazaan M I.Enhanced whale optimization algorithm for sizing optimization of skeletal structures[J].Mechanics Based Design of Structures&Machines,2017,45(3):345-362.
[7]Oliva D,Aziz M A E,Hassanien A E.Parameter estimation of photovoltaic cells using an improved chaotic whale optimization algorithm[J].Applied Energy,2017,200(8):141-154.
[8]Jangir P,Trivedi I N,Jangir N,et al.A novel adaptive whale optimization algorithm for global optimization[J].Indian Journal of Science&Technology,2016,9(38):DOI:10.17485/ijst/2016/v9i38/101939.
[9]Ling Ying,Zhou Yongquan,Luo Qifang.Lévy flight trajectory-based whale optimization algorithm for global optimization[J].IEEE Access,2017,5(99):6168-6186.
[10]钟明辉,龙文.一种随机调整控制参数的鲸鱼优化算法[J].科学技术与工程,2017,17(12):68-73.(Zhong Minghui,Long Wen.Whale optimization algorithm based on stochastic adjustment control parameter[J].Science Technology and Engineering,2017,17(12):68-73.)
[11]刘竹松,李生.正余混沌双弦鲸鱼优化算法[J].计算机工程与应用,2018,54(7):159-163,212.(Liu Zhusong,Li Sheng.Whale optimization algorithm based on chaotic sine cosine operator[J].Computer Engineering and Applications,2018,54(7):159-163,212.)
[12]Cheng T C E,Peng Bo,Lyu Zhipeng.A hybrid evolutionary algorithm to solve the job shop scheduling problem[J].Annals of Operations Research,2016,242(2):223-237.
[13]Dey S,Saha I,Bhattacharyya S,et al.Multi-level thresholding using quantum inspired meta-heuristics[J].Knowledge-Based Systems,2014,67(3):373-400.
[14]高洪元,刁鸣.量子群智能及其在通信技术中的应用[M].北京:电子工业出版社,2016.(Gao Hongyuan,Diao Ming.Quantum swarm intelligence and its application in communication technology[M].Beijing:Publishing House of Electronics Industry,2016.)
[15]Fang Wei,Sun Jun,Chen Huanhuan,et al.A decentralized quantuminspired particle swarm optimization algorithm with cellular structured population[J].Information Sciences,2016,330(C):19-48.
[16]姚远远,叶春明.求解作业车间调度问题的改进混合灰狼优化算法[J].计算机应用研究,2018,35(5):1310-1314.(Yao Yuanyuan,Ye Chunming.Solving Job-Shop scheduling problem using improved hybrid grey wolf optimizer[J].Application Research of Computers,2018,35(5):1310-1314.)
[17]Mirjalili S.How effective is the grey wolf optimizer in training multilayer perceptrons[J].Applied Intelligence,2015,43(1):150-161.
[18]Li Xiangtao,Yin Minghao.Modified cuckoo search algorithm with self adaptive parameter method[J].Information Sciences,2015,298(C):80-97.