胡耀龍，馮強(qiáng)，海星朔，任羿

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

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

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

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

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

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

1.1 ALPIO算法描述

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

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

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

步驟3 操作地圖與指南針?biāo)阕印８聜€(gè)體的速度和位置，更新全局最優(yōu)和個(gè)體歷史最優(yōu)。

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

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

步驟6 使用基于競(jìng)爭(zhēng)學(xué)習(xí)的預(yù)測(cè)策略從候選者和當(dāng)前全局最優(yōu)中選取較優(yōu)的作為新的全局最優(yōu)。

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

步驟8 判斷是否達(dá)到地圖與指南針?biāo)阕拥淖畲蟮螖?shù)，若是，轉(zhuǎn)到下一個(gè)操作；否則，轉(zhuǎn)回到步驟3。

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

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

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

在鴿群優(yōu)化算法地圖與指南針?biāo)阕拥牡^(guò)程在，個(gè)體的速度和位置更新方式為

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

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

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

1.3 基于自學(xué)習(xí)的候選者生成策略

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

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

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

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

1.4基于競(jìng)爭(zhēng)學(xué)習(xí)的預(yù)測(cè)策略

當(dāng)候選者生成之后，不能直接用候選者代替Xgbest。因?yàn)楹蜻x者引導(dǎo)種群跳出當(dāng)前局部最優(yōu)的能力不一定比當(dāng)前全局最優(yōu)強(qiáng)。因此，為了提高算法的利用率，本文提出了一種競(jìng)爭(zhēng)學(xué)習(xí)策略來(lái)預(yù)測(cè)候選算法的潛在引導(dǎo)能力。候選者生成后，ALPIO算法將在下一次迭代中通過(guò)評(píng)價(jià)個(gè)體學(xué)習(xí)候選者和Xgbest的性能來(lái)預(yù)測(cè)其潛在的引導(dǎo)能力。這2種個(gè)體學(xué)習(xí)的速度更新將遵循以下規(guī)則。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

續(xù)表

3 結(jié) 論

針對(duì)標(biāo)準(zhǔn)PIO算法容易陷入局部最優(yōu)值這一問(wèn)題，本文提出了一種基于自適應(yīng)學(xué)習(xí)策略的改進(jìn)鴿群優(yōu)化（ALPIO）算法。

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

2）所提算法通過(guò)基于競(jìng)爭(zhēng)學(xué)習(xí)的預(yù)測(cè)策略選擇具有更強(qiáng)領(lǐng)導(dǎo)能力的全局最優(yōu)，從而增強(qiáng)局部搜索能力。

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