基于记忆库粒子群算法的海上协作搜寻计划制定
|
摘要
海上搜寻任务通常由多个设施协作完成。针对海上协作搜寻计划制定问题,提出一种记忆库粒子群算法。该算法利用组合优化策略和连续优化策略,首先为单个设施生成相应的备选解并构建记忆库,通过从记忆库中学习、随机生成两种方式生成新的备选解;然后采用网格法更新记忆库,每个网格中最多有一个备选解保存在记忆库中,保证记忆库中备选解的多样性,基于此对解空间进行有效的全局搜索;最后通过从记忆库中随机选择多个备选解组合生成初始协作搜寻方案,利用粒子群策略围绕质量较好的备选解进行有效的局部搜索。实验结果表明,在效率方面,所提算法运行时间较短,在获取最小方差的同时可提高1%~5%的任务成功率,可有效应用于海上协作搜寻计划制定。
Maritime search tasks are usually completed by multiple facilities.In view of the maritime cooperative search planning problem,a Memory Bank Particle Swarm Optimization( MBPSO) algorithm was proposed.Combinatorial optimization strategy and continuous optimization strategy were employed.The candidate solutions and memory bank for every single facility were constructed at first.New candidate solutions were generated based on memory consideration and random selection.Then the memory bank was updated based on a method of lattice,which means that for each lattice,there was only one candidate solution to be stored in the memory bank at most.Based on that,the diversity of the solutions in the memory bank could be ensured and effective global search was performed.At last,initial cooperative search plans were generated by combing candidate solutions in the memory bank randomly.Based on the strategy of Particle Swarm Optimization(PSO),effective local search was performed by searching around the solutions with high quality.Experimental results show that,in terms of efficiency,the time consumed by the proposed algorithm is short; the lowest variance is acquired and the success probability can be increased by 1% to 5%.The proposed algorithm can be applied to make maritime cooperative search plans effectively.
Maritime search tasks are usually completed by multiple facilities.In view of the maritime cooperative search planning problem,a Memory Bank Particle Swarm Optimization( MBPSO) algorithm was proposed.Combinatorial optimization strategy and continuous optimization strategy were employed.The candidate solutions and memory bank for every single facility were constructed at first.New candidate solutions were generated based on memory consideration and random selection.Then the memory bank was updated based on a method of lattice,which means that for each lattice,there was only one candidate solution to be stored in the memory bank at most.Based on that,the diversity of the solutions in the memory bank could be ensured and effective global search was performed.At last,initial cooperative search plans were generated by combing candidate solutions in the memory bank randomly.Based on the strategy of Particle Swarm Optimization(PSO),effective local search was performed by searching around the solutions with high quality.Experimental results show that,in terms of efficiency,the time consumed by the proposed algorithm is short; the lowest variance is acquired and the success probability can be increased by 1% to 5%.The proposed algorithm can be applied to make maritime cooperative search plans effectively.
引文
[1]KOOPMAN B O.The theory of search.Ⅲ.The optimum distribution of searching effort[J].Operations Research,1957,5(5):613-626.
[2]KRATZKE T M,STONE L D,FROST J R.Search and rescue optimal planning system[C]//Proceedings of the 2010 13th Conference on Information Fusion.Piscataway,NJ:IEEE,2010:1-8.
[3]BMT Cordah.Search And Rescue Information System(SARIS)[EB/OL].[2010-08-11].http://www.bmtcordah.com/.
[4]BERGER J,LO N,NOEL M.A new multi-target,multi-Agent search-and-rescue path planning approach[J].International Journal of Computer,Information,Systems and Control Engineering,2014,8(6):902-912.
[5]BERGER J,LO N.An innovative multi-Agent search-and-rescue path planning approach[J].Computers and Operations Research,2015,53:24-31.
[6]邢胜伟.海上立体搜寻全局优化模型及仿真研究[D].大连:大连海事大学,2012:79-95.(XING S W.Research on global optimization model and simulation of joint aeronautical and maritime search[D].Dalian:Dalian Maritime University,2012:79-95.)
[7]郑宏喆,赵怀慈,王立勇.基于风压差翻转漂移模型的海上搜寻区域确定[J].中国航海,2016,39(4):102-107.(ZHENG H Z,ZHAO H C,WANG L Y.Determination of maritime search area based on leeway-jibing drift model[J].Navigation of China,2016,39(4):102-107.)
[8]王光源,刘建东,章尧卿,等.海上遇险目标漂移与搜寻区域优化确定分析[J].舰船电子工程,2017,37(12):21-24.(WANGG Y,LIU J D,ZHANG Y Q,et al.Optimization analysis of the maritime distress target’s drift and search area[J].Ship Electronic Engineering,2017,37(12):21-24.)
[9]刘勇,贾庆轩,陈钢,等.基于多目标粒子群优化算法的自由漂浮空间机器人负载最大化轨迹优化[J].机器人,2014,36(4):402-410.(LIU Y,JIA Q X,CHEN G,et al.Load maximization trajectory optimization for free-floating space robot using multi-objective particle swarm optimization algorithm[J].Robot,2014,36(4):402-410.)
[10]李洁,张兆薇.基于和声搜索算法和相关向量机的网络安全态势预测方法[J].计算机应用,2016,36(1):199-202.(LI J,ZHANG Z W.Network security situation prediction method based on harmony search algorithm and relevance vector machine[J].Journal of Computer Applications,2016,36(1):199-202.)
[11]LIU Z H,WEI H L,LIU K,et al.Global identification of electrical and mechanical parameters in PMSM drive based on dynamic self-learning PSO[EB/OL].[2018-02-09].http://eprints.whiterose.ac.uk/126906/1/Global%20Identification%20of%20Electrical%20Parameters%20(IEEE-TPEL%20Accepted%202018-01-23).pdf.
[12]LIU Z H,WEI H L,ZHONG Q C,et al.Parameter estimation for VSI-Fed PMSM based on a dynamic PSO with learning strategies[J].IEEE Transactions on Power Electronics,2017,32(4):3154-3165.
[13]LIU Z H,WEI H L,ZHONG Q C,et al.GPU implementation of DPSO-RE algorithm for parameters identification of surface PMSMconsidering VSI nonlinearity[J].IEEE Journal of Emerging and Selected Topics in Power Electronics,2017,5(3):1334-1345.
[14]欧阳海滨,高立群,邹德旋,等.和声搜索算法探索能力研究及其修正[J].控制理论与应用,2014,31(1):57-65.(OUY-ANG H B,GAO L Q,ZOU D X,et al.Exploration ability study of harmony search algorithm and its modification[J].Control Theory and Applications,2014,31(1):57-65.)
[15]胡旺,YEN G G,张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报,2014,25(5):1025-1050.(HU W,YEN GG,ZHANG X.Multiobjective particle swarm optimization based on Pareto entropy[J].Journal of Software,2014,25(5):1025-1050.)
[16]匡芳君,徐蔚鸿,张思扬.基于改进混沌粒子群的混合核SVM参数优化及应用[J].计算机应用研究,2013,31(3):671-674.(KUANG F J,XU W H,ZHANG S Y.Parameter optimization and application of SVM with mixtures kernels based on improved chaotic particle swarm optimization[J].Application Research of Computers,2013,31(3):671-674.)
[17]FROST J R,STONE L D.Reviews of search theory:advances and applications to search and rescue decision support[R].Washington,DC:United States Coast Guard,2001.
[18]国际海事组织/国际民用航空组织.国际航空和海上搜寻救助手册第二卷[M].北京:人民交通出版社,2002:148-154.(IMO/International Civil Aviation Organization.International Aeronautical and Maritime Search and Rescue ManualⅡ[M].Beijing:China Communications Press,2002:148-154.)
[19]陈志敏,薄煜明,吴盘龙,等.基于自适应粒子群优化的新型粒子滤波在目标跟踪中的应用[J].控制与决策,2013,28(2):193-200.(CHEN Z M,BO Y M,WU P L,et al.Novel particle filter algorithm based on adaptive particle swarm optimization and its application to radar target tracking[J].Control and Decision,2013,28(2):193-200.)
[20]刘长平,叶春明.具有Lévy飞行特征的蝙蝠算法[J].智能系统学报,2013,8(3):240-246.(LIU C P,YE C M.Bat algorithm with the characteristics of Lévy flights[J].CAAI Transactions on Intelligent Systems,2013,8(3):240-246.)
[2]KRATZKE T M,STONE L D,FROST J R.Search and rescue optimal planning system[C]//Proceedings of the 2010 13th Conference on Information Fusion.Piscataway,NJ:IEEE,2010:1-8.
[3]BMT Cordah.Search And Rescue Information System(SARIS)[EB/OL].[2010-08-11].http://www.bmtcordah.com/.
[4]BERGER J,LO N,NOEL M.A new multi-target,multi-Agent search-and-rescue path planning approach[J].International Journal of Computer,Information,Systems and Control Engineering,2014,8(6):902-912.
[5]BERGER J,LO N.An innovative multi-Agent search-and-rescue path planning approach[J].Computers and Operations Research,2015,53:24-31.
[6]邢胜伟.海上立体搜寻全局优化模型及仿真研究[D].大连:大连海事大学,2012:79-95.(XING S W.Research on global optimization model and simulation of joint aeronautical and maritime search[D].Dalian:Dalian Maritime University,2012:79-95.)
[7]郑宏喆,赵怀慈,王立勇.基于风压差翻转漂移模型的海上搜寻区域确定[J].中国航海,2016,39(4):102-107.(ZHENG H Z,ZHAO H C,WANG L Y.Determination of maritime search area based on leeway-jibing drift model[J].Navigation of China,2016,39(4):102-107.)
[8]王光源,刘建东,章尧卿,等.海上遇险目标漂移与搜寻区域优化确定分析[J].舰船电子工程,2017,37(12):21-24.(WANGG Y,LIU J D,ZHANG Y Q,et al.Optimization analysis of the maritime distress target’s drift and search area[J].Ship Electronic Engineering,2017,37(12):21-24.)
[9]刘勇,贾庆轩,陈钢,等.基于多目标粒子群优化算法的自由漂浮空间机器人负载最大化轨迹优化[J].机器人,2014,36(4):402-410.(LIU Y,JIA Q X,CHEN G,et al.Load maximization trajectory optimization for free-floating space robot using multi-objective particle swarm optimization algorithm[J].Robot,2014,36(4):402-410.)
[10]李洁,张兆薇.基于和声搜索算法和相关向量机的网络安全态势预测方法[J].计算机应用,2016,36(1):199-202.(LI J,ZHANG Z W.Network security situation prediction method based on harmony search algorithm and relevance vector machine[J].Journal of Computer Applications,2016,36(1):199-202.)
[11]LIU Z H,WEI H L,LIU K,et al.Global identification of electrical and mechanical parameters in PMSM drive based on dynamic self-learning PSO[EB/OL].[2018-02-09].http://eprints.whiterose.ac.uk/126906/1/Global%20Identification%20of%20Electrical%20Parameters%20(IEEE-TPEL%20Accepted%202018-01-23).pdf.
[12]LIU Z H,WEI H L,ZHONG Q C,et al.Parameter estimation for VSI-Fed PMSM based on a dynamic PSO with learning strategies[J].IEEE Transactions on Power Electronics,2017,32(4):3154-3165.
[13]LIU Z H,WEI H L,ZHONG Q C,et al.GPU implementation of DPSO-RE algorithm for parameters identification of surface PMSMconsidering VSI nonlinearity[J].IEEE Journal of Emerging and Selected Topics in Power Electronics,2017,5(3):1334-1345.
[14]欧阳海滨,高立群,邹德旋,等.和声搜索算法探索能力研究及其修正[J].控制理论与应用,2014,31(1):57-65.(OUY-ANG H B,GAO L Q,ZOU D X,et al.Exploration ability study of harmony search algorithm and its modification[J].Control Theory and Applications,2014,31(1):57-65.)
[15]胡旺,YEN G G,张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报,2014,25(5):1025-1050.(HU W,YEN GG,ZHANG X.Multiobjective particle swarm optimization based on Pareto entropy[J].Journal of Software,2014,25(5):1025-1050.)
[16]匡芳君,徐蔚鸿,张思扬.基于改进混沌粒子群的混合核SVM参数优化及应用[J].计算机应用研究,2013,31(3):671-674.(KUANG F J,XU W H,ZHANG S Y.Parameter optimization and application of SVM with mixtures kernels based on improved chaotic particle swarm optimization[J].Application Research of Computers,2013,31(3):671-674.)
[17]FROST J R,STONE L D.Reviews of search theory:advances and applications to search and rescue decision support[R].Washington,DC:United States Coast Guard,2001.
[18]国际海事组织/国际民用航空组织.国际航空和海上搜寻救助手册第二卷[M].北京:人民交通出版社,2002:148-154.(IMO/International Civil Aviation Organization.International Aeronautical and Maritime Search and Rescue ManualⅡ[M].Beijing:China Communications Press,2002:148-154.)
[19]陈志敏,薄煜明,吴盘龙,等.基于自适应粒子群优化的新型粒子滤波在目标跟踪中的应用[J].控制与决策,2013,28(2):193-200.(CHEN Z M,BO Y M,WU P L,et al.Novel particle filter algorithm based on adaptive particle swarm optimization and its application to radar target tracking[J].Control and Decision,2013,28(2):193-200.)
[20]刘长平,叶春明.具有Lévy飞行特征的蝙蝠算法[J].智能系统学报,2013,8(3):240-246.(LIU C P,YE C M.Bat algorithm with the characteristics of Lévy flights[J].CAAI Transactions on Intelligent Systems,2013,8(3):240-246.)