人工蜂群算法及其在土地資源優化中的應用研究

張泊平, 吳國璽

(1.許昌學院計算機科學與技術學院,河南許昌461000;2.許昌學院城市與環境學院,河南許昌461000)

0 引言

目前,解決系統優化問題的有效工具之一是群智能優化算法,但是算法收斂速度慢、容易陷入局部最優解[1-2]。2005年Karaboga提出了人工蜂群算法(Artificial Bee Colony Algorithm,ABC)[3],以解決相關問題。該算法的主要思想是對蜂群內部的蜜蜂進行明確分工,蜜蜂通過跳舞和嗅氣味等方式向同伴傳達蜜源地的信息、筑巢或者采集花粉等活動,這種行為使蜂群能夠迅速找到優質的蜜源地。人工蜂群算法與其他算法相比,在求解多變量、多峰值的全局優化問題時具有更好的適應性和魯棒性[4]。

學界在土地資源優化領域的研究中引入了很多新的方法[5],這些方法雖然在一定程度上解決了土地資源優化模型的非動態、單目標性,但是仍存在諸多等缺點。文中從模擬生物(蜜蜂)對環境的適應性和能動性出發,設計了應用于土地資源優化的人工蜂群算法,試圖構建基于多目標的土地資源優化模型,解決ABC算法應用于土地資源優化的過早老化的問題和收斂速度慢等兩個難題[3],并以許昌市為例,運用文中模型,進行了許昌市多目標土地利用優化應用研究,獲得理想的效果。

1 人工蜂群算法

在人工蜂群算法中首先將蜜蜂分為偵察蜂、引領蜂和跟隨蜂3類。3類蜜蜂能夠根據各自的分工進行活動,并實現蜂群內部的信息共享和交流。偵查蜂的任務是在鄰域附近隨機搜索蜜源地,引領蜂則把已經搜索到的蜜源地的信息存儲起來,以概率的方式分享給其他蜜蜂;跟隨蜂在蜂巢附近等待引領蜂跳舞,并根據舞姿選擇最滿意的蜜蜂跟隨。這里蜜源的位置代表土地優化問題的可能解,蜜源的含蜜量表現為優化問題的適應度值。蜂群通過不斷地搜索,找到含蜜量更高的蜜源地,最終找到含蜜量最高的蜜源地,從而得到問題的最優解。文獻[1]給出了人工蜂群算法的主要步驟。

2 土地資源優化ABC算法的構造

2.1 蜜蜂的采蜜行為和土地資源優化問題對應關系

蜜蜂的采蜜行為和土地資源優化問題對應關系如表1所示。

表1 蜜蜂的采蜜行為和土地資源優化問題對應關系

2.2 土地資源優化的ABC算法構造

2.2.1 初始種群

初始化時,首先隨機產生優化配置方案,設方案個數為L(0),然后采用貪婪原則構造出優化配置方案的譯碼算子,并進行譯碼。將譯碼從高到低排名,其中前50%的方案作為候選土地資源優化方案。隨機產生一個可行解,形成初始種群。

2.2.2 適應度評估方法

在土地資源優化問題的ABC算法中,通過比較適應度衡量土地資源優化方案的質量。適應度通過由目標函數變換而成的適應度函數(Fitness Function)求取。根據問題的目標函數,求解最短路徑 d,則適應度函數為距離的倒數,Fitness=。路徑越長適應度越低,蜜源地被授予的可能性越小,被跟隨蜂選擇的概率就越低。

2.2.3 鄰域搜索策略的選擇

首先隨機生成含有n個解的初始種群V,V={vij},i=1,2,…,n;j=1,2,…,S;S為搜索空間的維數,vi={vij｜j=1,2,…,S}表示第i只蜜蜂所在的位置。然后計算蜂群中各偵查蜂的適應度函數值,記錄當前蜂群中的最大花蜜量及其蜜源位置。引領蜂根據記憶的信息在其鄰域附近進行搜索,產生新位置pi={pij｜j=1,2,…,S}:

其中k是i附近的一個值,且k≠i,φ是[-1,1]間的隨機數。為了加大算法的收斂性,參考文獻[6]更新蜜源地。

2.2.4 偵查蜂選擇新的蜜源地

搜索算法經過多次循環迭代,丟棄沒有靠近最優解的解,隨機產生新的解。當被丟棄的解是當前最優解時,隨機產生新解,計算新解的適應度并與原解的適應度比較,如果優于原解就替換,否則取原解并重新開始循環,這樣做即能保證當前的最優解不被丟棄,又避免了因放棄當前最優解造成的算法不收斂的情況,同時也沒有限制偵查蜂尋找新的蜜源地,達到了算法跳出局部最優解的目的,提高了算法的收斂速度。

2.2.5 算法的終止條件

算法采用最大循環代數作為結束條件,一般取50～500代,文中取100代。

2.2.6 算法步驟

(1)初始化土地利用網絡。首先設置初始參數:種群數、最大循環次數、引領蜂引領強度系數r、遺忘因子τ、鄰域因子η、蜂群數量Total,限制參數Lim等,其中采蜜蜂和觀察蜂各占50%,偵察蜂1個;

(2)隨機產生種群L(0);

(3)偵查蜂搜索蜜源地,計算群體的初始適應度,循環開始;

(4)偵查蜂分享蜜源地信息,按式(1)選擇其中一個蜜源地,按文獻[6]方法進行鄰域搜索算法尋找新的蜜源地;

