基于萊維飛行和高斯分布的改進(jìn)教與學(xué)算法

付 帥，張曉霞，楊 嬌，胡銀銀

（遼寧科技大學(xué) 計(jì)算機(jī)與軟件工程學(xué)院，遼寧 鞍山 114051）

無論是在科學(xué)研究領(lǐng)域還是在許多實(shí)際問題應(yīng)用中，優(yōu)化問題存在十分廣泛，是一個(gè)非常重要的研究?jī)?nèi)容。針對(duì)不同的優(yōu)化問題，優(yōu)化算法有很多，傳統(tǒng)的優(yōu)化算法有拉格朗日乘數(shù)、單純形法、梯度下降法等。隨著互聯(lián)網(wǎng)技術(shù)以及優(yōu)化技術(shù)的不斷發(fā)展，在自然選擇和群體遺傳學(xué)原理的啟發(fā)下，越來越多群智能優(yōu)化算法應(yīng)用在優(yōu)化問題中。群智能優(yōu)化算法是一種模擬自然界動(dòng)物各種群體行為的隨機(jī)搜索算法，主要利用群體中個(gè)體之間的競(jìng)爭(zhēng)和合作近似求解一些難以直接求解的優(yōu)化問題。近年來，智能優(yōu)化算法解決優(yōu)化問題成為研究熱點(diǎn)，其中教與學(xué)優(yōu)化算法（Teachinglearning-based optimization algorithm，TLBO）被廣泛應(yīng)用于各種優(yōu)化問題的全局最優(yōu)解中。

TLBO算法［1］是Rao等提出的一種新的連續(xù)隨機(jī)群智能優(yōu)化算法，是受學(xué)校課堂環(huán)境中老師教學(xué)和學(xué)生學(xué)習(xí)過程啟發(fā)而提出的。與遺傳算法［2］和差分算法［3］相比，TLBO通過計(jì)算適應(yīng)度值選擇出種群中最優(yōu)的個(gè)體，引導(dǎo)整個(gè)種群進(jìn)入教師階段，提高了收斂速度。與粒子群算法［4］的單一算子相比，TLBO在教學(xué)階段完成后引入了另一個(gè)學(xué)習(xí)階段，增強(qiáng)了種群多樣性，提高了算法的開發(fā)能力。與其他算法相比，TLBO算法還具有很多優(yōu)點(diǎn)，算法原理簡(jiǎn)單易懂，除了種群大小和收斂準(zhǔn)則外，不需要調(diào)節(jié)任何參數(shù)；求解速度快，精度高且能快速收斂到全局最優(yōu)，特別在參數(shù)復(fù)雜的優(yōu)化問題中效果更為明顯［5］。目前被廣泛應(yīng)用于各種優(yōu)化問題的全局最優(yōu)解，如數(shù)字無限脈沖響應(yīng)濾波器設(shè)計(jì)中的參數(shù)識(shí)別問題［6］，具有模糊處理時(shí)間的柔性作業(yè)車間問題［7］，以及PID控制器設(shè)計(jì)問題［8］等。然而，與其他智能優(yōu)化算法一樣，TLBO算法隨著迭代次數(shù)的增加，容易陷入局部最優(yōu)，出現(xiàn)早熟收斂現(xiàn)象，導(dǎo)致種群缺少多樣性，對(duì)求解精度和收斂速度也會(huì)有一定影響。對(duì)于這些缺點(diǎn)，可以有很多辦法對(duì)其進(jìn)行改進(jìn)，比如改進(jìn)算法教學(xué)因子、優(yōu)化算法的學(xué)習(xí)階段、尋找其他合適的優(yōu)化智能算法與經(jīng)典教與學(xué)算法結(jié)合等等。

本文提出一種改進(jìn)的TLBO算法，一方面將原有的TLBO算法與萊維飛行策略相融合，萊維飛行策略是一個(gè)符合萊維分布的隨機(jī)游走的過程，具有很強(qiáng)的跳躍能力，可以使算法在教學(xué)階段前期增強(qiáng)老師的學(xué)習(xí)能力，選擇出教學(xué)能力突出的老師。另一方面，在學(xué)習(xí)階段加入高斯分布局部搜索算子，引導(dǎo)學(xué)生進(jìn)行自學(xué)習(xí)模式，高斯分布主要是對(duì)班級(jí)中某一維度進(jìn)行搜索，從而增強(qiáng)算法單維搜索能力和收斂速度。在TLBO算法進(jìn)化更新過程中引入這兩種策略，可以使改進(jìn)后的算法不僅提高基本教與學(xué)算法的有效性，而且增加了種群的多樣性，能夠使算法易跳出局部最優(yōu)，找到全局最優(yōu)。

