改进的人工蜂群算法及其在坐标转换七参数计算中的应用

汪继文，杜 迪，邱剑锋

（安徽大学 计算机科学与技术学院，安徽 合肥230039）

群体智能（swarm intelligence，简称SI）是以动物或昆虫群体的集体智慧为模型的一个研究领域，是一个涉及在分散系统中学习群体行为的计算智能技术.Bonabeau等［1］给出SI的定义：SI是指任何一种受社会昆虫群体和其他动物种群的社会行为启发而设计出的算法或以分布式方式解决问题的策略.在近几年产生了不少的SI算法，例如遗传算法（genetic algorithm，简称GA）［2］、粒子群优化算法（particle swarm optimization，简称PSO）［3］、蚁群算法（ant colony optimization，简称 ACO）［4］、调和搜寻算法（harmony search，简称 HS）［5］、ABC（artificial bee colony）算法［6］等.ABC算法是近几年发展起来的基于蜂群智能搜寻行为的群体优化算法，虽然该算法改进了参数优化的搜寻解决方案和获得了准确的预测，但仍然面临着一些挑战性的问题，其中两个最主要的问题是该算法容易陷入局部最优和收敛速度较慢.因此，跳出局部最优和加快收敛速度已经成为ABC算法研究中两个最重要的目标.

在大地测量和地图制图的工作中，坐标系是不可缺少的，任何测量和地图制图的工作都是在一定的参考坐标系中进行的.随着全球定位系统（global positioning system，简称GPS）定位精度的不断提升，GPS技术在各种测量中的应用也越来越广泛，但是GPS测量到的坐标是世界大地坐标系84（world geodetic system 84，简称WGS－84）坐标，只能够在WGS－84坐标系统中表示.我国的国土测量成果和在进行工程施工时大都采用北京54（Beijing－54，简称BJ－54）参心坐标系的坐标.如何实现 WGS－84坐标系与BJ－54坐标系之间的精确转换，一直是相关行业应用必须解决的问题.

目前完成不同空间直角坐标系的转换可采用三参数法、七参数法（布尔沙模型、莫洛琴斯基模型、范式模型）多项式逼近法等，其中布尔沙模型七参数转换法是坐标转换中常用的方法［7］，七参数的最优计算是该方法完成高精度坐标转换的关键所在［8］.但目前已有的方法计算出来的七参数的坐标转换精度尚有待提高.

作者提出将改进的ABC算法用于布尔沙模型坐标系转换七参数的计算.首先针对基本的ABC算法的两个缺点，并结合坐标转换七参数的计算，对算法进行改进，即在初始化阶段随机选择重合点的时候，剔除部分误差较大的点，在观察蜂阶段选择概率计算公式中，加入了对重合点个数和重合点外接多边形面积因素的评估，使得算法在收敛速度上有明显加快，并有效防止算法陷入局部最优；然后将改进的ABC算法应用到坐标转换七参数的计算中，并将计算结果与其他两种方法的计算结果进行比较.可以看出论文方法计算的七参数实现了更高精度的WGS－84坐标系与BJ－54坐标系坐标的转换.

1 布尔沙模型七参数坐标转换法

坐标转换通常的途径是根据给定的重合点来确定转换公式的参数，从而实现坐标系之间的转换，这里的重合点是指在两套坐标系中坐标已知的相同点.设某重合点在WGS－84坐标系的空间直角坐标表示为（X84，Y84，Z84），在 BJ－54坐标系的空间直角坐标表示为（X54，Y54，Z54），布尔沙模型七参数转换法的计算公式［9－10］为

上式中含有7个参数DX，DY，DZ，α，β，γ，K.其中：DX，DY，DZ分别表示坐标轴X，Y，Z轴方向的偏移量；α，β，γ分别表示X，Y，Z轴方向的旋转量；K表示缩放因子.七参数计算的目标是根据给定的重合点，求出坐标转换精度较高的七参数.将至少3个重合点的坐标代入（1）式，应用最小二乘原理可以求出坐标转换七参数的解.七参数至少需要3个重合点坐标才能求出，使用4个及4个以上数量的点可以得到更多的观测值，可求出坐标转换精度更高的七参数.

