基于模拟退火遗传算法求解整周模糊度*

李洪刚，王亚琦，李雪晴，亢俊健

(河北地质大学，河北 石家庄 050031)

GPS以载波相位观测量为依据进行精密定位，迅速又准确地固定整周模糊度是进行高精度相对定位、缩短工作时间和扩展高精度动态定位的关键.在整周模糊度的解算上，国内外学者提出了很多解算算法，如基于LAMBDA算法[1]、FARA算法、蚁群算法[2]、人工鱼群算法(Artificial Fish Swarm Algorithm,AFSA)[3]和遗传算法(Genetic Algorithm，GA)[4-5]等.遗传算法是一种以模拟自然进化过程来搜索最优解的方法，通过选择、交叉、变异等操作来寻求最优解.在搜索整周模糊度最优解的问题上遗传算法具有全局优化、稳健、高效等特点，但同时也面临着搜索空间较大、计算较为复杂且容易陷入局部最优等问题.模拟退火(Simulated Annealing,SA)[6-8]算法是从某一较高初温出发，伴随温度参数的不断下降并结合概率突跳特性，在解空间中随机寻找目标函数的全局最优解，从而有效避免陷入局部最优解并最终达到全局最优解的优化算法.因此，笔者提出利用基于实数编码的模拟退火遗传算法(Simulated Annealing Genetic Algorithm,SAGA)来求解整周模糊度，利用模拟退火来避免遗传算法的早熟问题，有望提高搜索质量.

1 GPS短基线整周模糊度与解算数学模型

1.1 GPS短基线整周模糊度

对定位模型进行线性处理，即将载波相位双差模型线性化，得到GPS短基线相位双差定位模型

y=Aa+Bb+εa∈Zn,b∈Rp.

(1)

其中：y为m维的GNSS观测量，一般包括观测时间内各频率的码观测值和载波相位观测值；A和B是整周模糊度和基线参数的设计矩阵；ε为观测噪声向量；a是单位为周的双差整周模糊度向量，b为包含基线向量和其他实数参数的向量.

由(1)式可得

(2)

进一步计算(2)式,可得

(3)

(4)

使用最小二乘法，(4)式可表示为

(5)

(6)

其中N为整周模糊度的组合数.当目标函数最小时，可得整周模糊度的固定解.

1.2 解算模型

由(6)式可知，第i个模糊度值为

遗传算法根据目标函数来计算适应度函数，从而确定最优解.根据(6)式，判别函数可表示为

f(N)=b-lg(J(N)).

2 基于模拟退火遗传算法的整周模糊度求解

2.1 模拟退火算法

遗传算法是一种有效的寻优算法，但仅采用遗传算法求解整周模糊度效果并不太好[10].因此，改进算法一方面采用实数编码来简化参数，减小引入模拟退火机制所产生的计算量；另一方面，引入模拟退火机制来避免陷入局部最优解，提高遗传算法的搜索能力.其基本流程为先随机产生一个初始种群，经过繁殖、交叉、变异等操作产生新的个体，这些个体经模拟退火后进入新一轮的遗传迭代运算[11].求解整周模糊度时，随着搜索范围变得越来越小，遗传算法易陷入局部最优.在目标函数最优值迭代中，随着温度的下降，模拟退火算法可以访问更多的领域，搜索更大范围的解空间，从而有效避免遗传算法的早熟收敛问题.模拟退火的基本流程如下：

Step1初始化模拟退火算法参数，如初始温度、温度降低参数、模拟退火记录次数.

Step2根据判别函数来判定当代种群的最优值是否比上一代的好，若是，则保留当代最好的个体和适应度，并将之代替当代最差的个体和适应度，温度下降，然后转step 5.

Step3若当代的最优值比上一代最优值差，则计算bh=vlast-vcur，ph= exp(1 000×bh/T).其中：bh是温度差；ph是降温的概率；vlast是上一代最优值；vcur是当代最优值；T为当前温度.

Step4当rand是0～1的随机数,ph大于rand时，保留上一代最好个体和适应度并代替当代最差的个体和适应度.

Step5生成新种群迭代更新.

2.2 Cholesky降相关处理

为了加快模糊度的搜索，需要对整周模糊度的浮点解和协方差矩阵进行Z变换，从而降低模糊度协方差矩阵的相关性.针对高斯分解去相关运算存在数值计算不稳定、运算量是乔里斯基分解的2倍的缺点，首先采用Cholesky分解对协方差矩阵进行去相关运算，然后对分解矩阵进行Z变换.具体过程[6，12]为

2.3 实数编码

很多经典的遗传算法都采用二进制编码.但相比二进制编码，实数编码能够反映整周模糊度解的结构特征，使得计算更加简单快捷,并且能避免Hamming悬崖问题.如采用二进制和7位编码，整周模糊度的组合有(27)3=2 097 152个，而采用实数编码时模糊度的组合仅有213=9 261个，远远小于二进制编码的组合数.

2.4 遗传算子设计及算法过程

