改進的人工蜂群算法及其在坐標轉(zhuǎn)換七參數(shù)計算中的應(yīng)用

汪繼文，杜 迪，邱劍鋒

（安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 合肥230039）

群體智能（swarm intelligence，簡稱SI）是以動物或昆蟲群體的集體智慧為模型的一個研究領(lǐng)域，是一個涉及在分散系統(tǒng)中學(xué)習(xí)群體行為的計算智能技術(shù).Bonabeau等［1］給出SI的定義：SI是指任何一種受社會昆蟲群體和其他動物種群的社會行為啟發(fā)而設(shè)計出的算法或以分布式方式解決問題的策略.在近幾年產(chǎn)生了不少的SI算法，例如遺傳算法（genetic algorithm，簡稱GA）［2］、粒子群優(yōu)化算法（particle swarm optimization，簡稱PSO）［3］、蟻群算法（ant colony optimization，簡稱 ACO）［4］、調(diào)和搜尋算法（harmony search，簡稱 HS）［5］、ABC（artificial bee colony）算法［6］等.ABC算法是近幾年發(fā)展起來的基于蜂群智能搜尋行為的群體優(yōu)化算法，雖然該算法改進了參數(shù)優(yōu)化的搜尋解決方案和獲得了準確的預(yù)測，但仍然面臨著一些挑戰(zhàn)性的問題，其中兩個最主要的問題是該算法容易陷入局部最優(yōu)和收斂速度較慢.因此，跳出局部最優(yōu)和加快收斂速度已經(jīng)成為ABC算法研究中兩個最重要的目標.

在大地測量和地圖制圖的工作中，坐標系是不可缺少的，任何測量和地圖制圖的工作都是在一定的參考坐標系中進行的.隨著全球定位系統(tǒng)（global positioning system，簡稱GPS）定位精度的不斷提升，GPS技術(shù)在各種測量中的應(yīng)用也越來越廣泛，但是GPS測量到的坐標是世界大地坐標系84（world geodetic system 84，簡稱WGS－84）坐標，只能夠在WGS－84坐標系統(tǒng)中表示.我國的國土測量成果和在進行工程施工時大都采用北京54（Beijing－54，簡稱BJ－54）參心坐標系的坐標.如何實現(xiàn) WGS－84坐標系與BJ－54坐標系之間的精確轉(zhuǎn)換，一直是相關(guān)行業(yè)應(yīng)用必須解決的問題.

目前完成不同空間直角坐標系的轉(zhuǎn)換可采用三參數(shù)法、七參數(shù)法（布爾沙模型、莫洛琴斯基模型、范式模型）多項式逼近法等，其中布爾沙模型七參數(shù)轉(zhuǎn)換法是坐標轉(zhuǎn)換中常用的方法［7］，七參數(shù)的最優(yōu)計算是該方法完成高精度坐標轉(zhuǎn)換的關(guān)鍵所在［8］.但目前已有的方法計算出來的七參數(shù)的坐標轉(zhuǎn)換精度尚有待提高.

作者提出將改進的ABC算法用于布爾沙模型坐標系轉(zhuǎn)換七參數(shù)的計算.首先針對基本的ABC算法的兩個缺點，并結(jié)合坐標轉(zhuǎn)換七參數(shù)的計算，對算法進行改進，即在初始化階段隨機選擇重合點的時候，剔除部分誤差較大的點，在觀察蜂階段選擇概率計算公式中，加入了對重合點個數(shù)和重合點外接多邊形面積因素的評估，使得算法在收斂速度上有明顯加快，并有效防止算法陷入局部最優(yōu)；然后將改進的ABC算法應(yīng)用到坐標轉(zhuǎn)換七參數(shù)的計算中，并將計算結(jié)果與其他兩種方法的計算結(jié)果進行比較.可以看出論文方法計算的七參數(shù)實現(xiàn)了更高精度的WGS－84坐標系與BJ－54坐標系坐標的轉(zhuǎn)換.