1 TLBO算法

TLBO算法分為2個(gè)階段：教學(xué)階段與學(xué)習(xí)階段。在教學(xué)階段，老師通過向?qū)W生傳授知識(shí)將學(xué)生成績(jī)接近自己水平，進(jìn)而提升整個(gè)班級(jí)學(xué)生的平均成績(jī)。在學(xué)習(xí)階段，學(xué)生之間通過取長(zhǎng)補(bǔ)短互相學(xué)習(xí)，獲取更多知識(shí)，提高自己的成績(jī)。TLBO種群中的個(gè)體為算法中的老師和學(xué)生，搜索空間中的每個(gè)種群是每個(gè)班級(jí)，種群的規(guī)模是班級(jí)里的人數(shù)，每個(gè)學(xué)生所學(xué)的某一科目相當(dāng)于一個(gè)決策變量，學(xué)習(xí)成績(jī)代表優(yōu)化算法中的適應(yīng)度，老師是種群適應(yīng)度值最好的個(gè)體，代表最優(yōu)解。

1.1 教學(xué)階段

教學(xué)階段主要模擬老師課堂教學(xué)過程，班級(jí)中的每名學(xué)生都會(huì)聽老師授課，老師會(huì)向?qū)W生分享自己的知識(shí)，學(xué)生根據(jù)老師和學(xué)生的平均值之間進(jìn)行差異性學(xué)習(xí)。

（1）計(jì)算教師跟平均值之間的差距值Different

式中：Xteacher表示教師；rand為學(xué)習(xí)步長(zhǎng)，表示［0，1］之間的隨機(jī)數(shù)；教學(xué)因子TF=round(1+rand(0,1))；Xmean表示所有學(xué)生的平均值。

（2）學(xué)生通過差距值Different向老師靠攏，則

式中：Xinew表示第i個(gè)學(xué)生Xi教學(xué)之后的值；Xiold表示第i個(gè)學(xué)生Xi教學(xué)之前的值。

1.2 學(xué)習(xí)階段

學(xué)習(xí)階段是模擬學(xué)生相互學(xué)習(xí)的過程，在課堂上，學(xué)生不僅會(huì)向老師學(xué)習(xí)，學(xué)生與學(xué)生之間也會(huì)相互交流學(xué)習(xí)，進(jìn)而提高自己的成績(jī)，種群多樣性得到提高。學(xué)生之間的交流合作增強(qiáng)了TLBO算法的探索能力。學(xué)生通過在班級(jí)中隨機(jī)選取一個(gè)學(xué)習(xí)對(duì)象來進(jìn)行學(xué)習(xí)

式中：j=1,2,…,N P,j≠i；Xinew表示第i個(gè)學(xué)生Xi學(xué)習(xí)后的值；Xiold表示第i個(gè)學(xué)生Xi學(xué)習(xí)前的值；Xj表示隨機(jī)選取的第j個(gè)學(xué)生。

TLBO算法流程圖如圖1所示。

圖1 TLBO算法流程圖Fig.1 Flow chart of TLBO algorithm

根據(jù)上述定義的原則和策略模式，將TLBO算法的步驟轉(zhuǎn)換為圖2所示的偽代碼。

圖2 TLBO算法偽代碼Fig.2 Pseudo-code of TLBO algorithm

2 萊維飛行機(jī)制和高斯分布

2.1 萊維飛行

