張曉琪, 胡 振, 唐天國

(南充職業(yè)技術(shù)學(xué)院 信息與管理工程系,南充 637131)

蝙蝠算法(Bat Algorithm,BA)是劍橋大學(xué)的Xin-She Yang基于蝙蝠的回聲定位特性提出的一種群體智能搜索算法[1],它完美結(jié)合了現(xiàn)有成功算法的主要優(yōu)點(diǎn)[2],具有模型簡單、求解效率高、潛在并行性和分布式等特點(diǎn)[3,4],其準(zhǔn)確性和有效性優(yōu)于遺傳算法(Genetic Algorithm,GA)、粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法等經(jīng)典算法[5,6],已被應(yīng)用于多個學(xué)科和工程領(lǐng)域[7-9]. 但BA沒有變異機(jī)制,難以保持種群的多樣性,容易陷入局部最優(yōu)而發(fā)生早熟收斂,致使求解精度較低; 它比PSO算法加強(qiáng)了局部搜索,卻也引起了后期收斂速度變慢的問題. 為了改善性能,已研究出各種進(jìn)化的、有效的變種蝙蝠算法[10],如： 劉長平等通過引入邏輯自映射函數(shù)改進(jìn)局部搜索能力,提出了一種具有混沌搜索策略的蝙蝠優(yōu)化算法[3,6]; 肖輝輝等將差分進(jìn)化(Differential Evolution,DE)算法的變異、交叉和選擇機(jī)制融合到基本蝙蝠算法中,增強(qiáng)了種群的多樣性、全局尋優(yōu)能力和搜索能力,形成了一種基于算法改進(jìn)的蝙蝠算法[4]; 薛威力等通過動態(tài)調(diào)整參數(shù)和高斯擾動避免陷入局部最優(yōu),提出了一種基于方差改進(jìn)的蝙蝠算法[10]. 這些改進(jìn)策略能夠增強(qiáng)全局尋優(yōu)能力、提高求解精度,但同時對算法的簡捷性和運(yùn)行效率帶來了不利影響.

本文提出一種基于權(quán)重因子、Cauchy分布隨機(jī)數(shù)擾動和非線性規(guī)劃的改進(jìn)蝙蝠算法,并將其應(yīng)用于模糊層次分析中的判斷矩陣一致性修正與因素權(quán)重計(jì)算,取得了較為滿意的結(jié)果.

1 蝙蝠算法及其改進(jìn)

1.1 基本蝙蝠算法

1.1.1 蝙蝠算法的仿生原理

BA是模擬自然界中蝙蝠利用超聲波來探測獵物、繞過障礙物的一種隨機(jī)搜索算法： 設(shè)有若干蝙蝠構(gòu)成群體,其個體映射為多維空間中的可行解,將搜索最優(yōu)解的過程模擬成蝙蝠個體移動和搜尋獵物過程;利用求解問題的適應(yīng)度函數(shù)值衡量蝙蝠所處位置的優(yōu)劣,將個體的優(yōu)勝劣汰過程類比為優(yōu)化過程中以較優(yōu)的可行解替代較差可行解的迭代過程.

1.1.2 蝙蝠行為與算法描述

將蝙蝠的回聲定位行為按如下規(guī)則理想化：

(1) 所有蝙蝠利用超聲波回音的感覺差異來區(qū)分食物/獵物和障礙物.

(2) 每只蝙蝠以速度vi、固定頻率fmin(或波長λ)在位置xi(問題的解)隨機(jī)飛行. 在搜索獵物時,它們根據(jù)目標(biāo)的遠(yuǎn)近調(diào)整波長λ(或頻率f)、響度A和脈沖發(fā)射率r∈[0,1].

(3) 響度A從最大值A(chǔ)0(正數(shù))以一定方式衰減到最小值A(chǔ)min.

對于求解非線性最小值函數(shù)minfx,設(shè)蝙蝠群體規(guī)模為n,在d維搜索空間中,個體在t時刻的速度和位置分別為,則在(t+1)時刻其速度和位置更新為：

在優(yōu)化過程中,當(dāng)滿足條件時BA會自動轉(zhuǎn)為局部搜索,從當(dāng)前最優(yōu)解集中選擇一個解,并令每只蝙蝠在其鄰域隨機(jī)游走產(chǎn)生局部新解：

