自適應(yīng)雜交退火粒子群優(yōu)化算法

路復(fù)宇, 童寧寧, 馮為可, 萬鵬程

(空軍工程大學(xué)防空反導(dǎo)學(xué)院, 陜西 西安 710051)

0 引 言

粒子群優(yōu)化(particle swarm optimization, PSO)算法是由Kennedy等在1995年提出的新興優(yōu)化算法。由于其生物社會(huì)背景嚴(yán)謹(jǐn)、易于理解、參數(shù)較少且操作簡單,對多峰函數(shù)問題和非線性問題具有良好的全局搜索能力,一經(jīng)提出就引起了相關(guān)研究熱潮,現(xiàn)已被廣泛應(yīng)用于模式識別、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、路徑規(guī)劃、雷達(dá)資源調(diào)度優(yōu)化、雷達(dá)圖像處理、波達(dá)方向估計(jì)、天線方向圖綜合等領(lǐng)域。但是,標(biāo)準(zhǔn)PSO算法存在著早熟收斂、后期搜索速度較慢、收斂精度較低等問題。

針對上述問題,諸多學(xué)者對PSO算法進(jìn)行了優(yōu)化和改進(jìn)。相關(guān)研究主要可以分為以下3類。

(1) 對PSO的慣性權(quán)重和加速系數(shù)等參數(shù)進(jìn)行改進(jìn)。例如,文獻(xiàn)[12]基于個(gè)體適應(yīng)度值和群體收斂信息劃分種群,采用不同的自適應(yīng)操作,使群體在進(jìn)化過程中始終保持慣性權(quán)重的多樣性,一定程度上解決了PSO算法早熟收斂問題。文獻(xiàn)[13]在線性變化加速系數(shù)的基礎(chǔ)上引入擾動(dòng)加速因子,使部分粒子可以有選擇地追隨全局最優(yōu)解,增強(qiáng)了算法的收斂速度及精度。

(2) 對粒子種群的鄰域拓?fù)浣Y(jié)構(gòu)進(jìn)行改進(jìn)。例如,文獻(xiàn)[14]從粒子獲取信息的角度出發(fā),基于個(gè)體極值中心點(diǎn)和全局極值點(diǎn)改進(jìn)粒子的行為方式,提高了算法的收斂精度及穩(wěn)定性。文獻(xiàn)[15]采用集成學(xué)習(xí)的方法設(shè)計(jì)了一種混沌PSO算法,通過在6種混沌拓?fù)浣Y(jié)構(gòu)上的實(shí)驗(yàn),驗(yàn)證了多混沌PSO算法的可行性。

(3) 利用其他智能優(yōu)化算法對PSO算法進(jìn)行改進(jìn)。例如,文獻(xiàn)[16]引入了基于離散正交交叉算子的免疫基因操作以及克隆算子,提高算法對多目標(biāo)優(yōu)化問題的有效性。文獻(xiàn)[17]利用強(qiáng)化學(xué)習(xí)的方法自動(dòng)調(diào)節(jié)參數(shù),進(jìn)一步提高了收斂速度和精度,為強(qiáng)化學(xué)習(xí)和群智能搜索算法的結(jié)合提供了一種新的方案。文獻(xiàn)[19]融合了幾種改進(jìn)方式,提出了一種自適應(yīng)模擬退火PSO(adaptive simulated annealing PSO, ASAPSO)算法,采用線性變化的加速系數(shù),用雙曲正切函數(shù)控制慣性權(quán)重,融合模擬退火算法提升算法跳出局部最優(yōu)的能力,基于典型測試函數(shù)與5種改進(jìn)PSO算法進(jìn)行了對比,證明了該算法在尋優(yōu)速度、收斂精度及穩(wěn)定性等方面的優(yōu)勢。

