哈尔滨工程大学本科生毕业论文
在二维定位估计中计算MV和MSE的方法为：
MV?E[(x,y)] (3.35)
?)2?(y?y?)2] (3.36) MSE?E[(x?x?,y?)为MS估计位置。 其中，(x,y)为MS实际位置，(x3.4 本章小结
本章主要给出了TDOA定位的数学模型，研究了基于TDOA的常见算法——Chan算法。综合分析可见，Chan算法为非递归算法，其解为明确的解析表达式，但需要一些有关MS位置的先验信息以解决其解存在的模糊性。在蜂窝网络信道环境中，Chan算法是定位性能很好的一种算法。因此，Chan算法是一种比较适合在蜂窝网络环境中对MS进行定位估计的算法[2]。在本章最后给出了定位准确率的评价指标：平均估计坐标和均方误差。平均估计坐标与实际位置越接近，均方误差越小，定位准确率越高，性能越好。
21
哈尔滨工程大学本科生毕业论文
第4章 遗传算法在TDOA定位中的应用
本章根据遗传算法的基本优化原理，研究了适用于TDOA定位的改进的遗传算法[8]。该算法首先根据移动台所在服务区来确定移动台的坐标范围，然后采用似然函数的倒数作为个体适应度值来选取优良个体并进行遗传操作，在服务台所确定的坐标范围内搜索移动台位置。仿真结果说明，算法的性能稳定，能得到较高精度的解。
4.1 遗传算法简介
4.1.1 遗传算法的基本原理
遗传算法(Genetic Algorithm，GA)是建立在自然选择和群体遗传学基础上的搜索方法，是由美国Michigan大学的Holland教授首先提出并发展起来的[9]。
遗传算法是从代表问题可能潜在解集的一个种群开始的，一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现(即基因型)是某种基因组合，它决定了个体形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射，即编码工作。初始种群产生之后，按照“适者生存”和“优胜劣汰”的原理，逐代演化产生出越来越好的近似解。在每一代中，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合、交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化的一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解[10]。
遗传算法是自然遗传学和计算机科学相互结合渗透的产物，借用了许多自然进化的基础术语。下面我们对一些术语进行简单的介绍：
(1) 群体和个体
遗传算法处理的是染色体，或者叫基因型个体，通常以一维串结构数据
22
哈尔滨工程大学本科生毕业论文
来表示；一定数量的个体组成群体。
(2) 适应度函数
各个个体对环境的适应程度叫做适应度。遗传算法对适应度函数并不要求可导等条件，只要求适应度函数是非负函数，同时要求把待解优化问题表达为最大化问题，即目标函数的优化方向为适应度函数的增大方向，所以有广泛的应用。在解决TDOA问题中，适应度函数就是目标函数。
(3) 编码和解码
遗传算法必须包含两个必须的数据转换操作，即把搜索空间中的参数或解转换成遗传空间中的染色体或个体，称为编码；反之，称之为解码。
(4) 遗传操作
遗传操作中包括三种主要操作，分别是选择、交叉和变异操作(详细在4.1.4节介绍)。 4.1.2 遗传算法的特点
遗传算法的特点[11]可以从它和传统搜索方法对比可以充分体现出来： 1、遗传算法不是直接作用在参变量集上，而是利用参变量集的某种编码 遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此编码操作，使遗传算法可直接对结构对象进行操作。这一特点，使得遗传算法具有广泛的应用领域。
2、遗传算法不是从单个点，而是从多个点的群体开始搜索
传统方法都是单点搜索，从一点移到另一点。这种点对点的搜索常常会陷入局部最优解；而遗传算法采用同时处理多个点的方法，对多个解进行评估，具有全局搜索性能，同时也易于并行化。
3、遗传算法利用适应值信息，无需导数和其他辅助信息
遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，对于输入可计算出正的函数值。这使得该算法的应用范围大大扩展。
23
哈尔滨工程大学本科生毕业论文
4、遗传算法利用概率转移规则，而非确定性规则
遗传算法采用概率作为一种工具来引导其搜索过程朝着搜索空间的更优化的解移动，因此具有明确的搜索方向。
上述特点，表明遗传算法适于解决维数很高，总体很大的复杂的非线性问题。这使遗传算法具有以下优点：
(1) 应用广泛性：易于写出通用算法，求解不同优化问题；
(2) 非线性性：其他多数算法都需与可导、线性、凸性等性质相联系，遗传算法只需适应度函数值非负，适合具有高度非线性问题的寻优；
(3) 易于修改性：遗传算法只需少量改变算法，即可适用于不同问题； (4) 易于并行实现。
4.1.3 遗传算法的基本流程图和主要步骤
标准遗传算法(SGA)的基本流程[7]如图4.1所示：
开始产生初始种群计算适应度值是否满足优化原则否选择是输出最佳个体结束交叉变异 图4.1 遗传算法的流程图
24
哈尔滨工程大学本科生毕业论文
算法主要步骤如下：
第1步：设置运行参数：群体大小N、终止进化代数T、交叉概率Pc、变异概率Pm；
第2步：随机产生初始群体；
第3步：计算个体的适应度，并判断是否符合优化准则。若符合，输出最佳个体及其代表的最优解，并结束计算；否则转向第3步；
第4步：依据适应度选择个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；
第5步：按照一定的交叉概率和交叉方法，生成新的个体； 第6步：按照一定的变异概率和变异方法，生成新的个体； 第7步：由交叉和变异产生新一代的种群，返回到第3步。 4.1.4 遗传算法的基本操作
1、编码与解码
应用遗传算法解决问题的关键步骤就是编码。由问题空间向遗传算法空间的映射称为编码，由遗传算法空间向问题空间的映射称为解码[10]。由于遗传算法并不直接作用于待求变量本身，而是先将待求问题的变量进行编码，表示成适于遗传算法求解的码串形式，然后进行遗传操作，故相应地应该有解码过程，也就是将编码变回数字变量，从而找到所求问题的最优解。
编码的方法有很多，比如有二进制编码法和浮点数编码法。由于二进制数占用的位数较多，解码时延增加，故本文中采用浮点数编码。
2、种群初始化
在应用遗传算法之前，要对一定群体规模的个体进行初始化，这些经过初始化后的个体将作为遗传进化的祖先(下一代的父代)。作为祖先的初始群体，这些给定数量的个体是通过随机方法生成的，以保证搜索空间中的每个可能解在初始群体中都有相同的出现机会。
3、个体适应度的评价[5]
25