一种基于元胞自动机的改进遗传算法

从冯·诺依曼“自复制自动机”到生命演化宇宙从确定的、自洽的规则中，也可以产生有序的、不确定的、自相似的结构，这种结构就是分形和混沌。

但是宇宙的演化并不止步于此，它从结构中再次演化出“自我执行与自我复制”的机制，并在此基础上酝酿出复杂生命。

“现代电子计算机之父”冯·诺依曼证明了可自我复制及可自动执行的程序是逻辑可行的，他在《自复制自动机理论》第一章中这样描述：“我们可以做下面这件事，我们可以把机器A和B组合在一起，并给A+B添加一个控制器C。

C按照下列方式对A和B施加控制：C 先命令B拷贝两份描述Φ(X)；然后再命令A按照Φ(X)来实际制造X，并把其中的1份Φ(X)拷贝去掉；最后，C会把X和剩下的那份Φ(X)捆在一起，并把它们从机器A+B+C的组合中间分离出去，这样一来，我们就制造出了X+Φ(X)这样的组合。

按照以上原理，如果我们用（A+B+C）来代替X，并进行上述同样的操作的话，那么(A+B+C)+Φ(A+B+C)的自动机组合，就可以制造出新的自动机组合：(A+B+C)+Φ(A+B+C)。

因此，自动机自复制得到了实现！”冯·诺依曼冯·诺依曼认为，生命就好像是宇宙中物理、数学法则的黑客，专门寻找后门，从而利用它完成自己的复制。

而生命所利用的漏洞恰恰是“概率论”中的漏洞，因此生命这种现象必然是一种“统计的”规律。

换句话说，生命是用一大堆不可靠的原件搭建起来的一台可靠的机器，这台可靠的机器会操纵概率法则来“统计地”实现自身的存在。

我们看到自然界中具有自复制自执行能力的系统都具有一定的复杂度，这个复杂度保证它能保持系统的稳定、延续和进化，而低于这个复杂度的系统则随着时光的流逝注定要被热力学熵增无情的吞噬。

冯·诺依曼研究自复制自执行系统的初衷就是为了找出这个复杂度的阈值，只有那些达到一定的复杂性并且突破了某个阈值的系统才有可能成功的利用“概率论中的漏洞”。

一种改进的混合遗传算法［提要］为了提高遗传算法的搜索效率，给出了一种改进的遗传算法。

该算法提出了新的交叉操作和仿粒子群变异，扩大了搜索范围。

通过经典函数的测试表明，改进算法与一般自适应遗传算法相比较，在函数最优值、平均收敛代数、收敛概率等方面都取得了令人满意的效果。

关键词：自适应遗传算法；适应度函数；交叉操作；仿粒子群变异中图分类号：TP3 文献标识码：A收录日期：2012年1月12日一、引言遗传算法（GA）由美国Michigan大学的Holland教授于1975年首先提出，后经De Jong、GoldBerg等人改进推广，广泛应用于各类问题。

它是一种模拟自然界生物进化过程与机制的全局概率优化搜索方法。

早期遗传算法在进化过程中易出现早熟收敛和局部收敛性差等问题，为了克服上述问题，人们提出了多种改进算法，本文针对遗传算法的不足，采用实数编码对遗传算法中的交叉和变异操作进行改进，提高了算法全局搜索能力，最后使用改进的算法进行仿真实验，结果表明本算法具有收敛概率高和平均收敛代数少的优点。

二、改进的遗传算法1、改进的交叉操作。

本文遗传算法采用实数编码，改进的交叉操作是先在交叉前产生三个服从均匀分布的随机数a∈［0，1］、b∈［－1，1］、c∈［－1，1］，然后假设x1，x2是要交叉的两个父代，个体变量为m维，则x1，x2可以表示为x1=（x11，x12，…，x1m），x2=（x21，x22，…，x2m），其中为位移变量，其中?驻ij=min｛（xij-），（－xij）｝（i=1，2；j＝1，2，…m），最后进行两次操作得：x1’=x1+b•?驻1x2’=x2+c•?驻2 （1）x1’’=ax1’+（1－a）x2’x2’’=ax2’+（1-a）x1’ （2）x1’，x2’，x1’’，x2’’分别为两次操作所产生的子代，从这4个子代中选取适应度大的两个保留到下一代。

通过这种操作可以有效地避免两个数值相近的个体进行“近亲繁殖”（数值相近的个体若只进行（2）式的操作会导致种群多样性快速下降），同时由于b，c的选取，生成的x1’，x2’是两个不相干的个体，彼此之间独立，由（2）式决定的后代还可以使子代遗传父代的某些有用因素，同时由于（1）式的位移调整，使得（2）式生成的后代比一般的算数交叉产生后代的范围扩大，提高算法的搜索范围，避免搜索陷入一个局部区域而出现“早熟”，最后再引入竞争机制在这四个后代中选出两个最好后代个体，这样在保证多样性的同时可以加快收敛的速度。

