一種正交對(duì)角化的磷蝦群算法

萬仁霞，張方星

(1. 北方民族大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院 寧夏 銀川 750021; 2. 寧夏智能信息與大數(shù)據(jù)處理重點(diǎn)實(shí)驗(yàn)室 寧夏 銀川 750021)

0 引言

最優(yōu)化是一門應(yīng)用相當(dāng)廣泛的學(xué)科，其目的是為討論決策問題的最佳選擇之特性構(gòu)造尋求最優(yōu)解的計(jì)算方法，并研究這些計(jì)算方法的理論性質(zhì)及實(shí)際表現(xiàn)[1]。優(yōu)化技術(shù)是以建立數(shù)學(xué)模型為基礎(chǔ),求解實(shí)際生活中的問題，以便得到最優(yōu)解為目的的應(yīng)用技術(shù)?，F(xiàn)實(shí)生活中普遍存在著優(yōu)化問題，包括線性、非線性、離散、連續(xù)等不同類型的問題。大部分問題都可以轉(zhuǎn)化為具有非確定性多項(xiàng)式難題(non-deterministic polynomial hard, NP-hard)的復(fù)雜優(yōu)化問題，使用傳統(tǒng)的方法已經(jīng)不能解決。因此，針對(duì)不同的優(yōu)化問題，各種類型的優(yōu)化算法應(yīng)運(yùn)而生。人類通過研究自然進(jìn)化和生物系統(tǒng)獲得靈感，并創(chuàng)造出元啟發(fā)式算法。例如人工蜂群算法[2]、螢火蟲算法[3]、布谷鳥算法[4]、蝙蝠群算法[5]、雞群優(yōu)化算法[6]、鳥群優(yōu)化算法[7]、粒子群算法[8]、蚱蜢優(yōu)化算法[9]等。

磷蝦群算法[10]是由Gandomi和Alavi在2012年提出的一種新型仿生物群智能算法,是對(duì)磷蝦的群體行為和群體智慧互動(dòng)的一種簡化，該算法模仿磷蝦群的3種基本行為：誘導(dǎo)運(yùn)動(dòng);覓食運(yùn)動(dòng);擾動(dòng)行為。通過這種群體智能解決最優(yōu)化問題。磷蝦群算法具有簡單、易實(shí)現(xiàn)、收斂性好、魯棒性強(qiáng)等優(yōu)點(diǎn)。在最近幾年里，研究學(xué)者改進(jìn)磷蝦群優(yōu)化算法取得了一些研究成果及經(jīng)驗(yàn)，這為磷蝦群優(yōu)化算法的發(fā)展提供了可靠的基礎(chǔ)，并為實(shí)際工程應(yīng)用指引了新的方向。文獻(xiàn)[11]提出一種混沌磷蝦群算法，采用singer map混沌映射生成慣性權(quán)重，同時(shí)加入精英策略，用全局最優(yōu)的個(gè)體替換最差個(gè)體，提高了全局最優(yōu)的可靠性和解的質(zhì)量。文獻(xiàn)[12]提出一種基于自然選擇和隨機(jī)擾動(dòng)的改進(jìn)磷蝦群算法。該算法采用非線性遞減策略計(jì)算誘導(dǎo)權(quán)重和覓食權(quán)重,并在產(chǎn)生新一代磷蝦種群時(shí)加入隨機(jī)擾動(dòng)因子,從而有效提升磷蝦種群中個(gè)體的質(zhì)量,并提高了全局搜索和局部勘探能力。文獻(xiàn)[13]是將布谷鳥算法與磷蝦群算法結(jié)合，采用貪心選擇方案。該算法在每次迭代結(jié)束后，丟棄一部分最差的磷蝦，并用隨機(jī)生成的新磷蝦來代替，從而保持了種群的多樣性，并且提高了算法的尋優(yōu)能力。

盡管磷蝦群算法的研究已取得許多重要進(jìn)展，但磷蝦群算法具有易陷入局部最優(yōu)、收斂速度慢等不足，因此，針對(duì)磷蝦群算法的改進(jìn)研究已成為一個(gè)重要的課題。本文采用正交對(duì)角化策略來處理磷蝦個(gè)體的位置更新，可以較好地改善磷蝦群算法不足。

1 磷蝦群算法

磷蝦群算法(krill herd, KH)是一種新的啟發(fā)式智能優(yōu)化算法。該算法位置更新主要受到誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)擴(kuò)散3個(gè)因素影響。

磷蝦個(gè)體的更新速度公式采用拉格朗日模型：

(1)

其中：Ni、Fi、Di分別代表誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)擴(kuò)散。

3個(gè)因素的計(jì)算公式為：

(2)

(3)

(4)

