模糊變異算子的改進(jìn)鴿群優(yōu)化算法

夏小剛，羅建婷，王 欣

(西安科技大學(xué) 理學(xué)院，陜西 西安 710054)

0 引言

鴿群優(yōu)化算法(pigeon-inspired optimization, PIO)是文獻(xiàn)[1]在2014年提出的一種模擬鴿子歸巢行為的新型群體智能優(yōu)化算法。當(dāng)前鴿群優(yōu)化算法研究主要集中在優(yōu)化算法改進(jìn)、理論研究和工程應(yīng)用3個(gè)方面。優(yōu)化算法改進(jìn)即通過(guò)對(duì)算法中2個(gè)相互獨(dú)立的迭代部分進(jìn)行研究進(jìn)而實(shí)現(xiàn)算法改進(jìn)[2-4]； 理論研究即進(jìn)一步完善算法的理論基礎(chǔ)[5-7]； 而工程應(yīng)用即將算法應(yīng)用于解決工程實(shí)際問(wèn)題中[8-11]，目前主要用于解決機(jī)器人、無(wú)人機(jī)路徑規(guī)劃問(wèn)題等。鴿群優(yōu)化算法雖然收斂速度快，但鴿群信息之間交互不足，且易于早熟收斂、陷入局部最優(yōu)[12]。為此，文獻(xiàn)[13]采用鞏固參數(shù)簡(jiǎn)化傳統(tǒng)鴿群優(yōu)化算法的結(jié)構(gòu)，實(shí)現(xiàn)了兩個(gè)算子的平滑過(guò)渡，又將自組織映射與改進(jìn)的鴿群優(yōu)化算法相結(jié)合，更好地控制決策空間并找到解的當(dāng)前分布。文獻(xiàn)[14]將延遲因子引入位置更新公式，提高了鴿群優(yōu)化算法的收斂速度。文獻(xiàn)[15]將鴿群優(yōu)化算法引入到粒子波算法中，從而提高了粒子波算法的精度和穩(wěn)定性。文獻(xiàn)[16-17]將鴿群優(yōu)化算法與其他算法相融合，相互補(bǔ)充和促進(jìn)，形成的混合優(yōu)化算法可更好地解決無(wú)人機(jī)路徑規(guī)劃問(wèn)題。

雖然近年來(lái)在鴿群優(yōu)化算法改進(jìn)方面取得了一定的研究成果，但優(yōu)化算法仍存在位置更新公式全局搜索能力弱、多樣性欠佳等不足。本文受差分進(jìn)化算法(differential evolution, DE)的啟發(fā)，在地圖和指南針?biāo)阕优c地標(biāo)算子的位置更新公式中引入模糊交叉變異算子，提出了一種改進(jìn)的鴿群優(yōu)化(improved pigeon-inspired optimization，IPIO)算法。借助仿真實(shí)驗(yàn)和對(duì)旅行商問(wèn)題(traveling salesman problem,TSP)[18-19]的測(cè)試，驗(yàn)證了改進(jìn)的鴿群優(yōu)化算法有利于增加種群多樣性，避免算法過(guò)早陷入局部最優(yōu)，能夠有效提高種群的收斂速度，增強(qiáng)算法的全局搜索能力。

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

1.1 鴿群優(yōu)化算法的基本理論

PIO主要由兩個(gè)算子構(gòu)成：地圖和指南針?biāo)阕?，地?biāo)算子。在地圖和指南針?biāo)阕又?，由?1)和式(2)確定第i只鴿子在第t次迭代中的位置Xi和速度Vi：

Xi(t)=Xi(t-1)+Vi(t)；

(1)

Vi(t)=Vi(t-1)·e-Rt+rand·(Xg-Xi(t-1))，

(2)

其中：R為地圖和指南針因子；rand∈[0,1]；Xg為第t次迭代中的最好位置；Vi(t)為第t次鴿子的當(dāng)前速度；Xi(t)為第i只鴿子在第t次迭代中的當(dāng)前位置。

在地標(biāo)算子中，每一代鴿子的數(shù)量都會(huì)減少1/2，用Np來(lái)記錄每一代鴿子的數(shù)量。排序接近目的地的鴿子根據(jù)式(4)計(jì)算剩余鴿子的中心位置，以此作為地標(biāo)來(lái)更新自己的位置。

(3)

(4)

其中：Np(t)為第t代鴿群的數(shù)量；Xc(t)是第t代鴿子飛近目的地時(shí)作為參考方向的中心位置(期望目的地)；Fitness(Xi(t))是適應(yīng)度值，對(duì)每只鴿子的適應(yīng)度值[16]進(jìn)行評(píng)估并排序，找到最優(yōu)路徑。式(5)對(duì)鴿群位置進(jìn)行越界處理，更新鴿群位置。

Xi(t)=Xi(t-1)+rand·(Xc(t)-Xi(t-1))。

(5)

1.2 模糊交叉變異的實(shí)現(xiàn)

針對(duì)種群中的每一個(gè)體Xi=(xi,1,xi,2,…,xi,n)，由模糊變異式(6)進(jìn)行變異操作：

