量子布谷鸟协同搜索的垃圾回收路径规划方法
|
摘要
针对城市垃圾回收路径规划问题,提出了一种量子布谷鸟协同搜索算法,用于优化最短路径.首先,采用Bloch球面坐标量子编码来扩大解空间;然后设计了一种基于差分进化的量子布谷鸟搜索策略,实现较差个体的改进以及劣势个体与优势个体之间的信息交换,增强全局搜索能力;最后,利用一种局部邻域搜索算法进一步提高解的质量.理论分析了所提算法的收敛性.基于无线传感网络采集数据进行了仿真实验,将量子布谷鸟协同搜索算法与传统遗传算法和量子布谷鸟搜索算法分别比较,求解垃圾回收最短路径问题的最优解和平均解均改进了20%～40%,结果证明了量子布谷鸟协同搜索算法的优越性.
A quantum-inspired cuckoo co-search algorithm is proposed to optimize the shortest path for garbage collection.First,the Bloch spherical coordinate quantum coding is used to enlarge the solution space.Then,a quantum cuckoo search strategy based on differential evolution is designed to realize the improvement of poor individuals and the information exchange between the inferior and dominant individuals.This strategy can enhance the global searching ability.Finally,a local neighborhood search algorithm is developed to further improve the quality of the solution.The convergence of the proposed algorithm is shown via a theoretical analysis.The simulation experiment is based on wireless sensor networks.Compared with the traditional genetic algorithm and the standard quantum-inspired cuckoo search algorithm,the proposed algorithm for the optimal solution and average solutions with the shortest path for garbage collection are improved by 20% ～ 40%,which proves the superiority of the proposed algorithm.
A quantum-inspired cuckoo co-search algorithm is proposed to optimize the shortest path for garbage collection.First,the Bloch spherical coordinate quantum coding is used to enlarge the solution space.Then,a quantum cuckoo search strategy based on differential evolution is designed to realize the improvement of poor individuals and the information exchange between the inferior and dominant individuals.This strategy can enhance the global searching ability.Finally,a local neighborhood search algorithm is developed to further improve the quality of the solution.The convergence of the proposed algorithm is shown via a theoretical analysis.The simulation experiment is based on wireless sensor networks.Compared with the traditional genetic algorithm and the standard quantum-inspired cuckoo search algorithm,the proposed algorithm for the optimal solution and average solutions with the shortest path for garbage collection are improved by 20% ～ 40%,which proves the superiority of the proposed algorithm.
引文
[1] 李宝磊,吕丹桔,张钦虎,等.基于多元优化算法的路径规划[J].电子学报,2016,44(9):2242-2247.Li B L,Lü D J,Zhang Q H,et al.A path planner based on multivariant optimization algorithm[J].Acta Electronic Sinica,2016,44(9):2242-2247.
[2] Pires A,Martinho G,Chang N B.Solid waste management in European countries:A review of systems analysis techniques[J].Journal of Environmental Management,2011,92(4):1033.
[3] Morrissey A J,Browne J.Waste management models and their application to sustainable waste management[J].Waste Management,2004,24(3):297-308.
[4] Badran M F,Elhaggar S M.Optimization of municipal solid waste management in Port Said-Egypt[J].Waste Management,2006,26(5):534-545.
[5] 贾学斌,刘冬梅,孙喆.用神经元理论优化生活垃圾收运路线[J].哈尔滨工业大学学报,2004,36(6):819-820.Jia X B,Liu D M,Sun Z.Application studies of nerve unit theory about routes optimization for daily rubbish carrying system[J].Journal of Harbin Institute of Technology,2004,36(6):819-820.
[6] Dang V T,Pinnoi A.Vehicle routing-scheduling for waste collection in Hanoi[J].European Journal of Operational Research,2000,125(3):449-468.
[7] Ghose M K,Dikshit A K,Sharma S K.A GIS based transportation model for solid waste disposal - A case study on Asansol municipality[J].Waste Management,2006,26(11):1287-1293.
[8] 钱志鸿,王义君.面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227.Qian Z H,Wang Y J.Internet of things-oriented wireless sensor networks review[J].Journal of Electronics & Information Technology,2013,35(1):215-227.
[9] Amdouni I,Adjih C,Plesse T.Network coding in military wireless ad hoc and sensor networks:Experimentation with GardiNet[C]//2015 International Conference on Military Communications and Information Systems.Piscataway,NJ,USA:IEEE,2015:1-9.
[10] 杜鹏桢,唐振民,陆建峰,等.不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法[J].电子学报,2014,42(3):616-624.Du P Z,Tang Z M,Lu J F,et al.Global path planning for ALV based on improved glowworm swarm optimization under uncertain environment[J].Acta Electronic Sinica,2014,42(3):616-624.
[11] 王雪松,高阳,程玉虎,等.知识引导遗传算法实现机器人路径规划[J].控制与决策,2009,24(7):1043-1049.Wang X S,Gao Y,Cheng Y H,et al.Knowledge-guided genetic algorithm for path planning of robot[J].Control and Decision,2009,24(7):1043-1049.
[12] 张雷,王道波,段海滨.基于粒子群优化算法的无人战斗机路径规划方法[J].系统工程与电子技术,2008,30(3):506-510.Zhang L,Wang D B,Duan H B.Study on uninhabited combat arial vehicle path planning method based on particle swarm optimization algorithm[J].System Engineering and Electrionics,2008,30(3):506-510.
[13] 胡军国,祁亨年,董峰,等.一种改进蚁群算法研究和旅游景区路径规划问题求解倡[J].计算机应用研究,2011,28(5):1647-1651.Hu J G,Qi H N,Dong F,et al.Improved ant colony algorithm for path planning tourist scenic area[J].Application Research of Computers,2011,28(5):1647-1651.
[14] Yang X S,Deb S.Cuckoo search via Lévy flights[C]//Proceedings of World Congress on Nature & Biologically Inspired Computing.Piscataway,NJ,USA:IEEE,2009:210-214.
[15] 钱洁,郑建国,张超群,等.量子进化算法研究现状综述[J].控制与决策,2011,26(3):321-326.Qian J,Zheng J G,Zhang C Q,et al.Reviews of current studying progress on quantum evolutionary computation[J].Control and Decision,2011,26(3):321-326.
[16] 杨淑云,徐云霞,李盼池.基于Bloch球面搜索的量子鱼群算法[J].信息与控制,2014,43(6):647-653.Yang S Y,Xu Y X,Li P C.Quantum-inspired artificial fish swarm algorithm based on the bloch sphere search algorithm[J].Information and Control,2014,43(6):647-653.
[17] Qi X,Wang H,Zhu H,et al.Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization[J].International Journal of Production Research,2016,54(16):1-16.
[18] 齐学梅,王宏涛,杨洁,等.量子萤火虫算法及在无等待流水调度上的应用[J].信息与控制,2016,45(2):211-217.Qi X M,Wang H T,Yang J,et al.Quantum glowworm swarm algorithm and its application to no-wait flowshop scheduling[J].Information and Control,2016,45(2):211-217.
[19] Yang X S,Deb S.Multiobjective cuckoo search for design optimization[J].Computers & Operations Research,2013,40(6):1616-1624.
[20] 齐学梅,王宏涛,陈付龙,等.新颖的阻塞流水车间调度量子差分进化算法[J].计算机应用,2015,35(3):663-667.Qi X M,Wang H T,Chen F L,et al.Novel quantum differential evolutionary algorithm for blocking flowshop scheduling[J].Journal of Computer Applications,2015,35(3):663-667.
[21] 黄翰,林智勇,郝志峰,等.基于关系模型的进化算法收敛性分析与对比[J].计算机学报,2011,34(5):801-811.Huang H,Lin Z Y,Hao Z F,et al.Convergence analysis and comparison of evolutionary algorithms based on relation model[J].Chinese Journal of Computers,2011,34(5):801-811.
[22] Dao T P,Huang S C,Thang P T.Hybrid Taguchi-cuckoo search algorithm for optimization of a compliant focus positioning platform[J].Applied Soft Computing,2017,57:526-538.
[2] Pires A,Martinho G,Chang N B.Solid waste management in European countries:A review of systems analysis techniques[J].Journal of Environmental Management,2011,92(4):1033.
[3] Morrissey A J,Browne J.Waste management models and their application to sustainable waste management[J].Waste Management,2004,24(3):297-308.
[4] Badran M F,Elhaggar S M.Optimization of municipal solid waste management in Port Said-Egypt[J].Waste Management,2006,26(5):534-545.
[5] 贾学斌,刘冬梅,孙喆.用神经元理论优化生活垃圾收运路线[J].哈尔滨工业大学学报,2004,36(6):819-820.Jia X B,Liu D M,Sun Z.Application studies of nerve unit theory about routes optimization for daily rubbish carrying system[J].Journal of Harbin Institute of Technology,2004,36(6):819-820.
[6] Dang V T,Pinnoi A.Vehicle routing-scheduling for waste collection in Hanoi[J].European Journal of Operational Research,2000,125(3):449-468.
[7] Ghose M K,Dikshit A K,Sharma S K.A GIS based transportation model for solid waste disposal - A case study on Asansol municipality[J].Waste Management,2006,26(11):1287-1293.
[8] 钱志鸿,王义君.面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227.Qian Z H,Wang Y J.Internet of things-oriented wireless sensor networks review[J].Journal of Electronics & Information Technology,2013,35(1):215-227.
[9] Amdouni I,Adjih C,Plesse T.Network coding in military wireless ad hoc and sensor networks:Experimentation with GardiNet[C]//2015 International Conference on Military Communications and Information Systems.Piscataway,NJ,USA:IEEE,2015:1-9.
[10] 杜鹏桢,唐振民,陆建峰,等.不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法[J].电子学报,2014,42(3):616-624.Du P Z,Tang Z M,Lu J F,et al.Global path planning for ALV based on improved glowworm swarm optimization under uncertain environment[J].Acta Electronic Sinica,2014,42(3):616-624.
[11] 王雪松,高阳,程玉虎,等.知识引导遗传算法实现机器人路径规划[J].控制与决策,2009,24(7):1043-1049.Wang X S,Gao Y,Cheng Y H,et al.Knowledge-guided genetic algorithm for path planning of robot[J].Control and Decision,2009,24(7):1043-1049.
[12] 张雷,王道波,段海滨.基于粒子群优化算法的无人战斗机路径规划方法[J].系统工程与电子技术,2008,30(3):506-510.Zhang L,Wang D B,Duan H B.Study on uninhabited combat arial vehicle path planning method based on particle swarm optimization algorithm[J].System Engineering and Electrionics,2008,30(3):506-510.
[13] 胡军国,祁亨年,董峰,等.一种改进蚁群算法研究和旅游景区路径规划问题求解倡[J].计算机应用研究,2011,28(5):1647-1651.Hu J G,Qi H N,Dong F,et al.Improved ant colony algorithm for path planning tourist scenic area[J].Application Research of Computers,2011,28(5):1647-1651.
[14] Yang X S,Deb S.Cuckoo search via Lévy flights[C]//Proceedings of World Congress on Nature & Biologically Inspired Computing.Piscataway,NJ,USA:IEEE,2009:210-214.
[15] 钱洁,郑建国,张超群,等.量子进化算法研究现状综述[J].控制与决策,2011,26(3):321-326.Qian J,Zheng J G,Zhang C Q,et al.Reviews of current studying progress on quantum evolutionary computation[J].Control and Decision,2011,26(3):321-326.
[16] 杨淑云,徐云霞,李盼池.基于Bloch球面搜索的量子鱼群算法[J].信息与控制,2014,43(6):647-653.Yang S Y,Xu Y X,Li P C.Quantum-inspired artificial fish swarm algorithm based on the bloch sphere search algorithm[J].Information and Control,2014,43(6):647-653.
[17] Qi X,Wang H,Zhu H,et al.Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization[J].International Journal of Production Research,2016,54(16):1-16.
[18] 齐学梅,王宏涛,杨洁,等.量子萤火虫算法及在无等待流水调度上的应用[J].信息与控制,2016,45(2):211-217.Qi X M,Wang H T,Yang J,et al.Quantum glowworm swarm algorithm and its application to no-wait flowshop scheduling[J].Information and Control,2016,45(2):211-217.
[19] Yang X S,Deb S.Multiobjective cuckoo search for design optimization[J].Computers & Operations Research,2013,40(6):1616-1624.
[20] 齐学梅,王宏涛,陈付龙,等.新颖的阻塞流水车间调度量子差分进化算法[J].计算机应用,2015,35(3):663-667.Qi X M,Wang H T,Chen F L,et al.Novel quantum differential evolutionary algorithm for blocking flowshop scheduling[J].Journal of Computer Applications,2015,35(3):663-667.
[21] 黄翰,林智勇,郝志峰,等.基于关系模型的进化算法收敛性分析与对比[J].计算机学报,2011,34(5):801-811.Huang H,Lin Z Y,Hao Z F,et al.Convergence analysis and comparison of evolutionary algorithms based on relation model[J].Chinese Journal of Computers,2011,34(5):801-811.
[22] Dao T P,Huang S C,Thang P T.Hybrid Taguchi-cuckoo search algorithm for optimization of a compliant focus positioning platform[J].Applied Soft Computing,2017,57:526-538.