然而,對于高維多峰函數(shù),ASAPSO算法存在易陷入局部最優(yōu)、尋優(yōu)精度較差等問題。為解決這些問題,本文提出了一種自適應(yīng)雜交退火PSO(adaptive hybrid annealing PSO,AHAPSO)算法。與ASAPSO算法相同,所提AHAPSO算法利用模擬退火算子提高粒子跳出局部最優(yōu)的能力,增強(qiáng)前期搜索的全局性。所提算法不同的是:① 采用Sigmoid函數(shù)控制慣性權(quán)重,采用雙曲正切函數(shù)控制加速系數(shù),使得算法在面對高維多峰函數(shù)問題時(shí)具有較好的適應(yīng)性,具備更優(yōu)的全局搜索和局部尋優(yōu)能力,降低前期陷入局部最優(yōu)的可能性;② 在后期引入雜交變異算子,提高種群多樣性,在保證原有最優(yōu)解不被覆蓋的情況下進(jìn)一步尋優(yōu),提高收斂能力?；谖墨I(xiàn)[19]給出的3種典型測試函數(shù)對所提算法進(jìn)行了驗(yàn)證,并與ASAPSO算法和標(biāo)準(zhǔn)PSO算法進(jìn)行了對比。結(jié)果表明，所提算法在尋優(yōu)精度和收斂速度上均具有一定優(yōu)勢。最后,將所提算法應(yīng)用于天線方向圖綜合,獲得了較好的性能。

1 標(biāo)準(zhǔn)PSO算法

對于復(fù)雜組合優(yōu)化問題,牛頓法等傳統(tǒng)優(yōu)化算法需要遍歷整個(gè)搜索空間,效率低且容易出現(xiàn)組合爆炸問題。受鳥類群體覓食行為的啟發(fā),Kennedy等提出了PSO算法,為解決搜索空間復(fù)雜龐大情況下的尋優(yōu)問題提供了一種新的思路。

PSO算法在求解優(yōu)化問題時(shí),將問題的若干個(gè)潛在解抽象為粒子,尋優(yōu)過程通過粒子在搜索空間內(nèi)的飛行完成。每個(gè)粒子都有位置和速度兩個(gè)特征,由被優(yōu)化函數(shù)決定其適應(yīng)度值。假定被優(yōu)化函數(shù)的自變量空間為維,PSO的粒子總數(shù)為,則第個(gè)(=1,2,…,)粒子的位置和速度可分別表示為

=[1,2,…,]

(1)

=[1,2,…,]

(2)

粒子在每次迭代時(shí)的進(jìn)化由3部分組成,分別是對上一次速度的繼承、自身記憶和種群的信息交互。因此,第次迭代過程可表示為

(+1)=()+[()-()]+[()-()]

(3)

(+1)=()+(+1)

(4)

式中：為慣性權(quán)重系數(shù)；和分別是自身加速系數(shù)和社會(huì)加速系數(shù),是控制PSO迭代的重要參數(shù);()和()分別代表第個(gè)粒子在第維度上(=1,2,…,)第次迭代時(shí)的位置和速度;和為均勻分布在[0,1]之間的隨機(jī)數(shù);為粒子個(gè)體最優(yōu)位置；為種群最佳位置。

粒子的搜索能力受到慣性權(quán)重系數(shù)和兩個(gè)加速系數(shù)控制:控制粒子的慣性,決定粒子對上一次速度的繼承比例;控制自我認(rèn)知部分,指導(dǎo)粒子向該粒子自身的歷史最佳位置飛行;控制社會(huì)認(rèn)知部分,體現(xiàn)種群中各粒子的信息交換,指導(dǎo)粒子向種群最佳的位置飛行。在飛行過程中,粒子的位置范圍和速度范圍分別為[-,]和[-,]。算法經(jīng)過參數(shù)初始化、適應(yīng)度計(jì)算、粒子信息更新、終止條件判斷等步驟,最終能夠得到符合條件的解。

