基于自適應(yīng)學習策略的改進鴿群優(yōu)化算法

胡耀龍，馮強，海星朔，任羿

（北京航空航天大學 可靠性與系統(tǒng)工程學院，北京100083）

仿生智能優(yōu)化算法是根據(jù)自然界中生物種群所表現(xiàn)出來的群體行為特性所總結(jié)的一種算法，這類算法在處理復(fù)雜問題中具有良好的表現(xiàn)。

2014年，Duan和Qiao［1］根據(jù)鴿群歸巢這一過程中鴿群所表現(xiàn)出的特殊的導航行為提出了鴿群優(yōu)化（Pigeon-Inspired Optimization，PIO）算法，該算法在無人機編隊和控制參數(shù)優(yōu)化等領(lǐng)域已有很好表現(xiàn)［2-6］，但是仍然存在一些諸如過早收斂、容易陷入局部最優(yōu)等不足之處［7］。針對這些不足，許多學者提出了一些改進方案，從不同角度對標準PIO算法進行了改進。Duan等［8］通過使用導航過渡因子見表2因子tr將標準PIO兩個算子合并在一個迭代循環(huán)中，并將鴿群的捕食逃逸機制引入到標準PIO中，提出了一種基于捕食逃逸鴿群優(yōu)化（CPIO）算法。Yang等［9］提出了一種基于柯西分布的柯西變異鴿群啟發(fā)優(yōu)化（CMPIO）算法，在CMPIO算法中，分別利用柯西突變機制對PIO算法中的地圖、指南針算子和地標算子進行了改進。Zhang和Duan［10］根據(jù)鴿群在飛行過程中個體間的等級制度，提出了一種新的基于社會等級的鴿群優(yōu)化（SCPIO）算法，利用社會等級策略來增強標準PIO的收斂能力。Hua等［11］提出了一種自適應(yīng)鴿群優(yōu)化（APIO）算法，在APIO算法中，地圖和指南針因子的參數(shù)設(shè)置隨著迭代的進行而變化。Xiang等［12］提出了一種基于禁忌表的鴿群綜合學習策略（CLPIO-TL），該策略利用綜合學習策略和自適應(yīng)調(diào)節(jié)機制，不同程度地提高了鴿群的學習能力，此外，CLPIO中還使用了自適應(yīng)機制來增強全局搜索能力和局部搜索能力之間的平衡。Huo等［13］提出了一種基于動態(tài)對立學習策略的突變鴿群激勵優(yōu)化（MPIO）算法，該算法利用具有非線性特征的突變算子增強全局搜索能力，加速全局最優(yōu)鴿子的收斂速度，同時引入動態(tài)的基于對立的學習策略，使算法具有較好的收斂速度。Hu等［14］提出了一種自適應(yīng)算子量子行為鴿群啟發(fā)優(yōu)化（AOQPIO）算法，該算法采用地圖和指南針因子R隨著迭代次數(shù)的變化來平衡全局搜索能力和局部搜索能力，在地標算子階段，提出了一個新的種群更新方程來增加搜索多樣性。Liu等［15］提出了一種改進的粒子群優(yōu)化（IPIO）算法，將粒子群優(yōu)化（PSO）算法、逆因子和高斯因子引入PIO算法，該改進算法將原地圖與指南針算子替換為PSO算法，避免了所有粒子的聚集狀態(tài)，從而增加了群體的多樣性，在地標算子中引入高斯因子，增強了全局搜索能力，將反向?qū)W習引入到算法中，并與粒子群的粒子學習相結(jié)合，有效地平衡全局搜索能力和局部搜索能力。Xu等［16］提出了一種獨立搜索和多區(qū)域收斂鴿群啟發(fā)優(yōu)化（ISMCPIO）算法，該算法在PIO中引入獨立搜索策略和多區(qū)域收斂機制，對包含可疑最優(yōu)解的多區(qū)域進行綜合搜索，提高了搜索的精度。Chen等［17］提出了一種基于量子數(shù)的混合鴿群優(yōu)化（QPIO）算法，在該算法中，當前的最優(yōu)解被認為是2個概率狀態(tài)的線性疊加，通過量子旋轉(zhuǎn)門平衡全局搜索能力和局部搜索能力。Hai等［18］將進化博弈理論引入到PIO算法中，提出了一種基于進化博弈論的自適應(yīng)鴿群優(yōu)化（EGTPIO）算法，在鴿群中展開雙重策略進化博弈，在提高搜索效率的同時，通過增強操作符和參數(shù)之間的協(xié)調(diào)和分配來提高標準PIO算法的適應(yīng)性。

本文在標準PIO算法的基礎(chǔ)之上，引入自適應(yīng)學習策略，提出了一種基于自適應(yīng)學習策略的改進PIO（ALPIO）算法。所提算法針對標準PIO算法容易陷入局部最優(yōu)的缺點，提出了一種基于容差的搜索方向調(diào)整策略，該策略通過判斷鴿群的迭代信息，對鴿群的搜索方向進行調(diào)整；采用了基于自學習的候選者生成策略來保證該算法的搜索能力，采用了基于競爭學習的預(yù)測策略來保證算法的可用性。