其中：Nmax、Vf、Dmax分別表示最大誘導(dǎo)速度、最大覓食速度、最大擴(kuò)散運(yùn)動(dòng)；αi、βi、δ分別表示誘導(dǎo)方向、覓食方向、擴(kuò)散方向；wn、wf分別表示誘導(dǎo)權(quán)重和覓食權(quán)重；t、tmax分別表示當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

磷蝦群的位置更新公式為

(5)

(6)

其中：Δt、Ct、Nv分別表示速度向量的縮放因子、步長因子、變量數(shù)；UBj、LBj分別表示第j個(gè)變量的上界和下界。

2 正交對(duì)角化的磷蝦群算法

正交策略是信息處理的一種重要方法,它通過構(gòu)建一個(gè)非常有效和有前途的范例來引導(dǎo)個(gè)體朝著更好的方向飛行，其適用于拓?fù)浣Y(jié)構(gòu)的特點(diǎn)已引起了學(xué)術(shù)界的廣泛關(guān)注。文獻(xiàn)[14-16]分別將正交策略用于人工蜂群算法、遺傳算法和粒子群算法。本文通過更新正交對(duì)角化矩陣來更新磷蝦個(gè)體位置，提出一種正交對(duì)角化的磷蝦群算法(orthogonal diagonalization krill herd, ODKH)。

2.1 正交對(duì)角化過程

在ODKH中，正交對(duì)角化是將3個(gè)矩陣的乘法轉(zhuǎn)化為一個(gè)對(duì)角矩陣，用于更新磷蝦個(gè)體的速度和位置。更新時(shí)，磷蝦的速度和位置向量只受矩陣的對(duì)角元素的影響。

矩陣對(duì)角化是將方陣B(d×d)轉(zhuǎn)換為對(duì)角矩陣E(d×d)的過程，步驟為

B=QEQ-1，

(7)

其中：矩陣Q是一個(gè)可逆矩陣，由矩陣B的特征向量組成的矩陣；矩陣E的對(duì)角元素包含相應(yīng)的特征值。

當(dāng)B是對(duì)稱矩陣時(shí)，式(7)可以寫成

B=CEC-1，

(8)

其中矩陣C的列向量彼此正交。

式(8)又可以寫為

E=C-1BC。

(9)

由于矩陣C是一個(gè)標(biāo)準(zhǔn)正交矩陣，式(9)可以寫成

E=CTBC。

(10)

2.2 ODKH學(xué)習(xí)過程

一個(gè)有m個(gè)磷蝦的群體，每個(gè)磷蝦的維數(shù)為d(m>d)。在每次迭代中，先將m個(gè)磷蝦分為兩組，其中第一組是位置最優(yōu)的前d個(gè)磷蝦，第二組是剩下的(m-d)個(gè)磷蝦；再將第一組磷蝦進(jìn)行正交對(duì)角化，得到矩陣B，然后計(jì)算標(biāo)準(zhǔn)正交矩陣C和對(duì)角矩陣E；最后通過矩陣E來更新所有磷蝦的位置。第二組是剩下的(m-d)個(gè)磷蝦按傳統(tǒng)磷蝦群算法進(jìn)行位置更新。由于確定了最優(yōu)位置，考慮了兩組中所有m個(gè)磷蝦的貢獻(xiàn)，從而保持了種群的多樣性。

2.3 ODKH算法

ODKH算法步驟如下。

步驟1 隨機(jī)產(chǎn)生m個(gè)磷蝦，并初始化其速度向量和位置向量；

步驟2 計(jì)算當(dāng)前目標(biāo)函數(shù)值，并將當(dāng)前磷蝦個(gè)體的位置和目標(biāo)函數(shù)值儲(chǔ)存在各個(gè)最優(yōu)Pbest中，將最優(yōu)Pbest儲(chǔ)存在全局最優(yōu)Gbest中；

步驟3 根據(jù)適應(yīng)度函數(shù)值(目標(biāo)函數(shù)值)按升序排列m個(gè)磷蝦位置向量；

步驟4 根據(jù)步驟3排好的順序構(gòu)造矩陣A，其大小為(m×d)；

步驟5 截取矩陣A的前d行，得大小為(d×d)的方陣B；

步驟6 對(duì)矩陣B進(jìn)行正交對(duì)角化，得到大小為(d×d)的對(duì)角矩陣E；

步驟7 更新m個(gè)磷蝦的位置：

1)i=1,2，…，d，Xi(t+1)=Xi(t)+r(Ei(t)-Xi(t))+Di，Di=wε·ones；

2)i=d+1，d+2,…，m。

磷蝦的位置按公式(5)和(6)更新，其中：r為[0,1]之間的隨機(jī)數(shù)；w為權(quán)值；ε是均值為0、標(biāo)準(zhǔn)方差為1的滿足高斯擾動(dòng)的隨機(jī)數(shù)；

步驟8 比較當(dāng)前的Pbest和Gbest，并更新Pbest和Gbest；

