基于改进遗传算法的定位问题研究

陈一鸣

（河海大学水利水电学院，南京　210098）

基于改进遗传算法的定位问题研究

陈一鸣

（河海大学水利水电学院，南京210098）

本文提出了一种基于物体影子随时间变化关系进行定位的新型定位方法。通过物体影长的模型与时间的函数关系，建立了基于最小二乘法的优化模型，并采用了遗传算法进行寻优求解，同时对遗传算法进行了一定改进，得到了较传统遗传算法更优的解答，得到的定位精度也较高。

空间定位；最小二乘法；改进的遗传算法

0　引 言

物体定位技术已经由传统的自然规律发展到现代的GPS定位和雷达定位等，而利用物体的影子进行定位即是将自然规律与现代科技相结合而形成的一种新型定位方法。物体的影子作为直观的视觉信息，研究影子的定位方法是一项新兴主题实用技术。该项技术对视频图像资料的定位提供了解决办法，而且也为刑侦以及失踪人员侦察等工作在相当程度上创造了真实便利。由于物体在不同地点、不同日期和不同时间的影子长度和角度会发生变化，本文针对影子坐标等数据建立最小二乘优化模型，在传统遗传算法的基础上，加入了寻优范围的约束建立改进遗传算法，对比2种算法，可以得到后者搜索结果残差平方和最小，说明改进遗传算法具有很好的鲁棒性。

1　数学模型

1.1问题描述

影子定位问题可以描述为：某一日期不同时刻t的一直杆影子的顶点坐标为（x，y），要求定位出此时刻的直杆经纬度。本文所采用数据为2015年数模竞赛A题附件1［1］。当地实际时间ts与北京时间t的时间差用Δt来表示，杆长为h。当地的纬度（φ）、太阳高度角（α）、太阳赤纬角（δ）、时角（ω）的相关公式如下：

（1）时角ω（度）［2］公式：

（2）太阳赤纬角δ［3］公式：

（3）太阳高度角α［4］公式：

由此可以得出影长L与太阳运动参数的关系如下：

1.2最小二乘优化模型

针对上述问题，要确定多个未知参数需采用最小二乘的思想建立优化模型，设研究中共有m组数据（x，y，t），令z= L2，则以残差平方和为目标函数建立规划模型如下：

2　遗传算法设计

遗传算法（Genetic Algorithm，简称GA）是美国密执安大学J.H.Holland教授于20世纪70年代中期首次提出的一种基于生物遗传和进化机制的适合复杂系统优化计算的自适应概率优化技术。作为一种智能优化算法，其鲁棒性较强，简单通用，具有较强容错能力，通过选择、交叉、变异等操作能极大限度地向最优解进行逼近。同时，变异等操作的引入可防止结果陷入局部最优解，增加搜索的灵活性。对于每一位个体，采用适应度函数对其评价。

基于上文建立的最小二乘优化模型，可以看作是染色体组（φ，h，Δt）在满足式（6）的约束条件下，通过评价函数对其进行评价，使评价值较高的个体进入到产生下一代的运算中，直至满足终止条件。遗传算法流程如图1所示。

图1　遗传算法流程图Fig.1 Genetic algorithm flowchart

2.1遗传编码

比较常见的遗传算法编码方式是二进制编码、格雷编码及符号编码等。本文采用二进制进行编码，并将染色体向量记为V=（φ，h，Δt）。然而，由于实际的算子存在小数，如果直接转化为二进制，可能会因此而出现无穷小数。针对这一状况，可将精度确定于小数点后三位，转换成二进制整数后再进行编码、运算，并将运算结果转化为十进制后再除以1 000即可。例如，对于染色体向量V=（0.213，2.986，0.721），得到1 000 V=（213，298 6，721），转为二进制V=［11010101，101110101010，1011010001］2。

2.2适应度函数

适应度函数是评价个体性能优劣的唯一指标。在本次研究中，基于最小二乘的思想，目标函数的结果值越小，表明拟合的程度越好，即所求得的经纬度更接近原始目的地。因此需将目标函数转换为适应度函数，以便进行个体优劣的目标判断。此时，可用适应度Gi表示第i位个体的优良程度：

其中，Q（Xi）是第i个母体的修正值。同时，由于该问题是带有约束的优化问题，则需在适应度上加入惩罚项。修正后的计算公式如下：

其中，f（Xi）即为式（5）的最小二乘残差平方和，M为惩

2.3选择算子

如何选择参与运算的个体是遗传算法中的执行实施重点，本文中采用轮盘赌的方法进行选择。实现过程如下：

1）计算出现在种群中所有个体的适应度Gi以及所有适应度值的倒数总和S。

2）划分区间［0，1/G1S），［1/G1S，1/G2S）……［1/GnS，1），表示轮盘各扇区的面积。设置生成一个随机数N∈［0，1），根据N所在的区间进行交叉算子的选择。如N∈［1/G1S，1/G2S），则选择第2位个体进行运算。

2.4交叉运算

