夏小剛,羅建婷,王 欣
(西安科技大學(xué) 理學(xué)院,陜西 西安 710054)
鴿群優(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í)際問題中[8-11],目前主要用于解決機(jī)器人、無(wú)人機(jī)路徑規(guī)劃問題等。鴿群優(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ī)劃問題。
雖然近年來(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ì)旅行商問題(traveling salesman problem,TSP)[18-19]的測(cè)試,驗(yàn)證了改進(jìn)的鴿群優(yōu)化算法有利于增加種群多樣性,避免算法過(guò)早陷入局部最優(yōu),能夠有效提高種群的收斂速度,增強(qiáng)算法的全局搜索能力。
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)
針對(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ù)γ表示變異算子的開發(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ù)。
模糊交叉變異算子有利于種群之間的信息交換,保證種群多樣性,擴(kuò)展種群的全局搜索范圍,據(jù)此在更新公式中引入模糊交叉變異算子,并提高算法的全局開發(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)化算法位置更新公式的修正。
本文提出的改進(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)算法流程圖
表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)行。
從表1可以看出: IPIO在f2、f7、f8、f10、f11、f13和f19均能收斂到理論最優(yōu)值。對(duì)于其他測(cè)試函數(shù),IPIO雖然沒有收斂到理論最優(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é)果。
本文算法參數(shù)仿真均以TSPLIB數(shù)據(jù)集中的dantzig42問題作為測(cè)試數(shù)據(jù),dantzig42問題是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問題,IPIO的求解精度優(yōu)于其他3種對(duì)比算法。除了單純的數(shù)據(jù),可以通過(guò)路徑仿真圖來(lái)模擬4種算法在實(shí)際中的最優(yōu)路徑效果。圖3給出了4種算法對(duì)dantzig42問題的路徑優(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é)果圖
(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)解。