基于遗传算法的TDOA应用仿真研究

刘宝生1，王孟2

刘宝生，王 孟

（1.国家无线电监测中心陕西监测站，西安 710200；2.国家无线电监测中心乌鲁木齐监测站，乌鲁木齐 830054）

摘要：遗传算法从一组随机产生的称为“种群（Population）”的初始解开始搜索过程，它的思想广泛的被计算机仿真中，其优点显而易见，但是缺点也存在，如计算比较复杂，对非线性的问题不易解决。

关键词：遗传算法；TDOA定位；计算机仿真 d o I：10.3969/J.ISSN.1672-7274.2017.07.020 中图分类号：TP391.9

1 遗传算法简介

文献标示码：A 文章编码：1672-7274（2017）07-0054-02

遗传算法（Genetic Algorithm，ga）最先是由美国Mic-hgan大学的john Holland于1975年提出

的，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过

程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作。参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等5个要素组成了遗传算法的核心内容。

遗传算法是一种基于生物自然选择与遗传机

[3]

理的随机搜索算法 ，与传统搜索算法不同，遗传算法从一组随机产生的称为“种群（ Population）”

的初始解开始搜索过程。种群中的每个个体是问题的一个解，称为“染色体（chromosome）”，染色体是一串符号，比如一个二进制字符串，这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“适应度（ fitness ）”来测量染色体的好坏，生成的下一代染色体称为后代（offspring）。后代是由前一代染色体通过交配（ crossover ）或者突变（mutation）运算形成的。

在新一代形成过程中，根据适度的大小选择部分后代，淘汰部分后代。从而保持种群大小是常数。适应度高的染色体被选中的概率较高，这样经 过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。

2 遗传算法的原理

使用遗传算法在实际工作的运用中的流程：

（1）编码：GA在进行搜索之前先将解空间的

解数据表示遗传空间的基因型串结构数据[2]，这些串结构数据的不同组合便构成了不同的点。

（2）初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了—个群体。GA以这N个串结构数据作为初始点开始迭代。

（3）适应度评估检测：适应性函数表明个体或解的优劣性。对于不同的问题，适应性函数的定义方式也不同。

（4 ）选择新种群：选择的目的是为了从当前群体个选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。

（5）交配：交配是遗传算法中最主要的遗传操作。通过交配可以得到新一代个体，新个体组合了其父辈个体的特性。

（6）突变：突变首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结

构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001～0.01之间。

3 遗传算法在TDOA定位中的应用

在无源定位系统中，应用方位角、到达时间差以及多普勒[1]对目标定位中广泛使用遗传算法，特

别是在TDOA定位中使用遗传算法可以得到比较准确定位结果。

遗传算法充分利用全局优化及局部优化的能

力[4]，实现对目标的高精度估计。实现的步骤如下按照遗传算法的原理进行：

（1）编码，在定位算法中使用浮点，个体直接用目标的状态量表示，即为：x=i=[i1,i2,i3,i4]。

（2）遗传选择，选择操作采用比例适应度的方法。由个体评估值在整个物种群中的估计出个体的适应值。

（3）遗传变异，随机选择两个地N代的个体按照线性䦸关系进行组合，产出新个体。新个体为：

i' =(1-r1 ) i 1n+r2䦸i2n，i'2n=(1-r2)䦸i1n+r2䦸i2n，其中，

1n

r1,r2是[0,1]的随机矢量；i'1n，i'2n为第n代交叉产生的新个体。

（4）查分变是由异8是由第N代个体i'2n变异产生的i"1n。

（5）差分交叉是按照交叉的策略交换新旧个体部分代码，从而形成新个体i'" 。

1n

（6）差分选择是将交叉的个体i'"1n与上一代或前几代进行比较，选择出适应度值高的作为下一代。

4 应用仿真

[5]按照上一节流程使用遗传算法 对TDOA进行定位，所用的仿真软件为MATLAB6 ，计算机为LENOVOTHINKPAD，INTERCORE5，64位处理器进行仿真实验，结果如图1所示。

5 遗传算法缺点

遗传算法的编程实现比较复杂，首先需要对问题进行编码，找到最优解之后还需要对问题进行解码；另外三个算子的实现也有许多参数，如交叉率和变异率，并且这些参数的选择严重影响解的品质，而目前这些参数的选择大部分是依靠经验；算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进；算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的一个研究热点方向。■

参考文献

[1]曹爱华，李万春．基于遗传算法的多普勒外辐射源定位算法的研究[J]．

信号处理，2009,25(10)1644-1648

[2]王孟，蔡明辉．基于新型改进遗传算法下的数字信号特征值调制识别

[J]．数字信号处理，2015

[3]周明，孙树栋．遗传算法及应用[M]．北京：国防工业出版社，1999 [4] 张石磊，王志强．浅谈遗传算法的研究与改进[J]．中国学术期刊，

2004.6

[5] 曹道友．基于改进遗传算法的应用研究[D]．安徽大学，2010.4