萊維（Levy）飛行以法國(guó)數(shù)學(xué)家保羅·萊維命名，運(yùn)動(dòng)軌跡可以時(shí)不時(shí)飛行，因此命名為萊維飛行。Levy飛行實(shí)質(zhì)上就是服從萊維分布的隨機(jī)搜索路徑，特點(diǎn)是在隨機(jī)行走的過程中有相對(duì)較高的概率出現(xiàn)大跨步，保證游走不止局限于某個(gè)局部的小范圍，可以增加種群多樣性和擴(kuò)大搜索范圍，有效地跳出局部最優(yōu)［9］。萊維飛行模擬主要采用Mantegna算法，進(jìn)而生成服從萊維分布的隨機(jī)步長(zhǎng)。萊維飛行的應(yīng)用有很多，如生物學(xué)中的“萊維飛行假說”、動(dòng)物尋找食物的運(yùn)動(dòng)模式、混沌理論等。目前，在優(yōu)化領(lǐng)域中，有很多算法與萊維飛行相結(jié)合，比如粒子群算法中就采用萊維飛行對(duì)粒子位置進(jìn)行更新操作。圖3為萊維飛行的偽代碼。

圖3 萊維飛行偽代碼Fig.3 Pseudo-code of Levy flights

萊維飛行的位置更新式為

式中：Xit+1為更新后位置；Xit為初始位置；⊕表示異或運(yùn)算；α表示步長(zhǎng)控制量；Levy(λ)為隨機(jī)路徑。

Levy(λ)滿足關(guān)系

萊維飛行的步長(zhǎng)符合萊維分布，但是萊維分布非常復(fù)雜，很難實(shí)現(xiàn)，所以用Mantegna算法來模擬，步長(zhǎng)s的計(jì)算式為

其中u、v為正態(tài)分布

其中σu和σv的表示為

2.2 高斯分布

高斯分布最早由棣莫弗在求二項(xiàng)分布的漸近公式中得到。高斯分布表達(dá)式為

其中，隨機(jī)變量x服從一個(gè)數(shù)學(xué)期望為μ、方差為σ2的高斯分布，記為x～N(μ,σ2)。根據(jù)高斯分布的特性，在搜索的過程中主要是對(duì)個(gè)體局部區(qū)域進(jìn)行大概率小范圍變異搜索，具有較好的局部搜索能力［10］。在TLBO算法中，教學(xué)階段和學(xué)習(xí)階段的個(gè)體進(jìn)行全維度更新，這樣會(huì)使局部搜索能力降低，因此在學(xué)習(xí)階段采用符合μ=0,σ=1的標(biāo)準(zhǔn)正態(tài)分布隨機(jī)搜索方式，增強(qiáng)局部搜索能力。高斯分布的曲線如圖4所示。

圖4 高斯分布曲線圖Fig.4 Diagram of Gaussian distribution

3 基于萊維飛行和高斯分布的改進(jìn)教與學(xué)優(yōu)化算法（LTLBO-GD）

3.1 自增強(qiáng)的學(xué)習(xí)機(jī)制

在TLBO算法中，教學(xué)階段的特點(diǎn)為班級(jí)中的每個(gè)個(gè)體都在根據(jù)差異性向老師進(jìn)行學(xué)習(xí)，這樣就會(huì)導(dǎo)致種群中所有個(gè)體都會(huì)向最好的個(gè)體老師靠攏，搜索速度提升，但是種群的多樣性會(huì)逐漸喪失，易陷入局部搜索收斂。當(dāng)學(xué)生與老師的水平越來越接近，老師的水平不能滿足學(xué)生的要求時(shí)，要促使老師增強(qiáng)自己的學(xué)習(xí)能力。在教學(xué)階段對(duì)老師部分加入萊維飛行，隨機(jī)游動(dòng)增加種群多樣性和擴(kuò)大搜索范圍，更容易跳出局部最優(yōu)點(diǎn)。加入萊維飛行策略的教與學(xué)優(yōu)化算法定義為L(zhǎng)TLBO算法，使老師形成自增強(qiáng)的學(xué)習(xí)機(jī)制，從而提高老師自身水平。增強(qiáng)老師學(xué)習(xí)能力的方法表示為

式中：Xtneeawcher為老師增強(qiáng)學(xué)習(xí)能力后的新解；Xteacher為老師的當(dāng)前解；s為萊維飛行步長(zhǎng)；Levy為萊維飛行機(jī)制。