式中,x'是在當(dāng)前最優(yōu)解x附近產(chǎn)生的局部新解;ε∈[-1,1]為d維隨機(jī)向量;是蝙蝠群體在t時刻的平均響度.

蝙蝠在接近獵物的過程中,其脈沖發(fā)射速率ri逐步提高,同時聲波的響度Ai逐漸降低,并在發(fā)現(xiàn)獵物時達(dá)到最小. 相應(yīng)迭代更新公式為：

1.2 蝙蝠算法的改進(jìn)

與其它群體智能優(yōu)化算法相似的是,BA也未能避免易陷入局部最優(yōu)、發(fā)生早熟收斂等問題,因而對復(fù)雜高維多目標(biāo)優(yōu)化問題的求解精度不高. 究其原因,BA的尋優(yōu)能力主要來自于蝙蝠個體間的相互作用,由于個體沒有變異機(jī)制,“超級蝙蝠”可能吸引其它個體迅速向其聚攏,致使種群多樣性嚴(yán)重下降; 同時,隨著蝙蝠個體在迭代過程中不斷移向最優(yōu)個體,種群逐漸喪失進(jìn)化能力,故而后期的收斂速度大為降低甚至停滯. 由此可見,對BA的改進(jìn)應(yīng)著眼于全程保持種群的多樣性,使其全局搜索能力和迭代后期的進(jìn)化能力得以增強(qiáng).

本文通過在BA中引入權(quán)重因子、Cauchy分布隨機(jī)數(shù)擾動和非線性規(guī)劃來改進(jìn)其性能.

1.2.1 引入速度權(quán)重因子

PSO算法以慣性權(quán)重w控制粒子對原有速度的繼承性,其值較大則粒子多樣性好,算法的全局搜索能力強(qiáng); 反之則粒子移動性減弱,局部搜索能力增強(qiáng). 在實(shí)際應(yīng)用中,通常令w在指定取值區(qū)間內(nèi)線性遞減,使PSO算法由前期強(qiáng)調(diào)全局搜索逐步轉(zhuǎn)為后期重在局部搜索,從而提高其整體優(yōu)化性能.

蝙蝠算法與粒子群算法同屬群智能優(yōu)化算法,二者的數(shù)學(xué)模型相近,故其運(yùn)行機(jī)制非常相似,前者強(qiáng)化了局部搜索能力,但可通過一定的參數(shù)設(shè)置演變?yōu)楹笳? 同時,兩種算法都存在早熟收斂、求解精度較低等問題,因而可采用某些相同的策略來進(jìn)行改進(jìn). 為此,我們將PSO算法的慣性權(quán)重引入BA,即為蝙蝠的速度增加一個權(quán)重因子w,并令其在區(qū)間[wl,wu]線性遞減,則將式(2)變?yōu)槿缦率?6)：

顯然,式(2)是w≡1時的一種特殊情況[11]. 每次迭代時,權(quán)重因子w按式(7)計(jì)算：

1.2.2 施加Cauchy分布隨機(jī)數(shù)擾動

Cauchy分布的概率特性是兩翼較長,易于產(chǎn)生遠(yuǎn)離原點(diǎn)的隨機(jī)數(shù). 因此,對蝙蝠位置進(jìn)行Cauchy分布隨機(jī)數(shù)擾動,可較好地保持蝙蝠群體的多樣性,降低其陷入局部最優(yōu)的概率,從而提高算法的全局搜索能力,有效防止早熟現(xiàn)象的發(fā)生. 擾動公式如下：

式中,Cauchy表示標(biāo)準(zhǔn)Cauchy分布隨機(jī)數(shù),其值為,其中為均勻分布隨機(jī)數(shù).

1.2.3 融入非線性規(guī)劃

將速度權(quán)重因子和Cauchy分布隨機(jī)數(shù)擾動引入BA,能改善其群體的多樣性,使其全局搜索能力得以提高,但也可能由于蝙蝠移動性的增強(qiáng)而錯過最佳解,為此在算法中融入非線性規(guī)劃函數(shù),以提高其局部搜索效率和整體優(yōu)化精度,并加快收斂速度.