1 布爾沙模型七參數(shù)坐標轉(zhuǎn)換法

坐標轉(zhuǎn)換通常的途徑是根據(jù)給定的重合點來確定轉(zhuǎn)換公式的參數(shù)，從而實現(xiàn)坐標系之間的轉(zhuǎn)換，這里的重合點是指在兩套坐標系中坐標已知的相同點.設(shè)某重合點在WGS－84坐標系的空間直角坐標表示為（X84，Y84，Z84），在 BJ－54坐標系的空間直角坐標表示為（X54，Y54，Z54），布爾沙模型七參數(shù)轉(zhuǎn)換法的計算公式［9－10］為

上式中含有7個參數(shù)DX，DY，DZ，α，β，γ，K.其中：DX，DY，DZ分別表示坐標軸X，Y，Z軸方向的偏移量；α，β，γ分別表示X，Y，Z軸方向的旋轉(zhuǎn)量；K表示縮放因子.七參數(shù)計算的目標是根據(jù)給定的重合點，求出坐標轉(zhuǎn)換精度較高的七參數(shù).將至少3個重合點的坐標代入（1）式，應(yīng)用最小二乘原理可以求出坐標轉(zhuǎn)換七參數(shù)的解.七參數(shù)至少需要3個重合點坐標才能求出，使用4個及4個以上數(shù)量的點可以得到更多的觀測值，可求出坐標轉(zhuǎn)換精度更高的七參數(shù).

坐標轉(zhuǎn)換精度可采用內(nèi)符合精度和外符合精度評價.內(nèi)符合精度是利用下面的重合點殘差和殘差中誤差來檢測

殘差中誤差計算公式［11－12］為

其中：MX，MY，MZ分別為空間直角坐標軸X，Y或Z的殘差中誤差，計算公式為MX（MY，MZ）＝是第i個重合點的X，Y或Z軸的殘差值，n為重合點個數(shù).為了便于比較，MP，MX，MY，MZ均取正值.

內(nèi)符合的檢測依據(jù)計算轉(zhuǎn)換參數(shù)的重合點殘差和殘差中誤差的倍數(shù)關(guān)系評估坐標轉(zhuǎn)換精度，殘差小于3倍殘差中誤差的重合點精度滿足要求.

外符合精度通過下述評價函數(shù)來檢測.定義第i個七參數(shù)所對應(yīng)的坐標轉(zhuǎn)換評價函數(shù)為

其中：C1，C2為取值在［0，1］之間的權(quán)重系數(shù).評價函數(shù)值越小，說明進行坐標轉(zhuǎn)換的誤差越小，坐標轉(zhuǎn)換的精度也就越高.

2 改進的ABC算法及其應(yīng)用于坐標轉(zhuǎn)換七參數(shù)的計算

2.1 用于坐標轉(zhuǎn)換七參數(shù)計算的ABC算法建模與改進

在一個真正的蜜蜂群體中，有些任務(wù)是由專門的個體完成的.基本的ABC算法模擬蜜蜂群體采蜜的過程，將蜜蜂分為雇傭蜂、觀察蜂和偵察蜂3種類型，3種蜜蜂根據(jù)各自的分工進行采蜜活動.每個蜜源代表優(yōu)化問題的一個可行解，蜜蜂通過對蜜源信息的交流與共享最終達到找到最好的蜜源（最優(yōu)解）的目的.初始化蜜源之后，雇傭蜂比較記憶中的最優(yōu)解和鄰域搜索解，當搜索解優(yōu)于記憶最優(yōu)解時，替換記憶解；反之，保持不變.所有的雇傭蜂搜索完之后，將蜜源信息通過舞蹈區(qū)與觀察蜂共享，觀察蜂按照一定的選擇機制選擇較好的蜜源，然后轉(zhuǎn)化為雇傭蜂；如果一個蜜源在多次迭代中都未被更新，則該蜜源將被拋棄，依附于該蜜源的雇傭蜂成為偵察蜂，重新初始化一個新的蜜源［13］.

