一種帶局部搜索功能的入侵雜草優(yōu)化算法*

劉 挺， 王聯(lián)國

(甘肅農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院，甘肅 蘭州 730070)

0 引 言

雜草具有生命力強、生長旺盛以及繁殖力強等特征，受雜草繁殖思想的啟發(fā)，Mehrabian A R和Lucas C于2006年針對雜草具有入侵性繁殖的這一特點進行研究，提出了一種入侵雜草優(yōu)化[1](invasive weed optimization,IWO)算法。作為一種兼顧了繁殖、擴散以及競爭等特征的智能優(yōu)化算法，IWO算法已經(jīng)成功應(yīng)用于DNA序列的編碼[2]、電力市場的動態(tài)分析[3]、魯棒性控制器的調(diào)優(yōu)[1]等問題。

然而,IWO算法存在著后期尋優(yōu)精度低、易陷入局部最優(yōu)等問題，明顯制約了IWO的應(yīng)用范圍。針對以上這些問題，很多學(xué)者采取了不同的改進策略，使得IWO算法的性能得到了明顯的提高[4～6]。

本文將球體局部搜索算子和Logistic映射搜索算子引入IWO算法，提出了一種帶局部搜索功能的雜草優(yōu)化(LSIWO)算法，通過仿真實驗，驗證了該算法具有良好的尋優(yōu)性能。

1 基本IWO算法

基本IWO算法的流程模仿了雜草的入侵過程，分為種群初始化、生長繁殖、空間擴散和競爭排斥4個階段。

1)種群初始化

在本階段中主要完成了算法參數(shù)的初始化操作，與其他算法不同，當(dāng)IWO確定了最大種群規(guī)模Pmax以后，算法僅在解空間內(nèi)對一小部分初始個體P0進行操作(P0

2)生長繁殖

根據(jù)適應(yīng)度值大小比例生成種子，給予適應(yīng)度較高的個體產(chǎn)生更多種子的機會，每個個體所產(chǎn)生的種子數(shù)目為

(1)

式中SNum為個體生成種子的數(shù)目，fi為第i個個體的適應(yīng)度值，fmax，fmin分別為種群當(dāng)前最大和最小的適應(yīng)度值，Seedmax，Seedmin分別為個體能生成的最大種子和最小種子數(shù)。

3)空間擴散

生成的種子是以正態(tài)分布的形式在父輩雜草周圍擴散的,公式實現(xiàn)為

(2)

式中δi為當(dāng)前的標準差,Itermax為最大迭代次數(shù)，Iter為當(dāng)前的迭代次數(shù)，δini,δfin分別為初始時的標準差和結(jié)束時的標準差， 為非線性調(diào)和指數(shù)。

4)競爭排斥

算法經(jīng)過一定代繁殖擴散后種群數(shù)量會達到最大規(guī)模Pmax，此時，將生成的種子連同原本的雜草個體一并按照其適應(yīng)度值優(yōu)劣進行排序，選取適應(yīng)度值較好的前Pmax個個體，其余的個體淘汰。

2 LSIWO算法

2.1 基于柯西分布擴展鄰域的球體局部搜索算子

對于個體進行鄰域搜索時，采用基于柯西分布的擴展鄰域策略，一定條件下擴展到最大鄰域[7]。

定義1[8]以球心為A,半徑大小為R1，在D維空間中產(chǎn)生球體C(A,R1),存在一點B，滿足B到球心A的距離小于半徑R1(即‖B-A‖

首先，以半徑為R1，球心為A初始球體，對球體C(A,R1)開展局部搜索，然后，保持球心位置不變，按照式(3)對半徑進行擴展

Ri=R1×(1+λCauchy(α,β)).

(3)

其中,i∈{1,2,…，N},為擴展半徑的次數(shù),這里i的初始值為1;λ為調(diào)整因子，取值為常數(shù);R1為球體的初始搜索半徑;Ri為第i次搜索時球體的半徑;Cauchy為柯西分布函數(shù)。球體局部搜索過程見圖1。

圖1 球體局部搜索過程

球體局部搜索算子流程：

1)初始化待改進個體位置，并計算其適應(yīng)度值。