第４５卷第３期２０２３年６月指挥控制与仿真ＣｏｍｍａｎｄＣｏｎｔｒｏｌ＆ＳｉｍｕｌａｔｉｏｎＶｏｌ ４５㊀Ｎｏ ３Ｊｕｎ ２０２３文章编号：１６７３⁃３８１９（２０２３）０３⁃００３９⁃０７基于改进遗传算法的ＡＵＶ动态目标搜索算法谢㊀锋，姚㊀尧，张晓霜（江苏自动化研究所，江苏连云港㊀２２２０６１）摘㊀要：针对水下动态目标搜索问题，提出一种基于改进遗传算法的ＡＵＶ动态目标搜索算法㊂采用蒙特卡罗统计方法生成大量目标运动轨迹，作为计算适应度依据；结合水声模型提出一种新型的累积探测概率计算方式；种群选择采用灾变思想与精英主义相结合方法，保证种群的非劣性和多样性，加速跳出局部极值；采用混沌序列方式选择交叉和变异点，增加种群随机性；采用动态自适应的交叉概率与变异概率，减少经验依赖，保证后期种群多样性㊂仿真实验结果表明，相较于传统算法和经典遗传算法，改进遗传算法能有效避免陷入局部极值，提高搜索概率㊂关键词：动态目标搜索；改进遗传算法；灾变思想；混沌序列；累积探测概率中图分类号：Ｕ６７４ ９４１；ＴＰ２３㊀㊀㊀㊀文献标志码：Ａ㊀㊀㊀㊀ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３⁃３８１９．２０２３．０３．００６ＤｙｎａｍｉｃｔａｒｇｅｔｓｅａｒｃｈａｌｇｏｒｉｔｈｍｆｏｒＡＵＶｂａｓｅｄｏｎｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍＸＩＥＦｅｎｇ，ＹＡＯＹａｏ，ＺＨＡＮＧＸｉａｏｓｈｕａｎｇ（ＪｉａｎｇｓｕＡｕｔｏｍａｔｉｏｎＲｅｓｅａｒｃｈＩｎｓｔｉｔｕｔｅ，Ｌｉａｎｙｕｎｇａｎｇ２２２０６１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｆｏｒｔｈｅｕｎｄｅｒｗａｔｅｒｄｙｎａｍｉｃｔａｒｇｅｔｓｅａｒｃｈｉｎｇｐｒｏｂｌｅｍ，ａｎＡＵＶｄｙｎａｍｉｃｔａｒｇｅｔｓｅａｒｃｈａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｉｍ⁃ｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ．ＴｈｅＭｏｎｔｅＣａｒｌｏｍｅｔｈｏｄｉｓｕｓｅｄｔｏｇｅｎｅｒａｔｅａｌａｒｇｅｎｕｍｂｅｒｏｆｔａｒｇｅｔｍｏｔｉｏｎｔｒａｊｅｃｔｏｒｉｅｓａｓｔｈｅｂａｓｉｓｆｏｒｃａｌｃｕｌａｔｉｎｇｔｈｅｆｉｔｎｅｓｓ；ａｎｏｖｅｌｗａｙｔｏｃａｌｃｕｌａｔｅｔｈｅｃｕｍｕｌａｔｉｖｅｄｅｔｅｃｔｉｏｎｐｒｏｂａｂｉｌｉｔｙｉｓｐｒｏｐｏｓｅｄｉｎｃｏｍｂｉｎａ⁃ｔｉｏｎｗｉｔｈｔｈｅｈｙｄｒｏａｃｏｕｓｔｉｃｍｏｄｅｌ；ｔｈｅｐｏｐｕｌａｔｉｏｎｓｅｌｅｃｔｉｏｎａｄｏｐｔｓａｃｏｍｂｉｎａｔｉｏｎｏｆｃａｔａｓｔｒｏｐｈｅｉｄｅａａｎｄｅｌｉｔｉｓｍｍｅｔｈｏｄｔｏｅｎｓｕｒｅｔｈｅｎｏｎ⁃ｉｎｆｅｒｉｏｒｉｔｙａｎｄｄｉｖｅｒｓｉｔｙｏｆｔｈｅｐｏｐｕｌａｔｉｏｎａｎｄａｃｃｅｌｅｒａｔｅｔｈｅｊｕｍｐｏｕｔｏｆｌｏｃａｌｅｘｔｒｅｍｅｓ；ｃｈａｏｔｉｃｓｅｑｕｅｎｃｅｉｓｕｓｅｄｔｏｓｅｌｅｃｔｔｈｅｃｒｏｓｓｏｖｅｒｐｏｉｎｔｓａｎｄｖａｒｉａｔｉｏｎｐｏｉｎｔｓｔｏｉｎｃｒｅａｓｅｔｈｅｐｏｐｕｌａｔｉｏｎｒａｎｄｏｍｎｅｓｓ；ａｄｏｐｔｉｎｇｄｙｎａｍｉｃａｄａｐｔｉｖｅｃｒｏｓｓｏｖｅｒｐｒｏｂａｂｉｌｉｔｙａｎｄｖａｒｉａｔｉｏｎｐｒｏｂａｂｉｌｉｔｙｒｅｄｕｃｅｅｍｐｉｒｉｃａｌｄｅｐｅｎｄｅｎｃｅａｎｄｅｎｓｕｒｅｐｏｐｕｌａｔｉｏｎｄｉｖｅｒｓｉｔｙｉｎｔｈｅｌａｔｅｒｓｔａｇｅ．Ｔｈｅｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｃａｎｅｆｆｅｃｔｉｖｅｌｙａｖｏｉｄｆａｌｌｉｎｇｉｎｔｏｌｏｃａｌｅｘｔｒｅｍｅｓａｎｄｉｍｐｒｏｖｅｔｈｅｓｅａｒｃｈｐｒｏｂａｂｉｌｉｔｙｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｔｒａｄｉｔｉｏｎａｌａｌｇｏｒｉｔｈｍａｎｄｃｌａｓｓｉｃａｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ．Ｋｅｙｗｏｒｄｓ：ｄｙｎａｍｉｃｔａｒｇｅｔｓｅａｒｃｈ；ｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｃａｔａｓｔｒｏｐｈｅｉｄｅａ；ｃｈａｏｔｉｃｓｅｑｕｅｎｃｅ；ｃｕｍｕｌａｔｉｖｅｄｅｔｅｃｔｉｏｎｐｒｏｂａｂｉｌｉｔｙ收稿日期：２０２２⁃１１⁃０１修回日期：２０２２⁃１２⁃１３作者简介：谢㊀锋（１９９８ ），男，硕士研究生，研究方向为控制工程㊂姚㊀尧（１９８４ ），女，博士，研究员㊂㊀㊀自主水下机器人（ＡｕｔｏｎｏｍｏｕｓＵｎｄｅｒｗａｔｅｒＶｅｈｉｃｌｅ，ＡＵＶ）航行噪声低㊁机动灵活㊁无人员伤亡等优点非常适用于各种水下作业，如探测㊁搜索㊁追踪㊁围堵等［１］㊂目前多数ＡＵＶ受续航能力限制，航速有限，面向水下有人平台搜索任务难以在任务约束时间内完成任务区域覆盖搜索［２⁃４］㊂因此如何有效规划ＡＵＶ的搜索路径，使得有限时间内搜索到目标的概率最大，成为亟待解决的关键问题㊂ＡＵＶ动态目标搜索过程实质上是连续时间和空间上的优化搜索问题，较多研究者在研究搜索作业时都进行了一定的简化处理，如将区域网格化等［５］，但这种方法使得搜索过程离散化，与实际情况有着较大的差异㊂遗传算法作为一种搜索启发式算法，广泛应用于解决最优化问题［６］，因此其适用于上述有限时间内动态目标搜索问题，但它也存在一定的不足，如各种算子的参数选择大多依靠经验，存在着一定的随机性，算法在大规模计算问题中容易陷入 早熟 ，即过早陷入局部极值，除此之外，既保留优秀个体又维持种群多样性同样也是该方法的一个难点㊂因此在解着决上述问题时需要对遗传算法进行优化㊂１㊀问题描述由于敌方目标在一定时间内航行深度较为稳定，本文重点研究二维平面内的搜索规划方法㊂假设某一时刻一艘ＡＵＶ接收到岸基总台发送的敌目标指示信息，目标位置记为Ｐｔ０，记岸基位置为坐标原点，以正东方向为Ｘ轴，正北方向为Ｙ轴建立平面直角坐标系，则目标位置可表示为Ｐｔ０＝ｘｔ０，ｙｔ０()㊂当ＡＵＶ到达Ｐｔ０位置，开始执行搜索任务，记为０时刻㊂ＡＵＶ在前往Ｐｔ０位置过程中，水下目标也处于动态运动中，但水下目标的运动具有很强的随机性，ＡＵＶ无法事先知道，故假设当ＡＵＶ到达Ｐｔ０位置时，水下目标运动起始位置Ｐｔ１＝ｘｔ１，ｙｔ１()服从二维正态分布，即４０㊀谢㊀锋，等：基于改进遗传算法的ＡＵＶ动态目标搜索算法第４５卷ｆｘｔ１，ｙｔ１()＝１２πσ２ｅ－（ｘｘ）＋（ｙｙ）２σ（１）其中，σ为导航误差㊂在一段较长的固定时间０，Ｔｅｎｄ[]的搜索任务中，ＡＵＶ和水下目标的转向时间可忽略不计㊂ＡＵＶ为确保探测声呐的稳定性，搜索行进时采用匀速航行，期间可多次调整方向，直至搜索时间结束㊂相比之下，水下运动目标具有更多的不确定性，可以多次进行改向和变速操作，但水下目标在转向时由于结构和体型等原因，无法像ＡＵＶ一样进行较大幅度的转向，目标在转向前的航向角αｎ和转向后的航向角αｎ＋１，应满足公式（２）和（３），其中ｆα１()为其开始任务时的航向角α１的概率密度函数㊂ｆα１()＝１２π㊀α１ɪ０，２π[)０ｅｌｓｅ{（２）αｎ＋１－αｎɤπ３㊀（αｎɪ［０，２π））（ｎ＝１，２，３， ）（３）目标各段速度ｖ的取值服从Ｖｍｉｎ，Ｖｍａｘ[]之间的均匀分布，各段航行时间ｔ服从参数为λ的指数分布㊂它们的概率密度函数如下所示：ｆｖ()＝１Ｖｍａｘ－Ｖｍｉｎ㊀Ｖｍｉｎ＜ｖ＜Ｖｍａｘ０ｅｌｓｅìîíïïï（４）ｆ（ｔ）＝λｅ－λｔ㊀λ＞０，ｔ＞００ｅｌｓｅ{（５）式（４）中Ｖｍａｘ和Ｖｍｉｎ分别为水下动目标的最大和最小运行速度㊂根据上述模型构建，所能得到的目标运动轨迹数目是无限的，无法通过列举等常规方法得出运动轨迹，但借用蒙特卡罗（ＭｏｎｔｅＣａｒｌｏ）方法，可以通过计算机辅助生成大量目标运动轨迹作为水下目标实际运动轨迹的模拟㊂蒙特卡罗目标运动模型由大量的目标轨迹组成，轨迹路线可以源自于历史数据分析，也可能源自于先验地图的仿真，也可以像前文所描述的采用随机数生成的方法，产生大量目标运动轨迹，抑或是多种数据的融合㊂以５０束目标运动轨迹为一簇作为基础，可以将这些轨迹整合为多簇，通过计算机模拟仿真生成的一簇轨迹如图１所示㊂受水中因素的影响，ＡＵＶ在搜索过程中常采用的工具是声呐，包括主动声呐和被动声呐，在本文中为扩大探索范围，可采用被动声呐进行探测，根据ＡＵＶ与水下动目标的距离Ｄ（单位：海里）进行瞬时探测，瞬时探测ＰＤ()可描述为下式图１㊀计算机模拟生成的５０条目标运动轨迹Ｆｉｇ １㊀Ｔｈｅ５０ｔａｒｇｅｔｔｒａｊｅｃｔｏｒｉｅｓｇｅｎｅｒａｔｅｄｂｙｃｏｍｐｕｔｅｒｓｉｍｕｌａｔｉｏｎＰＤ()＝１㊀㊀Ｄɤ１０．８１＜Ｄɤ２０．５２＜Ｄɤ３０Ｄ＞３ìîíïïïï（６）与其他搜索过程所注重的完成全覆盖搜索所用时间等完成度指标不同的是，本文将目标函数设为在一定时间内的最大探测概率，又称为累积探测概率（Ｃｕ⁃ｍｕｌａｔｉｖｅＤｅｔｅｃｔｉｏｎＰｒｏｂａｂｉｌｉｔｙ，ＣＤＰ）［７］㊂在０ɤｔɤＴ时，ｔ时刻的累积探测概率（ＣＤＰ）记为Ｆｄ（ｔ），定义为［０，Ｔ］时间段内至少发生一次探测的概率，即Ｆｄ（ｔ）＝Ｐｒ｛在时刻ｔ以前至少发生一次探测｝＝Ｐｒ初始探测时间ɤｔ{}２㊀基于改进遗传算法的目标搜索策略遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，简称ＧＡ）作为一种随机全局搜索优化方法，概念来源于生物系统的遗传与进化，通过模拟自然界基因层面上的复制㊁交叉（ｃｒｏｓｓｏｖｅｒ）和变异（ｍｕｔａｔｉｏｎ）等现象以及自然界中的物竞天择现象，在一代又一代种群的繁衍进化中，得到最适应环境的个体，即求得问题的最优解［６］㊂但它也存在着易 早熟 ，过早陷入极值等问题㊂本文采用改进遗传算法进行搜索路径优化，并采用蒙特卡罗统计方法建立评价度指标，在种群的选择上将灾变思想与精英主义相结合，既保留优秀个体，同时也给予种群产生更优秀基因片段的机会，避免过早陷入局部极值㊂交叉和变异操作基于椭圆约束遗传算子，并采用混沌序列对交叉或变异点的选取进行改进，再对交叉概率与变异概率进行动态自适应，减少对经验的依赖，同时尽量在后期也维持种群的多样性，具体流程图如图２所示㊂第３期指挥控制与仿真４１㊀图２㊀改进遗传算法流程图Ｆｉｇ ２㊀Ｆｌｏｗｃｈａｒｔｏｆｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ遗传算法最重要的几个部分为遗传算法编码的描述，适应度函数的设计，初始种群的产生，遗传过程中选择㊁交叉㊁变异的操作和最后的迭代终止条件的设定［８］㊂２ １㊀编码编码作为遗传算法的首要和关键步骤，会对交叉算子㊁变异算子等运算方法产生重要影响，进而影响遗传算法的效率［９］㊂在此问题中，ＡＵＶ的搜索过程实质上是连续时间和空间上的优化搜索问题，因此ＡＵＶ的编码形式采用变长实数编码㊂设Ｐ为种群的总体，种群大小为Ｎ，种群内的个体记为ｐｉ（ｉ＝１，２，３， ，Ｎ），表示一条搜索路径，每一个个体由多个基因组成，即ｐｉ＝（ｇｉ１，ｇｉ２， ，ｇｉｊ， ），ｇｉｊ代表第ｉ个个体上的第ｊ个基因，而ｇｉｊ＝ｘｉｊ，ｙｉｊ，ｔｉｊ()，其中ｘｉｊ，ｙｉｊ，ｔｉｊ分别代表第ｉ个个体运行至节点ｊ时的横坐标，纵坐标和时间点㊂２ ２㊀适应度函数由于此搜索过程是连续时间和空间上的［１０⁃１２］，航路实际上是无限条的，需要设计一个目标函数（适应度函数）作为评价指标，即后续选择操作的依据㊂本文采用ＣＤＰ作为适应度函数，可根据水声模型及离散探测概率公式，由蒙特卡罗法完成适应度函数的计算㊂假设根据蒙特卡罗法生成了Ｓ条目标路线，其中第ｊ条路线记为Ｓｊ，而在种群某代中某一个体ｐｉ有Ｍ个基因（即Ｍ个坐标点），则其路线共有Ｍ－１段，每一段均分为１０个点作为这一段的采样点，分别计算个体ｐｉ和路线Ｓｊ在这１０个采样点时刻的距离差值，代入公式（６）计算得到这１０个点的瞬时探测概率，取其中的最大值代表个体ｐｉ在第ｋ段的瞬时探测概率，记为Ｐｉｎｓ（ｋ）（ｋ＝１，２，３， ，Ｍ－１），则ｐｉ对Ｓｊ的探测概率可描述为Ｐｉｊ＝Ｆ（Ｐｉｎｓ（１），Ｐｉｎｓ（２）， ，Ｐｉｎｓ（Ｍ－１））（７）根据文献［７］和实验总结，可设计得到如下ＣＤＰ的计算公式㊀Ｆｄ（ｔ）＝１－１－Ｐｉｍａｘ１－αＰｉｍａｘᵑＭ－１ｋ＝１（１－αＰｉｎｓ（ｋ））（８）式中，α＝１－ｅ－λΔ，Δｋ为个体ｐｉ中第ｋ段路线的用时，Ｐｉｍａｘ为Ｐｉｎｓ（ｋ）中的最大值㊂２ ３㊀种群的产生初始种群按照一定的随机性生成初始群体㊂按照编码规则随机生成初始群体㊂初始种群可采用随机生成的方式，随机生成的个体可提供更丰富的基因片段，通过交叉和选择可留下更优秀的个体㊂２ ４㊀遗传过程的选择遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取优秀个体，以便遗传到下一代群体㊂选择操作用来确定重组或交叉个体，以及被选个体将产生多少个子代个体㊂现在大多数遗传算法的选择过程采用的都是轮盘赌的方式，但也会带来早期高适应度个体迅速占据种群和后期的种群中因个体适应度不大而导致的种群停止进化问题［６］㊂为避免此类问题，提出灾变思想与精英主义相结合的思想㊂灾变思想［１３］是指消灭最优秀的一部分个体，才有可能诞生更优秀的个体，而精英主义思想是指在每一次产生新一代时，保留上一代最优秀的一部分个体到下一代㊂看似冲突的两者却可以相结合㊂在每一代进行交叉运算时，直接将最优秀的个体复制到下一代，但当连续多代的最优秀个体没有变化时，则认为算法可能已经陷入了局部极值，此时进行灾变操作，将最优秀的部分个体消灭（包括直接保留的最优秀个体），再进行交叉变异等操作，在经历过若干次灾变后产生个体的适应度与灾变前一样时，则停止灾变，同时４２㊀谢㊀锋，等：基于改进遗传算法的ＡＵＶ动态目标搜索算法第４５卷认为算法已经跳出局部极值，表明进化完成㊂２ ５㊀遗传过程的交叉本文采用基于椭圆约束的单点交叉策略［１４⁃１５］，交叉概率设为Ｐｃ㊂如图３所示，若选择种群内的两个个体（即两条染色体）ｐ１和ｐ２进行交叉操作，Ａ㊁Ｂ㊁Ｃ三点位于染色体ｐ１上，坐标分别为ＸＡ，ＸＢ，ＸＣ，在时间轴上所代表的时间分别为ｔＡ，ｔＢ，ｔＣ，Ｄ㊁Ｅ㊁Ｆ三点位于染色体ｐ２上，坐标分别为ＸＤ，ＸＥ，ＸＦ，在时间轴上所代表的时间分别为ｔＤ，ｔＥ，ｔＦ，而Ｔ１和Ｔ２分别位于染色体ｐ１和ｐ２上，但它们在时间轴上都代表同一时刻ｔｃ，由于ＡＵＶ一直保持匀速运动，染色体的交叉过程应满足椭圆约束㊂在此设ｄＸｉ，Ｘｊ()代表Ｘｉ和Ｘｊ两点间的欧氏距离，而Ｘｉ可表示为Ｘｉ＝（ｘｉ，ｙｉ），因此有ｄＸｉ，Ｘｊ()＝ｘｉ－ｘｊ()２＋ｙｉ－ｙｊ()２（９）以图３为例，分别选取染色体ｐ１和ｐ２上的Ｂ㊁Ｅ两点作为交叉点，很明显，Ｂ㊁Ｅ两点需要满足ｄＢ，Ｅ()ɤＶ０ˑｔＢ－ｔＥ（１０）其中Ｖ０为ＡＵＶ的匀速速度㊂但线段ＢＥ不可能每次都恰好满足ＡＵＶ运动时的空间和时间上的连续性，即ｄＢ，Ｅ()＝Ｖ０ˑｔＢ－ｔＥ不是对所有的交叉点Ｂ和Ｅ都成立，因此，需要找一个点Ｇ，使得Ｅ㊁Ｇ间距离与Ｂ㊁Ｇ间距离之和等于Ｅ到Ｔ２的距离与Ｔ１到Ｂ的距离之和，即：ｄＢ，Ｇ()＋ｄＥ，Ｇ()＝Ｖ０ˑｔＴ－ｔＥ＋Ｖ０ˑｔＴ－ｔＢ＝Ｖ０ˑｔｃ－ｔＥ＋Ｖ０ˑｔｃ－ｔＢ＝Ｖ０ˑｔＢ－ｔＥ（１１）而Ｖ０ˑｔＢ－ｔＥ对于任意两个确定的交叉点Ｂ和Ｅ，其值都为一个常数，因此可看出Ｇ点位于以Ｂ㊁Ｅ为焦点的椭圆上，但由于时间上的不可逆性，通过基于椭圆约束的交叉方法只能生成１条子染色体，如图３中只能生成ＤＥＧＢＣ这条子染色体㊂图３㊀基于椭圆约束的交叉节点示意图Ｆｉｇ ３㊀Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｃｒｏｓｓｏｖｅｒｄｉａｇｒａｍｂａｓｅｄｏｎｅｌｌｉｐｔｉｃｃｏｎｓｔｒａｉｎｔｓ例子中的交叉点Ｂ㊁Ｅ可按照Ｌｏｇｉｓｔｉｃ混沌序列［１６］方式进行选取，具体步骤如下：若被选择染色体ｐ１共有２０个节点（包括起点和终点），编号为１－２０，因此可选取的交叉节点只有２－１９号㊂先取一个（０，１）的随机初始值，再利用混沌序列ｘ（ｎ＋１）＝４ｘ（ｎ）（１－ｘ（ｎ））迭代多次（即多次代入ｘ（ｎ））产生一个新值，再把这个值乘以１８再加２，最后取整数部分即可㊂假如这个数为１４，则表示这条染色体的１４号节点作为交叉点㊂同理可选取出ｐ２的交叉点，再按时间先后顺序生成了染色体㊂这种选取方式对原来的解改动较小，可以削弱遗传算法在组合优化算法中产生的寻优抖振问题，可以提高算法收敛精度［１６］㊂由于交叉过程中Ｇ点的选择具有较强的随机性，为做出一定的规范，取其椭圆短轴的顶点，顶点的选取应使ＥＧ的方向与ＤＥ的方向夹角不超过９０ʎ㊂２ ６㊀遗传过程的变异变异操作是实现全局最优解的关键环节，增加变异运算可以防止过早陷入局部最优解㊂在此模型中，变异概率设为Ｐｍ，可采用的合适的变异操作有替换节点或消除节点两种方案，采用替换和消除操作的概率相等，都为５０％㊂被替换节点Ｎｉ同样按照Ｌｏｇｉｓｔｉｃ混沌序列方式进行选取㊂替换节点和交叉一样，也受到椭圆约束，如图４所示㊂ｐ为一条染色体，替换节点选择Ｎｉ，Ｎｉ的前一个节点为Ｎｉ－１，Ｎｉ的后一个节点为Ｎｉ＋１，为保持ＡＵＶ运动时在空间和时间上的连续性，将节点Ｎｉ替换为Ｎᶄｉ时，应满足ｄＮｉ－１，Ｎᶄｉ()＋ｄＮᶄｉ，Ｎｉ＋１()＝ｄＮｉ－１，Ｎｉ()＋ｄＮｉ，Ｎｉ＋１()（１２）对每一条确定的染色体ｐ，ｄＮｉ－１，Ｎｉ()＋ｄＮｉ，Ｎｉ＋１()都为一个常数，因此，更改的节点Ｎᶄｉ也位于以Ｎｉ－１和Ｎｉ＋１为焦点的椭圆上㊂消除节点操作是指删去染色体中的某一节点Ｎｊ，将Ｎｊ的前一个节点Ｎｊ－１以及Ｎｊ的后一个节点Ｎｊ＋１连起来，并且将从Ｎｊ＋１及以后的节点的对应时间都进行改正，并在最后的节点末尾加上一段运动轨迹，以弥补因为删除节点而缺少的时间，使ＡＵＶ能在Ｔｅｎｄ时刻结束搜索㊂图４㊀基于椭圆约束的替换节点示意图Ｆｉｇ ４㊀Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｒｅｐｌａｃｅｍｅｎｔｎｏｄｅｂａｓｅｄｏｎｅｌｌｉｐｔｉｃｃｏｎｓｔｒａｉｎｔ２ ７㊀自适应的交叉与变异概率遗传算法中的交叉概率Ｐｃ和变异概率Ｐｍ对算法的行为和性能影响非常大，Ｐｃ过大会导致遗传模式出第３期指挥控制与仿真４３㊀现问题，高适应度的个体很难存活，Ｐｃ过小会导致搜索速度慢，种群停滞不前㊂Ｐｍ过大则偏向于随机搜索，Ｐｍ过小则不易产生新的个体，且算法各时期对交叉和变异的需求都不同，因此，Ｐｃ和Ｐｍ应随着适应度自动变化㊂本文采用任子武［１７］等提出的自适应公式㊂㊀Ｐｃ＝Ｐｃ１－Ｐｃ１－Ｐｃ２()ｆｍａｘ－ｆᶄ()ｆｍａｘ－ｆａｖｇ㊀ｆᶄȡｆａｖｇＰｃ１ｆᶄ＜ｆａｖｇìîíïïïï（１３）㊀Ｐｍ＝Ｐｍ１－Ｐｍ１－Ｐｍ２()ｆｍａｘ－ｆ()ｆｍａｘ－ｆａｖｇ㊀ｆȡｆａｖｇＰｍ１ｆ＜ｆａｖｇìîíïïïï（１４）其中，变量Ｐｃ和Ｐｍ为自适应后的交叉概率和变异概率，ｆｍａｘ为每代种群中最大的适应度值，ｆａｖｇ为每代种群中平均适应度值，ｆᶄ为要交叉的两个个体中较大的适应度值，ｆ为要变异个体的适应度值㊂Ｐｃ１㊁Ｐｃ２㊁Ｐｍ１㊁Ｐｍ２都有规范的取值㊂３㊀实验与仿真本次实验仿真平台为Ｍａｔｌａｂ，实验参数设置：水下动目标最小航速为０节，代表静止，最大航速为２０节；被发现初始位置点Ｐｔ０为（５０，５０），单位为海里，其运行路线为折线；ＡＵＶ行进匀速速度为１０节，两者水平面间距离为２海里，搜索任务总时长为３ｈ㊂为使结果更具有适用性和可靠性，在初始生成的路线数量设定上应尽可能多一些，因此设定初始种群的数量为１００，进化最大代数为１００，采用蒙特卡罗法仿真的水下动目标路线为２０００条㊂选择操作中直接保留优秀个体中的适应度值前２％的个体，而灾变操作中直接删除的个体占总数的５％，交叉算子和变异算子中的Ｐｃ１㊁Ｐｃ２㊁Ｐｍ１㊁Ｐｍ２取值采用经典取值，分别为０ ９㊁０ ６㊁０ １㊁０ ００１㊂先采用外螺旋式传统算法进行实验，可得到其行进路线，如图５所示，并与用蒙特卡罗法生成的２０００条水下目标运动路线进行仿真计算，可得出其探测概率为０ ４２９㊂传统遗传算法在同样的仿真环境，问题模型以及种群数目㊁目标数目和种群迭代数目等参数相同的条件下，得到的最优路径路线如图６所示，其各代最优适应度函数曲线如图７所示，各代探测概率中的最大值为５６ １％㊂从这个最大值可以看出，经典遗传算法相比外螺旋式传统算法，路径整体也呈现外螺旋式结构，但不规则，且各代最优适应度函数曲线整体先逐渐上升后趋于稳定㊂因为经典遗传算法未引入精英主义策略，所以该函数曲线不是每代的最大探测概率都能保证比上一代大，即呈现波动上升的趋势，且遗传算法由图５㊀外螺旋式搜索路径Ｆｉｇ ５㊀Ｅｘｔｅｒｎａｌｓｐｉｒａｌｓｅａｒｃｈｐａｔｈ于自身的局限性，非常容易陷入局部极值，像该曲线一样，从４４代开始最大探测概率就在５３％上下波动㊂图６㊀经典遗传算法最大适应度个体搜索路径Ｆｉｇ ６㊀Ｃｌａｓｓｉｃａｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｍａｘｉｍｕｍｆｉｔｎｅｓｓｉｎｄｉｖｉｄｕａｌｓｅａｒｃｈｐａｔｈ图７㊀经典遗传算法最大探测概率进化曲线Ｆｉｇ ７㊀Ｅｖｏｌｕｔｉｏｎｃｕｒｖｅｏｆｍａｘｉｍｕｍｄｅｔｅｃｔｉｏｎｐｒｏｂａｂｉｌｉｔｙｏｆｃｌａｓｓｉｃａｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ４４㊀谢㊀锋，等：基于改进遗传算法的ＡＵＶ动态目标搜索算法第４５卷由改进遗传算法得到的最优路径路线如图８所示，此路线和传统遗传算法一样，呈不规则的外螺旋状㊂改进遗传算法各代最优适应度函数曲线如图９所示，各代探测概率中的最大值为６３ ３％，从此值的对比可看出改进遗传算法累积探测概率明显优于外螺旋式传统算法，也优于经典遗传算法㊂由于引进了精英主义思想，保留最优秀个体，除了灾变发生时曲线基本不会下降㊂当多次最优适应度基本不变时，会进行灾变操作，去除最优的部分个体，此时曲线会降低，后逐步上升㊂改进遗传算法和经典遗传算法由于计算量基本相同，所用时间都较长，经典遗传算法收敛速度更快，但它更容易陷入极值，改进遗传算法在搜索概率上更具优势㊂图８㊀改进遗传算法最大适应度个体搜索路径Ｆｉｇ ８㊀Ｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｍａｘｉｍｕｍｆｉｔｎｅｓｓｉｎｄｉｖｉｄｕａｌｓｅａｒｃｈｐａｔｈ图９㊀改进遗传算法最大探测概率进化曲线Ｆｉｇ ９㊀Ｅｖｏｌｕｔｉｏｎｃｕｒｖｅｏｆｍａｘｉｍｕｍｄｅｔｅｃｔｉｏｎｐｒｏｂａｂｉｌｉｔｙｏｆｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ４㊀结束语针对未知区域的动态目标搜索问题，本文提出采用灾变思想与精英主义相结合的改进遗传算法，采用蒙特卡罗统计方法生成大量目标运动轨迹，作为计算种群个体适应度依据㊂同时在适应度函数的设计上结合水声模型提出一种新型的累积探测概率算法，使其具有更明显的区分性㊂种群选择方法上将灾变思想与精英主义相结合，在保留优秀个体的同时也给予种群产生更优秀基因片段的机会，有效跳出局部极值㊂交叉和变异操作基于椭圆约束遗传算子，并采用混沌序列对交叉或变异点的选取进行改进，提高随机性带来的差距，加速跳出局部极值㊂交叉概率与变异概率采用动态自适应策略，减少对经验的依赖，并在后期维持种群的多样性㊂本算法相较于外螺旋式传统算法和经典遗传算法，能有效跳出局部极值，提高搜索到动态目标的概率㊂尽管此方法得到了较高的搜索概率，但适用场景有限，接下来会考虑ＡＵＶ与目标的纵向运动，将此方法扩展到三维仿真环境中，同时根据实际环境增加障碍物，进一步优化算法的适应度函数设计，提高算法泛用性与可靠性㊂参考文献：［１］㊀朱丹．美军自主水下航行器发展研究［Ｊ］．指挥控制与仿真，２０２０，４２（１）：１３４⁃１４０．ＺＨＵＤ．ＤｅｖｅｌｏｐｍｅｎｔｒｅｓｅａｒｃｈｏｎＵ．Ｓ．ｎａｖｙａｕｔｏｎｏｍｏｕｓｕｎｄｅｒｗａｔｅｒｖｅｈｉｃｌｅ［Ｊ］．ＣｏｍｍａｎｄＣｏｎｔｒｏｌ＆Ｓｉｍｕｌａｔｉｏｎ，２０２０，４２（１）：１３４⁃１４０．［２］㊀张伟，王乃新，魏世琳，等．水下无人潜航器集群发展现状及关键技术综述［Ｊ］．哈尔滨工程大学学报，２０２０，４１（２）：２８９⁃２９７．ＺＨＡＮＧＷ，ＷＡＮＧＮＸ，ＷＥＩＳＬ，ｅｔａｌ．Ｏｖｅｒｖｉｅｗｏｆｄｅｖｅｌｏｐｍｅｎｔｓｔａｔｕｓａｎｄｋｅｙｔｅｃｈｎｏｌｏｇｉｅｓｏｆｕｎｍａｎｎｅｄｕｎ⁃ｄｅｒｗａｔｅｒｖｅｈｉｃｌｅｃｌｕｓｔｅｒ［Ｊ］．ＪｏｕｒｎａｌｏｆＨａｒｂｉｎＥｎｇｉｎｅｅｒｉｎｇＵｎｉｖｅｒｓｉｔｙ，２０２０，４１（２）：２８９⁃２９７．［３］㊀王永鼎，王鹏，孙鹏飞．自主式水下机器人控制技术研究综述［Ｊ］．世界科技研究与发展，２０２１，４３（６）：６３６⁃６４８．ＷＡＮＧＹＤ，ＷＡＮＧＰ，ＳＵＮＰＦ．Ｒｅｖｉｅｗｏｎｒｅｓｅａｒｃｈｏｆｃｏｎｔｒｏｌｔｅｃｈｎｏｌｏｇｙｏｆａｕｔｏｎｏｍｏｕｓｕｎｄｅｒｗａｔｅｒｖｅｈｉｃｌｅ［Ｊ］．ＷｏｒｌｄＳｃｉ⁃ＴｅｃｈＲ＆Ｄ，２０２１，４３（６）：６３６⁃６４８．［４］㊀韦韬，朱遴，梁世龙．水下无人系统集群感知与协同技术发展［Ｊ］．指挥控制与仿真，２０２２，４４（５）：６⁃１３．ＷＥＩＴ，ＺＨＵＬ，ＬＩＡＮＧＳＬ．Ｒｅｓｅａｒｃｈｏｎｐｅｒｃｅｐｔｉｏｎａｎｄｃｏｏｐｅｒａｔｉｏｎｔｅｃｈｎｏｌｏｇｉｅｓｆｏｒｕｎｄｅｒｗａｔｅｒｕｎｍａｎｎｅｄｓｙｓｔｅｍｓｗａｒｍ［Ｊ］．ＣｏｍｍａｎｄＣｏｎｔｒｏｌ＆Ｓｉｍｕｌａｔｉｏｎ，２０２２，４４（５）：６⁃１３．［５］㊀李娟，张建新，杨莉娟，等．未知环境下多自主水下航第３期指挥控制与仿真４５㊀行器目标搜索方法［Ｊ］．哈尔滨工程大学学报，２０１９，４０（１２）：１９５１⁃１９５７，１９７２．ＬＩＪ，ＺＨＡＮＧＪＸ，ＹＡＮＧＬＪ，ｅｔａｌ．Ｔａｒｇｅｔｓｅａｒｃｈｏｆｍｕｌｔｉｐｌｅａｕｔｏｎｏｍｏｕｓｕｎｄｅｒｗａｔｅｒｖｅｈｉｃｌｅｓｉｎａｎｕｎｋｎｏｗｎｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］．ＪｏｕｒｎａｌｏｆＨａｒｂｉｎＥｎｇｉｎｅｅｒｉｎｇＵｎｉｖｅｒｓｉｔｙ，２０１９，４０（１２）：１９５１⁃１９５７，１９７２．［６］㊀杨雄，吴东．遗传算法密码分析中改进选择算子研究［Ｊ］．信息工程大学学报，２０２２，２３（３）：３４４⁃３５０．ＹＡＮＧＸ，ＷＵＤ．Ｉｍｐｒｏｖｅｄｓｅｌｅｃｔｉｏｎｏｐｅｒａｔｏｒｉｎｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎａｌｙｓｉｓ［Ｊ］．ＪｏｕｒｎａｌｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＵｎｉｖｅｒｓｉｔｙ，２０２２，２３（３）：３４４⁃３５０．［７］㊀ＷＡＧＮＥＲＤＨ，ＭＹＬＡＮＤＥＲＷＣ，ＳＡＮＤＥＲＳＴＪ．海军运筹分析［Ｍ］．３版．姜青山，郑保华译．北京：国防工业出版社，２００８：１２３⁃１９３．ＷＡＧＮＥＲＤＨ，ＭＹＬＡＮＤＥＲＷＣ，ＳＡＮＤＥＲＳＴＪ．Ｎａｖａｌｏｐｅｒａｔｉｏｎｓａｎａｌｙｓｉｓ［Ｍ］．Ｔｈｉｒｄｅｄｉｔｉｏｎ．ＪＩＡＮＧＨＳ，ＺＨＥＮＧＢＨ，Ｔｒａｎｓ．Ｂｅｉｊｉｎｇ：ＮａｔｉｏｎａｌＤｅｆｅｎｓｅＩｎｄｕｓｔｒｙＰｒｅｓｓ，２００８：１２３⁃１９３．［８］㊀张献，任耀峰，王润芃．基于自适应遗传算法的连续时空最优搜索路径规划研究［Ｊ］．兵工学报，２０１５，３６（１２）：２３８６⁃２３９５．ＺＨＡＮＧＸ，ＲＥＮＹＦ，ＷＡＮＧＲＰ．Ｒｅｓｅａｒｃｈｏｎｏｐｔｉｍａｌｓｅａｒｃｈｐａｔｈｐｒｏｇｒａｍｍｉｎｇｉｎｃｏｎｔｉｎｕｏｕｓｔｉｍｅａｎｄｓｐａｃｅｂａｓｅｄｏｎａｎａｄａｐｔｉｖｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ［Ｊ］．ＡｃｔａＡｒｍａ⁃ｍｅｎｔａｒｉｉ，２０１５，３６（１２）：２３８６⁃２３９５．［９］㊀ＣＨＯＪＨ，ＫＩＭＪＳ，ＬＩＭＪＳ，ｅｔａｌ．Ｏｐｔｉｍａｌａｃｏｕｓｔｉｃｓｅａｒｃｈｐａｔｈｐｌａｎｎｉｎｇｂａｓｅｄｏｎｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｎｄｉｓｃｒｅｔｅｐａｔｈｓｙｓｔｅｍ［Ｊ］．ＪｏｕｒｎａｌｏｆＯｃｅａｎＥｎｇｉｎｅｅｒｉｎｇａｎｄＴｅｃｈｎｏｌｏｇｙ，２００６，２０（１）：６９⁃７６．［１０］金韩鹏．基于海洋环境的多ＡＵＶ协同探测路径规划技术研究［Ｄ］．杭州：浙江大学，２０２１．ＪＩＮＨＰ．Ｒｅｓｅａｒｃｈｏｎｍｕｌｔｉ⁃ＡＵＶｃｏｏｐｅｒａｔｉｖｅｄｅｔｅｃｔｉｏｎｐａｔｈｐｌａｎｎｉｎｇｔｅｃｈｎｏｌｏｇｙｂａｓｅｄｏｎｍａｒｉｎｅｅｎｖｉｒｏｎｍｅｎｔ［Ｄ］．Ｈａｎｇｚｈｏｕ：ＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉｔｙ，２０２１．［１１］ＣＡＯＸ，ＳＵＮＨＢ，ＪＡＮＧＥ．Ｍｕｌｔｉ⁃ＡＵＶｃｏｏｐｅｒａｔｉｖｅｔａｒ⁃ｇｅｔｓｅａｒｃｈａｎｄｔｒａｃｋｉｎｇｉｎｕｎｋｎｏｗｎｕｎｄｅｒｗａｔｅｒｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］．ＯｃｅａｎＥｎｇｉｎｅｅｒｉｎｇ，２０１８（１），１５０：１⁃１１．［１２］ＬＩＵＬＬ，ＬＩＵＪ，ＮＩＮＧＸＬ，ｅｔａｌ．Ｒｅａｌ⁃ｔｉｍｅａｎｄａｃｃｕｒａｔｅｐｕｌｓａｒｔｉｍｅ⁃ｏｆ⁃ａｒｒｉｖａｌｅｓｔｉｍａｔｉｏｎｕｓｉｎｇＧＡ⁃ｏｐｔｉ⁃ｍｉｚｅｄＥＭＤ⁃ＣＳ［Ｊ］．Ｏｐｔｉｋ，２０２１，２２５（１）：１６５８７１．［１３］张俞，冷璐，黎明．基于灾变机制下元胞遗传算法的精英迁移策略的研究［Ｊ］．科技通报，２０１５，３１（５）：２４６⁃２５０．ＺＨＡＮＧＹ，ＬＥＮＧＬ，ＬＩＭ．Ｓｔｕｄｙｏｎｅｌｉｔｅｍｉｇｒａｔｉｏｎｓｔｒａｔ⁃ｅｇｙｏｆｃｅｌｌｕｌａｒｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｄｉｓｔｕｒｂａｎｃｅｓ［Ｊ］．ＢｕｌｌｅｔｉｎｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，２０１５，３１（５）：２４６⁃２５０．［１４］ＫＩＥＲＳＴＥＡＤＤＰ，ＤＥＬＢＡＬＺＯＤＲ．Ａｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｐｐｌｉｅｄｔｏｐｌａｎｎｉｎｇｓｅａｒｃｈｐａｔｈｓｉｎｃｏｍｐｌｉｃａｔｅｄｅｎｖｉｒｏｎ⁃ｍｅｎｔｓ［Ｊ］．ＭｉｌｉｔａｒｙＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２００３，８（２）：４５⁃５９．［１５］张丹，熊雄，时光．基于遗传算法的航空磁探仪搜索路径优化算法［Ｊ］．电光与控制，２０１７，２４（１）：１０２⁃１０７．ＺＨＡＮＧＤ，ＸＩＯＮＧＸ，ＳＨＩＧ．Ｏｐｔｉｍａｌｓｅａｒｃｈｐａｔｈｐｌａｎ⁃ｎｉｎｇｆｏｒａｉｒｂｏｒｎｅｍａｇｎｅｔｉｃａｎｏｍａｌｙｄｅｔｅｃｔｉｏｎｂａｓｅｄｏｎｇｅ⁃ｎｅｔｉｃａｌｇｏｒｉｔｈｍ［Ｊ］．ＥｌｅｃｔｒｏｎｉｃｓＯｐｔｉｃｓ＆Ｃｏｎｔｒｏｌ，２０１７，２４（１）：１０２⁃１０７．［１６］殷新凯，茅健，周玉凤，等．基于混合混沌序列与遗传算法的排爆机器人路径规划［Ｊ］．计算机时代，２０１９（７）：５⁃８．ＹＩＮＸＫ，ＭＡＯＪ，ＺＨＯＵＹＦ，ｅｔａｌ．ＰａｔｈｐｌａｎｎｉｎｇｏｆＥＯＤｒｏｂｏｔｂａｓｅｄｏｎｈｙｂｒｉｄｃｈａｏｔｉｃｓｅｑｕｅｎｃｅａｎｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ［Ｊ］．ＣｏｍｐｕｔｅｒＥｒａ，２０１９（７）：５⁃８．［１７］任子武，伞冶．自适应遗传算法的改进及在系统辨识中应用研究［Ｊ］．系统仿真学报，２００６，１８（１）：４１⁃４３，６６．ＲＥＮＺＷ，ＳＡＮＹ．Ｉｍｐｒｏｖｅｄａｄａｐｔｉｖｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄｉｔｓａｐｐｌｉｃａｔｉｏｎｒｅｓｅａｒｃｈｉｎｐａｒａｍｅｔｅｒｉｄｅｎｔｉｆｉｃａｔｉｏｎ［Ｊ］．ＪｏｕｒｎａｌｏｆＳｙｓｔｅｍＳｉｍｕｌａｔｉｏｎ，２００６，１８（１）：４１⁃４３，６６．（责任编辑：胡前进）。

• 60•针对传统遗传算法在机器人路径规划上的不足，并针对特定的室内环境，本文提出一种在选取子代时随机改变每代的种群数、剔除极差的个体的原则进行子代筛选，从而使遗传算法避免陷入局部最优并且快速收敛。

仿真结果表明，这种算法是有效可行的。

引言：随着人工智能的发展，对机器人智能化要求越来越高，其中路径规划一直是机器人研究领域的重点，它的首要目标是在机器人所在环境内生成从起点到终点的无碰撞路径，其次则是改善该路径以达到更优的路径。

关于机器人路径规划，一般有静态路径规划和动态路径规划两种。

目前，有很多路径规划算法都被提出，其中遗传算法具有较强的全局搜索能力被很多研究所采用。

提出一种生成初始种群的方法和精英策略以提高搜索质量。

通过引入路径修复机制来提高遗传算法的收敛速度。

本文在室内环境下，充分理解室内环境的特点，运行时避开狭小的可行空间避免出现意外的堵塞，同时通过在选取子代时，采用随机改变每代的种群数、剔除极差的个体为原则来用子代来替代亲代，以快速收敛。

1 环境描述本文采用栅格法对环境进行描述，栅格大小的选取与环境以及移动机器人的大小有关。

由于本文所研究的环境是普通室内环境，具有大部分固定障碍物基本位置不变且占地面积大、室内总面积较小且平坦等特点，因此，将栅格大小设定为机器人自身大小，就可以用不多的栅格表示室内的桌椅等固定障碍物。

以1表示障碍物，0表示可行位置，即可得到图5中忽略路径所示的室内栅格地图。

2 全局路径规划2.1 编码同样采用0和1来对基因进行编码，基因的长度与栅格地图的长宽相关，取2×(长+宽)，以每两个相邻二进制位作为方向判别，约定这两个二进制组合为00、01、10、11分别表示可向东、南、西、北行走，可行则行，不可行则不考虑后面组合。

如栅格地图长宽为3×4，则单个个体的基因长度为14，假设其基因为0001 0110 0111 00，若栅格地图全部可行，那么它的方向就是东南南西南北南。

第41卷第2期 2018年4月武汉科技大学学报J o u rn a l o f W u h a n U n iv e rs ity o f Science an d TechnologyV o l.41,N o.2A p r.2018D O M0.3969/.issn. 1674-364 4. 2018. 02. 012基于改进遗传算法的自动化制造单元调度毛永年，唐秋华，张利平(1.武汉科技大学冶金装备及其控制教育部重点实验室，湖北武汉，430081 ;2.武汉科技大学机械传动与制造工程湖北省重点实验室，湖北武汉，430081 )摘要：研究了一类带时间窗口的自动化制造单元调度问题。

为了克服基本遗传算法求解此类问题容易陷入局部最优这一缺陷，在设计改进遗传算法时，采用基于循环序列的编码排列方式，并配合使用两点交叉操作，以增强进化过程中种群的多样性。

采用启发式目标函数以引导种群向有利方向进化。

针对进化过程中产生的大量不可行解，提出了具有联动修复机制的修复策略，根据修复过程自适应搜索待修复目标片段，同时引入禁忌表记录各基因的移动方向以避免迂回搜索，从而保证算法的搜索效率和求解质量。

最后，使用文献中的8 个基准案例进行算法测试，测试结果验证了本文提出的改进遗传算法的有效性。

关键词：自动化制造单元；生产调度；时间窗口；改进遗传算法；修复策略中图分类号：T G334. 9+ 3 文献标志码：A文章编号：1 674364 4 (2018) 02014 706自动化制造单元是一类以机器人为物料运输 工具的自动化生产系统，应用十分广泛。

工件在 此类制造单元中的加工通常具有一定的弹性，也 就是工件的加工时间可以在给定的上下限范围(即时间窗口）内变动。

物料搬运机器人必须在给 定的时间窗口内，将工件从当前工作站转移到下一工序所在的工作站。

为了便于管理，自动化制 造单元常采用循环生产模式，即物料搬运机器人在每一个生产循环内执行相同的搬运作业序列。

一种基于邻居自适应的多目标元胞遗传算法
张屹;刘铮;卢超
【期刊名称】《计算机应用研究》
【年(卷),期】2014(31)8
【摘要】针对现有多目标元胞遗传算法存在邻居单一固定、不能适时变化的缺点,提出一种基于邻居自适应的多目标元胞遗传算法.该算法在经典多目标元胞遗传算法的基础上引入邻居自适应机制,动态调节邻居结构,使算法不断寻找全局搜索与局部寻优之间的平衡点.最后,与现有流行的其他多目标进化算法作比较,通过对不同类型的20种基准测试函数问题进行测试,证明该算法具有良好的收敛性和扩展性.【总页数】5页(P2311-2314,2341)
【作者】张屹;刘铮;卢超
【作者单位】三峡大学机械与动力学院,湖北宜昌443002;三峡大学机械与动力学院,湖北宜昌443002;华中科技大学机械科学与工程学院,武汉430074
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.一种动态邻居元胞遗传算法 [J], 吴佳俊;王帮峰;芦吉云
2.基于三维元胞空间的多目标元胞遗传算法 [J], 祝勤友;许峰
3.自适应邻居结构元胞遗传算法 [J], 祝勤友;许峰
4.基于三维元胞空间的多目标元胞遗传算法 [J], 祝勤友;许峰
5.自适应邻居结构元胞遗传算法 [J], 祝勤友;许峰
因版权原因，仅展示原文概要，查看原文内容请购买。

基于元胞自动机的火灾模拟算法随着城市化进程不断加快，人们的生活和生产活动都离不开建筑物的使用。

但随之而来的是，建筑物火灾频繁发生，给人们的生命财产安全带来极大的威胁。

为了提高火灾事故的应对能力，火灾模拟技术应运而生。

基于元胞自动机的火灾模拟算法具有优异的特点和良好的应用前景，本文将重点介绍它的基本原理、模型构建以及应用情况。

一、基本原理元胞自动机（Cellular Automaton，CA）是一种由数字、节点或其他单元格组成的离散模型，它基于模型单元相互作用之间的规则，描述了一个物理系统的演化。

如图1所示，元胞自动机可以看作是一个由相互作用单元格组成的网格，每个单元格的状态有限且固定。

每次演化时，单元格会根据规则来转化自身状态，同时其相邻的单元格也会跟随转化。

这样一次转化过程也被称为元胞运算。

基于元胞自动机的火灾模拟算法，主要是利用这种元胞自动机计算模型，根据建筑物特点和火源情况，来模拟火灾的蔓延过程。

通过建立建筑物元胞自动机模型，定义每个单元格的状态、热量等参数，以及不同单元格之间的相互作用关系，可以精确地模拟火灾过程。

二、模型构建基于元胞自动机的火灾模拟算法通常包含两个方面的内容：建筑物元胞自动机模型和火源元胞自动机模型。

下面我们重点介绍建筑物元胞自动机模型的构建。

1. 建筑物元胞自动机模型变量定义建筑物元胞自动机模型变量包括：状态变量、热量变量、燃料变量、湿度变量、温度变量和烟雾变量等内容。

其中，状态变量表示每个单元格所处状态，可分为起火态、冷静态和烟雾态。

热量变量表示每个单元格的热度大小程度，燃料变量表示在溶解、蒸发、氧化等过程中，剩余可燃物的大小，湿度变量表示每个单元格中水分的大小，温度变量表示每个单元格中的温度大小，烟雾变量表示每个单元格所处烟雾的大小等。

2. 建筑物元胞自动机模型规则定义建筑物元胞自动机模型规则定义包括：转移规则、边界条件、热传递规则和质量守恒规则等。

转移规则是建立系统动力学方程的基础，通过转移规则来决定下一时刻的状态。

基于改进遗传算法的机器人动态路径规划王雷;李明;唐敦兵;蔡劲草【摘要】针对基本遗传算法解决移动机器人路径规划的不足,提出了一种改进的遗传算法.首先,采用栅格法对机器人路径规划进行建模.然后,提出一种生成初始种群的方法和精英策略,设计出自适应变异概率,提高了算法的求解质量.同时,在规划过程中,将全局路径规划与局部路径规划相结合,并且根据机器人与动态障碍物碰撞类型的不同,提出了相应的避碰策略.仿真实验表明:该算法优于基本遗传算法,能够有效地指导机器人在动态环境中实现避障,获得无碰最优或次优路径.【期刊名称】《南京航空航天大学学报》【年(卷),期】2016(048)006【总页数】6页(P841-846)【关键词】动态路径规划;栅格法;改进遗传算法;精英策略【作者】王雷;李明;唐敦兵;蔡劲草【作者单位】安徽工程大学机械与汽车工程学院,芜湖,241000;安徽工程大学机械与汽车工程学院,芜湖,241000;南京航空航天大学机电学院,南京,210016;安徽工程大学机械与汽车工程学院,芜湖,241000【正文语种】中文【中图分类】TP242移动机器人路径规划是在一个存在障碍物的有界工作空间内，依据相应的评价标准(路径长度、能量消耗等)规划出一条安全无碰撞而且较优的可行路径[1]。

一般来说，可将路径规划分为静态[2-3]和动态路径规划两类。

在实际中，机器人所处的大多数是一种动态变化的工作环境，因此，研究动态路径规划问题更具有实用价值。

目前，已有不少学者对此进行了大量研究并提出了多种路径规划方法与策略[4-8]。

近年来，由于遗传算法具有并行性、全局搜索能力等优点，所以在路径规划中得到广泛的应用。

例如，文献[9]将基于协进化机制的改进遗传算法应用到求解多机器人全局路径规划中。

文献[10]利用一种基于改进遗传算法求解机器人路径动态规划问题。

文献[11]将一种新的变异方法应用到求解机器人动态路径规划中。

文献[12]采用二次规划的方法对出现新的障碍物进行求解，虽然仿真结果表明该方法是可行的，但是却大大增加了路径规划时间。

科技信息2010年第5期SCIENCE &TECHNOLOGY INFORMATION 0引言路径规划问题是关于移动机器人的技术研究中的一个重点课题[1]，它是按照某一性能指标搜索一条从起始位置到目标位置的最优或次优的路径，可分为基于模型的环境已知的全局路径规划和基于传感器的环境未知的局部路径规划。

目前，全局路径规划方法有很多种，人工势场法较为常用，其基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动，但此法也存在一定的局限性，在相近障碍物面前机器人会振荡停滞不前，出现局部最小点问题；可视图法将机器人、目标点和多变形障碍物的各顶点进行组合连接，形成一张图，但此法的缺点是搜索路径复杂、搜索效率不高；删格法在环境密集的情况下发现路径能力较强，但其环境信息存储量较大和规划时间较长限制了此法的使用[2][3]。

本文研究了一种关于移动机器人全局路径规划的新方法，先对环境建模，再引入元胞自动机算法进行规划，最终得到最优路径。

仿真结果表明该算法建模简单，计算快捷，提高了机器人路径规划的性能。

1元胞自动机元胞自动机(Cellular Automata)，简称CA ，是一时间和空间都离散的动力系统[4]。

它是一种功能强大的工具,已成功应用在城市交通规划、地理环境模拟、微观晶粒生长等许多领域。

元胞自动机拥有规则布局的空间结构，标准CA 可以用一个四元数组表示：A =（Ld,S,N,f ）（1）其中A 代表一个元胞自动机系统；L 表示元胞空间，d 是正整数，表示元胞自动机内元胞空间的维数；S 是元胞有限的、离散的状态集合；N 表示一个邻域内所有元胞的组合(包括中心元胞)，即包含n 个不同元胞状态的一个空间矢量，记为：N =(S 1,S 2…S n )，n 是元胞的邻居个数，S i ∈Z ，Z i ∈(1,2…n )；f 表示将S n 映射到S 上的一个局部转换规则函数。

所有的元胞位于d 维空间上，其位置可用一个d 元的整数矩阵Z d 来确定。

第30卷第4期2010年8月大地测量与地球动力学J OURNAL OF GEODESY AND GEODYNAM I CSV o.l 30N o .4A ug .,2010文章编号:1671 5942(2010)04 0142 05二维元胞自动机相位解缠算法的改进*闫 满1,2)刘国林1) 郝华东1) 陶秋香1)1)山东科技大学测绘科学与工程学院,青岛 2665102)黑龙江科技学院计算机与信息工程学院,哈尔滨 150027摘 要 提出一种改进的二维元胞自动机相位解缠算法。

