基于探索与开发权衡的地磁仿生导航搜索方法-刘明雍.pdf

《基于探索与开发权衡的地磁仿生导航搜索方法-刘明雍.pdf》由会员分享，可在线阅读，更多相关《基于探索与开发权衡的地磁仿生导航搜索方法-刘明雍.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第38卷第7期 系统工程与电子技术 V0138 No72016年7月 Systems Engineering and Electronics July ZOl6文章编号：1001 506X(2016)071644一05 网址：wwwsyrelecom基于探索与开发权衡的地磁仿生导航搜索方法刘明雍，刘 坤，李 红，彭星光(西北工业大学航海学院，陕西西安710072)摘 要：针对地磁仿生导航过程中对搜索偏向性考虑不足的问题，提出了一种基于探索与开发权衡的导航方法。依据时序进化搜索策略的结构特征，从统计学角度建立了磁趋势性运动模型，分析了探索与开发和磁趋势性运动的关系，并将搜索偏向权衡问题归结为对种

2、群多样性的合理调控，引入分布熵的概念度量种群多样性，设计了分布熵约束下的磁趋势性搜索策略，给出了导航搜索流程。通过仿真分析，给出较为合理的参数设置，并将该方法与时序进化搜索方法进行对比实验，结果证实了所提方法能够有效提高导航效率。关键词：地磁导航；仿生导航；探索与开发；磁趋势性中图分类号：U 6661 文献标志码：A DOI：103969jissn1001506X20160725Geomagnetic bio。inspired naVigation based on balancingexploration and exploitationLIU Mingyong，LIU Kun，LI Hon

3、g，PENG Xingguang(CozZPge o，Mari”e SfiP卵fP n卵d TPc矗行oZogy，Nor叫Psfg，17 PoZyPf矗行ic盘Z U矗iugr5iy，Xin咒7j0072，C矗i72n)Abstract：A navigation method based on balancing exploration and exploitation is proposed for the issue ofinsufficient consideration of search bias in the geomagnetic bioinspired navigation p

4、rocess Firstly，according tothe structure feature of the sequence evolution search strategy，a magnetotaxis movement model is establishedbased on statistical Then，the relationship between the exploration-exploitation and the magnetota茹s movement isanalyzed，the problem of balancing searching bias is ge

5、neraIized as the reasonable control of populatjon diversity Theconcept of distribution entropy is introduced to measure the population diversity，and a new strategy for magnetotaxis search under the constraints of distribution entropy is designed The navigation search procedure is given Finally，throu