2)將改進個體A為球心，R1為半徑生成一個空間球體C(A,R1)，在搜索鄰域C(A,R1)內(nèi)產(chǎn)生V個隨機點，并計算這些隨機點的適應(yīng)度值，若存在適應(yīng)度值優(yōu)于A的個體B，用個體B代替A；否則，轉(zhuǎn)步驟(3)。

3)將半徑R1以公式 (3)擴展，重復(fù)步驟(2)繼續(xù)搜索，若經(jīng)過i次半徑擴展后仍未能找到適應(yīng)度值優(yōu)于A的點，則將個體A返回;否則，用找到適應(yīng)度最佳的個體替換A。

2.2 Logistic映射搜索算子

一維Logistic映射在數(shù)學(xué)角度上雖然是一個非常簡單的混沌映射[9],數(shù)學(xué)模型為

Xn+1=f(Xn)=μXn(1-Xn).

(4)

其中，Xn為狀態(tài)量，μ∈[0,4]為系統(tǒng)控制參數(shù)，Xn+1為生成的對象,當(dāng)Xn∈[0,1]時系統(tǒng)處于混沌狀態(tài)。

Logistic搜索策略：

1)利用式(5)將G投影到[0,1]范圍內(nèi),其中，Upnd,Dond分別為搜索空間的上界與下界

(5)

2)將G′利用式(4)所示的Logistic映射公式迭代10次產(chǎn)生一組混沌序列y=[y1,y2,y3,…,y10]。

3)將產(chǎn)生的混沌序列y通過式(6)投影回原來的搜索空間

(6)

2.3 局部搜索功能的雜草優(yōu)化算法流程

由于單一的局部搜索算子局限性很大，易陷入局部最優(yōu)，因此,在基本入侵雜草算法的基礎(chǔ)上，根據(jù)一定概率對每一代的最優(yōu)個體執(zhí)行兩種不同的搜索算子，搜尋優(yōu)于該個體較優(yōu)個體，算法流程如下：

1)在D維空間內(nèi)初始化P0,Pmax,δini,δfin,Seedmax,Seedmin等相關(guān)參數(shù)。

2)判斷算法是否達到終止條件,若達到，輸出最優(yōu)解；否則，執(zhí)行步驟(3)。

3)計算種群中的每個個體的適應(yīng)度值。

4)對于種群中的每個個體按照公式(1)產(chǎn)生相應(yīng)的種子。

6)判斷新種群是否達到了最大種群數(shù)目Pmax，若達到了則執(zhí)行步驟(7);否則，執(zhí)行步驟(8)。

7)將新種群中的個體按照適應(yīng)度值大小進行排序，選擇適應(yīng)度較好的前Pmax個個體。

8)產(chǎn)生隨機概率θ，若θ>0.7,則對每代最優(yōu)個體執(zhí)行球體局部搜索算子；否則,執(zhí)行Logistic搜索算子，轉(zhuǎn)步驟(2)。

3 仿真實驗與結(jié)果分析

3.1 實驗參數(shù)設(shè)置

在實驗中，設(shè)置雜草數(shù)目P0為5株，最大種群規(guī)模為10，設(shè)置初始標準差δini為UD/3(UD為搜索的上界)，終止標準差δfin取為0.05，種子的最大生成數(shù)Seedmax與最小生成數(shù)Seedmin分別為15和0。球體搜索時初始的搜索半徑R1為0.1，并且經(jīng)過多次實驗最終將每次球體搜索生成的點數(shù)設(shè)為V=5，算子選擇概率θ=0.7時實驗效果最佳。

3.2 實驗結(jié)果

用IWO算法，文獻[10]中的CMIWO算法和本文LSIWO算法分別對7個測試函數(shù)的最小值進行優(yōu)化，其中，f1～f4是單峰函數(shù)，f5～f7是多峰函數(shù)，具體函數(shù)和參數(shù)見表1。最終測試結(jié)果采用獨立運行50次后的平均值，實驗結(jié)果見表2。圖2(a)～(g)為3種算法對函數(shù)f1～f7經(jīng)過200次迭代的適應(yīng)度進化曲線。