坐标转换精度可采用内符合精度和外符合精度评价.内符合精度是利用下面的重合点残差和残差中误差来检测

残差中误差计算公式［11－12］为

其中：MX，MY，MZ分别为空间直角坐标轴X，Y或Z的残差中误差，计算公式为MX（MY，MZ）＝是第i个重合点的X，Y或Z轴的残差值，n为重合点个数.为了便于比较，MP，MX，MY，MZ均取正值.

内符合的检测依据计算转换参数的重合点残差和残差中误差的倍数关系评估坐标转换精度，残差小于3倍残差中误差的重合点精度满足要求.

外符合精度通过下述评价函数来检测.定义第i个七参数所对应的坐标转换评价函数为

其中：C1，C2为取值在［0，1］之间的权重系数.评价函数值越小，说明进行坐标转换的误差越小，坐标转换的精度也就越高.

2 改进的ABC算法及其应用于坐标转换七参数的计算

2.1 用于坐标转换七参数计算的ABC算法建模与改进

在一个真正的蜜蜂群体中，有些任务是由专门的个体完成的.基本的ABC算法模拟蜜蜂群体采蜜的过程，将蜜蜂分为雇佣蜂、观察蜂和侦察蜂3种类型，3种蜜蜂根据各自的分工进行采蜜活动.每个蜜源代表优化问题的一个可行解，蜜蜂通过对蜜源信息的交流与共享最终达到找到最好的蜜源（最优解）的目的.初始化蜜源之后，雇佣蜂比较记忆中的最优解和邻域搜索解，当搜索解优于记忆最优解时，替换记忆解；反之，保持不变.所有的雇佣蜂搜索完之后，将蜜源信息通过舞蹈区与观察蜂共享，观察蜂按照一定的选择机制选择较好的蜜源，然后转化为雇佣蜂；如果一个蜜源在多次迭代中都未被更新，则该蜜源将被抛弃，依附于该蜜源的雇佣蜂成为侦察蜂，重新初始化一个新的蜜源［13］.

为应用ABC算法来计算七参数，论文建立七参数计算与ABC算法之间的对应关系如表1所示.

表1 七参数计算与ABC算法对应关系Tab.1 Relationship between calculating seven parameters and ABC algorithm

进一步，结合坐标转换七参数计算的特点，论文对基本的ABC算法进行改进，主要包括以下两个方面：

（1）初始解的改进.基本的ABC算法的初始解是随机生成的，在坐标系转换七参数的计算问题中，随机选择的3个重合点计算出来的七参数中有很大一部分是不满足坐标转换精度要求的，再改进下去意义不大，不如在随机初始生成的解中剔除坐标转换精度不达标的七参数及其对应的重合点组，以便后续计算越来越好.剔除解的标准为

如果Num＞3，不符合内符合检测标准，应当舍弃该解及其对应的重合点组.

（2）观察蜂选择策略改进.基本的ABC算法中观察蜂在进行蜜源选择时采用了随机贪婪策略，忽略了个体之间的位置关系［14］，使得观察蜂有可能选择了对应重合点个数较少或者重合点构成的外接多边形面积较小的解，从而导致没能顾及整个测区的精确度，容易陷入局部最优的解中.针对此问题，作者提出，在观察蜂阶段选择机制中加入对重合点个数和重合点构成的外接多边形面积因素的评估，即依据如下公式计算解被选择的概率

其中：SN是整个测区初始解的个数；Ni表示当前解对应的重合点组所包含的重合点个数；Si为重合点组构成的外接多边形面积；R1，R2，R3为权重系数且fiti为第i个七参数的适应度值，计算公式如下

其中：fi是（4）式给出的评价函数.

2.2 改进的ABC算法应用到坐标转换七参数计算的流程