為應(yīng)用ABC算法來計算七參數(shù)，論文建立七參數(shù)計算與ABC算法之間的對應(yīng)關(guān)系如表1所示.

表1 七參數(shù)計算與ABC算法對應(yīng)關(guān)系Tab.1 Relationship between calculating seven parameters and ABC algorithm

進一步，結(jié)合坐標轉(zhuǎn)換七參數(shù)計算的特點，論文對基本的ABC算法進行改進，主要包括以下兩個方面：

（1）初始解的改進.基本的ABC算法的初始解是隨機生成的，在坐標系轉(zhuǎn)換七參數(shù)的計算問題中，隨機選擇的3個重合點計算出來的七參數(shù)中有很大一部分是不滿足坐標轉(zhuǎn)換精度要求的，再改進下去意義不大，不如在隨機初始生成的解中剔除坐標轉(zhuǎn)換精度不達標的七參數(shù)及其對應(yīng)的重合點組，以便后續(xù)計算越來越好.剔除解的標準為

如果Num＞3，不符合內(nèi)符合檢測標準，應(yīng)當舍棄該解及其對應(yīng)的重合點組.

（2）觀察蜂選擇策略改進.基本的ABC算法中觀察蜂在進行蜜源選擇時采用了隨機貪婪策略，忽略了個體之間的位置關(guān)系［14］，使得觀察蜂有可能選擇了對應(yīng)重合點個數(shù)較少或者重合點構(gòu)成的外接多邊形面積較小的解，從而導(dǎo)致沒能顧及整個測區(qū)的精確度，容易陷入局部最優(yōu)的解中.針對此問題，作者提出，在觀察蜂階段選擇機制中加入對重合點個數(shù)和重合點構(gòu)成的外接多邊形面積因素的評估，即依據(jù)如下公式計算解被選擇的概率

其中：SN是整個測區(qū)初始解的個數(shù)；Ni表示當前解對應(yīng)的重合點組所包含的重合點個數(shù)；Si為重合點組構(gòu)成的外接多邊形面積；R1，R2，R3為權(quán)重系數(shù)且fiti為第i個七參數(shù)的適應(yīng)度值，計算公式如下

其中：fi是（4）式給出的評價函數(shù).

2.2 改進的ABC算法應(yīng)用到坐標轉(zhuǎn)換七參數(shù)計算的流程

步驟1 在測區(qū)內(nèi)獲取多個在兩套不同坐標系下均勻分布的重合點坐標，隨機選擇3個重合點構(gòu)成一個重合點組，選擇SN個重合點組，依據(jù)公式（1）計算每個重合點組對應(yīng)的七參數(shù)；依據(jù)公式（3）計算當前七參數(shù)進行坐標轉(zhuǎn)換的殘差中誤差值，根據(jù)公式（5）剔除精度不達標的解及其對應(yīng)的重合點組，并再隨機生成重合點組補充精度不達標的解，構(gòu)成SN個符合條件的初始解；

步驟2 設(shè)置外循環(huán)初始值m＝0，設(shè)置內(nèi)循環(huán)初始值n＝0；

步驟3 在重合點組任選一個重合點，在其附近隨機增加一個點產(chǎn)生新的重合點組，根據(jù)公式（5）監(jiān)測是否符合內(nèi)檢測標準，符合則繼續(xù)；不符合，則再隨機增加一個點，直至滿足內(nèi)符合標準，然后按照公式（7）計算新解適應(yīng)度值，如果新解的適應(yīng)度值大于舊解，則用新解對應(yīng)的重合組代替舊解對應(yīng)的重合組；否則，保持不變；

步驟4 如果解沒有改進，則limit＝limit＋1；否則limit保持不變；

步驟5 根據(jù)公式（6），計算選擇概率Pi，觀察蜂根據(jù)選擇概率Pi選擇食物源，然后通過增加重合點的方法產(chǎn)生新解，并根據(jù)公式（7）計算適應(yīng)度值；如果新解的適應(yīng)度值大于舊解，則用新解代替舊解；否則，保持原解不變；

