哈尔滨工程大学本科生毕业论文
第5章 差分演进算法在TDOA定位中的应用
根据差分演进算法的基本原理，从另一个角度研究了一种适用于TDOA定位的差分演进算法，并进行了计算机仿真，与Chan算法和GA算法进行了性能比较，证明了方法的可行性和有效性。
5.1 差分演进算法简介
差分演进算法[11](Differential Evolution，DE)是由Storne等人于1995年提出的，最初的设想是用于解决切比雪夫多项式问题，后来发现DE也是解决复杂优化问题的有效技术。DE与人工生命，特别是进化算法有着极为特殊的联系。
5.1.1 差分演进算法的基本原理
DE是一种基于群体进化的算法，具有记忆个体最有解和种群内信息共享的特点，即通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法。差分演进算法与标准的遗传算法一样，都包含有选择，交叉和变异三个操作。于遗传算法不同的是，DE采用的是由变异到交叉再到选择的操作顺序[12]。
算法的基本思想是[13]：首先在问题的可行解空间随机初始化种群
000Np为种群规模。个体xi0?[xi0,1,xi0,2,?,xi,DX0?{x1,x0]用于表征问2,?,xNp}，
题解，D为优化问题的维数。算法的基本思想是：对当前种群进行变异和交叉操作，产生另一个新种群；然后利用基于贪婪思想的选择操作对这两个种群进行一对一的选择，从而产生最终的新一代种群。具体而言，首先通过式(5.1)对每一个时刻的个体xit实施变异操作，得到与其相对应的变异个体vit?1，即
ttt vit?1?xr. (5.1)?Fx?xrr123tt其中，r1,r2,r3??1,2,?,Np?互不相同且与i不同；xrt1为父代基向量；xr?xr23????称作父代差分向量；F为缩放比例因子。然后利用式(5.2)对xit和由式(5.1)生
36
哈尔滨工程大学本科生毕业论文
成的变异个体vit?1实施交叉操作，生成试验个体uit?1，即
ut?1i?vit?1,If?rand?j??CR?or??t?xi,Otherwise.j?rnbr?i?; (5.2)
rand?j?为?0,1?之间的随机数；rnbr?i?其中：CR为范围在?0,1?之间的交叉概率；
1,2?D?之间的随机量。利用式(5.3)对试验个体uit?1和xit的目标函数进行为?比较，对于最小化问题，则选择目标函数低的个体最为新种群的个体xit?1，即
x其中f为目标函数。
5.1.2 差分演进算法与传统进化算法的不同
综上所述，DE算法与传统的进化算法有三点明显的不同[14]：
(1)DE算法中都是使用实数编码，而传统的二进制编码多以二进制编码为主，但是近期的进化算法也慢慢改用实数编码作为个体编码方式。
(2)在进化算法中，通常是选择两个个体进行交叉操作重组产生子代，而在DE算法中，子代的产生式通过三个母体的扰动作用而产生的。步：进行选择操作，得到新种群。
(3)在DE算法中新产生的个体保留与否是通过与被选出来进行比较替换的标志向量进行优劣对比而决定的。 5.1.3 差分演进算法的优点
相对于其他进化算法，DE保留了基于种群的全局搜索策略，采用实数编码，基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，DE特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略。
归纳起来，DE算法具有如下优点[12]： (1)算法通用，不依赖于问题信息；
37
t?1i?uit?1,Iffuit?1?fxit; (5.3) ??t?xi,Otherwise.????哈尔滨工程大学本科生毕业论文
(2)算法原理简单，容易易实现； (3)群体搜索，具有记忆个体最优解的能力；
(4)协同搜索，具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力；
(5)易于与其他算法混合，构造出具有更优性能的算法。 5.1.4 差分演进算法的流程
DE算法可以按照下面的流程进行计算[15]：
第1步：确定DE控制参数及采用的具体策略，DE控制参数包括：种群规模Np，交叉因子CR，最大进化代数T，终止条件等。
第2步：随机产生初始种群。
第3步：对初始种群进行评价，即计算初始种群中每个个体的目标函数值。
第4步：判断是否达到终止条件或进化代数达到最大，若是，则进化终止，将此时的最佳个体作为解输出；若不是，则继续。
第5步：进行变异操作 第6步：进行交叉操作
第7步：对边界条件进行处理，得到临时种群，并对临时种群进行评价，计算临时种群中，每个个体的目标函数值。
第8步：进行选择操作，得到新种群。 第9步：进化代数T?T?1，转第4步。 5.1.5 差分演进算法的参数选取
影响差分演进算法性能的三个主要参数[16]：种群规模Np，缩放比例因子F，交叉概率CR。试验表明：在给定最大进化代数情况下，种群规模要适中，才能很好的保持多样性和收敛速度的平衡，如果种群规模较大，就要付出较大的进化代数为代价。缩放比例因子对算法的局部搜索和全局搜索起
38
哈尔滨工程大学本科生毕业论文
到了一定的调节作用， 缩放比例因子较大时，有利于保持种群多样性和全局搜索能力，较小时，有利于局部搜索和提高收敛速度。所以，缩放比例因子的取值既不能太大，又不能小于某一特定值，取值在?0.5,1?之间时算法才能取得较好的效果。交叉概率较小时，收敛速度较慢，但成功率较高，算法稳定性好，较大时，常常会加速收敛，但易于陷入局部最优，发生早熟现象，成功率差，算法的稳定性差。可见，成功率和收敛速度是一对矛盾。
5.2 差分演进算法在TDOA定位中的实现
5.2.1 差分演进算法的实现
本节中，我们将差分演进算法应用到TDOA定位中。本节的算法是建立在小节4.2.1所建立的TDOA双曲线定位模型上。根据5.1.1和5.1.4节，可以很方便的实现差分演进算法在TDOA定位中的应用。
1、个体编码
由于我们解决的定位问题是二维的，并且采用实数编码，所以我们考虑的个体由两个基因组成。首先根据移动台所处服务基站小区确定移动台的坐标范围：
?xmin?x?xmax (5.4) ??ymin?y?ymax式中，xmin，xmax分别表示基站覆盖区域的横坐标范围的最小值和最大值，
2、初始化种群
根据式(5.4)确定的坐标范围，生成2?N维均匀随机数矩阵V，
V?{v1,v2,?vN}，作为初始种群，初始种群的种群规模是Np。个体
vi?(vi,1,vi,2,?,vi,D)用于表征待估计得坐标，因为所研究是在二维的平面上所以D?2。vi,1和vi,2分别表示个体向量vi所对应的移动台的坐标xi和yi。
3、计算个体适应度值
根据4.2.1节的内容，我们取适应度函数[8]为：
39
哈尔滨工程大学本科生毕业论文
f(zi)?1 (5.5) T(?R?R?R1)(?R?R?R1)|zi式中，zi?[vi,1,vi,2]T,其中vi,1和vi,2分别表示个体向量vi所对应的移动台的坐标xi和yi。
4、变异操作
根据（5.1）式的原理，对每一个时刻的个体vit实施变异操作，得到与其相对应的变异个体xit?1，即
ttt xit?1?vr (5.6) ?Fv?vrr123??式中xit?1表示变异个体
5、交叉操作
利用式（5.7），把vit和由式（5.6）生成的变异个体xit?1实施交叉操作，生成试验个体uit?1，即
u6、选择操作
分别计算个体vit和试验个体uit?1的适应度值，对个体vit和试验个体uit?1的适应度值进行比较，选择适应度值高的个体最为新种群的个体vit?1，即
?uit?1,Iffuit?1?fvit;t?1 vi??t (5.8)
?vi,Oherw .iset?1i?xit?1,If?rand?j??CR?orj?rnb?ir?; (5.7) ??t. i s e ?vi,Otherw????其中fuit?1为试验个体uit?1的适应度，fvit为个体vit的适应度。
7、产生新的种群
经过上述变异、交叉和选择操作的个体作为父代，生成下一代种群。 8、评价新种群
根据第3步，计算新种群中每个染色体的适应度值。若新种群的平均适应度值较高，则选择新种群，淘汰原种群；若原种群的适应度值较高，则选择原种群，淘汰新种群。并判断是否满足终止条件，如果满足并判断是否满足终止条件，如果满足则终止；否则重复步骤4~8，直到满足终止条件。本文中将最大迭代次数作为终止条件。
40
????