PSO算法結(jié)構(gòu)簡單、運(yùn)行速度快,在處理復(fù)雜優(yōu)化問題上具有一定的優(yōu)勢。但是,PSO算法的參數(shù)均為固定值,無法根據(jù)算法運(yùn)行的程度進(jìn)行自動(dòng)調(diào)節(jié),導(dǎo)致早熟收斂現(xiàn)象。此外,在進(jìn)化后期,大量粒子聚集在一起,粒子速度會(huì)急劇降低,導(dǎo)致后期收斂速度較慢。同時(shí),隨著速度的降低,粒子很難跳出局部最優(yōu),導(dǎo)致收斂精度較低。

2 所提算法

為解決PSO算法易早熟收斂、后期速度較慢、收斂精度較低等問題,本文提出了AHAPSO算法,對慣性權(quán)重和加速系數(shù)進(jìn)行自適應(yīng)調(diào)節(jié),并引入模擬退火算子和雜交變異算子提高算法精度。下面,分別對自適應(yīng)慣性權(quán)重、自適應(yīng)加速系數(shù)、模擬退火算子和雜交變異算子4個(gè)模塊進(jìn)行介紹,并給出所提算法的具體步驟。

2.1 自適應(yīng)慣性權(quán)重

慣性權(quán)重用于控制PSO算法的開發(fā)和探索能力,其物理意義為粒子的慣性,即飛行過程中粒子對當(dāng)前速度的繼承比例。在實(shí)際優(yōu)化過程中,一般希望粒子在前期具有良好的全局搜索能力,在后期具有較好的局部尋優(yōu)能力,這就要求慣性權(quán)重在前期的取值較大,在后期的取值較小。Sigmoid函數(shù)在線性與非線性之間具有良好的平衡,可以滿足慣性權(quán)重在算法各個(gè)階段的需求。因此,本文選取[-,]之間的Sigmoid函數(shù)自適應(yīng)控制慣性權(quán)重,表示為

(5)

式中：和分別為慣性權(quán)重的最大值和最小值；為最大迭代次數(shù)；為當(dāng)前迭代次數(shù)。

2.2 自適應(yīng)加速系數(shù)

加速系數(shù)和分別調(diào)節(jié)粒子向個(gè)體最優(yōu)和群體最優(yōu)飛行的步長,決定了粒子自我認(rèn)知和社會(huì)信息交流的權(quán)重關(guān)系。當(dāng)>時(shí),粒子更趨向于自身歷史最優(yōu)方向運(yùn)動(dòng),反之則更趨向于群體最優(yōu)方向運(yùn)動(dòng)。在算法初期,著重運(yùn)動(dòng)的遍歷性,減小粒子陷入局部最優(yōu)的概率,需要加大的比重;在算法后期,個(gè)體之間需要充分進(jìn)行信息共享,著重在群體最優(yōu)附近進(jìn)行搜索,需要加大的比重。雙曲正切函數(shù)可以隨迭代的進(jìn)行逐漸放大參數(shù)間的對比差異,其非線性特征可以使得粒子在前期充分進(jìn)行全局搜索,在中后期迅速轉(zhuǎn)入對群體最優(yōu)附近空間的搜索。因此,本文選取[-,]之間的雙曲正切函數(shù)對和進(jìn)行自適應(yīng)控制,表示為

(6)

(7)

式中：和為自身加速系數(shù)的最大值和最小值;和為社會(huì)加速系數(shù)的最大值和最小值。

2.3 模擬退火算子

在面對復(fù)雜組合優(yōu)化問題時(shí),初始化的粒子往往很難分布在全局最優(yōu)附近,加之PSO算法在前期有較強(qiáng)的收斂能力,從而導(dǎo)致算法很容易早熟收斂。為解決此問題,要求粒子能夠在搜索空間內(nèi)進(jìn)行充分的探索,并且有能力跳出局部最優(yōu)。因此,在更新群體最優(yōu)的過程中引入模擬退火算子,使算法以一定概率接受差解,具備突跳能力,讓一部分粒子朝最優(yōu)解的反向運(yùn)動(dòng),從而跳出局部最優(yōu),帶動(dòng)算法開展全局搜索。