1 改進的鴿群優(yōu)化算法

在復(fù)雜優(yōu)化問題的求解過程中，標準PIO算法容易陷入局部最優(yōu)［19］。為此，本文在標準PIO算法地圖與指南針算子的迭代過程中引入自適應(yīng)學習策略，增強種群多樣性，確保種群中個體具有更強的搜索能力、適應(yīng)能力，提高算法搜索到全局最優(yōu)的概率。ALPIO算法的流程如圖1所示，圖中t為迭代次數(shù)。3種策略的具體描述見1.2～1.4節(jié)。

1.1 ALPIO算法描述

步驟1 設(shè)定算法中各個參數(shù)的值，如種群數(shù)量N、搜索空間維數(shù)D、指南針因子R、地圖和指南針算子最大迭代次數(shù)T1、地標算子最大迭代次數(shù)T2、最大迭代次數(shù)MaxIter。

圖1 ALPIO算法流程Fig.1 Flowchart of ALPIO algorithm

步驟2 初始化個體的位置和速度，計算每個個體的適應(yīng)度值，找出當前最好的位置。

步驟3 操作地圖與指南針算子。更新個體的速度和位置，更新全局最優(yōu)和個體歷史最優(yōu)。

步驟4 如果Prob＿adjust＞rand（），則停止使用當前全局最優(yōu)；否則，轉(zhuǎn)回到步驟3。

步驟5 使用基于自學習的候選者生成策略產(chǎn)生一個候選者。

步驟6 使用基于競爭學習的預(yù)測策略從候選者和當前全局最優(yōu)中選取較優(yōu)的作為新的全局最優(yōu)。

步驟7 使用基于容差的搜索方向調(diào)整策略更新容差T和Prob＿adjust。

步驟8 判斷是否達到地圖與指南針算子的最大迭代次數(shù)，若是，轉(zhuǎn)到下一個操作；否則，轉(zhuǎn)回到步驟3。

步驟9 操作地標算子。更新種群數(shù)量和位置，計算種群中心位置，更新全局最優(yōu)和個體歷史最優(yōu)。

步驟10 判斷是否達到地標算子的最大迭代次數(shù)，若是，輸出全局最優(yōu)解；否則，轉(zhuǎn)回到步驟9。

1.2 基于容差的搜索方向調(diào)整策略

在鴿群優(yōu)化算法地圖與指南針算子的迭代過程在，個體的速度和位置更新方式為

時，可以認為鴿群有可能會陷入局部最優(yōu)。式中：F（Xi）t為第i個個體在第t次迭代后的適應(yīng)度值；Xi為第i個個體的位置。但是不能直接判定鴿群一定會陷入局部最優(yōu)，因為在復(fù)雜優(yōu)化問題的求解過程中，第t次迭代后的全局最優(yōu)值Xgbest具有引導種群進化的潛力，在之后的迭代中有希望尋找到全局最優(yōu)值。因此，為了避免算法陷入局部最優(yōu)并充分利用Xgbest的進化潛力，本文提出了一個基于容差的搜索方向調(diào)整機制［20］。

定義一個容差T作為計數(shù)器，每當在一次迭代后，所有個體的最佳位置沒有變化，T就根據(jù)式（3）進行更新。

Prob＿adjust在每一次的迭代過程中更新一次，當滿足Prob＿adjust＞rand（）時，種群的搜索方向進行調(diào)整。種群不再使用當前全局最優(yōu)位置Xgbest，而轉(zhuǎn)向使用一個新候選者個體。

1.3 基于自學習的候選者生成策略

為了生成一個候選者來代替Xgbest在鴿群中的引導作用，本文提出了一種基于自學習的候選者生成策略。候選者的生成需要滿足以下要求：①要充分利用鴿群中每個個體的最優(yōu)位置信息；②要保證生成候選的候選者與全局最優(yōu)Xgbest具有相似的結(jié)構(gòu)。這種策略可以保證算法在每次的迭代過程中，充分利用每個個體的最優(yōu)解結(jié)構(gòu)，學習自身的優(yōu)勢。

為了使所生成的候選者能夠有效地利用鴿群中所有個體的最優(yōu)位置信息，并將種群引導出當前局部最優(yōu)，對候選者的定義為

式中：N為種群數(shù)量。

綜上所述，該策略充分利用了當前種群所有個體各自的個體最優(yōu)解結(jié)構(gòu)，保證了算法的尋優(yōu)能力。

1.4基于競爭學習的預(yù)測策略

當候選者生成之后，不能直接用候選者代替Xgbest。因為候選者引導種群跳出當前局部最優(yōu)的能力不一定比當前全局最優(yōu)強。因此，為了提高算法的利用率，本文提出了一種競爭學習策略來預(yù)測候選算法的潛在引導能力。候選者生成后，ALPIO算法將在下一次迭代中通過評價個體學習候選者和Xgbest的性能來預(yù)測其潛在的引導能力。這2種個體學習的速度更新將遵循以下規(guī)則。