通過實(shí)驗(yàn)獲得老師增強(qiáng)自己學(xué)習(xí)能力的次數(shù)SE=5，即每個(gè)老師只有5次增強(qiáng)學(xué)習(xí)能力的機(jī)會(huì)，在這5次中對(duì)比Xtneeawcher和Xteacher對(duì)應(yīng)的適應(yīng)度值進(jìn)行更新操作，當(dāng)Xtneeawcher的學(xué)習(xí)成績(jī)值好于Xteacher時(shí)進(jìn)行更新操作，反之不更新。

3.2 自學(xué)習(xí)策略

在TLBO算法的學(xué)習(xí)階段，每名學(xué)生隨機(jī)在班級(jí)中選取一名學(xué)生進(jìn)行差異性相互學(xué)習(xí)，所涉及到的范圍較小。但是在現(xiàn)實(shí)生活中，每個(gè)學(xué)生與同學(xué)之間相互交流學(xué)習(xí)的同時(shí)，還會(huì)自己學(xué)習(xí)新的知識(shí)，從而提高學(xué)習(xí)成績(jī)。這種自學(xué)習(xí)策略就是對(duì)于第i個(gè)學(xué)生Xi，以一定概率選擇與同學(xué)之間交流學(xué)習(xí)或者自學(xué)，自學(xué)的方式是產(chǎn)生一個(gè)［0，1］之間的隨機(jī)數(shù)σ和一個(gè)斜對(duì)角矩陣，斜對(duì)角矩陣中唯一有值的元素服從高斯分布，用于選擇種群中的某一維度進(jìn)行搜索。在教學(xué)階段加入萊維飛行策略以及在學(xué)習(xí)階段加入高斯分布的教與學(xué)優(yōu)化算法定義為L(zhǎng)TLBO-GD算法。自學(xué)習(xí)策略表示為

式中：Xinew表示第i個(gè)學(xué)生Xi自學(xué)之后的值；Xiold表示第i個(gè)學(xué)生Xi自學(xué)之前的值；σ表示［0，1］之間的隨機(jī)數(shù)；Ra表示D×D維的斜對(duì)角矩陣，其中唯一有值的元素服從高斯分布。

3.3 LTLBO-GD算法步驟

步驟1：初始化種群。為保證個(gè)體在決策空間中的多樣性，搜索空間中按照隨機(jī)生成的方式初始化學(xué)生，班級(jí)中的每個(gè)學(xué)生(i=1,2,…,NP)，其中NP為班級(jí)學(xué)生的總?cè)藬?shù)，D代表每個(gè)學(xué)生所需要學(xué)習(xí)的科目數(shù)量。

一個(gè)班級(jí)可以表示為

步驟2：計(jì)算適應(yīng)度值。根據(jù)目標(biāo)函數(shù)計(jì)算出個(gè)體適應(yīng)度值，選擇當(dāng)前班級(jí)中適應(yīng)度最好的個(gè)體作為老師，即Xteacher。

步驟3：增強(qiáng)老師學(xué)習(xí)能力。當(dāng)前班級(jí)中的老師通過式（13）進(jìn)行5次學(xué)習(xí)，增強(qiáng)老師自己的學(xué)習(xí)水平。萊維飛行后根據(jù)老師學(xué)習(xí)前后的水平進(jìn)行對(duì)比，判斷是否更新。

步驟4：教學(xué)階段。（1）班級(jí)中的每名學(xué)生根據(jù)式（1）和式（3）向老師進(jìn)行差異性學(xué)習(xí)。（2）教學(xué)完成后，根據(jù)每個(gè)學(xué)員學(xué)習(xí)前后的成績(jī)對(duì)比，產(chǎn)生新的學(xué)習(xí)者。適應(yīng)度f(Xi)反映學(xué)員成績(jī)。

步驟5：學(xué)習(xí)階段。對(duì)于每一個(gè)學(xué)生，在學(xué)習(xí)的過程中會(huì)以一定的概率進(jìn)行學(xué)習(xí)方式的選擇。（1）交流學(xué)習(xí)。在班級(jí)中隨機(jī)選擇一名學(xué)生Xj，學(xué)生Xi與Xj根據(jù)式（4）進(jìn)行互補(bǔ)學(xué)習(xí)交流。（2）自主學(xué)習(xí)。學(xué)生根據(jù)式（14）開展自學(xué)的方式，學(xué)習(xí)不一樣的知識(shí)，從而提高自己的學(xué)習(xí)成績(jī)。（3）學(xué)習(xí)完成后，產(chǎn)生新的學(xué)習(xí)者，進(jìn)行更新操作。