6、gh the simulation analysis，the reasonable parameter set is given，and comparing the proposedmethod with the sequence evoIution search strategy，the simulation results show the effectiveness of the proposed approachKeywor(1s：geomagnetic navigation；bioinspired navigation；exploration and exploitation；mag

7、netotaxis0 引 言地磁仿生导航是指模拟生物长途迁徙的原理，在无先验地磁数据库的条件下，通过对地磁场信息的感知，实现自主搜索到达目标地磁场环境的目的，能够为无人运载体远程航行提供导航与定位功能的技术，属于新概念导航技术。自然界中，生物经过长期进化，逐渐形成了与生长环境相适应的组织结构和生存方式，其中诸如海龟、信鸽口、大马哈鱼33等部分生物拥有了对地磁场高明的利用能力。在它们洄游、归巢、迁徙等过程中，往往需要跨越数十甚至数千米，如果说它们简单而原始的脑细胞能够存储完整地磁图，显然是难以想象的。近年来，仿生导航逐渐引起国内外学者的关注，对多种动物的地磁导航行为进行了相关实验验证和研究分析，

8、大量研究表明s，地磁场是动物长途运动可信赖的导航信息源，磁趋势性搜索是导航的关键。目前，受上述生物行为启发的仿生导航研究较少。文献78将地磁场视为多种参量的混合体，提出了一种多目标时序后验搜索的导航方式，将进化搜索与导航运动相结合，构成受运动路径约束的时序进化搜索过程，通过对多目标问题的求解，实现导航目的。由于算法采用随机游走模型模拟生物体运动，在导航过程中，搜索偏向具有很大随机性，从而导致系统对信息的获取以及利用缺少必要的指向性，增加了主动搜索的随机性，降低了导航效率。未知环境中，主动搜寻的核心在于信息获取及利用，通收稿日期：20141222；修回日期：201 5一1120；网络优先出版日期

9、：201 6一0218。网络优先出版地址：http：wwwcn kinetkcms“tail112422TN201602181216016htm基金项目：国家自然科学基金(513791 76，511791 56，61473233)资助课题万方数据第7期 刘明雍等：基于探索与开发权衡的地磁仿生导航搜索方法 1645过外向型探索获取信息，依靠内向型开发利用信息，从生物自组织角度应对环境未知所带来的盲目、随机。探索与开发长期以来一直是进化计算领域的核心问题9。1，由于不同算法的进化机理不同，影响探索与开发性质的因素也不完全相同。本文从信息传播的角度，在时序进化搜索策略中引入探索与开发的概念，提出分布

10、熵约束下的导航搜索方法，通过约束搜索行为的多样性，权衡导航搜索的偏向，从而达到合理利用信息的目的，并结合仿真试验给出参数的具体设置。l 地磁仿生导航问题描述导航是自然界中生物重要的生存能力之一，能够引导生物快速、安全、准确地到达指定位置巢穴、繁殖地、觅食区等。动物在利用地磁方面拥有超乎寻常的能力，典型的导航行为在动物界并不罕见，如：信鸽口1被以复杂运输手段带至陌生环境，放飞后经历数千公里跋涉，仍能安全、快速地归巢；绿毛海龟口1漫无目的的巡游路径往往达到数万公里，而当繁殖期来临之际，却能够跨越茫茫海洋，快速而准确地回到其出生的海滩。从仿生学角度，生物地磁导航是利用了磁场多参量定位的物理特性。地磁

11、场是多种参量的混合体，利用磁场的多要素特征能够唯一性地描述近地空间任意位置，这就为生物利用地磁信息进行导航提供了可靠的物理基础。空间中，任意位置C处的地磁场环境特征集合为：Bf一：E，韪，E)，其中，B表示地磁场要素标量值，九为参量维度。生物从位置C到目标位置G处的导航过程，实质上就是特征集合B中各参量向集合B6中各参量的收敛过程，可归结为：参量分布未知情况下的多参量收敛问题。因此，可将地磁仿生导航表示为，min F(B，量)一(，。(B，尼)，(B2，正)，(B。，是)(2兀协)。种群中，数值相同的样本个体所占的比例，代表了该方向上运动趋势的强度。导航起始阶段，载体对外界地磁场环境缺乏必要探

12、索，导航运动无明显趋势性特征，各运动方向分布均匀，此时载体的运动呈现出无序、混沌的特征；随着导航任务的进行，载体对地磁场有了一定程度的认知，逐渐形成向目标点收、，哆生瓤一一，9、万方数据 1646 系统工程与电子技术 第38卷敛的趋势性运动。此时在进化种群中，代表该收敛方向的样本将逐渐占据主导地位。而当某时刻，种群完全由该样本替代时，运动趋势性最为显著。借助统计学观点，磁趋势性可描述为盐 盐。一2：M。=芝：可(cos(Q。)+jsin(Q。) (4)式中，D的方向表示趋势性搜索方向；lDl代表方向的趋势性搜索强度。3导航搜索方法31 探索与开发权衡的基本思想探索与开发是算法搜索过程中的两个基

13、本策略9，决定搜索的偏向性，关乎算法的搜索质量。探索是以获取信息为目的的搜索偏向，在导航中体现为漫无目的的游走，通过游走感知未知环境，是消除或减小导航不确定性的前提；开发则是以利用信息为目的的搜索偏向，利用历史信息逐渐消除或减小导航不确定性，建立趋势性运动，引导载体到达目标点。在地磁仿生导航中，受磁场参量分布复杂、未知所带来的不确定性影响，搜索行为中的探索与开发行为相辅相成、缺一不可。通常，在进化算法中，搜索的偏向性由种群多样性决定，具有如图2所示关系。种群样奉多样性图2 种群多样性与开发和探索的关系Fig2 Relationship between population diversityw

14、ith exploration and expIoitation种群多样性是随进化的深入而动态变化，进化程度越高，多样性越低，种群搜索的开发比重越大，容易导致早熟现象的产生。种群的早熟现象实际上是种群对历史信息的过度开发，缺少必要探索的一种体现。通过对多样性的有效调控，不仅有利于搜索偏向的权衡，同时能够较好地避免搜索陷入局部极值问题，保证种群进化的有序进行。32分布熵约束下的磁趋势导航搜索方法为了度量多样性，此处引入分布熵的概念，并设计一种熵约束下的磁趋势性导航搜索方法。321搜索行为分布熵文献12提出了一种基于样本位置方差的多样性描述方法，通过度量样本个体在多个空间维度中的位置差异，表征种群

15、多样性。由于该方法采用了方差计算，对样本个体分布差异的描述不足，难以充分显示种群多样性的特点。为此，引入分布熵来定量描述样本多样性。定义1分布熵：样本种类为N类，样本个体可表示为Q，Q2，Q。群体进化的某时刻，样本个体在群体中的比例分别为户。，户。，户。，满足：户一1，则分布熵为12lH(户l，户2，户N)一一2j户。1n户。 (5)t=l式中，H为分布熵。分布熵在分布空间内具有非负性、对称性和可加性，是一个严格凹函数。当且各类样本均匀分布概率户。一户。一一p。一1N时，H具有唯一最大值；当某一类个体占据了群体绝大部分时，即户。一1，p，一o(Vi1)，有r 三 1limHlim J一户。ln

16、户。一：p1n声，lo (6)11 l一1L t=2 J此时分布熵最低。分布熵量化了种群的多样性，反应了种群的搜索偏向。熵值越大，种群的全局探索行为越强；熵值越小，种群的局部开发能力越强。322 熵约束下的磁趋势性搜索策略种群的进化是对搜索问题的求解，而搜索策略的确立需要考虑进化算法的特性。从进化种群特性来看，为了避免因信息过度开发而造成的种群早熟，设定最小分布熵门限值H。，避免多样性偏低，维持探索与开发的比例关系。在导航搜索过程中，利用种群的进化，实现了探索与开发的相互转化，其转化的核心在于信息的传播，表现为分布熵的动态变化。然而，过大或过小的变化幅度H，又容易造成信息失真或冗余的存在，不利

17、于导航搜索的有效进行。基于上述，针对导航的自组织搜索，设定分布熵最低门限值H。，控制分布熵变化幅度H，以达到约束导航的搜索行为，避免无谓探索和过度开发，提升导航效率。当种群分布熵过低于门限，即HG(志一1)，则执行淘汰操作；繁殖操作：保留原样本P(j)，随机选取一定数量的个体P(r)一P(i)；淘汰操作：随机产生新个体，替换原样本；变异操作：执行变异算子户。，得到下一代进化种群。执行权衡策略(步骤4)。步骤4(探索与开发权衡搜索策略)依据式(5)计算分布熵H，如果H2的范围导航搜索严重偏向探索，不利于导航进行，因此不在分析范围内。在o，2的区间内，每间隔o1进行l 000次仿真，统计结果如图3

18、所示。图3不同门限熵H约束下的导航耗时Fig3 Navigation times within different entropy threshold Hn图3描述了在不同门限熵约束下的导航搜索耗时，A、B、c 3个区域，代表分布熵约束的3个不同阶段。A区域内，导航耗时无明显变化，此时门限熵的设置过小，未对导航搜索起到约束调节的作用；B区域内，导航耗时逐渐降低，门限熵对搜索的约束力度逐渐加强，引导搜索偏向开发行为；C区域内，种群多样性增加，开发逐渐向探索转化，导航耗时逐渐增加。通过仿真，能够看到较为合理的门限熵值为H。一13。(2)种群繁殖比例分布熵变化幅度H的不同将对导航搜索性能产生一定的影

19、响，而决定H变化的关键参数则为种群繁殖比例。此处，针对不同繁殖比例对导航耗时的影响进行仿真分析。在不同繁殖比例下，选取门限熵H。一13，进行对比分析。在不同样本下分别进行了1 000次仿真试验，试验统计结果如图4所示。繁殖比例图4不同繁殖比例下的导航耗时Fig4 Navigation times within different reproduction ratio图4描述了繁殖比例对导航耗时的影响，能够看到过大或过小的繁殖比例均不利于导航搜索的高效进行。通过仿真分析，能够看到较为合理的繁殖比例为种群规模6。实验2导航算法性能对比(1)导航路程对比下面分析算法改进前后的导航路程比，表1给出了5

20、组不同导航任务下1 ooo次试验的路程比。以直线最短路程为基数，进行统计。由于导航过程中无先验数据库的参考，故直线路径为理想结果。表l导航路程比Table l Comparin of different曲Vigation model in distance ratio通过表1能够看到，在无先验地磁数据的情况下，改进前后的算法均能够引导载体到达目标点，摆脱了地磁导航对先验数据库的依赖；改进前的航程比近似为24，而改进后的航程比为2，改进后的方法明显缩短了导航路程。(2)稳定对比由于地磁仿生导航采用了随机游走模型作为导航搜索的基础，导航路径具有很强的随机性，对于导航算法时长的万方数据1648 系统

21、工程与电子技术 第38卷稳定则是算法性能主要的指标。以表1所对应的实验为对象，对导航耗时进行统计分析如图5所示。改进前；：改进后。图5稳定性对比Fig5 Comparison of different navigation model stability从导航耗时的统计均值来看，改进后的方法在导航耗时上普遍有所提升。对两者耗时的方差进行统计后，发现两者差异较小，改进后的方法在搜索可控性上与改进前基本持平。换而言之，限制分布熵的最低门限后，并未因增加或降低种群多样性，而影响导航搜索行为的随机性，反而通过有效合理的权衡探索与开发的搜索偏向，缩短了导航耗时，提升了导航效率。5 结 论本文从探索与开发

22、角度，研究了地磁仿生导航搜索问题，建立了探索与开发权衡的导航方法。借鉴熵理论知识，评估种群多样性，通过对分布熵的动态约束，提升导航搜索效率。最后利用实验仿真的方法，给出合理取值范围。分布熵的门限设置在一定程度上增加了种群多样性，能够避免一定程度的局部极值，然而受地磁场异常存在，搜索空间中局部极值分布极为复杂，容易陷入局部最优。这一问题，将是下一阶段的工作重点。参考文献：1Lohmann K J，Luschi P，Hays G CGoal nav追ation and island-finding in sea turtlesJJoMm“o，Erpe一柠醒眦口f Ma一船BioogynndoZog

23、y，2008，356(1)：83952Mora C V，Davison M，wiId J M，et aIMagnetoreception andits trigeminal mediation in the homing pigeon口Nn“re，2004，432(7016)：5085113Hays G cA血mal rlavigation：salmon track magnetic variation口CkrM眦BioZogy，2013，23(4)：144一1454Grocott D F HMaps in mind_how animaIs get home?口Th，o“rn口Z o，N口“g

24、口io竹，2003，56(1)：l一145walker M M，Dennis T E，Kirschvink J LThe magnetic senseand its use in long-distance navigation by animalsJc“rrPnO声iniDn in Ne“r06ioZog，2002，12(6)：7357446wiltschko R，wiltschko w MagnetoreceptionJBioesmys，2006，Z8(Z)：1571687Liu M，Liu K，Li H，et a1A study of bioinspired geomagneticnav

25、igation using timing evolutjon searching strategyJ_，。“，w口zo，Norf叫es拓rn PZDye如nicnUni口er“缈，2014，32(6)：894898(刘明雍，刘坤，李红，等基于时序进化搜索策略的地磁仿生导航研究口西北工业大学学报，2014，32(6)：894898)8Liu M，Liu K，Yang P，et aIBioinspired navigation based ongeomagneticcProco，fP JEEE J以把rnnionnz conrP拍：PDRo幻f缸j口肝d Bi口优imffif5，2013：2339

26、234496epin盖ek M，Liu s HMernik MExpIoration and exploitationin evolutionary algorithms：a surveyJACM Comp“fi竹g s“r一可Pj，s，2013，45(3)：13410Lavie D，Rosenkopf L Balancing exploration and expIoitationin alliance formationJAcndP优y o，Mnnng已m鲫Jo越rnnz，2006，49(4)：79781811Nehrnzow USci8if”M旃。出抽M6泷r06优ifs：口”i缸iw鲫

27、zys妇o-厂班耐施“o“rM_L0ndon：Springer，200612ursem R K Diversityguided evoIutionary algorithmscProcof tk Pnmlel Probzem Solut托g from NaturePPSNW，2002：46247113Avens L，Lohmann K JUse of multjple o“emation cue5 by juvenile loggerhead sea turtles Caretta carettaJThP JD“rnnz o，EpPrimen口Z BioZogy，2003，206(23)：43174325作者简介：刘明雍(1971一)，男，教授，博士，主要研究方向为自主水下航行器与自主移动机器人、先进控制理论与应用、信息融合理论与应用。Email：liumingyongnwpueducn刘坤(1984一)，通讯作者，男，博士研究生，主要研究方向为地磁仿生导航、多目标优化。E-mail：Iiukunkmz126com李红(1985一)，女，博士研究生，主要研究方向为地磁仿生导航、进化搜索。Email：mydreamlLhong126com彭星光(1981一)，男，副教授，博士，主要研究方向为进化计算、机器学习、水下机器人。E-mail：pxgnwpueducn万方数据