(1)选择.笔者采用经典的轮盘选择原理来选择种群的个体，每个个体被选择的期望值与其适应度值和群体平均适应值的比值相关[10].首先计算适应度的累加，个体的适应度越大，占适应度累加和的比例就越大，被选择的概率就越高.

(2)单点交叉.交叉即结合来自父代交配种群的信息而产生新的个体.交叉算子的选择决定了交叉操作的频率，交叉算子概率越高，收敛速度越快，但也有可能带来过早收敛的情况.本研究随机对2个个体的2点进行交叉，经多次实验后取交叉概率为0.6.

(3)变异.变异概率一般选择较小的数值，若选择较高的变异概率，可能会破坏最优解.经多次实验后，本研究的变异概率取0.06.此时效果最佳.

(4)遗传退火.随着遗传算法的不断迭代，种群也越来越逼近最优解，但由于遗传算法的交叉、变异等操作可能会破坏接近最优解的个体，使相对最差的个体进入下一代，不利于遗传算法的求解；因此笔者将精华保留与模拟退火相结合，在交叉变异操作后按照一定的策略选择最佳个体以代替最差个体，从而保证最差个体不进入下一代.

3 实验分析

依照文献[13]中的解算实例进行仿真分析，整周模糊度的取值范围为[-10,10]，选取的三维GPS模糊度浮点解及其相应的协方差矩阵分别为

本实验以时间效率、成功率和模糊度固定正确所需的迭代次数作为评价指标，先后对比有无去相关和是否添加模拟退火对算法性能的影响程度，最后将改进算法与经典LAMBDA算法进行比较.表1列出了部分实验参数，表2列出了整周模糊度的固定解.

表1 参数设置

表2 实例解算结果

经去相关处理过的协方差矩阵较原始协方差矩阵，其元素之间的相关性有了明显的降低，适应度的函数特性发生了明显的变化.去相关前、后适应度的函数分布分别如图1，2所示.由图1，2可知，去相关前的函数存在多个极值，求解整周模糊度时容易陷入局部最优，而经去相关后的函数较单调，只有一个极值，因此能提高求解整周模糊度的正确率和效率.

图1 去相关前适应度函数分布Fig. 1 Fitness Function Before Decorrelation

图2 去相关后适应度函数分布Fig. 2 Fitness Function After Decorrelation

因为对固定后的整周模糊度的估计具有不确定性，所以要进行模糊度正确性的检验.只有验证了整周模糊度的质量即模糊度固定解的可靠性，讨论模糊度固定解的正确率才有意义.ratio值作为模糊度得到固定解的置信度指标，是检验整周模糊度固定可靠性的最常用方法之一，可以由次优的模糊度向量的残差平方和与最优的模糊度向量的残差平方和的比值得到[14].根据经验，ratio值一般可以取2或3，在本实验中设ratio值为3，当ratio值大于3时，判定模糊度固定解是正确的[15].

为了验证算法的有效性和可靠性，针对传统遗传算法和模拟退火遗传算法重复进行了100次对比实验，分别对比了2种算法的模糊度固定解所需的迭代次数、适应度和运行时间.实验结果如图3—5所示.

图3 迭代次数对比Fig. 3 Comparison of Numbers of Iterations

图4 适应度变化对比Fig. 4 Comparison of Fitness Values

图5 运行时间对比Fig. 5 Comparison of Search Time Between Two Algorithms

由图3可知，模拟退火遗传算法的迭代次数明显少于传统遗传算法，即遗传算法经模拟退火算法改进后，能以更快的收敛速度收敛到全局最优解，从而以更少的迭代次数达到固定的正确解.

由图4可知，模拟退火遗传算法的迭代次数明显少于传统遗传算法，即遗传算法经模拟退火算法改进后，能以更高的效率收敛到全局最优解，并且更加稳定.

由图5的数据计算可得模拟退火遗传算法的平均运行时间为0.060 s，收敛速度稍慢于传统遗传算法.将模拟退火遗传算法与经典LAMBDA算法、遗传算法和人工鱼群算法的性能进行比较，100次实验的平均值列于表3.表3中：tmean为算法平均运行时间；Nmean为正确固定整周模糊度的平均次数；Smean为模糊度固定解的正确率.

表3 4种算法性能比较

由表3的实验数据可知：模拟退火遗传算法与LAMBDA算法相比，算法效率和成功率相差不多，但模拟退火遗传算法在计算结果上的稳定性和精度远远优于传统的遗传算法；在保持极高的固定整周模糊度的成功率下，模拟退火遗传算法在计算时间上远远小于人工鱼群算法.

4 结语

遗传算法具有较强的全局搜索能力，但在实际应用中容易出现早熟的问题，而模拟退火机制可以有效跳出局部最优，从而帮助遗传算法快速收敛到全局最优解.引入模拟退火思想，笔者对基于实数编码的遗传算法进行了改进，并将改进的算法应用于整周模糊度问题的解算上.实验结果表明，改进的算法在有效性和稳定性方面都有优秀的表现.