首先,根據(jù)初始化信息確定溫度,即

(8)

式中：()為每次迭代中的溫度；為降溫系數(shù)；()為第次迭代時(shí)群體最優(yōu)粒子的適應(yīng)度值。

然后,根據(jù)式(8)所確定的溫度,計(jì)算接受差解的概率:

(9)

式中：()為粒子第次迭代后的個(gè)體最優(yōu)位置的適應(yīng)度值。

最后,根據(jù)Metropolis準(zhǔn)則更新群體最優(yōu),表示為

(10)

式中：為均勻分布在[0,1]之間的隨機(jī)數(shù)。

2.4 雜交變異算子

隨著算法的進(jìn)行,大量粒子趨向同一,粒子種群多樣性急劇下降,使得后期收斂速度明顯下降,甚至無法繼續(xù)優(yōu)化。當(dāng)種群多樣性低于一定程度時(shí),算法繼續(xù)開發(fā)的難度較大,此時(shí)引入雜交變異算子來增加種群多樣性,可以促進(jìn)算法的進(jìn)一步收斂。

首先,根據(jù)PSO體的平均中心距評判種群的多樣性,表示為

(11)

(12)

則對種群進(jìn)行雜交變異操作。其中,Div()為第次迭代時(shí)的平均中心距,Div(0)為初始平均中心距,為雜交概率,為均勻分布在[0,1]之間的隨機(jī)數(shù),為閾值系數(shù)(通過對不同優(yōu)化函數(shù)進(jìn)行仿真分析可以發(fā)現(xiàn),當(dāng)?shù)^程中的種群多樣性下降為種群初始多樣性的1%～5%時(shí),粒子搜索能力下降,容易陷入局部最優(yōu)。因此,在實(shí)際應(yīng)用中,綜合考慮收斂精度和收斂速度,一般可以將閾值系數(shù)取值為001～005)。

然后,根據(jù)雜交比例,在原始種群中隨機(jī)選取個(gè)粒子進(jìn)行雜交,產(chǎn)生子代粒子存入雜交池中,子代的位置和速度由父代隨機(jī)交叉產(chǎn)生,表示為

(13)

最后,為保留種群原始特性以及原有最優(yōu)值,將原有群體最優(yōu)粒子存入保留區(qū),再從原始種群中隨機(jī)抽取[(1-)-1]個(gè)粒子放入保留區(qū),與雜交池內(nèi)的子代粒子共同構(gòu)成新的種群,新的種群將繼續(xù)進(jìn)行尋優(yōu)。

2.5 算法步驟

基于以上4個(gè)模塊,所提AHAPSO算法的具體步驟如下。

初始化、、、、、、、、等參數(shù)。

隨機(jī)生成個(gè)粒子,初始化粒子個(gè)體最優(yōu)位置和最優(yōu)值、群體最優(yōu)位置和最優(yōu)值。

根據(jù)式(5)～式(7)自適應(yīng)調(diào)整、和的值。

根據(jù)式(3)和式(4)更新粒子位置和速度。

對超出搜索空間和速度邊界值的粒子進(jìn)行邊界處理,隨機(jī)賦予一個(gè)邊界內(nèi)的值。

更新,并根據(jù)式(8)～式(10)更新。

根據(jù)式(11)和式(12)判斷是否滿足雜交條件,若不滿足則返回步驟4。

根據(jù)式(13)執(zhí)行雜交變異算子,產(chǎn)生新的種群。

記錄本次迭代的群體最優(yōu)及最優(yōu)值。

判斷算法是否達(dá)到最大迭代次數(shù),若未達(dá)到則返回步驟3,若達(dá)到則輸出當(dāng)前最優(yōu)結(jié)果。

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

