張泊平, 吳國(guó)璽

(1.許昌學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南許昌461000;2.許昌學(xué)院城市與環(huán)境學(xué)院,河南許昌461000)

0 引言

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

學(xué)界在土地資源優(yōu)化領(lǐng)域的研究中引入了很多新的方法[5],這些方法雖然在一定程度上解決了土地資源優(yōu)化模型的非動(dòng)態(tài)、單目標(biāo)性,但是仍存在諸多等缺點(diǎn)。文中從模擬生物(蜜蜂)對(duì)環(huán)境的適應(yīng)性和能動(dòng)性出發(fā),設(shè)計(jì)了應(yīng)用于土地資源優(yōu)化的人工蜂群算法,試圖構(gòu)建基于多目標(biāo)的土地資源優(yōu)化模型,解決ABC算法應(yīng)用于土地資源優(yōu)化的過(guò)早老化的問(wèn)題和收斂速度慢等兩個(gè)難題[3],并以許昌市為例,運(yùn)用文中模型,進(jìn)行了許昌市多目標(biāo)土地利用優(yōu)化應(yīng)用研究,獲得理想的效果。

1 人工蜂群算法

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

2 土地資源優(yōu)化ABC算法的構(gòu)造

2.1 蜜蜂的采蜜行為和土地資源優(yōu)化問(wèn)題對(duì)應(yīng)關(guān)系

蜜蜂的采蜜行為和土地資源優(yōu)化問(wèn)題對(duì)應(yīng)關(guān)系如表1所示。

表1 蜜蜂的采蜜行為和土地資源優(yōu)化問(wèn)題對(duì)應(yīng)關(guān)系

2.2 土地資源優(yōu)化的ABC算法構(gòu)造

2.2.1 初始種群

初始化時(shí),首先隨機(jī)產(chǎn)生優(yōu)化配置方案,設(shè)方案?jìng)€(gè)數(shù)為L(zhǎng)(0),然后采用貪婪原則構(gòu)造出優(yōu)化配置方案的譯碼算子,并進(jìn)行譯碼。將譯碼從高到低排名,其中前50%的方案作為候選土地資源優(yōu)化方案。隨機(jī)產(chǎn)生一個(gè)可行解,形成初始種群。

2.2.2 適應(yīng)度評(píng)估方法

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

2.2.3 鄰域搜索策略的選擇

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

其中k是i附近的一個(gè)值,且k≠i,φ是[-1,1]間的隨機(jī)數(shù)。為了加大算法的收斂性,參考文獻(xiàn)[6]更新蜜源地。

2.2.4 偵查蜂選擇新的蜜源地

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

2.2.5 算法的終止條件

算法采用最大循環(huán)代數(shù)作為結(jié)束條件,一般取50～500代,文中取100代。

2.2.6 算法步驟

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

(2)隨機(jī)產(chǎn)生種群L(0);

(3)偵查蜂搜索蜜源地,計(jì)算群體的初始適應(yīng)度,循環(huán)開(kāi)始;

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

(5)計(jì)算新蜜源地的適應(yīng)度值,依據(jù)貪婪原則選擇更優(yōu)的蜜源地;

(6)判斷是否滿足種群約束條件,如果滿足約束條件則計(jì)算種群的整體適應(yīng)度(個(gè)體適應(yīng)度之和),否則重新分配不滿足約束條件的蜜源地,并重新計(jì)算種群的整體適應(yīng)度;判斷整體適應(yīng)度是否發(fā)生變化,如果變化就返回(4);否則結(jié)束算法,存儲(chǔ)此最優(yōu)解;

(7)循環(huán)次數(shù)加1;

(8)滿足終止條件,達(dá)到最大循環(huán)次數(shù)。

3 實(shí)例仿真

為了驗(yàn)證算法的有效性,以許昌市土地資源優(yōu)化為例,整理已有的土地利用數(shù)據(jù),把研究區(qū)域的土地利用類型分為居住用地、商業(yè)用地、工業(yè)用地、可耕地等4種類型。仿真實(shí)驗(yàn)的系統(tǒng)環(huán)境為CUP雙核3.20G,內(nèi)存4GB,軟件環(huán)境為Delphi 2010,選取了3個(gè)基準(zhǔn)函數(shù)進(jìn)行對(duì)比測(cè)試[7]。

3.1 實(shí)驗(yàn)參數(shù)的設(shè)置

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

3.2 測(cè)試函數(shù)的選擇

在仿真實(shí)驗(yàn)中,選擇了Sphere函數(shù)、Rosenbrock函數(shù)和Penalized函數(shù)這3個(gè)測(cè)試函數(shù),其定義如下:

(1)Sphere函數(shù)

f1(x)=測(cè)試結(jié)果如圖1所示。

(2)Rosenbrock函數(shù)

f2(x)=測(cè)試結(jié)果如圖2所示。

(3)Rastrigin函數(shù)

f3(x)=測(cè)試結(jié)果如圖3所示。

圖1 Sphere測(cè)試函數(shù)

圖2 Rosenbrock測(cè)試函數(shù)

圖3 Rastingin測(cè)試函數(shù)

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

3.3 實(shí)驗(yàn)結(jié)果分析

3.3.1 尋找最優(yōu)解的迭代次數(shù)

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

3.3.2 收斂率

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

3.3.3 優(yōu)化結(jié)果

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

圖4 文獻(xiàn)[5]的適應(yīng)度函數(shù)

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

由分析結(jié)果可以看出,隨著“工業(yè)許昌”的建設(shè),可耕地總量下降是必然的。鑒于許昌的自然環(huán)境和經(jīng)濟(jì)能力,實(shí)現(xiàn)耕地使用平衡的難度很大,因此,優(yōu)化模型得出的短中期優(yōu)化值將更接近許昌市未來(lái)的真實(shí)情況,遠(yuǎn)期優(yōu)化值則僅具參考意義。

4 結(jié)束語(yǔ)

把人工蜂群算法應(yīng)用于土地資源優(yōu)化,構(gòu)建了基于ABC算法的土地利用優(yōu)化配置模型;解決了ABC算法應(yīng)用于目標(biāo)優(yōu)化的兩個(gè)難題:收斂速度慢的問(wèn)題和過(guò)早老化的問(wèn)題;以許昌市土地資源優(yōu)化為例,驗(yàn)證了本算法的應(yīng)用。結(jié)果表明:優(yōu)化模型得到的土地利用格局、算法的適應(yīng)度和收斂速度的均有明顯提高。

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

[2] 張國(guó)有,曾建潮.基于黃蜂群算法的群機(jī)器人全區(qū)域覆蓋算法[J].模式識(shí)別與人工智能,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] 張鴻輝,曾永年,劉慧敏.多目標(biāo)土地利用空間優(yōu)化配置模型及其應(yīng)用[J].中南大學(xué)學(xué)報(bào),2011,42(4):1056-1067.

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

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