Wi=γ·xr1+(1-γ)·F·(xr2-xr3)，

(6)

其中：xr1為當(dāng)前種群中適應(yīng)度值最好的個(gè)體；xr2和xr3為群體中隨機(jī)選取的個(gè)體；F∈[0,2]為比例因子，比例因子F保證了種群的多樣性和搜索能力，大多數(shù)函數(shù)F的最優(yōu)值為0.5～1.0；γ∈[0,1]為模糊參數(shù)，模糊參數(shù)γ表示變異算子的開(kāi)發(fā)和貪婪程度，用于擴(kuò)大局部和全局搜索能力[20]。

依據(jù)式(6)得到的變異種群Qi=(qi,1,qi,2,…,qi,n)，由式(7)進(jìn)行交叉操作，得到新的種群Mi=(mr,1,mr,2,…,mr,n)。對(duì)排序接近目的地的鴿子進(jìn)行越界處理，若Mi支配Xi,則用Mi代替Xi；若Xi支配Mi，則直接丟棄Mi。若互不支配，則將Mi加入Xi。交叉公式為：

(7)

其中：CR為交叉概率，取值(0,1)，即randβ∈(0,1)；β是在{1,2，…，n}中隨機(jī)選取的數(shù)。

1.3 位置更新公式的修正

模糊交叉變異算子有利于種群之間的信息交換，保證種群多樣性，擴(kuò)展種群的全局搜索范圍，據(jù)此在更新公式中引入模糊交叉變異算子，并提高算法的全局開(kāi)發(fā)能力和局部搜索能力。通過(guò)隨機(jī)選擇解空間中的個(gè)體來(lái)調(diào)節(jié)鴿子的位置，從而增強(qiáng)群體的多樣性和全局探索能力。

改進(jìn)的鴿群優(yōu)化算法的地圖和指南針?biāo)阕拥奈恢酶鹿綖椋?/p>

Xi(t)=Xi(t-1)+Vi(t)+Wi，

(8)

地標(biāo)算子的位置更新公式為：

Xi(t)=Xi(t-1)+rand·(Xc(t-1)-Xi(t-1))+Wi，

(9)

其中：Wi為模糊交叉變異算子。由式(8)和式(9)可以看出：與式(1)和式(5)相比，式(8)和式(9)增加了模糊交叉變異算子，從而達(dá)到對(duì)傳統(tǒng)鴿群優(yōu)化算法位置更新公式的修正。

1.4 改進(jìn)鴿群優(yōu)化算法流程圖

本文提出的改進(jìn)算法流程圖如圖1所示。根據(jù)式(2)和式(5)可以看出，傳統(tǒng)鴿群優(yōu)化算法的位置更新公式只考慮了鴿子的當(dāng)前位置和鴿群最優(yōu)位置，由鴿群最優(yōu)位置進(jìn)行搜索，忽略了算法的搜索能力。受差分進(jìn)化算法的啟發(fā)，在傳統(tǒng)鴿群優(yōu)化算法中的位置更新公式中引入模糊交叉變異算子，位置更新公式的修正如式(8)和式(9)所示，引導(dǎo)種群變異，增加種群的多樣性，提高算法的全局搜索能力。

圖1 改進(jìn)算法流程圖

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

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

表1給出DE、粒子群算法(particle swarm optimization，PSO)、PIO、IPIO這4種算法在19個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)中分別進(jìn)行20次實(shí)驗(yàn)的結(jié)果，分別記錄4種算法的最優(yōu)適應(yīng)度值(Optimal)、平均適應(yīng)度值(Mean)和方差(Variane)。其中，最優(yōu)適應(yīng)度值反映解的質(zhì)量；平均適應(yīng)度值反映算法的收斂速度；方差反映算法的穩(wěn)定性和魯棒性。將表1中最優(yōu)適應(yīng)度值和平均適應(yīng)度值達(dá)到理論最優(yōu)值的數(shù)據(jù)均標(biāo)注為粗體，最優(yōu)個(gè)數(shù)表示達(dá)到最優(yōu)適應(yīng)度值及平均最優(yōu)適應(yīng)度值的個(gè)數(shù)。19個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)即Schwefel’s problem 2.22(f1)、Sphere(f2)、Schwefel 2.21(f3)、Rosenbrock(f4)、Step(f5)、Quartic(f6)、Goldstein-Price(f7)、Hartmann 6-Dimensional(f8)、Shekel(f9)、Generalized Schwefel’s(f10)、Rastrigin(f11)、Ackley(f12)、Griewank(f13)、Levy(f14)、Levy n.13(f15)、De Gong Function n.5(f16)、Kowalik(f17)、Camel(f18)、Branin(f19)。其中，f1～f9是單峰函數(shù)，f10～f19是多峰函數(shù)。實(shí)驗(yàn)中4種算法參數(shù)設(shè)置如下：種群規(guī)模50，最大迭代次數(shù)為1 000，比例因子設(shè)為0.5[21]，模糊參數(shù)設(shè)為0.5。實(shí)驗(yàn)在MATLAB2018b軟件中進(jìn)行編程運(yùn)行。

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