步驟6 設(shè)置n＝n＋1，如果n＜N，轉(zhuǎn)步驟3；

變電站在電力系統(tǒng)中有著重要的地位和作用，實現(xiàn)變電站的無人值守是當今電力系統(tǒng)的發(fā)展趨勢。但現(xiàn)有變電站圖像監(jiān)控系統(tǒng)雖可以實現(xiàn)圖像監(jiān)控與報警信號進行簡單的聯(lián)動，還無法實現(xiàn)各子系統(tǒng)之間遙信、遙測、遙視、遙控信息的系統(tǒng)級別的智能聯(lián)動。變電站運檢人員在現(xiàn)場進行設(shè)備巡視，只是對運行設(shè)備進行感觀的、簡單的定性判斷，而還存在一些現(xiàn)場巡檢人員靠肉眼無法完全發(fā)現(xiàn)的缺陷。如果這些缺陷未能及時發(fā)現(xiàn)和處理，可能發(fā)生嚴重事故，造成不必要的損失。

步驟7 判斷解沒有被改進的次數(shù)是否超過limit值，如果超過，則拋棄該解及其對應(yīng)的重合點組，全局隨機生成一個新解，轉(zhuǎn)入步驟3；

步驟8 所有搜索完畢后，記錄當前最優(yōu)解；

步驟9 設(shè)置m＝m＋1，如果m＜M，轉(zhuǎn)至步驟3；否則，結(jié)束.

3 性能分析及仿真實驗

3.1 性能分析

為了驗證改進的ABC算法的良好性能，在.NET環(huán)境下使用基本的ABC算法和論文改進的ABC算法進行坐標轉(zhuǎn)換七參數(shù)計算，將得到的坐標轉(zhuǎn)換精度結(jié)果進行對比.設(shè)置相關(guān)實驗參數(shù)：種群大小SN＝50，內(nèi)循環(huán)次數(shù)N＝100，外循環(huán)次數(shù)M＝100，權(quán)重系數(shù)C1＝0.4，C2＝0.2，R1＝0.5，R2＝R3＝0.25.輸出迭代次數(shù)和評價函數(shù)值如圖1所示，其中橫軸為迭代次數(shù)，縱軸為評價函數(shù)值.由圖1所示的實驗結(jié)果可以看出，由于改進的ABC算法對于初始解進行了優(yōu)化，及時剔除不滿足條件的解，并考慮到最優(yōu)解所包含的重合點個數(shù)和重合點構(gòu)成外接多邊形面積對于選擇概率的影響，使得算法最后輸出的解轉(zhuǎn)換精確度有所提高并且收斂速度有了明顯加快.

3.2 仿真實驗

為了驗證改進的ABC算法在坐標系轉(zhuǎn)換七參數(shù)計算中的能夠計算出坐標轉(zhuǎn)換精度較高的七參數(shù)，該研究對設(shè)定的算法進行了真實數(shù)據(jù)實驗，根據(jù)所設(shè)定的算法，實驗采用基于ArcGIS Enginge、.NET平臺在 Visual Studio 2013中編程實驗（計算機配置：Intel Core i5－3470 CPU 3.20GHz）.

實驗數(shù)據(jù)集為某地區(qū)（大約100km×100km）的200個重合點坐標，它們是BJ－54坐標系下空間直角坐標和對應(yīng)的由靜態(tài)測量得到的WGS－84坐標系下的空間大地坐標.要實現(xiàn)從 WGS－84到BJ－54坐標系的坐標轉(zhuǎn)換，要先將測得的WGS－84空間大地坐標轉(zhuǎn)換成空間直角坐標［15］.表2展示部分重合點數(shù)據(jù)（由于涉及國家機密，表中所給的數(shù)據(jù)非真實數(shù)據(jù)，只為了形象的表達而展示）.

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