步骤1 在测区内获取多个在两套不同坐标系下均匀分布的重合点坐标，随机选择3个重合点构成一个重合点组，选择SN个重合点组，依据公式（1）计算每个重合点组对应的七参数；依据公式（3）计算当前七参数进行坐标转换的残差中误差值，根据公式（5）剔除精度不达标的解及其对应的重合点组，并再随机生成重合点组补充精度不达标的解，构成SN个符合条件的初始解；

步骤2 设置外循环初始值m＝0，设置内循环初始值n＝0；

步骤3 在重合点组任选一个重合点，在其附近随机增加一个点产生新的重合点组，根据公式（5）监测是否符合内检测标准，符合则继续；不符合，则再随机增加一个点，直至满足内符合标准，然后按照公式（7）计算新解适应度值，如果新解的适应度值大于旧解，则用新解对应的重合组代替旧解对应的重合组；否则，保持不变；

步骤4 如果解没有改进，则limit＝limit＋1；否则limit保持不变；

步骤5 根据公式（6），计算选择概率Pi，观察蜂根据选择概率Pi选择食物源，然后通过增加重合点的方法产生新解，并根据公式（7）计算适应度值；如果新解的适应度值大于旧解，则用新解代替旧解；否则，保持原解不变；

步骤6 设置n＝n＋1，如果n＜N，转步骤3；

变电站在电力系统中有着重要的地位和作用，实现变电站的无人值守是当今电力系统的发展趋势。但现有变电站图像监控系统虽可以实现图像监控与报警信号进行简单的联动，还无法实现各子系统之间遥信、遥测、遥视、遥控信息的系统级别的智能联动。变电站运检人员在现场进行设备巡视，只是对运行设备进行感观的、简单的定性判断，而还存在一些现场巡检人员靠肉眼无法完全发现的缺陷。如果这些缺陷未能及时发现和处理，可能发生严重事故，造成不必要的损失。

步骤7 判断解没有被改进的次数是否超过limit值，如果超过，则抛弃该解及其对应的重合点组，全局随机生成一个新解，转入步骤3；

步骤8 所有搜索完毕后，记录当前最优解；

步骤9 设置m＝m＋1，如果m＜M，转至步骤3；否则，结束.

3 性能分析及仿真实验

3.1 性能分析

为了验证改进的ABC算法的良好性能，在.NET环境下使用基本的ABC算法和论文改进的ABC算法进行坐标转换七参数计算，将得到的坐标转换精度结果进行对比.设置相关实验参数：种群大小SN＝50，内循环次数N＝100，外循环次数M＝100，权重系数C1＝0.4，C2＝0.2，R1＝0.5，R2＝R3＝0.25.输出迭代次数和评价函数值如图1所示，其中横轴为迭代次数，纵轴为评价函数值.由图1所示的实验结果可以看出，由于改进的ABC算法对于初始解进行了优化，及时剔除不满足条件的解，并考虑到最优解所包含的重合点个数和重合点构成外接多边形面积对于选择概率的影响，使得算法最后输出的解转换精确度有所提高并且收敛速度有了明显加快.

3.2 仿真实验

为了验证改进的ABC算法在坐标系转换七参数计算中的能够计算出坐标转换精度较高的七参数，该研究对设定的算法进行了真实数据实验，根据所设定的算法，实验采用基于ArcGIS Enginge、.NET平台在 Visual Studio 2013中编程实验（计算机配置：Intel Core i5－3470 CPU 3.20GHz）.

实验数据集为某地区（大约100km×100km）的200个重合点坐标，它们是BJ－54坐标系下空间直角坐标和对应的由静态测量得到的WGS－84坐标系下的空间大地坐标.要实现从 WGS－84到BJ－54坐标系的坐标转换，要先将测得的WGS－84空间大地坐标转换成空间直角坐标［15］.表2展示部分重合点数据（由于涉及国家机密，表中所给的数据非真实数据，只为了形象的表达而展示）.

表2 部分重合点的BJ－54坐标和WGS－84坐标Tab.2 BJ－54coordinates and WGS－84coordinates of some coincidence points