通过将原有元胞自动机相位解缠算法中的4邻域迭代规则改进为最近邻域规则,以干涉图的边缘作为始点进行迭代,逐一减少干涉条纹的数目,达到相位解缠的目的。

用模拟和真实的干涉图进行实验,结果表明,该算法减少了原有元胞自动机相位解缠算法的迭代次数,降低了计算机内存的占用率,提高了相位解缠的精度。

关键词 元胞自动机;相位解缠;最近邻域规则;4邻域规则;干涉图中图分类号:P225.1 文献标识码:AIM PROVE M ENT OF PHA S E UN WRAPPING METHODFOR T W O D IM EN SI ONAL CELLULAR AUTO MATAY an M an1,2),L i u Guo li n 1),H ao H uadong1)and Tao Q i u x iang1)1)G eo ma tics College,Shandong University o f Science and Technology ,Qingdao 2665102)Co mputer and Infor m ation Eng i n eering College ,H eilongjiang Instit u te of Science and Technolo gy,Haerbin 150027AbstractAn i m proved phase unw rapp i n g m ethod for cell u lar auto m ata is proposed .It rev ises t h e four ne i g hborhood of the o ri g i n alm e t h od to the nearest ne i g hborhood,beg i n s fr o m the boundary of the i n terferogra m to iterate ,e li m i n ates the phase fri n ges one by one to ach ieve t h e pur pose o f phase unw rapp i n g .The experi m ents by using t h e si m u lated and real i n terferogra m s are m ade .The result sho w s that th ism ethod can decrease the ori g ina l itera ti v e ti m es ,reduce the occupancy rate o f the m e m ory and i m prove the accuracy o f the phase unw rapp i n g .K ey w ords :ce llular auto m a ta ;phase unw rapp i n g ;nearest neighbor hood ru l e ;four ne i g hborhood rule ;i n terferog ra m1 引言合成孔径雷达干涉测量(I nSAR )利用雷达干涉数据的相位信息获取高精度数字地形信息。