2 仿真實驗

為了驗證ALPIO算法的有效性和處理復(fù)雜優(yōu)化問題的能力，在CEC2013基準測試函數(shù)［21］中分別選取2個單峰函數(shù)、4個多峰函數(shù)以及2個組合函數(shù)，在維度D＝10、30以及50的情況下分別與標準PIO、標準PSO和EGTPIO進行對比優(yōu)化實驗，如表1所示。

2.1 參數(shù)設(shè)置

本文通過對5種算法在不同維度下的測試函數(shù)進行優(yōu)化實驗，其參數(shù)設(shè)置如表2所示。其中，迭代次數(shù)以及種群數(shù)量隨著優(yōu)化函數(shù)維度的不同而不同；PSO 算法中的學習因子c1、c2按照文獻［22］推薦選擇。

表1 測試函數(shù)Tab1e 1 Test functions

表2 參數(shù)設(shè)置Tab1e 2 Parameter setting

2.2 實驗結(jié)果分析

為了直觀體現(xiàn)ALPIO算法的優(yōu)越性，選取同一個基準函數(shù)f17在不同維度（10維、30維和50維）下5個算法的迭代曲線。由圖2（a）～（c）可以看出，隨著搜索維度的增加，PIO、PSO以及EGTPIO容易過早收斂，陷入局部最優(yōu)值；SCPIO雖然最終也能搜索到全局最優(yōu)值，但在開始時會陷入局部最優(yōu)；ALPIO由于增加了種群多樣性，因此在每個維度下都能較快地收斂到全局最優(yōu)值。可以看出，ALPIO不僅具有較好的收斂精度和較強的全局搜索能力，而且在不同維度上都表現(xiàn)出了良好的性能，具有普遍適用性。

針對不同維度（10維、30維、50維）在8個基準測試函數(shù)上對ALPIO、PIO、PSO、SCPIO和EGTPIO進行51次獨立運行。這8個基準測試函數(shù)包含有單峰函數(shù)、多峰函數(shù)以及組合函數(shù)，因此具有一定的代表性，其測試結(jié)果能很好地顯示所有算法的性能。測試結(jié)果如表3～表5所示。下面的數(shù)據(jù)涵蓋尋優(yōu)結(jié)果的最好值、最差值、中位數(shù)、平均值以及方差；其中，均值越小表明算法的搜索能力越強，方差越小表明算法的穩(wěn)定性越強。

由數(shù)據(jù)可以看出，在不同維度下，ALPIO在所有的測試函數(shù)中都達到了最優(yōu)值并保證方差為0。在單峰函數(shù)上，ALPIO的性能明顯優(yōu)于PIO，在10維基準函數(shù)f18上的性能表現(xiàn)：ALPIO ＝SCPIO＞EGTPIO＞PIO＞PSO，隨著維度的增加，ALPIO仍然保持著性能上的優(yōu)勢；在多峰函數(shù)上，ALPIO的最好值、最差值、中位數(shù)、平均值以及方差要明顯優(yōu)于PIO和PSO，在不同維度基準函數(shù)f17上，ALPIO的各項性能都要優(yōu)于EGTPIO；在組合函數(shù)上，ALPIO的性能要優(yōu)于PIO和PSO，與SCPIO和EGTPIO在各方面的指標都相同。綜上所述，ALPIO在每個維度下都表現(xiàn)出了最優(yōu)性能。

圖2 D＝10，30，50時f17迭代曲線Fig.2 Iteration curves of f17 at D＝10，30，50

表3 D＝10時測試函數(shù)上算法的性能比較Tab1e 3 Performance comparison of a1gorithms on test functions at D＝10

表4 D＝30時測試函數(shù)上算法的性能比較Tab1e 4 Performance comparison of a1gorithms on test functions at D＝30

表5 D＝50時測試函數(shù)上算法的性能比較Tab1e 5 Performance comparison of a1gor ithms on test functions at D＝50

續(xù)表

3 結(jié) 論

針對標準PIO算法容易陷入局部最優(yōu)值這一問題，本文提出了一種基于自適應(yīng)學習策略的改進鴿群優(yōu)化（ALPIO）算法。

1）所提算法通過基于容差的搜索方向調(diào)整策略和基于自學習的候選者生成策略及時調(diào)整種群的搜索方向，增強種群多樣性和全局搜索能力，避免陷入局部最優(yōu)。

2）所提算法通過基于競爭學習的預(yù)測策略選擇具有更強領(lǐng)導能力的全局最優(yōu)，從而增強局部搜索能力。

3）在不同維度上的基準函數(shù)優(yōu)化實驗結(jié)果表明，與標準的PIO、PSO、CPIO以及最新的EGTPIO算法相比，ALPIO在解決復(fù)雜性優(yōu)化問題方面表現(xiàn)出明顯的優(yōu)勢；實驗結(jié)果表明，ALPIO不僅可以收斂到全局最優(yōu)，而且可以跳出局部最優(yōu)。