算法实验的具体参数设置如下：种群大小SN＝30，内循环次数N＝40，外循环次数M＝500，权重系数C1＝0.4，C2＝0.2，R1＝0.5，R2＝R3＝0.25.基于改进的ABC算法计算七参数的计算结果列于表3（3次独立运行的实验结果，分别编号为1，2，3）.

表3 改进的ABC算法得到的七参数值Tab.3 Seven parameter values obtained by the improved ABC algorithm

表4 两种方法计算的七参数值Tab.4 Seven parameter values calculated by two methods

由其他的所有未参与七参数计算的重合点中随机取出10、15、20、25、30、35、40、45、50个点，根据公式（4）计算表3、表4两个表中5个实验结果的七参数对应的评价函数值，其对比结果如图2所示.

从图2中可以看出，直接由最小二乘法计算出的七参数误差相对较大，评价函数值在6～9cm；使用基于非迭代法与迭代法联合估计方法计算出来的七参数进行坐标转换的精度相对于直接由最小二乘法计算的结果要好，但也没有太大提高；而采用了改进的ABC算法计算出来的七参数在实际的坐标转换中能够保持相对较高的精度，评价函数值稳定在1～5cm，误差相对其他两种方法明显减少.

4 结束语

论文针对ABC算法收敛速度慢和容易陷入局部最优的缺点，并与坐标系转换七参数计算问题相结合，提出了对基本ABC算法的初始解和观察蜂选择策略两个方面的改进.实验表明，论文提出的改进的ABC算法应用到坐标系转换七参数计算上，与所比较方法求出的七参数计算坐标转换精度相比，具有良好的寻优性和稳定性，能够实现精度较高的坐标转换.

［1］Bonabeau E，Dorigo M，Theraulaz G.Swarm intelligence：from natural to artificial systems［M］.London：Oxford University Press，1999.

［2］Tang K S，Man K F，Kwong S，et al.Genetic algorithms and their applications［J］.Signal Processing Magazine，IEEE，1996，13（6）：22－37.

［3］Kennedy J.Particle swarm optimization［C］／／Encyclopedia of Machine Learning，Springer US，2010：760－766.

［4］Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem［J］.Evolutionary Computation，IEEE Transactions on，1997，1（1）：53－66.

［5］Geem Z W，Kim J H，Loganathan G V.A new heuristic optimization algorithm：harmony search［J］.Simulation，2001，76（2）：60－68.

［6］Karaboga D.An idea based on honey bee swarm for numerical optimization［R］.Technical Report－tr06，Erciyes University，Engineering Faculty，Computer Engineering Department，2005.

［7］徐仕琪，张晓帆.关于利用七参数法进行 WGS84和BJ54坐标系转换问题讨论［J］.测绘与空间地理信息，2007，30（5）：33－39.

［8］谭骏祥，李少达，杨容浩.基于非迭代与迭代法联合估计的七参数坐标转换方法研究［J］.大地测量与地球动力学，2014，34（1）：131－134.

［9］柳光魁，王振禄，赵永强，等.BJ－54坐标系与 WGS－84坐标系转换方法及精度分析［J］.测绘与空间地理信息，2007，30（3）：167－168.

［10］张敬伟.布尔莎模型坐标转换适用范围及精度分析［J］.测绘与空间地理信息，2013（1）：175－176.

［11］高永甲.WGS－84坐标系和西安80坐标系转换方法及精度分析——基于新疆兵团C、D级GPS网成果［J］.测绘工程，2009，18（3）：32－35.

［12］骆永炎.关于中误差公式的文字解释［J］.测绘通报，1982（4）：15.

［13］汪继文，杨丹，邱剑锋，等.改进人工蜂群算法求解非线性方程组［J］.安徽大学学报：自然科学版，2014，38（3）：16－23.

［14］张鹏，刘弘，刘鹏.改进的蜂群算法及其在 CBD选址规划中的应用［J］.计算机科学，2013，40（8）：210－213.

［15］王解先，徐志京.三种坐标间转换的雅可比矩阵数值导数计算方法［J］.大地测量与地球动力学，2005，24（4）：19－23.