基于自适应遗传算法的连续时空最优搜索路径规划研究

张献;任耀峰;王润芃

兵工学报 ›› 2015, Vol. 36 ›› Issue (12) : 2386-2395.

EN 投稿 期刊 文章 图表 检索
高级检索

  • 主管：中国科学技术协会

    主编：许毅达

    ISSN 1000-1093

    　

  • 主办：中国兵工学会

    出版：《兵工学报》 编辑部

    CN 11-2176/TJ

《兵工学报》是我国国防科技领域最具影响力的学术期刊之一，创刊于1979年，目前被国内所有重要数据库收录，其综合评价指标近年来一直名列兵工技术类科技期刊的首位；《兵工学报》目前还被国际上著名的检索机构美国......
兵工学报 ›› 2015, Vol. 36 ›› Issue (12) : 2386-2395. DOI: 10.3969/j.issn.1000-1093.2015.12.024
研究简报

基于自适应遗传算法的连续时空最优搜索路径规划研究

  • 张献， 任耀峰， 王润芃
作者信息 +

Research on Optimal Search Path Programming in Continuous Time and Space Based on an Adaptive Genetic Algorithm

  • ZHANG Xian， REN Yao-feng， WANG Run-peng
Author information +
文章历史 +

摘要

针对连续时空最优搜索者路径问题，利用随机微分方程描述Markov运动目标，建立了同时优化搜索者方向和速度的规划模型，并考虑了搜索速度对探测能力的影响。设计了一种新颖的自适应变异遗传算法，算法采用较高的变异概率作用于父代精英个体组，通过引入3种控制因子对变异方向和幅度进行自适应控制，动态调节局部搜索和全局搜索的平衡。在对方向未知的逃离目标搜索算例中，得到了近似对数螺旋曲线的搜索路径；在直升机搜索多目标的路径规划中，提供了合理有效的搜索方案。算法对比表明所给出的算法在全局优化能力和稳定性上有明显的优势，适用于求解连续搜索路径规划问题。

Abstract

A Markovian-target model based on stochastic differential equations and a path programming model with both searcher’s direction and velocity treated as decision variables are presented for optimal searcher path problem in continuous time and space, and the effect of searcher’s velocity on the detection ability is considered. A genetic algorithm with adaptive mutation is designed by introducing three kinds of control factors, which fulfills the adaptive control of the direction and range of mutation and dynamically regulates the balance between local search and global search. In an example of searching a target with a random escaping direction, an approximate logarithmic spiral path is found. Moreover, the algorithm provides a reasonable and effective search scheme in a path programming problem for a helicopter searching multiple targets. The results indicate that the proposed algorithm has the significant advantages of stability and global optimizing ability in comparison with other methods, and is well suitable for the search path programming problem in continuous time and space.

关键词

运筹学 / 最优搜索 / 连续时空 / Markovian目标 / 自适应变异遗传算法 / 反潜搜索

Key words

operations research / optimal search / continuous time and space / Markovian target / genetic algorithm with adaptive mutation / anti-submarine search

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
张献， 任耀峰， 王润芃. 基于自适应遗传算法的连续时空最优搜索路径规划研究. 兵工学报. 2015, 36(12): 2386-2395 https://doi.org/10.3969/j.issn.1000-1093.2015.12.024
ZHANG Xian， REN Yao-feng， WANG Run-peng. Research on Optimal Search Path Programming in Continuous Time and Space Based on an Adaptive Genetic Algorithm. Acta Armamentarii. 2015, 36(12): 2386-2395 https://doi.org/10.3969/j.issn.1000-1093.2015.12.024

基金

全军军事学研究生课题（2011JY002-423）

参考文献