交叉运算是遗传算法中目标实现的关键所在。其本质是模拟自然界中生物优胜劣汰的原则。即优良的个体将有更大的机会产生后代，从而后代性能必然不断趋近于更加优秀。在本例中，基于前述采用的是二进制编码，这里采用了单点交叉的方法。随机生成3个交叉点位，对选定的染色体组执行交叉运算。如生成的交叉点位向量Y=（5，3，6），对于染色体向量pop1和pop2，操作过程如图2所示。交叉运算以后产生后代pop1＇和pop2＇，存入下一代中，母代的个体则继续参与其后的变异运算，从而保证了种群的多样性。

图2　交叉运算示意图Fig.2 Schematic diagram of cross-operation

2.5变异运算

变异运算是模拟自然界中生物进化时的产生的偶发的基因突变。事实上，在用遗传算法求取最优解问题中，变异运算一定程度上保证了种群不会陷入局部最优解，增强了遗传算法对全局最优解的搜索能力。本文采用的变异方式有旋转变异以及位变异2种。

对于旋转变异，操作方式如下：选取pm1·pop个母体，对于所选的染色体组中的3个染色体，随机选择3个位置，并分别以其为分界点，将每个染色体左右的基因互换，完成旋转变异。如对于染色体组pop：

进行旋转变异后的结果为：

至此，完成了对旋转变异的操作。对于位变异，类似于旋转变异，先选取pm2·pop个母体在生成变异位的基础上，将所对应的基因进行取反处理，即若基因为1，则取为0，反之即取为1，其他位不变。本文取变异概率pm1=0.1，pm2=0.1。

2.6 终止条件

由于本研究是一个最小二乘的优化问题，对精度要求较高才能搜索到满意最优解，设置终止条件为进化代数generation=1 000。

2.7遗传算法的改进

为了得到精度更高的最佳结果，可以采用改进的遗传算法搜索可行解。通过传统遗传算法计算可得的解集V=（φ，h，Δt）是有一定范围的，其中h的范围为［1.86，1.946］，φ的范围为［0.3，0.319］，△t的范围为［0.56，0.645］，因此可以认定实际上的最优解应在这些范围附近。通过重新设置变量V=（φ，h，Δt）的范围，再进一步实施遗传算法寻优，可以显著提升算法效率，从而得到更加精确的总体可行解。

设置一个放大系数λ，将上述所求解的范围记为：

则得到新的范围：

此处取λ=1.3，并将新的范围作为约束条件代入改进的遗传算法程序。

2.8改进的遗传算法与遗传算法的实例比较

本文采用全国大学生数学建模竞赛A题目附件1的数据［1］，利用最小二乘模型，分别采用2种遗传算法编程，求解结果如表1所示，进化情况分别为图3和图4所示。

表1　遗传算法与改进遗传算法结果比较Tab.1 Comparison of GA and improved GA

图3　遗传算法进化图Fig.3 Evolutionary graph of GA

图4　改进后的遗传算法进化图Fig.4 Evolutionary graph of improved GA

由上述结果可得，采用遗传算法进行计算得到的目标函数值在10-5左右，但是所求的各组h、φ、Δt值之间偏差较大，无法得到一个确定、且较优的解答。通过表1对比可得，改进后的遗传算法获得的最优解要远远优于之前的遗传算法，所得到的解集V=（φ，h，Δt）则更加趋向于一固定值，并且算法时间复杂度也仅是呈现为线性增加，因此具有较强的通用性。研究最后，可以定位出物体所在经纬度为（N21°36′1.83″，E108°49′30″）。

3　结束语

影子的存在能够为光线估计、姿态估计、目标大小估计、深度估计、立体匹配等计算机视觉任务提供重要的线索。本文主要采用杆影日照原理，借助已知影子的轨迹可以反演出杆影目标地点的具体经纬度方位。研究中建立了影长模型和最小二乘优化模型，同时采用遗传算法来求解直杆相关参数的可行解，并对传统意义上的遗传算法提出了一定改进，缩小了遗传算法的搜索范围，大大提高了算法的效率以及结果的精度，对于精确定位具有一定的现实重要意义。

［1］中国工业与应用数学学会.2015高教社杯全国大学生数学建模竞赛A题［EB/OL］.［2015-09-12］.http：//www.mcm.edu.cn/ html_cn/node/ac8b96613522ef62c019d1cd45a125e3.html.

［2］方荣生.太阳能应用技术［M］.北京：中国农业机械出版社，1985.［3］陈晓勇，郑科科.对建筑日照计算中太阳赤纬角公式的探讨［J］.浙江建筑，2011，28（9）：6-8，12.

［4］维基百科.太阳高度角［EB/OL］.［2014-12-06］.http：//zh. wikipedia.org/zh-cn/.

Research on location problem based on improved genetic algorithm

CHEN Yiming
（Institute of Water Conservancy and Hydroelectric Power，Hehai University，Nanjing 210098，China）

The paper proposes a new method based on the relationship of object shadow with time.The optimization model based on the least square method is established by means of function relation between the model and the time of object shadow，and the genetic algorithm is used to solve the optimization.At the same time，the genetic algorithm is improved to get the solution better than the traditional genetic algorithm，which has the higher positioning accuracy.

spatial location；least square method；improved genetic algorithm

TP391

A

2095-2163（2016）03-0055-03

2016-04-23

陈一鸣（1994-），男，本科生，主要研究方向：水利水电工程。