非線性規(guī)劃(Nonlinear Programming,NP)研究n元實(shí)函數(shù)在一組等式或不等式約束條件下的極值問題,其目標(biāo)函數(shù)和約束條件必有至少一個為未知量的非線性函數(shù). 一般形式如下：

設(shè)計(jì)非線性規(guī)劃函數(shù)fnp(或直接使用MATLAB的fmincon函數(shù)),從變量的初始值開始搜索約束條件下的函數(shù)最小值,在BA尋優(yōu)過程中調(diào)用之： 傳送x的當(dāng)前值(蝙蝠位置)至fnp函數(shù),以之為初始值進(jìn)行最佳函數(shù)值的搜索,并將所得x的更好值返回BA繼續(xù)迭代過程. 為避免對算法的運(yùn)行速度產(chǎn)生明顯影響,可根據(jù)優(yōu)化問題的實(shí)際需要,每完成10次或20次迭代調(diào)用1次fnp函數(shù).

1.3 改進(jìn)蝙蝠算法的流程

(1) 設(shè)置算法參數(shù). 確定蝙蝠數(shù)量n、變量維度d和最大迭代次數(shù)T,設(shè)置搜索脈沖頻率范圍[fmin,fmax]、脈沖速率最大值r0及其增強(qiáng)系數(shù)γ、響度最大值A(chǔ)0及其衰減系數(shù)α,給出變量空間[xl,xu]、蝙蝠速度范圍[vl,vu]及其權(quán)重取值區(qū)間[wl,wu];

(2) 隨機(jī)初始化蝙蝠位置xi、速度vi及搜索脈沖的頻率fi、速率ri和響度Ai,并根據(jù)適應(yīng)度值找出當(dāng)前最優(yōu)個體位置x*;

(3) 根據(jù)式(1)更新脈沖頻率fi,依次由式(7)、式(6)計(jì)算蝙蝠的速度vi,再按式(3)更新其位置xi,即得新一代蝙蝠群體;

(4) 若隨機(jī)數(shù)rand>ri,則利用式(4)對當(dāng)前最優(yōu)蝙蝠位置進(jìn)行隨機(jī)擾動,以擾動結(jié)果替換當(dāng)前蝙蝠個體位置,并計(jì)算其適應(yīng)度值;

(5) 若蝙蝠位置得到改善且rand＜Ai,則接受所得新解,并按式(5)更新脈沖響度Ai和發(fā)射速率ri. 否則按式(8)對蝙蝠位置施加Cauchy分布隨機(jī)數(shù)擾動,并進(jìn)行越界處理;

(6) 根據(jù)適應(yīng)度值找出蝙蝠群體的當(dāng)前最優(yōu)解和最優(yōu)值;

(7) 若迭代次數(shù)t為20(或10)的倍數(shù),則調(diào)用非線性規(guī)劃函數(shù)fnp加強(qiáng)局部搜索;

(8) 若達(dá)到最大迭代次數(shù)T(或優(yōu)化精度ε),停止搜索并輸出全局最優(yōu)解和最優(yōu)值,否則轉(zhuǎn)到步驟(3)進(jìn)入下一次迭代.

1.4 改進(jìn)蝙蝠算法的測試

采用標(biāo)準(zhǔn)測試函數(shù),在32位Windows7系統(tǒng)環(huán)境用MATLAB R2015b編程運(yùn)行. 為了方便敘述和比較分析,將僅引入速度權(quán)重和Cauchy分布隨機(jī)數(shù)擾動的蝙蝠算法稱為WCBA,而將在此基礎(chǔ)上融入非線性規(guī)劃的改進(jìn)算法簡稱WCNBA.

1.4.1 測試函數(shù)及參數(shù)設(shè)置

選用5個標(biāo)準(zhǔn)測試函數(shù),其屬性如表1所示.

表1 5個測試函數(shù)

由于測試目的是將WCBA和WCNBA與BA進(jìn)行比較,以驗(yàn)證改進(jìn)的有效性,因此沒有刻意對算法的參數(shù)進(jìn)行優(yōu)化,而是統(tǒng)一設(shè)置為：n=40,T=300;fi∈[-1,1],r0=0.75,A0=0.25,γ=α=0.9;vi∈[-1,1],wi∈[1.0,0.5].

