基于量子进化算法的多轮廓路径优化
|
摘要
针对多轮廓样片加工快进路径优化问题,提出一种改进的量子进化算法。算法设计了基于二维量子位概率幅矩阵模型的快进路径编码方法,实现了由该模型引导的全局搜索,能直接生成样片加工的顺序序列,解码效率高;利用多轮廓加工最优子结构的特征,设计了基于动态规划法的个体适应度评价方法;新的动态旋转角的量子更新策略增强了种群的全局搜索能力。通过标准算例仿真和算法对比实验结果,验证了所提算法的可行性和有效性。
To solve the optimization problem of fast forward path for multi-contour processing,an Improved Quantum Evolutionary Algorithm(IQEA)was proposed.The coding method of fast forward path based on two-dimensional Qubit Measurement Model(QMM)was designed,and the global searching guided by QMM was realized to generate the machining sequence of multi-segment.The decoding efficiency was higher in IQEA.By using the optimal substructure of multi-contour processing,the evaluation method of individual fitness based on dynamic programming algorithm was designed.The global searching ability of population was enhanced by the new dynamic rotation angle in quantum updating strategy.The simulation results and comparative experiments on classic benchmarks demonstrated the feasibility and effectiveness of the presented IQEA.
To solve the optimization problem of fast forward path for multi-contour processing,an Improved Quantum Evolutionary Algorithm(IQEA)was proposed.The coding method of fast forward path based on two-dimensional Qubit Measurement Model(QMM)was designed,and the global searching guided by QMM was realized to generate the machining sequence of multi-segment.The decoding efficiency was higher in IQEA.By using the optimal substructure of multi-contour processing,the evaluation method of individual fitness based on dynamic programming algorithm was designed.The global searching ability of population was enhanced by the new dynamic rotation angle in quantum updating strategy.The simulation results and comparative experiments on classic benchmarks demonstrated the feasibility and effectiveness of the presented IQEA.
引文
[1]HOU Yuanbin,GAO Yangdong,ZHENG Maoquan.Optimization empty run for multiple contour mixed path processing based on greedy and genetic algorithm[J].Journal of Mechanical Engineering,2013,49(21):153-159(in Chinese).[侯媛彬,高阳东,郑茂全.基于贪心遗传算法的混合轨迹加工走刀空行程路径优化[J].机械工程学报,2013,49(21):153-159.]
[2]OYSU C,BINGUL Z.Application of heuristic and hybridGASA algorithms to tool-path optimization problem for minimizing airtime during machining[J].Engineering Applications of Artificial Intelligence,2009,22(3):389-396.
[3]BONTOUX B,ARTIGUES C,FEILLET D.A Memetic Algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem[J].Computers&Operations Research,2010,37(11):1844-1852.
[4]ARDALAN Z,KARIMI S,POURSABZI O,et al.A novel imperialist competitive algorithm for generalized traveling salesman problems[J].Applied Soft Computing,2015,26(1):546-555.
[5]TASGETIREN M,SUGANTHAN P N,QUAN K E.An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem[J].Applied Mathematics and Computation,2010,215(9):3356-3368.
[6]YANG Jinhui,SHI Xiaohu,MARCHESE M,et al.An ant colony optimization method for generalized TSP problem[J].Progress in Natural Science,2008,18(11):1417-1422.
[7]KARAPETYAN D,GUTIN G.Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem[J].European Journal of Operational Research,2012,219(2):234-251.
[8]WU C G,LIANG Y C,LEE H P,et al.Generalized chromosome genetic algorithm for generalized traveling salesman problems and its applications for machining[J].Physical Review,2004,70(1):1-13.
[9]SNYDER L V,DASKIN M S.A random key genetic algorithm for the generalized traveling salesman problem[J].European Journal of Operational Research,2006,174(1):38-53.
[10]NARAYANAN A,MOORE M.Quantum inspired genetic algorithms[C]//Proceedings of the 1996IEEE International Conference on Evolutionary Computation.Piscataway,N.J.,USA:IEEE Press,1996:41-66.
[11]HAN K,KIM J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J].IEEE Transactions on Evolutionary Computation,2003,6(6):580-593.
[12]PATVARDHAN C,BANSAL S,SRIVASTAV A.Solving the 0-1quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm[J].Journal of Computational&Applied Mathematics,2015,285(1):86-99.
[13]GU J,GU M,CAO C,et al.A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem[J].Computers&Operations Research,2010,37(5):927-937.
[14]ZHAO Yanwei,LI Chuan,ZHANG Jingling,et al.Novel algorithm for multi-objective vehicle routing problem with stochastic demand[J].Computer Integrated Manufacturing Systems,2012,18(3):523-530(in Chinese).[赵燕伟,李川,张景玲,等.一种新的求解多目标随机需求车辆路径问题的算法[J].计算机集成制造系统,2012,18(3):523-530.]
[15]QIAN Jie,WANG Baohua,ZHENG Jianguo,et al.A quantum evolutionary algorithm for quadratic multiple knapsack problem[J].Chinese Journal of Computers,2015,38(8):1518-1528(in Chinese).[钱洁,王保华,郑建国,等.多重二次背包问题的量子进化求解算法[J].计算机学报,2015,38(8):1518-1528.]
[16]LIU Xiaobing,JIAO Xuan,NING Tao,et al.Flexible job shop scheduling based on double chains quantum genetic algorithm[J].Computer Integrated Manufacturing Systems,2015,21(2):495-502(in Chinese).[刘晓冰,焦璇,宁涛,等.基于双链量子遗传算法的柔性作业车间调度[J].计算机集成制造系统,2015,21(2):495-502.]
[17]CAO Gaoli,HU Rong,QIAN Bin,et al.Effective hybrid quantum evolutionary algorithm for capacitated vehicle problem[J].Computer Integrated Manufacturing Systems,2015,21(4):1101-1113(in Chinese).[曹高立,胡蓉,钱斌,等.一种有效混合量子进化算法求解带容量约束的车辆路径优化问题[J].计算机集成制造系统,2015,21(4):1101-1113.]
[18]ALKAYA A,DUMAN E.Application of Sequence-Dependent Traveling Salesman Problem in Printed Circuit Board Assembly[J].IEEE Transactions on Components Packaging&Manufacturing Technology,2013,3(6):1063-1076.
[19]ADIL B,ZEYNEP D U.A multi-agent based approach to modeling and solving dynamic generalized travelling salesman problem[J].Journal of Intelligent&Fuzzy Systems,2016,31(1):77-90.
[20]WANG Yuping,LI Yinghua,DANG Chuangying.A novel globally convergent hybrid evolutionary algorithm for traveling salesman problems[C]//Proceedings of the 3rd International Conference on Machine Learning and Cybernetics.Washington,D.C.,USA:IEEE,2004:2485-2489.
[21]BISWAS A,RANJAN D,ZUBAIR M,et al.A dynamic programming algorithm for finding the optimal placement of a secondary structure topology in cryo-EM Data[J].Journal of Computational Biology,2015,22(9):837-843.
[22]CHE A,WU P,CHU F,et al.Improved Quantum-Inspired Evolutionary Algorithm for Large-Size Lane Reservation[J].IEEE Transactions on Systems Man&Cybernetics Systems,2015,45(12):1535-1548.
[23]FU Wenyuan,LING Chaodong.Brownian motion based simulated annealing algorithm[J].Chinese Journal of Computers,2014,37(6):1301-1308(in Chinese).[傅文渊,凌朝东.布朗运动模拟退火算法[J].计算机学报,2014,37(6):1301-1308.]
[24]PLATEL M D,SCHLIEBS S,KASABOV N.Quantum-inspired evolutionary algorithm:a multimodel EDA[J].IEEE Transactions on Evolutionary Computation,2009,13(6):1218-1232.
[2]OYSU C,BINGUL Z.Application of heuristic and hybridGASA algorithms to tool-path optimization problem for minimizing airtime during machining[J].Engineering Applications of Artificial Intelligence,2009,22(3):389-396.
[3]BONTOUX B,ARTIGUES C,FEILLET D.A Memetic Algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem[J].Computers&Operations Research,2010,37(11):1844-1852.
[4]ARDALAN Z,KARIMI S,POURSABZI O,et al.A novel imperialist competitive algorithm for generalized traveling salesman problems[J].Applied Soft Computing,2015,26(1):546-555.
[5]TASGETIREN M,SUGANTHAN P N,QUAN K E.An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem[J].Applied Mathematics and Computation,2010,215(9):3356-3368.
[6]YANG Jinhui,SHI Xiaohu,MARCHESE M,et al.An ant colony optimization method for generalized TSP problem[J].Progress in Natural Science,2008,18(11):1417-1422.
[7]KARAPETYAN D,GUTIN G.Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem[J].European Journal of Operational Research,2012,219(2):234-251.
[8]WU C G,LIANG Y C,LEE H P,et al.Generalized chromosome genetic algorithm for generalized traveling salesman problems and its applications for machining[J].Physical Review,2004,70(1):1-13.
[9]SNYDER L V,DASKIN M S.A random key genetic algorithm for the generalized traveling salesman problem[J].European Journal of Operational Research,2006,174(1):38-53.
[10]NARAYANAN A,MOORE M.Quantum inspired genetic algorithms[C]//Proceedings of the 1996IEEE International Conference on Evolutionary Computation.Piscataway,N.J.,USA:IEEE Press,1996:41-66.
[11]HAN K,KIM J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J].IEEE Transactions on Evolutionary Computation,2003,6(6):580-593.
[12]PATVARDHAN C,BANSAL S,SRIVASTAV A.Solving the 0-1quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm[J].Journal of Computational&Applied Mathematics,2015,285(1):86-99.
[13]GU J,GU M,CAO C,et al.A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem[J].Computers&Operations Research,2010,37(5):927-937.
[14]ZHAO Yanwei,LI Chuan,ZHANG Jingling,et al.Novel algorithm for multi-objective vehicle routing problem with stochastic demand[J].Computer Integrated Manufacturing Systems,2012,18(3):523-530(in Chinese).[赵燕伟,李川,张景玲,等.一种新的求解多目标随机需求车辆路径问题的算法[J].计算机集成制造系统,2012,18(3):523-530.]
[15]QIAN Jie,WANG Baohua,ZHENG Jianguo,et al.A quantum evolutionary algorithm for quadratic multiple knapsack problem[J].Chinese Journal of Computers,2015,38(8):1518-1528(in Chinese).[钱洁,王保华,郑建国,等.多重二次背包问题的量子进化求解算法[J].计算机学报,2015,38(8):1518-1528.]
[16]LIU Xiaobing,JIAO Xuan,NING Tao,et al.Flexible job shop scheduling based on double chains quantum genetic algorithm[J].Computer Integrated Manufacturing Systems,2015,21(2):495-502(in Chinese).[刘晓冰,焦璇,宁涛,等.基于双链量子遗传算法的柔性作业车间调度[J].计算机集成制造系统,2015,21(2):495-502.]
[17]CAO Gaoli,HU Rong,QIAN Bin,et al.Effective hybrid quantum evolutionary algorithm for capacitated vehicle problem[J].Computer Integrated Manufacturing Systems,2015,21(4):1101-1113(in Chinese).[曹高立,胡蓉,钱斌,等.一种有效混合量子进化算法求解带容量约束的车辆路径优化问题[J].计算机集成制造系统,2015,21(4):1101-1113.]
[18]ALKAYA A,DUMAN E.Application of Sequence-Dependent Traveling Salesman Problem in Printed Circuit Board Assembly[J].IEEE Transactions on Components Packaging&Manufacturing Technology,2013,3(6):1063-1076.
[19]ADIL B,ZEYNEP D U.A multi-agent based approach to modeling and solving dynamic generalized travelling salesman problem[J].Journal of Intelligent&Fuzzy Systems,2016,31(1):77-90.
[20]WANG Yuping,LI Yinghua,DANG Chuangying.A novel globally convergent hybrid evolutionary algorithm for traveling salesman problems[C]//Proceedings of the 3rd International Conference on Machine Learning and Cybernetics.Washington,D.C.,USA:IEEE,2004:2485-2489.
[21]BISWAS A,RANJAN D,ZUBAIR M,et al.A dynamic programming algorithm for finding the optimal placement of a secondary structure topology in cryo-EM Data[J].Journal of Computational Biology,2015,22(9):837-843.
[22]CHE A,WU P,CHU F,et al.Improved Quantum-Inspired Evolutionary Algorithm for Large-Size Lane Reservation[J].IEEE Transactions on Systems Man&Cybernetics Systems,2015,45(12):1535-1548.
[23]FU Wenyuan,LING Chaodong.Brownian motion based simulated annealing algorithm[J].Chinese Journal of Computers,2014,37(6):1301-1308(in Chinese).[傅文渊,凌朝东.布朗运动模拟退火算法[J].计算机学报,2014,37(6):1301-1308.]
[24]PLATEL M D,SCHLIEBS S,KASABOV N.Quantum-inspired evolutionary algorithm:a multimodel EDA[J].IEEE Transactions on Evolutionary Computation,2009,13(6):1218-1232.