步驟9 若滿足中止條件(迭代次數(shù))，則停止，輸出結(jié)果。否則，返回步驟2。

由于參與正交化的磷蝦個(gè)數(shù)是與磷蝦的數(shù)據(jù)維數(shù)關(guān)聯(lián)的，步驟7的2)確保在數(shù)據(jù)維數(shù)較小情況下，算法也能保證尋優(yōu)過程的開展。實(shí)際上，當(dāng)d=1時(shí)，算法退化為傳統(tǒng)磷蝦群算法。

3 實(shí)驗(yàn)分析

3.1 測(cè)試函數(shù)及測(cè)試結(jié)果

為了驗(yàn)證ODKH算法的性能，本文將ODKH算法與KH算法、CSKH算法[13]進(jìn)行比較。分別對(duì)12個(gè)典型的標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行30次數(shù)值實(shí)驗(yàn)，f1～f3為單峰函數(shù)，f4～f12為多峰函數(shù),其中f7～f9是低維多峰函數(shù)。f1～f3分別為Sphere、Sum squares和Zakharov函數(shù)，f4～f12分別為Rastrigin、Ackley、Griewank、Bukin、Drop-wave、Eggholder、Penalty #1、Penalty #2和Schwefel 2.22函數(shù)。為了保證實(shí)驗(yàn)的公平性，種群規(guī)模設(shè)置為m=35，維數(shù)d=30，權(quán)值w=0.01，迭代次數(shù)為1 000次。KH算法、CSKH算法分別采用文獻(xiàn)[17]、文獻(xiàn)[13]中的方法設(shè)置參數(shù)。每種算法在函數(shù)上運(yùn)行30次，并統(tǒng)計(jì)最小值、最大值、平均值、方差和運(yùn)行時(shí)間這5項(xiàng)數(shù)值的平均值。表1和表2分別為測(cè)試函數(shù)及其結(jié)果。

表1 測(cè)試函數(shù)Table 1 The Function

為了更加直觀地展現(xiàn)算法的優(yōu)越性，本文通過3個(gè)算法的收斂曲線圖來進(jìn)一步說明算法性能，圖1～12分別對(duì)應(yīng)上述12種函數(shù)尋優(yōu)測(cè)試結(jié)果(圖中為取對(duì)數(shù)后的結(jié)果)。

3.2 結(jié)果分析

通過表2和圖1～12可以看出，ODKH算法在處理高維單峰和多峰函數(shù)時(shí)，效果顯著；處理低維多峰函數(shù)時(shí)效果也要比其他兩種算法好。通過圖1～6和圖10～12可以看出，ODKH算法收斂速度明顯優(yōu)于其他兩種算法。通過表2還可以看出ODKH算法的運(yùn)行時(shí)間比其他兩種算法短，具有更好的時(shí)間效率和尋優(yōu)穩(wěn)定性。

表2 函數(shù)測(cè)試結(jié)果Table 2 The results on function

圖1 f1收斂曲線圖Figure 1 f1 convergence curve

圖2 f2收斂曲線圖Figure 2 f2 convergence curve

圖3 f3收斂曲線圖Figure 3 f3 convergence curve

圖4 f4收斂曲線圖Figure 4 f4 convergence curve

圖5 f5收斂曲線圖Figure 5 f5 convergence curve

圖6 f6收斂曲線圖Figure 6 f6 convergence curve

圖7 f7收斂曲線圖Figure 7 f7 convergence curve

圖8 f8收斂曲線圖Figure 8 f8 convergence curve

圖9 f9收斂曲線圖Figure 9 f9 convergence curve

圖10 f10收斂曲線圖Figure 10 f10 convergence curve

圖11 f11收斂曲線圖Figure 11 f11 convergence curve

圖12 f12收斂曲線圖Figure 12 f12 convergence curve

實(shí)驗(yàn)表明，ODKH算法尋優(yōu)能力、收斂速度方面較優(yōu)于其他兩種算法，在處理高維函數(shù)中收斂速度明顯優(yōu)于其他算法。

綜上所述，對(duì)比同類算法，ODKH算法具有魯棒性較強(qiáng)、求解精度較高、運(yùn)行時(shí)間短等特點(diǎn)，同時(shí)有著較穩(wěn)定的全局搜索能力。

4 結(jié)束語

為了解決磷蝦群算法容易陷入局部最優(yōu)、收斂速度慢的問題，本文提出一種正交對(duì)角化的磷蝦群算法。數(shù)值實(shí)驗(yàn)對(duì)比表明，本文提出的算法在處理單峰函數(shù)和多峰函數(shù)時(shí)，在尋優(yōu)精度和速度上都具有較明顯優(yōu)勢(shì)，尤其在對(duì)高維函數(shù)的尋優(yōu)中具有顯著的收斂能力和穩(wěn)定性。