同時,我們也選取兩種經(jīng)典算法DE和PSO對一些函數(shù)進(jìn)行測試,以便進(jìn)一步對蝙蝠算法及其改進(jìn)效果進(jìn)行對比分析. DE算法參數(shù)： 縮放因子F0=0.5,交叉概率CR=0.25; PSO算法參數(shù)： 學(xué)習(xí)因子c1=c2=2.05,速度取值區(qū)間v∈[-1,1]. 結(jié)果表明,BA、WCBA和WCNBA全面優(yōu)于DE和PSO算法,其中單峰函數(shù)Sphere與多峰函數(shù)Rastrigin的求解迭代曲線分別如圖1、圖2所示.

圖1 Sphere函數(shù)的求解迭代曲線

圖2 Rastrigin函數(shù)的求解迭代曲線

1.4.2 測試結(jié)果分析

每個測試函數(shù)獨(dú)立運(yùn)行30次,取最優(yōu)值、最差值、平均值和尋優(yōu)成功率(獲得理論最優(yōu)值的次數(shù)占獨(dú)立運(yùn)行總次數(shù)的比率)進(jìn)行比較,所得結(jié)果如表2所示.

表2 標(biāo)準(zhǔn)函數(shù)測試結(jié)果

從表2的測試結(jié)果看,基于BA改進(jìn)的WCBA和WCNBA皆顯著優(yōu)于基本蝙蝠算法. 其中,WCNBA對f1～f4都能完全收斂到理論最優(yōu)值,尋優(yōu)成功率達(dá)到100%; 對于f5所得結(jié)果的平均值也非常接近理論最優(yōu)值. 而WCBA對f4可完全收斂于理論最優(yōu)值,對f1和f3的尋優(yōu)成功率則分別達(dá)到70.0%和33.3%,對f2和f5所得結(jié)果也遠(yuǎn)優(yōu)于BA. 因此,WCNBA是一種成功的BA改進(jìn)算法,WCBA也具有一定的實(shí)用價值.

2 改進(jìn)蝙蝠算法在模糊層次分析中的應(yīng)用

2.1 模糊層次分析的步驟與關(guān)鍵環(huán)節(jié)

層次分析法(Analytic Hierarchy Process,AHP)是將決策問題作為一個系統(tǒng),將其影響因素分解為目標(biāo)、準(zhǔn)則和方案等層次,在此基礎(chǔ)上將定性指標(biāo)模糊量化,遵照人類的思維、判斷規(guī)律進(jìn)行決策過程的一種實(shí)用方法. 因在處理復(fù)雜決策問題方面的實(shí)用性和有效性,AHP廣泛應(yīng)用于眾多領(lǐng)域.

將AHP應(yīng)用于模糊環(huán)境即為模糊層次分析法(Fuzzy Analytic Hierarchy Process,FAHP),它應(yīng)用模糊數(shù)學(xué)的隸屬度來量化指標(biāo)實(shí)測值,從而解決層次分析中的模糊性(如因素類屬之間不明晰、專家認(rèn)識上的模糊性等)問題,最大限度地降低人為因素的影響.FAHP的主要步驟為：

(2) 確定各層因素分別對其直接上級重要程度兩兩比較的隸屬度,以之建立模糊互補(bǔ)矩陣;

(3) 層次單排序(計(jì)算各層因素的相對權(quán)重);

(4) 方案總排序(方案層對目標(biāo)層的合成權(quán)重).

模糊層次分析的數(shù)據(jù)量大、計(jì)算復(fù)雜繁瑣,其關(guān)鍵環(huán)節(jié)為計(jì)算因素權(quán)重,它決定了決策結(jié)果的科學(xué)性、合理性和可信度. 計(jì)算因素權(quán)重的必要條件是模糊互補(bǔ)矩陣具有滿意一致性,因此還需先對其進(jìn)行一致性檢驗(yàn)和修正.

2.2 用改進(jìn)蝙蝠算法求解因素權(quán)重

對于模糊互補(bǔ)矩陣M=(mij)n×n(n為因素個數(shù))：