［1］ LavisB, Furukawa T, Durrant-Whyte H F. Dynamic space reconflguration for Bayesian search and tracking with moving targets［J］. Autonomous Robots, 2008, 24(4): 387-399.
［2］ 吴文超,黄长强,宋磊,等. 不确定环境下的多无人机协同搜索航路规划［J］. 兵工学报, 2011, 32(11):1337-1342.
WU Wen-chao, HUANG Chang-qiang, SONG Lei, et al. Cooperative search and path planning of multi-unmanned air vehicles in uncertain environment［J］. Acta Armamentarii, 2011, 32(11): 1337-1342. (in Chinese)
［3］ HongS P, Cho S J, Park M J. A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search ［J］. European Journal of Operational Research, 2009, 193(2): 351-364.
［4］ StoneL D. What's happened in search theory since the 1975 Lanchester prize?［J］. Operations Research, 1989, 37(3): 501-506.
［5］ TrummelK E, Weisinger J R. The complexity of the optimal searcher path problem［J］. Operations Research, 1986, 34(2): 324-327.
［6］ EagleJ N. The optimal search for a moving target when the search path is constrained［J］. Operations Research, 1984, 32(5): 1107-1115.
［7］ EagleJ N, Yee J R. An optimal Branch-and-Bound procedure for the constrained path, moving target search problem［J］. Operations Research, 1990, 38(1): 110-114.
［8］ LauH, Huang S, Dissanayake G. Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times［J］. European Journal of Operational Research, 2008, 190(2): 383-397.
［9］ SatoH, Royset J O. Path optimization for the resource-constrained searcher［J］. Naval Research Logistics, 2010, 57(5): 422-440.
［10］ RoysetJ O, Sato H. Route optimization for multiple searchers［J］. Naval Research Logistics, 2010, 57(8): 701-717.
［11］ HongS P, Cho S J, Park M J, et al. Optimal search-relocation trade-off in Markovian-target searching［J］. Computers & Operations Research, 2009, 36(6): 2097-2104.
［12］ 杨日杰,吴芳,徐俊艳,等. 基于马尔可夫过程的水下运动目标启发式搜索［J］.兵工学报, 2010, 31(5): 586-591.
YANG Ri-jie, WU Fang, XU Jun-yan, et al. Heuristic search for moving underwater targets based on Markov process［J］. Acta Armamentarii, 2010, 31(5): 586-591. (in Chinese)
［13］ OhsumiA. Optimal searching for a Markovian-target［J］. Naval Research Logistics, 1991, 38(4): 531-554.
［14］ 朱清新,卿利,彭博.随机运动目标搜索问题的最优控制模型［J］.控制理论与应用, 2007, 24(5): 841-845.
ZHU Qing-xin, QING Li, PENG Bo. Optimal control model of search problem for randomly moving targets［J］. Control Theory & Applications, 2007, 24(5): 841-845. (in Chinese)
［15］ KiersteadD P, DelBalzo D R. A genetic algorithm applied to planning search paths in complicated environments［J］. Military Operations Research, 2003, 8(2): 45-59.
［16］ ChoJ H, Kim J S, Lim J S, et al. Optimal acoustic search path planning for sonar system based on genetic algorithm［J］. International Journal of Offshore and Polar Engineering, 2007, 17 (3): 218-224.
［17］ ChoJ H, Kim J S. Benchmarking of optimal acoustic search path planning［C］ //Proceedings of the 19th International Offshore and Polar Engineering Conference.Osaka, Japan:International Society of Offshore and Polar Engineers, 2009: 620-626.
［18］ 厄克森达尔B.随机微分方程导论与应用［M］.第6版.刘金山,吴付科,译.北京:科学出版社, 2012.
Oksendal B. Stochastic differential equations［M］.6th ed.LIU Jin-shan, WU Fu-ke， translated. Beijing: Science Press, 2012. (in Chinese)
［19］ 瓦格纳D H,迈兰德W,森德 T J.海军运筹分析［M］.第3版.姜青山,郑保华,译.北京:国防工业出版社, 2008:207-212.
Wagner D H, Charles Mylander W, Sanders T J. Naval operations analysis［M］.3rd ed. JIANG Qing-shan, ZHENG Bao-hua，translated. Beijing: National Defense Industry Press, 2008:207-212.(in Chinese)
［20］ 李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用［M］. 北京:科学出版社, 2002.
LI Min-qiang, KOU Ji-song, LIN Dan, et al. The basic theory and applications of genetic algorithm［M］. Beijing: Science Press, 2002. (in Chinese)
［21］ 李乃奎,崔同生.军事运筹学基础理论教程［M］. 北京:国防大学出版社, 2005.
LI Nai-kui, CUI Tong-sheng. Basic theory of military operation research［M］. Beijing: National Defense University Press, 2005. (in Chinese)
［22］ Foraker J. Optimal search for moving targets in continuous time and space using consistent approximations ［D］. Monterey, California: Naval Postgraduate School, 2011.
［23］ 肖洋,柳思思.索马里海盗的“恐怖主义化”及对策［J］.当代世界, 2010（1）: 57-59.
XIAO Yang, LIU Si-si. “Terrorism” of Somali pirates and countermeasures［J］. The Contemporary World, 2010（1）: 57-59. (in Chinese)
［24］ 邵哲平,潘家财.亚丁湾水域交通特征分析及防海盗策略研究［J］. 中国航海, 2011, 34(4):119-122.
SHAO Zhe-ping, PAN Jia-cai. Analysis of the Gulf of Aden’s traffic characteristics and study of anti-piracy strategy［J］. Navigation of China, 2011, 34(4):119-122. (in Chinese)
［25］ ForakerJ, Royset J O, Kaminer I. Search-trajectory optimization: part I, formulation and theory ［J/OL］. Journal of Optimization Theory and Applications, 2015. doi:10.1007/s10957-015-0768-y.
［26］ ForakerJ, Royset J O, Kaminer I. Search-trajectory optimization: part II, algorithms and computations［J/OL］. Journal of Optimization Theory and Applications, 2015. doi:10.1007/s10957-015-0770-4.
［27］ YakimenkoO. Direct method for rapid prototyping of near-optimal aircraft trajectories［J］. Journal of Guidance, Control, and Dynamics, 2000, 23(5): 865-875 .
［28］ GhabchelooR, Kaminer I, Aguiar A, et al. A general framework for multiple vehicle time-coordinated path following control［C］∥American Control Conference. St Louis, Missouri, US: the American Automatic Control Council, 2009: 3071-3076.

文章所在专题

制导技术

Accesses

Citation

Detail
段落导航
相关文章

/

〈 〉