圖2 f1～f7函數(shù)適應(yīng)度進化曲線

表1 測試函數(shù)

表2 7個函數(shù)的實驗結(jié)果

3.3 實驗結(jié)果分析

由表2可知，LSIWO算法的最優(yōu)值、最差值、平均數(shù)和標準差總體優(yōu)于其他2種算法。對于單峰函數(shù)f1～f4,其中函數(shù)f1,f3，LSIWO算法所找到的最優(yōu)值與CMIWO的最優(yōu)值處于同一個數(shù)量級，其他指標LSIWO算法則都明顯優(yōu)于其他2種被比較算法1～5個數(shù)量級。在多峰函數(shù)f5～f7的優(yōu)化上，除了對函數(shù)f6優(yōu)化時,CMIWO與LSIWO算法的平均值處在同一個數(shù)量級以外，其他各項指標LSIWO分別好于被比較的2種算法1～7個數(shù)量級。由此可以看出：LSIWO算法的尋優(yōu)精度更高，穩(wěn)定性更強。

圖2(a)～(g)描述了在迭代次數(shù)為200時，3種算法對于7個測試函數(shù)的適應(yīng)度進化曲線，總體上看，LSIWO算法的搜索能力和尋優(yōu)精度都較其他2種算法更強。但是對于函數(shù)f1,f2,f3,LSIWO算法后期的收斂速度減慢，這是由于算法中加入了局部搜索算子的原因。

4 結(jié)束語

本文在IWO算法的基礎(chǔ)上，按照一定概率對每代最優(yōu)個體執(zhí)行了球體局部搜索算子和Logistic搜索算子，搜索最優(yōu)個體周圍較優(yōu)的個體，引導(dǎo)種群向更好的方向發(fā)展。仿真表明:該算法尋優(yōu)能力、尋優(yōu)精度和穩(wěn)定性方面都有了明顯的提高。但是由于局部搜索算子的介入，算法的后期收斂速度有所降低，這將成為以后待解決的一個問題。

參考文獻:

[1] Mehrabian A R,Lucas C.A novel numerical optimization algorithm inspired from weed colonization[J].Ecological Informatics,2006,1(4):355-366.

[2] Zhang X,Wang Y,Cui G,et al.Application of a novel IWO to the design of encoding sequences for DNA computing[J].Computers and Mathematics with Applications,2009,57(11/12):2001-2008.

[3] Sahraei Ardakani M,Roshanaei M,Rahimi Kian A.A study of electricity market dynamics using invasive weed optimization[C]∥IEEE Symposium on Computational Intelligence and Games,Piscataway:Perth,Australia:IEEE,2008:276-282.

[4] Zhang Xuncai,Xu Jin,Guangzhao,et al.Research on invasive weed optimization based on the cultural framework[C]∥Proceedings of the 3rd International Conference on Bio-inspired Computing，Piscataway:IEEE,2008:129-134.

[5] Hajimirsadeghi H,Lucas.A hybrid IWO/PSO algorithm for fast and global optimization [C]∥IEEE EUROCON,Piscataway:IEEE,2009:1964-1971.

[6] Zhang Xuncai,Niu Ying,Gui Guanzhao,et al.A modified invasive weed optimization with crossover operation [C]∥Proceeding of the 8th World Congress on Intelligent Control and Automation,Piscataway:IEEE,2010:11-14.

[7] 魏 臻,吳 雷,葛方振,等.基于Memetic框架的混合粒子群算法[J].模式識別與人工智能,2012,25(2):213-219.

[8] Rachid C,Patrick S.Tabu search applied to global optimization[J].European Journal of Operational Research,2000,123(2):256-270.

[9] 李 兵，蔣慰孫.混沌優(yōu)化方法及其應(yīng)用[J].控制理論與應(yīng)用，1997,14(4):613-615.

[10] 陳 歡,周永權(quán),趙光偉.基于混沌序列的多種群入侵雜草算法[J].計算機應(yīng)用,2012,32(7):1958-1961.