為驗(yàn)證所提算法的性能,選取3種典型標(biāo)準(zhǔn)測試函數(shù)作為目標(biāo)函數(shù),取函數(shù)值為粒子適應(yīng)度值,比較本文AHAPSO算法與ASAPSO算法和標(biāo)準(zhǔn)PSO算法的性能。此外,將所提算法應(yīng)用在陣列天線方向圖綜合設(shè)計(jì)上,進(jìn)一步驗(yàn)證其有效性。

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

所選取的3種典型標(biāo)準(zhǔn)測試函數(shù)具體信息如表1所示。其中,函數(shù)為較復(fù)雜的單峰函數(shù),其在[1,1,…,1]處取得最優(yōu)值0;為典型多峰函數(shù),在搜索空間內(nèi)存在多個(gè)局部最優(yōu)值,在[1,1,…,1]處取得最優(yōu)值0;函數(shù)為復(fù)雜多峰函數(shù),搜索空間較大,多個(gè)峰值之間差異較小,在[420.968 7,420.968 7,…,420.968 7]處取得最優(yōu)值0。由文獻(xiàn)[19]結(jié)果可知,ASAPSO算法在各類測試函數(shù)下的效果較近年來其他同類算法均有較大優(yōu)勢,但在這3種函數(shù)上的測試結(jié)果與理論最優(yōu)值還有一定的差距。

表1 3種典型標(biāo)準(zhǔn)測試函數(shù)Table 1 Three typical standard test functions

為保持實(shí)驗(yàn)結(jié)果的一致性,統(tǒng)一設(shè)置不同算法的種群規(guī)模為=30,最大迭代次數(shù)為=1 000。在所提AHAPSO算法中,=10,=08,=02,=4,=25,=125,=25,=125,=095,=1%,=08,=06,慣性權(quán)重和加速系數(shù)自適應(yīng)變化曲線如圖1所示。ASAPSO算法中的其余參數(shù)與文獻(xiàn)[19]相同;標(biāo)準(zhǔn)PSO算法取=08,==15。

圖1 慣性權(quán)重和加速系數(shù)自適應(yīng)變化曲線Fig.1 Adaptive curve of inertia weight and acceleration coefficient

3.2 仿真結(jié)果比較

對于3種測試函數(shù),分別在維度=10和=30條件下運(yùn)行1 000次,記錄不同算法所得結(jié)果的平均值(avg)和最小值(min),結(jié)果如表2所示?？梢钥闯?① 所提算法對函數(shù)能夠搜索到理論最優(yōu)值,對和函數(shù)搜索得到的最優(yōu)值也能夠比較接近理論最優(yōu)值;② 所提算法對3種函數(shù)得到的平均值和最優(yōu)值均優(yōu)于ASAPSO算法和PSO算法。結(jié)果表明,本文所提出的改進(jìn)方法可以有效提高算法收斂精度。

表2 PSO、ASAPSO和AHAPSO算法測試結(jié)果Table 2 Test results of PSO, ASAPSO, and AHAPSO algorithm

為比較3種算法的收斂速度,更加直觀地體現(xiàn)算法精度,圖2～圖4給出了3種算法在不同函數(shù)下的適應(yīng)度進(jìn)化曲線(維度=30)。由圖2和圖3可知:① 在處理單峰函數(shù)以及復(fù)雜程度不高的多峰函數(shù)時(shí),PSO算法收斂速度最快、精度最低,反映出PSO算法易早熟收斂、易陷入局部最優(yōu)的問題;② 所提AHAPSO算法與ASAPSO算法在前期收斂速度均略有不足,主要原因是引入自適應(yīng)參數(shù)變化和模擬退火算子,使粒子在搜索空間內(nèi)充分探索,避免過早陷入局部最優(yōu),因此在前期收斂速度較慢;③ 在算法運(yùn)行中后期,所提AHAPSO算法會(huì)有一個(gè)加速下探的過程,體現(xiàn)了雜交變異算子在中后期的主導(dǎo)作用,重新恢復(fù)多樣性的粒子種群會(huì)加速尋優(yōu)過程。由圖4可知，在處理較為復(fù)雜的高維度多峰函數(shù)時(shí),PSO算法在前期快速早熟收斂,ASAPSO算法雖在前期有較好性能,但中后期粒子停止探索,而所提AHAPSO算法在前期可保持較快收斂速度,中后期可進(jìn)一步加速收斂,因此在整個(gè)運(yùn)算過程中均具有較快速度。