（一）從政治意義看，習(xí)近平新時代中國特色社會主義思想，是新時代國家政治生活和社會生活的根本指針。從政黨發(fā)展史看，擁有堅(jiān)強(qiáng)的領(lǐng)導(dǎo)核心，擁有科學(xué)的指導(dǎo)思想，是一個政黨形成凝聚力戰(zhàn)斗力不可或缺的兩個方面，也是政黨走向成熟的重要標(biāo)志。我們黨確立習(xí)近平新時代中國特色社會主義思想的指導(dǎo)地位，確立習(xí)近平總書記的核心地位，對于維護(hù)黨中央權(quán)威和集中統(tǒng)一領(lǐng)導(dǎo)，對于保證黨和國家事業(yè)興旺發(fā)達(dá)、長治久安具有重大而深遠(yuǎn)的意義，標(biāo)志著我們這個走過97年光輝歷程的世界第一大黨，達(dá)到了政治上、思想上、組織上的空前團(tuán)結(jié)和統(tǒng)一，為推進(jìn)新時代中國特色社會主義事業(yè)提供了堅(jiān)強(qiáng)政治保障。

以0.1～0.9標(biāo)度法表示其元素值,則由模糊互補(bǔ)矩陣的定義可知：mii=0.5、mij+mji=1(i,j=1,2,…,n分別為元素mij的行號和列號),亦即M的對角線元素恒為0.5、其左下區(qū)域元素mji=1-mij. 因此,在應(yīng)用中只需確定右上區(qū)域元素mij,即可算得左下區(qū)域元素mji.

傳統(tǒng)做法是先用手工調(diào)整或數(shù)學(xué)變換法進(jìn)行模糊互補(bǔ)矩陣的一致性檢驗(yàn)與修正,再以方根法、特征值法、和行歸一化法和排序法等由模糊互補(bǔ)一致性矩陣計(jì)算因素權(quán)重,其計(jì)算量大、繁瑣費(fèi)時. 應(yīng)用WCNBA可將這兩步工作合二為一,即同時完成模糊互補(bǔ)矩陣的一致性檢驗(yàn)、修正和相應(yīng)的因素權(quán)重計(jì)算,從而簡化步驟、提高效率.

2.2.1 模糊互補(bǔ)一致性矩陣的充要條件

定義1. 對于模糊互補(bǔ)矩陣M=(mij)n×n,若,都有：

則稱M為加性一致性模糊互補(bǔ)矩陣. 由此可推知模糊互補(bǔ)一致性矩陣的充要條件為： 任意指定行與其余各行對應(yīng)元素之差為某一常數(shù).

定理1. 設(shè)M=(mij)n×n為模糊互補(bǔ)矩陣,則M是模糊一致性矩陣的充要條件為： 存在一階非負(fù)歸一化向量及正數(shù)α,使得,皆有

式中,α是對因素之間重視程度差異的度量,其值小則決策者越重視這種差異;wi為因素權(quán)重.

2.2.2 用改進(jìn)蝙蝠算法求解因素權(quán)重

設(shè)R=(rij)n×n為修正后的模糊互補(bǔ)矩陣,將式(9)的推論和式(10)結(jié)合起來,可得模糊互補(bǔ)矩陣一致性的指標(biāo)函數(shù)：

該指標(biāo)函數(shù)值越小,則R的一致性越好; 其值為0時,R具有完全一致性. 在實(shí)際應(yīng)用中,通常以f(n)＜0.1為模糊互補(bǔ)矩陣具有滿意一致性的標(biāo)準(zhǔn).

應(yīng)用WCNBA同步進(jìn)行模糊互補(bǔ)矩陣的一致性修正和因素權(quán)重計(jì)算時,以因素權(quán)重及矩陣右上區(qū)域(不含對角線)除第一行之外的元素為優(yōu)化變量(共有(n-1)(n-2)/2+n個,n為因素個數(shù)),以實(shí)數(shù)形式編碼,并設(shè)其搜索區(qū)間為[0,1]; 以式(11)為適應(yīng)度函數(shù)進(jìn)行搜索,當(dāng)其值＜0.1或達(dá)到最大迭代次數(shù)時,返回因素權(quán)重和修正后的元素值.

2.2.3 應(yīng)用實(shí)例

