種群規(guī)模對蝙蝠算法性能的影響

郭小雪,賀興時,羅 東

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

0 引 言

蝙蝠算法(BA)[1]是楊新社教授于2010年基于群體智能[2]提出的一種啟發(fā)式搜索算法。目前,BA作為一種新型的群智能優(yōu)化算法,已成功應(yīng)用于很多領(lǐng)域[3-6],但與其他群智能優(yōu)化算法一樣,也存在收斂速度慢、求解精度低的問題。因此，通過優(yōu)化算法性能,避免算法出現(xiàn)早熟現(xiàn)象,提高算法自身尋優(yōu)能力具有重要意義。

目前,蝙蝠算法的研究主要集中在算法的改進(jìn)以及參數(shù)的設(shè)置。在算法改進(jìn)方面,學(xué)者們分別從對蝙蝠個體進(jìn)行不同變異，調(diào)整蝙蝠個體速度更新策略以及在蝙蝠學(xué)習(xí)機(jī)制中引入權(quán)重策略等不同角度對BA的性能進(jìn)行了優(yōu)化改進(jìn),提高了BA的求解精度和收斂速度。 這些研究[7-9]中種群規(guī)模的設(shè)置分別為50,40和30,對種群規(guī)模大小的選擇缺乏理論指導(dǎo)。

在參數(shù)設(shè)置方面,文獻(xiàn)[10-13]分別從影響蝙蝠音量和脈沖發(fā)生率變化的參數(shù),速度和位置的相關(guān)算子以及慣性權(quán)重的值三方面分析了不同參數(shù)對BA性能的影響,并得到最優(yōu)參數(shù),提高了BA的性能。但是，這些研究均忽略了種群規(guī)模對BA收斂速度和求解精度的影響。本文將分別從算法收斂速度、求解精度、全局搜索能力[14]、收斂時間4個方面分析不同種群規(guī)模對BA的影響,并對所得結(jié)論進(jìn)行驗(yàn)證。

1 BA性能的評估指標(biāo)和種群規(guī)模

1.1 BA性能評估指標(biāo)

(1) 收斂速度 在數(shù)值分析中,收斂序列向其極限逼近的速度稱為收斂速度。用于最優(yōu)化算法中,被定義為一個迭代序列向其局部最優(yōu)值逼近(假設(shè)計(jì)算過程收斂,并能達(dá)到最優(yōu)值)的速度,是評價(jià)迭代法性能的一個重要指標(biāo)。

(2) 求解精度 收斂序列逼近其最優(yōu)值的程度,即表示算法尋得的最優(yōu)值與實(shí)際最優(yōu)值的接近程度。

(3) 全局搜索能力 算法獨(dú)立運(yùn)行M次,得到滿足算法收斂精度的解的總次數(shù)為N,則A=N/M表示全局搜索能力。

(4) 收斂時間 收斂序列逼近其最優(yōu)值或達(dá)到收斂精度的運(yùn)行時間。

1.2 種群規(guī)模

在原始蝙蝠算法中,種群規(guī)模[15]始終是固定不變的。不過，不同問題對種群規(guī)模選取有不同的需求,使得種群規(guī)模在一些問題的尋優(yōu)過程中表現(xiàn)的不合理。特別是蝙蝠算法在解決一些具有較大群體規(guī)模的實(shí)際問題時,需要對很多個體進(jìn)行適應(yīng)度值的計(jì)算和評估,導(dǎo)致算法的迭代過程運(yùn)行緩慢,很難達(dá)到預(yù)想中的尋優(yōu)效果。

種群規(guī)模是蝙蝠算法的一個重要參數(shù),對算法的尋優(yōu)能力和求解精度有較大影響。如果選取的種群規(guī)模較大,算法會以更大的可能性搜索到全局最優(yōu)解;如果選取的種群規(guī)模較小,會導(dǎo)致搜索范圍減小,算法在短時間內(nèi)很難收斂到全局最優(yōu)解。

為了分析不同種群規(guī)模對蝙蝠算法性能的影響,本文采用具有代表性的單峰函數(shù)(Zakharov函數(shù))和多峰函數(shù)(Ackley函數(shù))分析種群規(guī)模對算法收斂速度、求解精度、全局搜索能力的影響以及種群規(guī)模對單峰函數(shù)(Zakharov函數(shù)和Sphere函數(shù))收斂時間的影響。