步驟6：若滿足終止條件，優(yōu)化結(jié)束輸出最優(yōu)解，否則返回步驟2。

LTLBO-GD算法的步驟轉(zhuǎn)換為圖5所示的偽代碼。

圖5 LTLBO-GD算法偽代碼Fig.5 Pseudo-code of LTLBO-GD algorithm

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 測(cè)試函數(shù)

為了驗(yàn)證LTLBO-GD算法性能，隨機(jī)選取6個(gè)典型的標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，其函數(shù)表達(dá)式及對(duì)應(yīng)取值范圍如表1所示。為了保證檢驗(yàn)算法結(jié)果的客觀性，其中函數(shù)f1、f5、f6是高維單模態(tài)函數(shù)，f2、f3、f4是高維多模態(tài)函數(shù)。Sphere、Step和Zakharov函數(shù)只有一個(gè)最優(yōu)解為0，函數(shù)曲面光滑；Rastrigin函數(shù)含有余弦調(diào)制傳遞函數(shù)，其函數(shù)產(chǎn)生頻繁的局部最小值，極小值的位置具有規(guī)律性；Girewank函數(shù)存在很多局部極小點(diǎn)，其數(shù)目與問題的維數(shù)有關(guān)，其全局最優(yōu)值為0；Schwefel Problem22函數(shù)是連續(xù)的、平滑多峰函數(shù)，當(dāng)自變量趨近于無窮大時(shí)，函數(shù)會(huì)形成大量局部極值區(qū)域。高維單模態(tài)函數(shù)主要測(cè)試算法的整體尋優(yōu)能力，而高維多模態(tài)函數(shù)主要測(cè)試算法跳出局部收斂的能力。

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

將LTLBO-GD算法分別與基本TLBO算法以及改進(jìn)后的LTLBO算法進(jìn)行對(duì)比，三種算法的參數(shù)取值均為：算法初始種群規(guī)模p=50，變量維度d=30，最大迭代次數(shù)Tmax=500。

4.2 參數(shù)分析實(shí)驗(yàn)

在教學(xué)階段加入萊維飛行策略使老師形成自增強(qiáng)的學(xué)習(xí)機(jī)制，從而提高老師自身水平。老師自增強(qiáng)學(xué)習(xí)次數(shù)過少或者過多都會(huì)導(dǎo)致學(xué)習(xí)成功率較低。分別取自增強(qiáng)次數(shù)SE=4、SE=5、SE=6，對(duì)函數(shù)f1～f6的最優(yōu)值進(jìn)行分析測(cè)試，結(jié)果如表2所示。當(dāng)SE=5時(shí)，函數(shù)f1、f2、f5、f6最優(yōu)值全部?jī)?yōu)于其他兩個(gè)SE取值。函數(shù)f3和f4的最優(yōu)值在三個(gè)SE取值時(shí)均為0，但當(dāng)SE=5時(shí)函數(shù)最優(yōu)值的收斂速度最快。

表2 自增強(qiáng)次數(shù)分析Tab.2 Self-enhancement frequency analysis

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

4.3.1 TLBO、LTLBO、LTLBO-GD算法比較 表3給出三種算法測(cè)試函數(shù)獨(dú)立運(yùn)行30次的統(tǒng)計(jì)結(jié)果，包括最優(yōu)值、最優(yōu)值的均值和最優(yōu)值的方差。LTLBO-GD算法相比于其他算法在6個(gè)測(cè)試函數(shù)中取得的最優(yōu)值更接近函數(shù)最優(yōu)值0。LTLBO算法和LTLBO-GD算法都取得了函數(shù)f3、f4的最優(yōu)值0。對(duì)于函數(shù)f1、f2，LTLBO-GD算法求解精度至少高于LTLBO算法30個(gè)數(shù)量級(jí)；對(duì)于函數(shù)f5、f6，LTLBO-GD算法求解精度至少高于LTLBO算法10個(gè)數(shù)量級(jí)；因此證明LTLBO-GD算法的求解精度優(yōu)于LTLBO算法。性能指標(biāo)函數(shù)誤差的均值和方差能夠評(píng)價(jià)各算法的求解精度，方差反映算法的穩(wěn)定性能。LTLBO-GD算法對(duì)所有測(cè)試函數(shù)最優(yōu)值的方差都小于其他兩種算法，說明算法非常穩(wěn)定。表明LTLBO-GD算法根據(jù)在教學(xué)階段的學(xué)習(xí)機(jī)制和學(xué)習(xí)階段的學(xué)習(xí)策略，有助于算法性能的改善，解的質(zhì)量較好。