從表1可以看出： IPIO在f2、f7、f8、f10、f11、f13和f19均能收斂到理論最優(yōu)值。對(duì)于其他測(cè)試函數(shù)，IPIO雖然沒(méi)有收斂到理論最優(yōu)值，但其獲取的適應(yīng)度值與理論最優(yōu)值十分接近。對(duì)于函數(shù)f7、f18和f19，4種算法都能取得相同的理論最優(yōu)值。對(duì)于函數(shù)f5，傳統(tǒng)PIO取得了理論最優(yōu)值。此外，DE有3個(gè)測(cè)試函數(shù)取得理論最優(yōu)值，PSO有4個(gè)測(cè)試函數(shù)取得理論最優(yōu)值。DE與PSO相比，尋優(yōu)能力差不多，雖然DE和PSO求解最優(yōu)適應(yīng)度方面效果較差，但2個(gè)算法的穩(wěn)定性較好。IPIO獲取的尋優(yōu)個(gè)數(shù)為18個(gè)，尋優(yōu)率達(dá)到了94.7%，相較于傳統(tǒng)PIO尋優(yōu)個(gè)數(shù)提高了9個(gè)，尋優(yōu)率提升了47.3%，取得了較好的最優(yōu)適應(yīng)度值、平均適應(yīng)度值和方差，尋優(yōu)能力均優(yōu)于其他3種對(duì)比算法。

表1 4種算法在標(biāo)準(zhǔn)測(cè)試函數(shù)中適應(yīng)度值比較

選出具有代表性的3個(gè)測(cè)試函數(shù)f8、f9、f10，4種算法在測(cè)試函數(shù)上的收斂曲線如圖2所示。

(a) f8的收斂曲線 (b) f9的收斂曲線 (c) f10的收斂曲線

圖2a表明：在求解函數(shù)f8時(shí)，4條曲線均為先快速下降，在50次至200次迭代后趨于穩(wěn)定，PIO雖然在200次迭代后跳出局部最優(yōu)，但求解精度不如其他3種對(duì)比算法。DE和PSO在前期收斂速度較快，但后期均陷入局部最優(yōu)。IPIO收斂速度不僅快，而且比其他3種算法的求解精度高。圖2b表明：在求解函數(shù)f9時(shí)，其他3種函數(shù)都過(guò)早地陷入局部最優(yōu)，IPIO在早期收斂速度較慢，但分別在200次和700次迭代后跳出局部最優(yōu)，因此可以得出IPIO的求解精度相比其他3種算法有了顯著提高。圖2c表明：在求解函數(shù)f10時(shí)，PSO過(guò)早地陷入局部收斂，DE和PIO前期下降速度幾乎相同，PIO和IPIO都在700次迭代后跳出局部最優(yōu)，但I(xiàn)PIO得到一個(gè)更好的適應(yīng)度值。IPIO顯然比其他3種算法求解精度高，且有效地避免算法陷入早熟收斂，可得到較好的結(jié)果。

3 改進(jìn)鴿群優(yōu)化算法求解旅行商問(wèn)題

本文算法參數(shù)仿真均以TSPLIB數(shù)據(jù)集中的dantzig42問(wèn)題作為測(cè)試數(shù)據(jù)，dantzig42問(wèn)題是TSPLIB數(shù)據(jù)集中的一個(gè)數(shù)據(jù)文件，城市規(guī)模為42，已知最優(yōu)解為699，運(yùn)行10次。IPIO與其他3種對(duì)比算法的仿真實(shí)驗(yàn)結(jié)果如表2所示。

由表2可以看出：無(wú)論是平均最優(yōu)值還是相對(duì)誤差，改進(jìn)算法均優(yōu)于其他3種對(duì)比算法。在10次仿真結(jié)果中，IPIO有3次仿真實(shí)驗(yàn)達(dá)到理論最優(yōu)解，平均最優(yōu)值為700.3，且大多數(shù)數(shù)據(jù)都集中在最優(yōu)解范圍內(nèi)，相對(duì)誤差為0.19%。這表明對(duì)于dantzig42問(wèn)題，IPIO的求解精度優(yōu)于其他3種對(duì)比算法。除了單純的數(shù)據(jù)，可以通過(guò)路徑仿真圖來(lái)模擬4種算法在實(shí)際中的最優(yōu)路徑效果。圖3給出了4種算法對(duì)dantzig42問(wèn)題的路徑優(yōu)化結(jié)果圖，根據(jù)路徑圖的線路復(fù)雜程度可以看出IPIO較其他3種對(duì)比算法效果更好。

表2 4種算法仿真實(shí)驗(yàn)結(jié)果對(duì)比

(a) DE優(yōu)化結(jié)果圖 (b) PSO優(yōu)化結(jié)果圖

4 結(jié)論

(1)IPIO在平均適應(yīng)度值方面優(yōu)于DE、PSO和PIO。IPIO在尋找最優(yōu)適應(yīng)度值方面優(yōu)于DE、PSO和PIO。

(2)IPIO能夠跳出局部最優(yōu)，避免早熟收斂，增強(qiáng)算法的全局搜索能力。

(3)IPIO能有效提高TSP的最優(yōu)解。