2 仿真實(shí)驗(yàn)

算法參數(shù)設(shè)置如下:α=β=0.9,響度A在[1,2]之間初始化,脈沖發(fā)射率R在[0,1]初始化。 Ackley函數(shù)、Zakharov函數(shù)和Sphere函數(shù)的最大迭代次數(shù)分別設(shè)置為1 000次、100次和1 000次。測試函數(shù)及迭代結(jié)果見表1。

表 1 測試函數(shù)

2.1 種群規(guī)模對算法收斂速度和求解精度的影響

在分析種群規(guī)模對算法收斂速度和求解精度的影響時,固定最大迭代次數(shù)不變,依次增大種群規(guī)模,觀察收斂速度和求解精度隨著種群規(guī)模不斷增大的變化。 為了分析不同維度下種群規(guī)模對算法搜索精度的影響,將問題維度設(shè)置為30，60，100和200等4種情況。對于求解單峰函數(shù)(Zakharov函數(shù))問題,算法的種群規(guī)模設(shè)置為20，50，100，200和500等5種規(guī)格,共20種組合,每一種組合算法獨(dú)立運(yùn)行50次并取其均值；對于求解多峰函數(shù)(Ackley函數(shù))問題,算法的種群規(guī)模設(shè)置為50，100，200，300，400和500等6種規(guī)格,共24種組合,每一種組合算法獨(dú)立運(yùn)行50次并取其均值。圖1為Ackley和Zakharov函數(shù)種群規(guī)模和收斂速度的關(guān)系,表2和表3分別為Zakharov和Ackley函數(shù)種群規(guī)模與算法求解精度的關(guān)系。

表 2 Zakharov函數(shù)種群規(guī)模與算法求解精度的關(guān)系

注：最優(yōu)解為0。

表 3 Ackley函數(shù)種群規(guī)模與算法求解精度的關(guān)系

注：最優(yōu)解為0。

(a) Ackley

(b) Zakharovarov圖 1 種群規(guī)模和收斂速度的關(guān)系

從圖1可以看出,對于求解Zakharov函數(shù)和Ackley函數(shù)問題,算法的收斂速度都是隨著種群規(guī)模的增大而加快。但是，不同的函數(shù)具有不同的下降速率曲線,下降速率曲線呈波動型下降,而非嚴(yán)格遞減。 對于Zakharov函數(shù)問題,當(dāng)種群規(guī)模大于50時,算法的收斂速度對種群規(guī)模不敏感；對于Ackley函數(shù)問題,當(dāng)種群規(guī)模大于100時,算法的收斂速度對種群規(guī)模不敏感。

由表2和表3可以看出,當(dāng)維度固定時,無論求解單峰函數(shù)問題還是多峰函數(shù)問題,隨著種群規(guī)模的不斷增大,蝙蝠算法的搜索精度不斷提高;當(dāng)種群規(guī)模固定時,隨著維度的增加,算法的求解精度無明顯變化規(guī)律,說明維度對算法的搜索精度影響不大。同時可以看出,對于Zakharov函數(shù)問題,在維度一定時,當(dāng)種群規(guī)模大于100,算法的搜索精度的變化不大;對于Ackley函數(shù)問題,當(dāng)種群規(guī)模大于300時,算法的搜索精度趨于穩(wěn)定。

2.2 種群規(guī)模對算法全局搜索能力的影響

從圖2可以看出,當(dāng)種群規(guī)模增大時,不論是求解Zakharov函數(shù)問題還是Ackley函數(shù)問題,蝙蝠算法的全局搜索能力均有所提高。但是，當(dāng)種群規(guī)模達(dá)到一定值后,全局搜索能力趨于穩(wěn)定值1,即算法獨(dú)立運(yùn)行的總次數(shù)和滿足算法收斂精度的解的次數(shù)相等。

(a) Ackley

(b) Zakharov圖 2 種群規(guī)模與全局收斂能力的關(guān)系

2.3 種群規(guī)模對算法收斂時間的影響