(5)計算新蜜源地的適應度值,依據貪婪原則選擇更優的蜜源地;

(6)判斷是否滿足種群約束條件,如果滿足約束條件則計算種群的整體適應度(個體適應度之和),否則重新分配不滿足約束條件的蜜源地,并重新計算種群的整體適應度;判斷整體適應度是否發生變化,如果變化就返回(4);否則結束算法,存儲此最優解;

(7)循環次數加1;

(8)滿足終止條件,達到最大循環次數。

3 實例仿真

為了驗證算法的有效性,以許昌市土地資源優化為例,整理已有的土地利用數據,把研究區域的土地利用類型分為居住用地、商業用地、工業用地、可耕地等4種類型。仿真實驗的系統環境為CUP雙核3.20G,內存4GB,軟件環境為Delphi 2010,選取了3個基準函數進行對比測試[7]。

3.1 實驗參數的設置

實驗中種群個數設置為50,引領蜂和跟隨蜂的個數均為25,測試函數分別取30維、50維,相應的最大迭代次數分別為 1000和2000,α∈[0.8,1],β∈[1,1.2]之間,蜂群數量 50,其中采蜜蜂和觀察蜂各占50%,偵察蜂1個,限制參數Limit為50,針對每個測試函數各算法均隨機運行30次求其平均值。

3.2 測試函數的選擇

在仿真實驗中,選擇了Sphere函數、Rosenbrock函數和Penalized函數這3個測試函數,其定義如下:

(1)Sphere函數

f1(x)=測試結果如圖1所示。

(2)Rosenbrock函數

f2(x)=測試結果如圖2所示。

(3)Rastrigin函數

f3(x)=測試結果如圖3所示。

圖1 Sphere測試函數

圖2 Rosenbrock測試函數

圖3 Rastingin測試函數

上述3個測試函數中,f1(x)是單峰連續函數,f2(x)是一個經典的復雜優化問題,取值范圍內走勢平坦,只能為算法提供少量的信息,要達到全局最優點的機會很小,f1(x)、f2(x)常用于檢驗算法收斂速度。函數 f3(x)是復雜非線性多峰函數,具有許多局部極值點,可有效檢驗算法的全局搜索的性能和避免早熟的能力。

3.3 實驗結果分析

3.3.1 尋找最優解的迭代次數

圖4是文獻[5]的適應度函數,與圖1、圖2和圖3比較可以看出,在相同迭代次數下,人工蜂群算法比文獻[5] 算法表現更出色。

3.3.2 收斂率

收斂率是指優化算法找到全局最優解的概率。收斂率越高,優化算法越容易找到全局最優解,算法的優化性好。以50維的實驗結果為例,在固定的進化情況下,文中算法的收斂速度快,收斂率高于文獻[4]算法,其運行效率比文獻[5]的提高了25%,總體適應度提高了8.9%,最大誤差不超過1%,短中期優化精度吻合更好,可以為政府和城市規劃工作者制定用地政策提供定量的輔助決策依據。

3.3.3 優化結果

圖5(a)是許昌市2005年上述4類用地的空間分布格局,圖5(b)是許昌市2010年優化后的空間分布格局。對比可以看出:優化后的居民用地整體上分布更加集中,土地利用斑塊內部的空地減少,城市近郊的零星土地利用斑塊也有所減少,同類土地利用的空間集聚度增高,新增城市用地的增長方式大多是內部填充式的,避免了城市用地的進一步擴張。

圖4 文獻[5]的適應度函數

圖5 優化配置前后許昌市土地利用空間格局比較圖

由分析結果可以看出,隨著“工業許昌”的建設,可耕地總量下降是必然的。鑒于許昌的自然環境和經濟能力,實現耕地使用平衡的難度很大,因此,優化模型得出的短中期優化值將更接近許昌市未來的真實情況,遠期優化值則僅具參考意義。

4 結束語

把人工蜂群算法應用于土地資源優化,構建了基于ABC算法的土地利用優化配置模型;解決了ABC算法應用于目標優化的兩個難題:收斂速度慢的問題和過早老化的問題;以許昌市土地資源優化為例,驗證了本算法的應用。結果表明:優化模型得到的土地利用格局、算法的適應度和收斂速度的均有明顯提高。

[1] 鄭偉,劉靜,曾建潮.人工蜂群算法及其在組合優化中的應用研究[J].太原科技大學學報,2010,31(6):467-471.

[2] 張國有,曾建潮.基于黃蜂群算法的群機器人全區域覆蓋算法[J].模式識別與人工智能,2011,24(3):431-438.

[3] Karaboga D,Basturk B.On the performance of artificial bee colony(ABC)algorithm[J].Applied Soft Computing,2008,8(1):687-697.

[4] Ligmarm-Zielinska A,Church R,Jankowski E.Spatial optimization as a generative technique for sustainable multi objective land-use allocation[J].International Journal of Geographical Information Science,2008,22(6):601-622.

[5] 張鴻輝,曾永年,劉慧敏.多目標土地利用空間優化配置模型及其應用[J].中南大學學報,2011,42(4):1056-1067.

[6] 王輝.改進的蜂群算法[J].計算機工程與設計,2011,32,(11):3869-3873.

[7] 胡珂,李迅波,王振林.改進的人工蜂群算法性能[J].計算機應用,2011,31(4):1107-1111.