在某校的課程建設(shè)質(zhì)量評價中,采用模糊層次分析法確定各級評價指標(biāo)的主觀權(quán)重,其中有如下兩個模糊互補(bǔ)矩陣[13]：

用WCNBA進(jìn)行M1、M2的一致性修正和因素權(quán)重計(jì)算,算法的運(yùn)行參數(shù)均按1.4.1設(shè)置,其尋優(yōu)迭代過程如圖3所示,所得結(jié)果如表3所示.

圖3 用WCNBA對M1、M2的尋優(yōu)迭代過程

將表3與M1、M2的數(shù)據(jù)對比可知,M1的(2,4)和M2的(2,3)、(3,5)位置處的元素得到了修正,于是相應(yīng)的模糊互補(bǔ)一致性矩陣R1和R2如下：

表3 M1、M2的一致性修正和因素權(quán)重計(jì)算結(jié)果

3 結(jié)論

本文針對基本蝙蝠算法在尋優(yōu)過程中難以保持種群的多樣性、易發(fā)生早熟收斂、求解精度較低等問題,通過引入速度權(quán)重因子、施加Cauchy分布隨機(jī)數(shù)擾動和融入非線性規(guī)劃函數(shù)等措施,設(shè)計(jì)并實(shí)現(xiàn)了改進(jìn)的蝙蝠算法WCBA和WCNBA. 經(jīng)用標(biāo)準(zhǔn)函數(shù)測試,并在模糊層次分析中應(yīng)用,結(jié)果表明改進(jìn)的蝙蝠算法顯著優(yōu)于基本蝙蝠算法.

1Yang XS. A new metaheuristic bat-inspired algorithm.González JR,Pelta DA,Cruz C,et al. Nature Inspired Cooperative Strategies for Optimization. Berlin Heidelberg：Springer,2010. 65-74.

2李煜,馬良. 新型全局優(yōu)化蝙蝠算法. 計(jì)算機(jī)科學(xué),2013,40(9)： 225-229.

3劉長平,葉春明. 具有混沌搜索策略的蝙蝠優(yōu)化算法及性能仿真. 系統(tǒng)仿真學(xué)報(bào),2013,25(6)： 1183-1188,1195.

4肖輝輝,段艷明. 基于DE算法改進(jìn)的蝙蝠算法的研究及應(yīng)用. 計(jì)算機(jī)仿真,2014,31(1)： 272-277,301.

5賀興時,丁文靜,楊新社. 基于模擬退火高斯擾動的蝙蝠優(yōu)化算法. 計(jì)算機(jī)應(yīng)用研究,2014,31(2)： 392-397.

6劉長平,葉春明,劉滿成. 來自大自然的尋優(yōu)策略： 像蝙蝠一樣感知. 計(jì)算機(jī)應(yīng)用研究,2013,30(5)： 1320-1322,1356.

7盛曉華,葉春明. 蝙蝠算法在PFSP調(diào)度問題中的應(yīng)用研究. 工業(yè)工程,2013,16(1)： 119-124.

8李枝勇,馬良,張惠珍. 0-1規(guī)劃問題的元胞蝙蝠算法. 計(jì)算機(jī)應(yīng)用研究,2013,30(10)： 2903-2906,2935. [doi： 10.3969/j.issn.1001-3695.2013.10.005]

9張蓉. 蝙蝠算法優(yōu)化最二乘支持向量機(jī)的網(wǎng)絡(luò)入侵檢測.激光雜志,2014,35(11)： 101-104.

10薛威力,賀興時,楊新社. 蝙蝠算法的一種改進(jìn). 哈爾濱商業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,32(6)： 706-712.

11李枝勇,馬良,張惠珍. 蝙蝠算法收斂性分析. 數(shù)學(xué)的實(shí)踐與認(rèn)識,2013,43(12)： 182-190. [doi： 10.3969/j.issn.1000-0984.2013.12.026]

12胡振. QPSO混合算法在PID控制器優(yōu)化中的應(yīng)用. 計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,23(10)： 233-238. [doi： 10.3969/j.issn.1003-3254.2014.10.042]

13陳素彬,胡振. 高職院校分析化學(xué)課程建設(shè)的量化評價方法. 化學(xué)教育,2017,38(8)： 44-50.