哈尔滨工程大学本科生毕业论文
以该方法可以将适应度大的个体以较大的概率遗传到下一代群体中[9]。
p1pNp2?2?pi?pi 图4.3 轮盘赌选择法
5、交叉算子
由于本文采用浮点数编码系统，一个基因代表一个优化变量，为保持群体的多样性，采用如下的非一致算术交叉算子[9][10]：
假设在两个父代个体v1和v2之间进行交叉，则交叉运算所产生的新个体
?和v?v12分别为：
??λv1?(1?λ)v2v1 (4.12)
v??λv?(1?λ)v221式中，?为0到1之间的随机数。
6、变异算子
变异操作的目的是为了引进新的基因，增强群体的多样性。
本文采用非均匀变异算子[9][10]，设v，v??分别是要变异的和变异后的个体，则
tb?v?N(B?v)(1?),随机数为0M?MU?T (4.13) v????tb?v?NM?M(v－BL)(1?),随机数为1T?式中，t是迭代次数；T是最大迭代数；v是第t次迭代时的染色体向量，v??是第t?1次迭代时的染色体向量；NM?M是对角矩阵，其对角线元素是在[0,1]间
31
哈尔滨工程大学本科生毕业论文
符合均匀分布的随机数；M是染色体向量的维数；BU是染色体向量取值范围的上界；BL是染色体向量取值范围的下界；b是确定对迭代数依赖程度的
tbN(B?v)(1?)系统参数。从式(4.13)能看出，随着迭代次数的增加， M?MUTtbN(v－B)(1?和 这说明初始搜索在大范围均匀M ?ML ) 项靠近零的概率增加，
T进行，随着迭代次数增加，新产生的染色体靠近父代的概率增加，即强化了对局部空间的搜索，局部微调有助于提高精度。
7、产生新的种群
经过上述选择、交叉和变异操作的个体作为父代，生成下一代种群。 8、评价新种群
根据第3步，计算新种群中每个染色体的适应度值。并判断是否满足终止条件，如果满足则终止；否则重复步骤4~8，直到满足终止条件。本文中将最大迭代次数T作为终止条件。 4.2.3 Chan-GA算法的实现
基于TDOA定位的遗传定位算法虽有好的收敛性能，定位精度很高，但由于搜索范围大，计算时间较长，我们可以利用Chan算法的快速收敛特性，把Chan算法的输出运用到GA算法中，有效缩小最优解的搜索范围，加快遗传算法的收敛速度，达到收敛速度和定位精度的折衷。
根据Chan算法搜索到的局部最优解(xb,yb)，确定Chan-GA算法的搜索区间为[xb?C,xb?C]和[yb?C,yb?C]，即移动台的坐标范围为：
?xb?C?x?xb?C (4.14) ??yb?C?y?yb?C在此基础上对染色体进行编码，其余的选择、交叉和变异过程与改进的遗传算法相同。
4.3 计算机仿真
上面对基于TDOA定位的算法进行了详细的推导分析，本节在前面的基
32
哈尔滨工程大学本科生毕业论文
础上讨论分析不同算法在高斯噪声环境下的性能。
仿真背景和参数设置如下：考虑蜂窝网如图4.2所示，蜂窝半径为3km，有5个基站，其位置分别为(0,0),(33,3),(33,?3),(0,?6),(?33,?3)；源点位置为(1,2.5)。
改进的遗传算法中，种群数为70，交叉概率Pc为0.15，变异概率Pm为0.25，迭代次数为60，系统参数b取6。独立运行1000次，评价指标采用3.3节给出的平均估计坐标MV和均方误差MSE。便于比较，Chan-GA算法的参数与改进的遗传算法取相同值。仿真所得平均估计坐标MV如表4.1所示。图4.4给出了不同算法均方误差与测量误差(dB)之间的关系。
表4.1 三种算法的MV比较
10lg(c?) /dB ?20 ?18
Chan算法 的MV （0.9998，2.5001） （0.9995，2.5004） （1.0000，2.4972） （1.0016，2.4955） （1.0014，2.4919） （1.0012，2.4807）
GA算法 的MV （1.0118，2.4835） （1.0101，2.4860） （1.0112，2.4838） （1.0128，2.4817） （1.0105，2.4859） （1.0115，2.4856）
Chan-GA算法 的MV （1.0037，2.4957） （1.0032，2.4963） （1.0029，2.4957） （1.0044，2.4941） （1.0033，2.4965） （1.0020，2.4996）
?16
?14 ?12 ?10
表4.1中的Chan算法栏是Chan算法的仿真结果(独立运行1000次)；GA算法栏是文献[8]中改进的遗传算法的仿真结果；Chan-GA算法栏是本文提出的Chan-GA算法的仿真结果，其选取的参数与GA算法一致，只是将Chan算法的定位结果上下浮动0.5km。表中第1栏10lg(c?)是根据蜂窝网通信系统与系统热噪声等原因确定的[8]。
从图4.4可以看出，当测量误差很小时，Chan算法和Chan-GA算法的性能优于GA算法；但是当测量误差加大时，Chan算法的性能恶化，GA算法
33
哈尔滨工程大学本科生毕业论文
和Chan-GA算法的性能明显好于Chan算法，其主要原因是此时噪声的二次项带来的影响越来越大，变得不可忽视，导致Chan算法性能下降，而另外两种算法都是对最大似然函数进行移动台位置搜索，避免了这种影响。
图4.4 三种算法的MSE的比较
下面我们来进行一下收敛速度的仿真比较，为了便于比较，我们将GA和Chan-GA两种算法的终止迭代次数定为40。图4.5给出了两种算法的MSE收敛性能曲线。
图4.5 两种算法的MSE收敛曲线的比较
34
哈尔滨工程大学本科生毕业论文
图4.5是GA算法和Chan-GA算法是在测量误差为?16dB的条件下的MSE收敛曲线，通过比较可以看出，Chan-GA算法的收敛速度很快，在30代时就比GA算法45代的结果要好，这是因为Chan-GA算法引入了Chan算法的快速收敛特性，将Chan算法的结果运用到GA算法中，使GA算法解的搜索范围大大减小了，在不影响定位精度的同时有效提高了搜索解的速度。
4.4 本章小结
本章主要介绍了遗传算法的基本原理、改进的遗传算法在TDOA定位中的实现过程以及Chan-GA算法在TDOA中的实现。综合本章算法分析和计算机仿真可见，当测量误差很小时，Chan算法和Chan-GA算法的性能优于GA算法；当测量误差加大时，Chan-GA算法、GA算法与Chan算法相比，能够得到更准确的定位估计。这是因为遗传算法直接根据似然函数进行求解，而没有引入二次项误差。而与GA算法相比，Chan-GA算法由于引入Chan算法快速收敛的特性，将Chan算法的仿真结果直接运用到GA算法中，在不影响算法定位精度的同时，有效提高了搜索速度，达到定位精度和收敛速度的折衷。
35