算法實驗的具體參數(shù)設(shè)置如下：種群大小SN＝30，內(nèi)循環(huán)次數(shù)N＝40，外循環(huán)次數(shù)M＝500，權(quán)重系數(shù)C1＝0.4，C2＝0.2，R1＝0.5，R2＝R3＝0.25.基于改進的ABC算法計算七參數(shù)的計算結(jié)果列于表3（3次獨立運行的實驗結(jié)果，分別編號為1，2，3）.

表3 改進的ABC算法得到的七參數(shù)值Tab.3 Seven parameter values obtained by the improved ABC algorithm

表4 兩種方法計算的七參數(shù)值Tab.4 Seven parameter values calculated by two methods

由其他的所有未參與七參數(shù)計算的重合點中隨機取出10、15、20、25、30、35、40、45、50個點，根據(jù)公式（4）計算表3、表4兩個表中5個實驗結(jié)果的七參數(shù)對應(yīng)的評價函數(shù)值，其對比結(jié)果如圖2所示.

從圖2中可以看出，直接由最小二乘法計算出的七參數(shù)誤差相對較大，評價函數(shù)值在6～9cm；使用基于非迭代法與迭代法聯(lián)合估計方法計算出來的七參數(shù)進行坐標轉(zhuǎn)換的精度相對于直接由最小二乘法計算的結(jié)果要好，但也沒有太大提高；而采用了改進的ABC算法計算出來的七參數(shù)在實際的坐標轉(zhuǎn)換中能夠保持相對較高的精度，評價函數(shù)值穩(wěn)定在1～5cm，誤差相對其他兩種方法明顯減少.

4 結(jié)束語

論文針對ABC算法收斂速度慢和容易陷入局部最優(yōu)的缺點，并與坐標系轉(zhuǎn)換七參數(shù)計算問題相結(jié)合，提出了對基本ABC算法的初始解和觀察蜂選擇策略兩個方面的改進.實驗表明，論文提出的改進的ABC算法應(yīng)用到坐標系轉(zhuǎn)換七參數(shù)計算上，與所比較方法求出的七參數(shù)計算坐標轉(zhuǎn)換精度相比，具有良好的尋優(yōu)性和穩(wěn)定性，能夠?qū)崿F(xiàn)精度較高的坐標轉(zhuǎn)換.

［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］徐仕琪，張曉帆.關(guān)于利用七參數(shù)法進行 WGS84和BJ54坐標系轉(zhuǎn)換問題討論［J］.測繪與空間地理信息，2007，30（5）：33－39.

［8］譚駿祥，李少達，楊容浩.基于非迭代與迭代法聯(lián)合估計的七參數(shù)坐標轉(zhuǎn)換方法研究［J］.大地測量與地球動力學(xué)，2014，34（1）：131－134.

［9］柳光魁，王振祿，趙永強，等.BJ－54坐標系與 WGS－84坐標系轉(zhuǎn)換方法及精度分析［J］.測繪與空間地理信息，2007，30（3）：167－168.

［10］張敬偉.布爾莎模型坐標轉(zhuǎn)換適用范圍及精度分析［J］.測繪與空間地理信息，2013（1）：175－176.

［11］高永甲.WGS－84坐標系和西安80坐標系轉(zhuǎn)換方法及精度分析——基于新疆兵團C、D級GPS網(wǎng)成果［J］.測繪工程，2009，18（3）：32－35.

［12］駱永炎.關(guān)于中誤差公式的文字解釋［J］.測繪通報，1982（4）：15.

［13］汪繼文，楊丹，邱劍鋒，等.改進人工蜂群算法求解非線性方程組［J］.安徽大學(xué)學(xué)報：自然科學(xué)版，2014，38（3）：16－23.

［14］張鵬，劉弘，劉鵬.改進的蜂群算法及其在 CBD選址規(guī)劃中的應(yīng)用［J］.計算機科學(xué)，2013，40（8）：210－213.

［15］王解先，徐志京.三種坐標間轉(zhuǎn)換的雅可比矩陣數(shù)值導(dǎo)數(shù)計算方法［J］.大地測量與地球動力學(xué)，2005，24（4）：19－23.