圖2 f1函數(shù)下不同算法的收斂速度Fig.2 Convergence rate of different algorithms under f1 function

圖3 f2函數(shù)下不同算法的收斂速度Fig.3 Convergence rate of different algorithms under f2 function

圖4 f3函數(shù)下不同算法的收斂速度Fig.4 Convergence rate of different algorithms under f3 function

從實(shí)驗(yàn)結(jié)果可以看出,本文所提出的AHAPSO算法能有效解決PSO算法易早熟、后期收斂速度慢、收斂精度低等問題,在收斂速度與精度上均有較大優(yōu)勢。

3.3 陣列方向圖綜合設(shè)計(jì)

最后,為進(jìn)一步驗(yàn)證所提算法的性能,將其應(yīng)用于陣列天線方向圖綜合設(shè)計(jì)之中。根據(jù)天線陣?yán)碚?對于由個(gè)陣元組成的均勻直線陣列,若不考慮陣元之間的耦合,則該陣列的遠(yuǎn)場方向圖函數(shù)可表示為

(14)

式中：為角度；和分別為第個(gè)陣元的幅度加權(quán)系數(shù)和相位；=2π為波數(shù),為工作波長；為陣元間距。

由文獻(xiàn)[30]可知,陣列方向圖的最大旁瓣電平(maximum sidelobe level, MSLL)可表示為

(15)

={|≤≤-∪+≤≤}

(16)

式中：為波束的指向；為主瓣零功率點(diǎn)；和分別為角度最小值和最大值。

利用PSO算法、ASAPSO算法和所提AHAPSO算法對一個(gè)陣元數(shù)=32、陣元間距=05的同相陣列進(jìn)行設(shè)計(jì),使其方向圖的旁瓣電平最低。令32個(gè)陣元對稱分布,設(shè)置每個(gè)粒子的維度為16,其余各參數(shù)均與第3.1節(jié)中相同,可得3種算法的最大旁瓣電平進(jìn)化曲線如圖5所示,陣列綜合設(shè)計(jì)結(jié)果如圖6所示?？梢钥闯?所提AHAPSO算法在中后期具有更高的收斂速度和收斂精度,所得陣列方向圖的最大旁瓣電平小于-47 dB,相比其他兩種算法均有一定提高,驗(yàn)證了其優(yōu)越性。

圖5 不同算法的最大旁瓣電平收斂曲線Fig.5 MSLL convergence curve of different algorithms

圖6 不同算法優(yōu)化得到的陣列方向圖Fig.6 Array direction graph optimized by different algorithms

4 結(jié) 論

本文提出了一種AHAPSO算法,采用Sigmoid函數(shù)和雙曲正切函數(shù)分別控制慣性權(quán)重和加速系數(shù),引入模擬退火算子提高算法跳出局部最優(yōu)能力,利用雜交變異算子提高后期尋優(yōu)速度。3種典型標(biāo)準(zhǔn)測試函數(shù)的實(shí)驗(yàn)結(jié)果表明,所提算法相較于同類算法收斂精度和速度更高。在陣列方向圖綜合應(yīng)用之中,本文所提算法可使得陣列方向圖的最大旁瓣電平控制在-47 dB以下,進(jìn)一步驗(yàn)證了其性能。