哈尔滨工程大学本科生毕业论文
在遗传算法中评价值被称为个体适应度值，定义一个适应性函数是遗传算法中评价个体优劣的手段，评价的标准因所研究问题的不同而异，它通常由目标函数转化而来，并要求与目标函数有相同的极值点和可行解域，且值域非负，这样就可以将目标函数的极小值问题，转化为求适应函数的极大值问题，便于遗传操作。本文将目标函数的倒数作为适应度函数[12]。在评价中，取其倒数是因为习惯上按从大到小的顺序排列适应值，计算出群体中每个解相应的适应度函数，适应度函数值越大，表示该个体适应度越高，亦即该个体的质量较好，更适应于目标函数所定义的生存环境，因此也应该较其它个体有更多的机会参与遗传操作，并将其优良性能遗传给更多的子代，适应函数为群体进化的选择提供了依据。
4、选择
选择运算是从群体中选择优良的个体、淘汰劣质个体的操作，用于模拟生物界去劣存优的自然选择现象。选择的目的是把优异的个体特性直接遗传到下一代或通过配对交叉将其部分优良特性遗传给新的个体，再遗传到下一代群体。
选择方法有轮盘赌选择法、随机遍历抽样、锦标赛选择等，其中轮盘赌选择法较为常用。首先计算所有个体的适应度值总和和每个个体的适应度值所占适应度值总和的比重。它把种群中所有个体适应度的总和看成一个轮子的圆周，每个个体按其适应度值在总和中的比重占据轮子的一个扇区，每次个体的选择可以看作轮子的一次随机转动，它转到哪个扇区停下来，那个扇区对应的个体就被选中。比重越大，能参与繁殖的概率越大，此概率与其个体适应度的大小成正比。即适合于生存环境的优良个体将有更多的繁殖后代的机会，从而使得优良特性得以遗传。选择是遗传算法的关键，它体现了自然界中“适者生存”的思想。本文中采用轮盘赌法进行个体的选择。
5、交叉
交叉操作利用了来自不同符号串的基因经由交换而混合以产生新符号串的概念，它是根据交叉概率在种群中选取两个个体做为父体和母体，再依交
26
哈尔滨工程大学本科生毕业论文
叉概率将两个个体中位于交叉位后的符号串互换，保留交叉位前的各基因位符号不变，形成两个下一代新个体的遗传操作[10]。由此可以看出，适应度值大的个体参与交叉的机率大，通过交叉把遗传信息传给了子代，使优良的性状更易继承下去。根据交叉点的不同，交叉运算有单点交叉、多点交叉、均匀交叉等多种不同的交叉方法。
6、变异
为了避免落入局部最优，遗传算法中引入了变异算子，变异是为了避免“近亲繁殖”，它可以保持群体的多样性，以避免局部收敛，同时还可以恢复丢失的或寻找未找到的优良信息，在当前解的附近找到更好的解[10]。变异操作可使适应度值小的个体或群体素质趋于一致的个体发生变化，同时防止适应值大的个体变异，从而使每一代保持新鲜个体，避免进化停滞，过早收敛，确保群体能继续优化。
4.2 遗传算法在TDOA定位中的实现
遗传算法在开发最好解和探求搜索空间两方面同时努力，即在探究搜索空间的同时，维持一个潜在解的群体。这一特性对于寻找全局最优点是非常有利的。下面我们将遗传算法用于TDOA定位中。 4.2.1 TDOA双曲线定位模型
如图4.2所示，假设M个接收机随机分布在二维平面上，(x,y)为移动台MS的待估计位置，(Xi,Yi)为第i个基站BS的已知位置。MS到基站i的距离为Ri，令Ri0,1表示MS与基站i(i?1)和基站1(服务基站)的实际距离差，测量值记作Ri,1，则
Ri,1?cdi,1?Ri0,1?cni,1?Ri?R1?cni,1,i?2,?,M (4.1) 式中：c为电波传播速度；di,1是TDOA测量值；ni,1是测量TDOA时引入的噪声，为方便起见，可认为是独立同分布的方差为?2的高斯白噪声。 又因为
Ri?(Xi?x)2?(Yi?y)2 (4.2)
27
哈尔滨工程大学本科生毕业论文
y6kmx：源点位置，坐标（x，y）图4.2 基站与源点位置示意图
所以有
Ri,1?(Xi?x)2?(Yi?y)2?(X1?x)2?(Y1?y)2?cni,1,i?2,3,?,M(4.3)
记作
?R?[R2,1,R3,1,?,RM,1]T(M?1)?1R?[R2,R3,?,RM]T(M?1)?1R1?[R1,R1,?,R1]T(M?1)?1n?[n2,1,n3,1,?,nM,1]T(M?1)?1可得
?(X?x)2?(Y?y)2?(X?x)2?(Y?y)2?2211??2222?(X3?x)?(Y3?y)?(X1?x)?(Y1?y)??R?R?R1?cn???cn (4.4) ????2222??(XM?x)?(YM?y)?(X1?x)?(Y1?y)??本文考虑M?3时的情况。为了充分利用统计信息，采用最大似然法估计源点坐标(x,y)。因为Ri,1服从均值为(Ri?R1)，方差为?2的高斯分布，又因各测量值独立，则似然函数
28
哈尔滨工程大学本科生毕业论文
?1??(?Ri?Ri?R1)2???exp??????22?2??i?1??????M?1?1?????2???M?1?(?R?R?R1)T(?R?R?R1)?exp???2?2?? (4.5)
求使似然函数最大的坐标值，相当于求
??(?R?R?R1)T(?R?R?R1)????(x,y)?arg?max?exp(?)? (4.6) ?22???????也就是求
T(x,y)?argmin?(?R?R?R)(?R?R?R1)?1?? (4.7)
??式(4.7)表明要求解出坐标值，必须求非线性函数的最小值[8]。用解析法求解式(4.7)的非线性函数的最小值是比较困难的。可将式(4.7)的倒数用作适应度函数，在这一章和下一章中应用，用于评价遗传算法和差分进化算法中个体的适应度。
4.2.2 改进的遗传算法的实现
本节对基本遗传算法进行了改进，并根据4.2.1节的数学模型给出了具体的实现方法。
1、染色体编码
由于我们解决的定位问题是二维的，并且采用浮点数编码，所以我们考虑的染色体由两个基因组成。首先根据移动台所处服务基站小区确定移动台的坐标范围：
?xmin?x?xmax (4.8) ?y?y?ymax?min式中，xmin，xmax分别表示基站覆盖区域的横坐标范围的最小值和最大值，
ymin，ymax分别表示基站覆盖区域的纵坐标范围的最小值和最大值。
将待优化的x变量和y变量通过式(4.9)进行归一化处理：
?x?xmin?v(1)[xmax?xmin] (4.9) ??y?ymin?v(2)[ymax?ymin] 29
哈尔滨工程大学本科生毕业论文
将x和y转换为[0,1]区间上的实数v(i),i?1,2，称v(i)为基因，x，y变量对应的基因v(1)和v(2)一起构成该实数编码的染色体，记v?[v(1),v(2)]T。
2、初始化种群
设群体规模为N，在[0,1]区间上生成2?N维均匀随机数矩阵V，
V?{v1,v2,?vN}，作为初始群体的父代个体值。
3、个体适应度值
根据4.2.1节的内容，本文算法中我们取适应度函数[8]为：
1 (4.10) f(zi)?T(?R?R?R1)(?R?R?R1)|zi式中，zi?[xi,yi]T，其中xi和yi为染色体向量v所对应的移动台的坐标。它可以通过将染色体向量v代入公式(4.9)中得到。
4、个体的选择
本文采用轮盘赌选择法，以保证适应度较大的个体能够被遗传到下一代群体中，即
(1) 计算个体的相对适应度
个体的相对适应度pi也可以称为选择概率，它是某个个体被选中的概率，定义[9]为：
pi?fi?fi?1N,i?1,2,?N (4.11)
i从式(4.11)可以看出个体适应度越大，则该个体的相对适应度pi越大，我们可以利用相对适应度pi将最优个体选择进入下一代群体。
(2) 依据选择概率pi生成下一代群体
根据选择概率pi,i?1,2,?N把一个圆盘分成N份，其中第i扇形的中心角为2?pi，如图4.3所示。在进行选择时，假想转动一下圆盘，若某参照点落入到第i个扇形内，则选择个体i。这种选择策略可以通过以下方式实现：在[0,1]内的生成一随机数r，若p0?p1???pi-1?r?p1?p2???pi，则选择个体i，此处假设p0?0。小扇区的面积越大，就越有可能选择该个体，所
30