在分析不同種群規(guī)模與算法收斂時間的關(guān)系時,設(shè)置收斂精度一定,運(yùn)行程序,記錄算法滿足該收斂精度所需的運(yùn)行時間。由于多峰函數(shù)大多有局部極值,容易陷入局部最優(yōu),難以計(jì)算其收斂時間,因此僅分析具有代表性的單峰函數(shù)的收斂時間。選取Zakharov和Sphere 2種單峰函數(shù)，分析種群規(guī)模與算法收斂時間的關(guān)系，結(jié)果見表4。

由表4可以看出,對于Zakharov函數(shù)問題,當(dāng)維度固定時,隨著種群規(guī)模的擴(kuò)大,算法的收斂時間逐漸減小;當(dāng)種群規(guī)模達(dá)到100時,算法的收斂時間隨著種群規(guī)模的擴(kuò)大開始遞增。當(dāng)種群規(guī)模固定時,算法的收斂時間隨著維度的增加不斷變大。 對于Sphere函數(shù)問題,當(dāng)維度固定時,算法的收斂時間隨著種群規(guī)模的增大而增加;當(dāng)種群規(guī)模固定時,隨著問題維度的增加算法收斂時間也變大。

在尋找問題的最優(yōu)解時,若側(cè)重加快收斂速度,則求解Zakharov函數(shù)問題時算法的種群規(guī)?？稍O(shè)為50左右,求解Ackley函數(shù)問題時算法的種群規(guī)?？稍O(shè)為100左右；若側(cè)重提高搜索精度,則求解Zakharov函數(shù)和Ackley函數(shù)問題時算法的種群規(guī)?？煞謩e設(shè)為100和300;若側(cè)重增強(qiáng)全局搜索能力,則求解Zakharov函數(shù)問題時算法的種群規(guī)?？稍O(shè)為50左右,求解Ackley函數(shù)問題時算法的種群規(guī)?？稍O(shè)為100左右。若側(cè)重減小運(yùn)行時間,則求解Sphere和Zakharov函數(shù)問題時算法的種群規(guī)模可設(shè)為50～100。

表4Zakharov及Sphere函數(shù)種群規(guī)模與算法收斂時間的關(guān)系

Table 4 The relationship between population size and algorithm convergence time of Zakharov and Sphere functions

在評估算法性能時,應(yīng)綜合考慮影響算法性能的4個因素,不應(yīng)只考慮其中一種因素,即應(yīng)取以上4個種群規(guī)模的均值,才能更準(zhǔn)確的評估算法的性能。對于求解單峰和多峰函數(shù)問題,算法的種群規(guī)模應(yīng)分別設(shè)為70和170左右。

2.4 T檢驗(yàn)

T檢驗(yàn)主要用于樣本含量較小,總體標(biāo)準(zhǔn)差σ未知的正態(tài)分布,是用t分布理論來推論差異發(fā)生的概率,從而比較兩樣本均值的差異是否顯著。 T檢驗(yàn)分為3種方法:單一樣本T檢驗(yàn)、配對樣本T檢驗(yàn)和獨(dú)立樣本T檢驗(yàn)。 本文使用獨(dú)立樣本T檢驗(yàn),用于觀察兩組數(shù)據(jù)的平均值有無差異。

為了驗(yàn)證所得結(jié)論的準(zhǔn)確性,對表1中的4個單峰函數(shù)和4個多峰函數(shù)在種群規(guī)模分別為40，70及40，170等2種情況下進(jìn)行仿真測試，并假設(shè)原始蝙蝠算法種群規(guī)模為40。分別獨(dú)立運(yùn)行100次,這樣在每個測試函數(shù)問題上,2種種群規(guī)模下算法均有100個樣本；取其均值,利用T檢驗(yàn)法比較分析2種種群規(guī)模下算法的性能。結(jié)果表明,這8個函數(shù)在種群規(guī)模分別為70和170時算法的性能最好。

3 結(jié) 語

分析不同種群規(guī)模對蝙蝠算法性能的影響,選用3個基本測試函數(shù)進(jìn)行仿真實(shí)驗(yàn),結(jié)果表明,種群規(guī)模對蝙蝠算法性能有顯著影響。利用8個測試函數(shù)對結(jié)論進(jìn)行驗(yàn)證,結(jié)果表明在單峰和多峰問題上,種群規(guī)模選取為70和170時算法的性能優(yōu)于種群規(guī)模為40時算法的性能。