表3 三種算法的比較結(jié)果Tab.3 Comparison between three methods

三種算法對(duì)于6個(gè)測(cè)試函數(shù)的進(jìn)化收斂曲線如圖6所示。對(duì)于函數(shù)f4和f5的收斂曲線，TLBO算法和LTLBO算法在收斂過程中曲線出現(xiàn)部分重合，但從整體來看，LTLBO算法的收斂速度快于TLBO算法。LTLBO-GD算法的收斂曲線均位于其他算法的下方，說明其優(yōu)化效果最好。LTLBOGD算法在6個(gè)測(cè)試函數(shù)中都快速收斂到全局最優(yōu)解附近，并且收斂速度最快，優(yōu)化效果最好。

圖6 三種算法的仿真結(jié)果Fig.6 Simulated results of three algorithms

本文提出的LTLBO-GD算法實(shí)驗(yàn)結(jié)果整體表現(xiàn)很穩(wěn)定，明顯優(yōu)于其他兩種算法。表明該算法具有良好的求解精度、收斂速度，以及全局搜索能力和跳出局部最優(yōu)的能力，具有更廣的應(yīng)用前景。

4.3.2 LTLBO-GD、DE、PSO算法比較 為了證明LTLBO-GD算法的優(yōu)越性以及實(shí)際應(yīng)用價(jià)值，選取不同類型且最具有代表性的智能優(yōu)化算法差分進(jìn)化算法（DE）［11］、粒子群優(yōu)化算法（PSO）［4］作對(duì)比。為了算法比較的嚴(yán)謹(jǐn)性，三種算法的參數(shù)取值均為：算法初始種群規(guī)模p=50，變量維度d=30，最大迭代次數(shù)Tmax=500。在PSO算法中慣性權(quán)重從0.8線性遞減到0.4，學(xué)習(xí)因子c1=c2=1.5。在DE算法中，變異率F=0.5，交叉因子Cr=0.9。三種算法測(cè)試函數(shù)獨(dú)立運(yùn)行30次的統(tǒng)計(jì)結(jié)果，包括最優(yōu)值、最優(yōu)值的均值和最優(yōu)值的方差如表4所示。LTLBO-GD算法30次運(yùn)行最好的最優(yōu)值、最優(yōu)值的平均值和最優(yōu)值的方差都遠(yuǎn)優(yōu)于DE算法和PSO算法，因此，LTLBO-GD算法具有更高的尋優(yōu)精度和更強(qiáng)的尋優(yōu)能力。

表4 其他算法比較結(jié)果Tab.4 Comparison with other algorithms

5 結(jié)論

提出一種基于萊維飛行和高斯分布的教與學(xué)優(yōu)化算法LTLBO-GD算法。為了克服基本算法的缺點(diǎn)，在教學(xué)階段融入萊維飛行策略，該策略具有很強(qiáng)的跳躍能力，使算法在尋找最優(yōu)解的過程中能夠擴(kuò)大搜索范圍進(jìn)而保證種群多樣性。在學(xué)習(xí)階段加入高斯分布，利用服從高斯分布的斜對(duì)角矩陣對(duì)種群中隨機(jī)選擇的某一維進(jìn)行搜索，目的是對(duì)當(dāng)前解進(jìn)行大概率小范圍變異，進(jìn)而增強(qiáng)單維搜索能力，避免過早陷入局部最優(yōu)。6個(gè)典型標(biāo)準(zhǔn)測(cè)試函數(shù)仿真結(jié)果表明，LTLBO-GD算法明顯優(yōu)于其他四種算法，整體表現(xiàn)非常穩(wěn)定，求解能力大幅度提高，具有良好的求解精度和收斂速度。