基于協(xié)同變異與萊維飛行策略的教與學(xué)優(yōu)化算法及其應(yīng)用

高 昊，張慶科，卜降龍，李俊青，張化祥

（山東師范大學(xué) 信息科學(xué)與工程學(xué)院，濟(jì)南 250358）

0 引言

近年來(lái)，隨著待優(yōu)化實(shí)際問(wèn)題日益復(fù)雜，各種智能優(yōu)化算法為代替?zhèn)鹘y(tǒng)優(yōu)化方法而相繼被提出，具有效率高、求解代價(jià)小的特點(diǎn)，以智能隨機(jī)的方式求解，在計(jì)算精度、收斂速度、單目標(biāo)與多目標(biāo)問(wèn)題、單峰與多峰等問(wèn)題上各有側(cè)重。教與學(xué)優(yōu)化（Teaching-Learning-Based Optimization，TLBO）算法［1］是一種針對(duì)連續(xù)非線性大規(guī)模優(yōu)化問(wèn)題的優(yōu)化算法，無(wú)需提前設(shè)定參數(shù)，不必關(guān)注參數(shù)對(duì)解質(zhì)量的影響。目前，許多文獻(xiàn)已將TLBO 算法及其相關(guān)變體應(yīng)用于比例-積分-微分控制器（Proportion Integration Differentiation，PID）優(yōu)化［2］、系統(tǒng)優(yōu)化［3］、風(fēng)險(xiǎn)預(yù)測(cè)［4］、路徑優(yōu)化［5］、序列比對(duì)［6］、特征選擇［7］、經(jīng)濟(jì)負(fù)荷調(diào)度［8］、故障檢測(cè)［9］、圖像工程［10］等領(lǐng)域，并取得了不錯(cuò)的應(yīng)用效果。

與眾多智能優(yōu)化算法一樣，TLBO 算法也會(huì)有陷入局部極值、算法早熟等問(wèn)題。為了更好地解決這些問(wèn)題，本文對(duì)TLBO 算法相關(guān)研究進(jìn)展歸納總結(jié)如下：

1）種群初始化。Wang 等［11］使用Logistic 混沌映射初始化種群，生成均勻分布在解空間的個(gè)體，提升了種群多樣性；Roy 等［12］提出一種基于反向?qū)W習(xí)的教與學(xué)優(yōu)化（Oppositional TLBO，OTLBO）算法，使用反向?qū)W習(xí)生成反向種群，并在算法迭代過(guò)程中產(chǎn)生反向?qū)W習(xí)種群，與種群中相對(duì)應(yīng)的個(gè)體進(jìn)行比較，篩選比較好的個(gè)體來(lái)加快算法收斂速度。

2）引入策略和機(jī)制。Chen 等［13］提出了一種可變種群方案，種群規(guī)模隨三角形震蕩折線圖的波動(dòng)動(dòng)態(tài)變化，在種群規(guī)模增長(zhǎng)階段使用高斯分布生成新個(gè)體，在種群規(guī)模減小階段刪除最相似的個(gè)體；Yu 等［14］提出了一種分組策略，將種群分為若干組進(jìn)行老師的教學(xué)任務(wù)，防止算法過(guò)早收斂，同時(shí)在學(xué)生交流階段讓某位學(xué)生隨機(jī)選擇兩名學(xué)生進(jìn)行交流，以提升算法的種群多樣性；Wang 等［15］讓學(xué)習(xí)者在迭代學(xué)習(xí)過(guò)程中使用差異變異來(lái)保持學(xué)習(xí)者的多樣性，避免了采用重復(fù)消除近似個(gè)體的重啟方法造成算法時(shí)間復(fù)雜度的提升；Taheri 等［16］提出了一種平衡教與學(xué)優(yōu)化（Balanced TLBO，BTLBO）算法，新增了輔導(dǎo)階段與重啟階段，在提升算法局部勘探能力的同時(shí)又能兼顧全局探索能力；He 等［17］提出了一種混沌教與學(xué)優(yōu)化（Chaotic TLBO，CTLBO）算法，將萊維飛行與混沌映射相結(jié)合，對(duì)適應(yīng)度值較差個(gè)體執(zhí)行萊維飛行策略，并對(duì)部分個(gè)體進(jìn)行混沌搜索，提升了算法的全局搜索能力；Rao 等［18］提出了一種基于精英概念的精英教與學(xué)優(yōu)化（Elitist TLBO，ETLBO）算法，使用精英解替換較差解，提升了種群整體質(zhì)量；于坤杰等［19］提出了加入反饋學(xué)習(xí)階段的反饋精英教與學(xué)優(yōu)化（Feedback Elitist TLBO，F(xiàn)ETLBO）算法，能平衡算法的全局探索與局部開(kāi)發(fā)能力。

3）引入慣性權(quán)重因子。Niu 等［20］設(shè)計(jì)了一種隨迭代次數(shù)線性遞減的慣性權(quán)重，并用于教學(xué)階段的個(gè)體更新，提高了算法的收斂速度；Wu 等［21］引入一種非線性慣性加權(quán)因子用于教學(xué)階段和學(xué)習(xí)者階段的學(xué)習(xí)者更新；Cao 等［22］設(shè)計(jì)了一種自適應(yīng)權(quán)重因子來(lái)獲得較強(qiáng)的全局搜索能力；Coelho等［23］提出一種基于混沌慣性權(quán)重的教與學(xué)優(yōu)化（Chaotic Inertia Weight TLBO，TLBOCIW）算法，通過(guò)混沌權(quán)重更新個(gè)體，使個(gè)體在解空間中的分布更加均勻，種群的多樣性得到提升。

4）混合算法。Zou 等［24］將粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）的社會(huì)特性融入TLBO 算法，個(gè)體位置的更新由原始位置、平均位置、全局最佳位置共同決定；Ouyang 等［25］在TLBO 算法中引入和聲搜索（Harmony Search，HS）算法來(lái)優(yōu)化當(dāng)前最佳個(gè)體；Chen 等［26］在教學(xué)和學(xué)習(xí)者階段加入模擬退火算子進(jìn)行個(gè)體水平的更新。

由于不存在一種優(yōu)化算法可以解決所有優(yōu)化問(wèn)題，針對(duì)算法的單一策略改進(jìn)并不利于提升算法面對(duì)復(fù)雜問(wèn)題的能力，因此，有必要進(jìn)一步深入探究多策略融合方法。本文提出了一種基于均衡優(yōu)化與萊維飛行策略的新型教與學(xué)優(yōu)化（Equilibrium-Lévy-Mutation TLBO，ELMTLBO）算法，在解決算法易陷入局部最優(yōu)、算法早熟等問(wèn)題的同時(shí)，提升算法綜合性能。首先，算法采用多精英均衡引導(dǎo)策略，避免種群陷入局部最優(yōu)；其次，在萊維飛行的基礎(chǔ)上引入一種自適應(yīng)權(quán)重，二者結(jié)合平衡算法的局部勘探和全局探索能力；最后，設(shè)計(jì)包含多種變異算子的變異算子池，豐富了種群的多樣性。

1 教與學(xué)優(yōu)化算法

TLBO 算法主要靈感來(lái)源于課堂上學(xué)生學(xué)習(xí)進(jìn)步的過(guò)程。在TLBO 中，一組學(xué)習(xí)者或一類(lèi)學(xué)習(xí)者構(gòu)成了整個(gè)種群，種群中的每一個(gè)個(gè)體通過(guò)成績(jī)或水平來(lái)評(píng)價(jià)其優(yōu)劣，種群的最佳個(gè)體被選擇為老師，老師即為目前最佳解決方案，肩負(fù)著引領(lǐng)種群迭代的任務(wù)?；谝陨厦枋?，算法工作流程被分為兩個(gè)階段：教學(xué)階段和學(xué)習(xí)者階段。

1.1 教學(xué)階段

在教學(xué)階段，老師會(huì)根據(jù)學(xué)習(xí)者們的平均水平進(jìn)行教學(xué)任務(wù)。教學(xué)階段老師的教學(xué)過(guò)程描述如下：

其中：xmean為班級(jí)的平均水平，它是所有個(gè)體的算術(shù)平均值；i為個(gè)體編號(hào)，j為分量編號(hào)；nPop為種群規(guī)模，dim為個(gè)體維度；r1為［0，1］區(qū)間服從均勻分布的隨機(jī)向量；TF∈{1，2}為教學(xué)因子，算法在TF=1 時(shí)偏向于全局搜索，TF=2 時(shí)偏向于局部搜索。

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

在學(xué)習(xí)者階段，一名學(xué)習(xí)者通過(guò)隨機(jī)挑選另一名學(xué)習(xí)者進(jìn)行相互交流學(xué)習(xí)。低水平者將向高水平者學(xué)習(xí)，而高水平者將吸取低水平者的經(jīng)驗(yàn)教訓(xùn)。這個(gè)過(guò)程通過(guò)以下公式加以描述：

其中：k為與個(gè)體i交流的隨機(jī)個(gè)體；r2為［0，1］區(qū)間服從均勻分布的隨機(jī)向量。學(xué)習(xí)者通過(guò)上述兩個(gè)階段來(lái)提升自身水平，并選擇種群中的最佳個(gè)體作為老師來(lái)引導(dǎo)種群進(jìn)行下一次的迭代。

2 基于教與學(xué)優(yōu)化算法的改進(jìn)

2.1 均衡引導(dǎo)

均衡引導(dǎo)是一種避免全局最優(yōu)解過(guò)度引導(dǎo)的策略。算法可以通過(guò)精英池篩選4 個(gè)精英解及1 個(gè)平均狀態(tài)解作為引導(dǎo)個(gè)體，4 個(gè)精英解有助于提升算法的局部勘探能力，而作為4 個(gè)精英解算術(shù)平均值的平均狀態(tài)解可以提升算法的全局探索能力。若候選解數(shù)少于4，會(huì)提高算法在單峰函數(shù)上的性能，但會(huì)降低算法在多峰和復(fù)合函數(shù)上的性能；若候選解數(shù)超過(guò)4 則會(huì)產(chǎn)生相反的效果［27］。在標(biāo)準(zhǔn)TLBO 算法中，老師作為種群的當(dāng)前最佳決策方案引導(dǎo)種群進(jìn)行迭代，若當(dāng)前最佳個(gè)體陷入局部最優(yōu)則導(dǎo)致整個(gè)種群更新停滯不前。于是，將均衡引導(dǎo)策略引入TLBO 算法是一種不錯(cuò)的解決方案。引導(dǎo)種群迭代的不再是當(dāng)前迭代的最優(yōu)個(gè)體，而是精英池中的精英，通過(guò)精英的均衡引導(dǎo)可以避免算法搜索停滯。

2.2 基于萊維飛行的自適應(yīng)權(quán)重

萊維飛行可以在不確定環(huán)境中最大限度地提高資源搜索的效率，它常見(jiàn)于自然界中動(dòng)物的覓食、移動(dòng)等過(guò)程。萊維飛行服從萊維分布，它以極大的概率進(jìn)行小范圍游走，以極小概率產(chǎn)生一段長(zhǎng)距離的飛行。這種隨機(jī)游走屬于一種馬爾可夫鏈，即當(dāng)前位置只與上一狀態(tài)的位置及轉(zhuǎn)移概率有關(guān)［28-29］。在此前的研究中，Yang［30］把萊維分布函數(shù)經(jīng)過(guò)簡(jiǎn)化和傅里葉變換后得到它的冪次形式的概率密度函數(shù)如下：

生成一個(gè)服從萊維分布的隨機(jī)數(shù)比較難，Yang［30］采用Mantegna 方法通過(guò)式（5）提取萊維飛行步長(zhǎng)s：

其中：u～N(0，σ2)；v～N(0，1)；β=1.5。方差σ如式（6）所示：

其中：σ是通過(guò)復(fù)雜運(yùn)算得到的一個(gè)標(biāo)量；Γ 為伽馬函數(shù)。

在調(diào)研國(guó)內(nèi)外相關(guān)研究時(shí)，無(wú)一例外地發(fā)現(xiàn)很多有關(guān)于萊維飛行的改進(jìn)算法均使用式（7）［31］進(jìn)行個(gè)體更新。

其中：α為步長(zhǎng)控制因子；?為點(diǎn)乘；Levy(β)為服從萊維分布的步長(zhǎng)。

由于α的值會(huì)影響萊維飛行的方向及所產(chǎn)生的步長(zhǎng)，因此本文在此前研究的基礎(chǔ)上增大σ，減小出現(xiàn)遠(yuǎn)距離飛行的頻率并增加萊維飛行所產(chǎn)生的步長(zhǎng)，以平衡萊維飛行所提供的搜索能力。

如果萊維飛行產(chǎn)生的步長(zhǎng)較大，會(huì)跳過(guò)全局最優(yōu)解，而步長(zhǎng)過(guò)小則會(huì)降低算法收斂速度，同時(shí)在算法陷入局部最優(yōu)時(shí)也無(wú)法提供跳出局部最優(yōu)的能力［32］。綜上所述本文提出一種將萊維飛行與自適應(yīng)動(dòng)態(tài)權(quán)重相結(jié)合的方法，基于萊維飛行的權(quán)重來(lái)控制個(gè)體位置更新的過(guò)程，并提出如下公式：

其中：s是萊維飛行產(chǎn)生的步長(zhǎng)；r3、r4和r5為［0，1］區(qū)間服從均勻分布的隨機(jī)數(shù)；ub與lb分別為問(wèn)題的上下界；RSR為縮放范圍（Scaling Range，SR）因子，是根據(jù)問(wèn)題上下界確定的步長(zhǎng)縮量因子，它將萊維飛行產(chǎn)生的較大步長(zhǎng)限定在解空間內(nèi)，使萊維飛行機(jī)制既有效又不至于直接越界；X為在迭代范圍[1，maxiter]內(nèi)單調(diào)遞減的凸函數(shù)，由當(dāng)前迭代次數(shù)iter和最大迭代次數(shù)maxiter共同確定；C=4.5，為固定的常數(shù)，經(jīng)過(guò)試錯(cuò)法重復(fù)實(shí)驗(yàn)得到，設(shè)計(jì)目的是在算法迭代后期削弱萊維飛行的能力，使算法趨向于局部收斂的過(guò)程；w是由問(wèn)題的上下界、當(dāng)前迭代次數(shù)和最大迭代次數(shù)、服從萊維分布的步長(zhǎng)共同確定的自適應(yīng)慣性權(quán)重，自適應(yīng)權(quán)重對(duì)個(gè)體進(jìn)行控制，以平衡算法的全局探索和局部開(kāi)發(fā)能力。

為了保證算法具有足夠的跳躍性，增加了一個(gè)提升算法跳躍能力的式（13），此公式產(chǎn)生的步長(zhǎng)將有一定的概率替代經(jīng)權(quán)重控制后產(chǎn)生的步長(zhǎng)，本文將此概率設(shè)置為0.3。

2.3 變異算子池

在進(jìn)化類(lèi)算法中，通過(guò)變異可以豐富種群多樣性，提高算法的全局搜索能力，避免算法陷入局部最優(yōu)。為此，本文在TLBO 算法中設(shè)計(jì)了變異池策略（圖1），在變異池中融入了兩類(lèi)變異操作，即基于差分進(jìn)化（Differential Evolution，DE）算法的變異操作和基于遺傳算法（Genetic Algorithm，GA）的變異操作。首先，差分操作是通過(guò)對(duì)不同個(gè)體間進(jìn)行差分?jǐn)_動(dòng)操作產(chǎn)生更多潛在的解。差分進(jìn)化算法的變異策略有多種，其中一類(lèi)變異算子在單峰問(wèn)題上表現(xiàn)突出，另一類(lèi)變異算子在多峰問(wèn)題上表現(xiàn)突出［33］?；诖?，本文將差分進(jìn)化算法的兩類(lèi)變異算子融合，以提升算法的全局探測(cè)和局部開(kāi)發(fā)能力。其次經(jīng)典遺傳算法的變異操作則是針對(duì)個(gè)體進(jìn)行的變異，遺傳算法的變異算子也可以提升種群多樣性，但由于涉及個(gè)體的重啟操作，種群多樣性會(huì)更高。遺傳算法的變異算子分為均勻變異算子和非均勻變異算子：均勻變異算子產(chǎn)生的數(shù)值可均勻地分布到整個(gè)搜索空間，所以會(huì)提高算法全局探索能力；非均勻分布的變異算子則是對(duì)個(gè)體某些維度進(jìn)行小范圍隨機(jī)擾動(dòng)，提升算法收斂精度。綜上所述，本文在變異算子池中融合了上述變異算子，在算法迭代進(jìn)化過(guò)程中，針對(duì)某一個(gè)學(xué)習(xí)者個(gè)體，隨機(jī)選擇上述一種變異算子進(jìn)行變異操作。變異算子池的引入平衡了算法的全局探索與局部勘探能力，在豐富算法種群多樣性的同時(shí)也能夠提升算法局部搜索的能力。

圖1 變異算子池Fig.1 Mutation operator pool

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

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

對(duì)ELMTLBO 算法在15 個(gè)國(guó)際測(cè)試函數(shù)上進(jìn)行了多方面的評(píng)估。這15 個(gè)測(cè)試函數(shù)都是最小化問(wèn)題，大小和復(fù)雜性各不相同，詳情如表1 所示。需要注意的是，單峰函數(shù)只有一個(gè)最優(yōu)解，而多峰函數(shù)有多個(gè)最優(yōu)解；單峰函數(shù)用于評(píng)價(jià)優(yōu)化算法的開(kāi)發(fā)能力，而多峰函數(shù)則用于評(píng)價(jià)優(yōu)化算法的探索能力。

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

3.2 實(shí)驗(yàn)環(huán)境設(shè)置及評(píng)價(jià)標(biāo)準(zhǔn)

對(duì)比算法選擇了幾種先進(jìn)的智能優(yōu)化算法，包括：侏儒貓鼬優(yōu) 化算法（Dwarf Mongoose Optimization Algorithm，DMOA）［34］、白鯊優(yōu)化器（White Shark Optimizer，WSO）［35］、向量的加權(quán)平均數(shù)（weIghted meaN oF vectOrs，INFO）［36］、冠狀病毒群體免疫優(yōu)化器（Coronavirus Herd Immunity Optimizer，CHIO）［37］、平衡優(yōu)化器（Equilibrium Optimizer，EO）［27］、樽海鞘算法（Salp Swarm Algorithm，SSA）［38］和Jaya 算法［39］；以及TLBO 和它的一些改進(jìn)算法，包括：BTLBO、CTLBO、ETLBO、FETLBO、TLBOCIW 和OTLBO。

由于算法的不穩(wěn)定性，為了使實(shí)驗(yàn)真實(shí)、公平，每組實(shí)驗(yàn)獨(dú)立運(yùn)行20 次，結(jié)果取平均值。在與先進(jìn)的智能優(yōu)化算法進(jìn)行對(duì)比實(shí)驗(yàn)時(shí)，每個(gè)算法的最大評(píng)價(jià)次數(shù)（MaxFEs）為5×105，種群規(guī)模設(shè)置為40，決策變量維度設(shè)置為50；而在進(jìn)行同類(lèi)型TLBO 改進(jìn)算法對(duì)比實(shí)驗(yàn)時(shí)，每個(gè)算法的最大評(píng)價(jià)次數(shù)為10×105，種群規(guī)模設(shè)置為40，決策變量維度設(shè)置為100。在以上實(shí)驗(yàn)中，所有結(jié)果統(tǒng)計(jì)表中均加粗標(biāo)注表現(xiàn)最佳算法的平均值（Mean）和標(biāo)準(zhǔn)差（Std）。

各算法在15 個(gè)函數(shù)上均進(jìn)行了測(cè)試，但為方便展示，僅列出有代表性的4 個(gè)測(cè)試函數(shù)的收斂曲線及箱圖，其中：F4代表單峰函數(shù)，F(xiàn)8和F9代表復(fù)雜多峰函數(shù)，F(xiàn)14代表簡(jiǎn)單多峰函數(shù)。

3.3 不同類(lèi)型算法的50維性能測(cè)試

與先進(jìn)智能優(yōu)化算法的對(duì)比結(jié)果如表2，圖2 為部分函數(shù)的收斂曲線圖。

圖2 不同類(lèi)型算法針對(duì)50維問(wèn)題在基準(zhǔn)函數(shù)上的平均適應(yīng)度值誤差收斂曲線比較Fig.2 Comparison of fitness convergence curves of different types of algorithms on benchmark functions for 50-dimensional problems

表2 ELMTLBO與不同類(lèi)型算法針對(duì)50維問(wèn)題在基準(zhǔn)函數(shù)上的性能比較Tab.2 Performance comparison of ELMTLBO and different types of algorithms on benchmark functions for 50-dimensional problems

從表2 可以明顯看到，ELMTLBO 在15 個(gè)測(cè)試函數(shù)上表現(xiàn)優(yōu)秀，在其中13 個(gè)測(cè)試函數(shù)上均找到了全局最優(yōu)解，而且在F8和F9上的性能最突出。在對(duì)比算法中，EO 表現(xiàn)較為優(yōu)秀，它在9 個(gè)測(cè)試函數(shù)上找到了全局最優(yōu)解，但是在F8和F9函數(shù)上表現(xiàn)不及ELMTLBO；表現(xiàn)最差的SSA 和Jaya 在任何測(cè)試函數(shù)上均表現(xiàn)不佳。結(jié)果表明，ELMTLBO 能夠平衡算法的搜索能力，提高算法的綜合求解性能。

從圖2 可以明顯看到，ELMTLBO 算法在F4函數(shù)上比EO等算法具有更高的收斂速度，且收斂精度也得到提升，基于萊維飛行產(chǎn)生的自適應(yīng)權(quán)重可以使算法在前期快速收斂。在F14、F8、F9函數(shù)上，EO 算法在搜索后期陷入了局部最優(yōu)，局部搜索能力弱，而ELMTLBO 借助萊維飛行機(jī)制以及變異算子池使算法能夠在高速收斂的同時(shí)保證算法具有的逃逸能力。在F8函數(shù)上，ELMTLBO 依靠萊維飛行機(jī)制跳出了局部最優(yōu)，從而使得收斂曲線突降；而在F9函數(shù)上，ELMTLBO算法的收斂曲線穩(wěn)定下降，避開(kāi)了其他算法易陷入的停滯點(diǎn)，驗(yàn)證了ELMTLBO 較其他算法更具有全局探索能力，依靠均衡引導(dǎo)及變異算子池增強(qiáng)的種群多樣性，能避免算法陷入局部最優(yōu)；同時(shí)在ELMTLBO 陷入局部最優(yōu)且算法搜索停滯后，依靠萊維飛行使算法跳出了局部最優(yōu)，從而使得收斂曲線急速下降。以上分析表明，ELMTLBO 與幾種先進(jìn)的智能優(yōu)化算法相比，綜合求解性能突出，能夠高效求解各種問(wèn)題。

3.4 同類(lèi)型算法的100維性能測(cè)試

ELMTLBO 與TLBO 及它的一些改進(jìn)算法的收斂精度如表3 所示，部分函數(shù)的收斂曲線圖如圖3 所示，比對(duì)箱圖如圖4 所示。

圖3 ELMTLBO與TLBO算法變體針對(duì)100維問(wèn)題在基準(zhǔn)函數(shù)上的平均適應(yīng)度值誤差收斂曲線比較Fig.3 Comparison of fitness error convergence curves of ELMTLBO and TLBO algorithm variants on benchmark functions for 100-dimensional problems

圖4 ELMTLBO與經(jīng)典TLBO改進(jìn)算法針對(duì)100維問(wèn)題在基準(zhǔn)函數(shù)上的箱圖比較Fig.4 Comparison of box plots of ELMTLBO and classic improved algorithms of TLBO on benchmark functions for 100-dimensional problems

表3 ELMTLBO與同類(lèi)型改進(jìn)算法針對(duì)100維問(wèn)題在基準(zhǔn)函數(shù)上的性能比較Tab.3 Performance comparison of ELMTLBO and improved algorithms of the same type on benchmark functions for 100-dimensional problems

從表3 可以明顯看到，大多數(shù)算法都可以在某些函數(shù)上找到全局最優(yōu)，其中表現(xiàn)較為優(yōu)秀的CTLBO 在12 個(gè)函數(shù)上收斂到全局最優(yōu)，但在多峰函數(shù)F8、F9上性能卻不及ELMTLBO；而ELMTLBO 在13 個(gè)函數(shù)上均收斂到全局最優(yōu)，求解能力較強(qiáng)。除此之外，ELMTLBO 在F8和F9函數(shù)上的性能明顯優(yōu)于其他優(yōu)化算法，這意味著ELMTLBO 在多峰函數(shù)上具有比其他改進(jìn)算法更強(qiáng)的尋優(yōu)能力，表明算法能很好地平衡全局探索與局部勘探能力。

從收斂精度圖（圖3）可以看出，TLBO 在F1函數(shù)上收斂較快，而在迭代后期陷入局部最優(yōu)；TLBO、BTLBO 等算法在F8、F9和F14函數(shù)上出現(xiàn)早熟現(xiàn)象，并一直持續(xù)到迭代終止。面對(duì)解空間較大的多峰函數(shù)F8，依靠萊維飛行機(jī)制，在算法搜索中期收斂曲線出現(xiàn)了明顯的跳躍，并在均衡引導(dǎo)和協(xié)同變異策略的引導(dǎo)下，算法繼續(xù)精細(xì)化搜索。而在多峰函數(shù)F9上，表現(xiàn)相對(duì)較好的CTLBO 在迭代后期陷入了局部最優(yōu)，而ELMTLBO 依靠均衡引導(dǎo)策略、萊維飛行和自適應(yīng)權(quán)重策略、變異算子池策略的相互協(xié)作，仍可以使算法逐步向最優(yōu)解逼近而不會(huì)陷入搜索停滯。

從圖4 可知，ETLBO、FETLBO 算法結(jié)果數(shù)據(jù)較離散，顯示出算法極大的不穩(wěn)定性，這一特點(diǎn)在F4和F8上較為明顯。CTLBO 和ELMTLBO 算法在所有測(cè)試函數(shù)的數(shù)據(jù)結(jié)果分布均較為集中，且結(jié)果的精度較高，驗(yàn)證了CTLBO 和ELMTLBO 算法具有穩(wěn)定性及高效性。

整體來(lái)看ELMTLBO 算法在單峰問(wèn)題和多峰問(wèn)題上均表現(xiàn)出了卓越的性能，這說(shuō)明本文對(duì)TLBO 的改進(jìn)是有效的；而相較于其他經(jīng)典的TLBO 改進(jìn)算法，本文對(duì)TLBO 的改進(jìn)效果更加顯著。總的來(lái)說(shuō)，ELMTLBO 具有可以應(yīng)對(duì)復(fù)雜多樣問(wèn)題的綜合能力。

3.5 完整性消融實(shí)驗(yàn)

為體現(xiàn)本文各策略的有效性，對(duì)ELMTLBO 算法中的三個(gè)策略進(jìn)行完整性消融實(shí)驗(yàn)，在原始TLBO 算法中分別融入均衡引導(dǎo)策略（TLBOE）、基于萊維飛行的自適應(yīng)權(quán)重策略（TLBOL）以及變異算子池策略（TLBOM），并與標(biāo)準(zhǔn)TLBO 和ELMTLBO 算法一起進(jìn)行函數(shù)測(cè)試。參與測(cè)試的所有算法，均循環(huán)10 次，測(cè)試維度為30，最大評(píng)價(jià)次數(shù)為3×105，并對(duì)最佳適應(yīng)度值取平均值。這些測(cè)試是基于CEC2005 和CEC2017 測(cè)試集中的部分測(cè)試函數(shù)進(jìn)行的。表4 展示了不同改進(jìn)策略的收斂精度情況。從表4 可以看到，帶有均衡引導(dǎo)策略的TLBOE在F1、F5上優(yōu)于TLBO 算法；帶有自適應(yīng)權(quán)重的TLBOL在F1、F5、F10、F13上優(yōu)于TLBO 算法；帶有變異算子池策略的TLBOM在F1、F5、F11、F13、F15上優(yōu)于TLBO 算法。所有的改進(jìn)策略都在不同測(cè)試函數(shù)上優(yōu)于TLBO 算法，這說(shuō)明每個(gè)策略在TLBO 算法上是有效的。而對(duì)于三個(gè)策略融合的ELMTLBO 算法，其收斂精度高于參與測(cè)試的任何算法，這表明所有改進(jìn)策略都是相輔相成且穩(wěn)定有效的，它們能夠提升ELMTLBO 算法的綜合求解能力。

表4 不同改進(jìn)策略的結(jié)果對(duì)比Tab.4 Comparison of results of different improvement strategies

4 基于隱馬爾可夫模型的多序列比對(duì)

多序列比對(duì)（Multiple Sequence Alignment，MSA）是為了揭示整個(gè)基因家族的特征，找出DNA 或RNA 序列的相似性或不相似性，可以判斷同源基因間親緣關(guān)系的遠(yuǎn)近，為預(yù)測(cè)或治療疾病提供幫助，是一個(gè)NP 完全組合優(yōu)化問(wèn)題（Nondeterministic Polynomial Complete，NP-C）。MSA 目前缺乏快速有效的算法來(lái)解決比對(duì)問(wèn)題，而使用隱馬爾可夫模型（Hidden Markov Model，HMM）來(lái)解決多序列比對(duì)問(wèn)題是一個(gè)熱點(diǎn)方向。于是，本文使用ELMTLBO 算法優(yōu)化HMM，并以此來(lái)求解多序比對(duì)問(wèn)題。最終獲得的基因序列可以用于基因溯源，可以收集、整理、檢索和分析序列中表征蛋白質(zhì)結(jié)構(gòu)與功能的信息，并在相關(guān)病毒的疫苗或特效藥研究等領(lǐng)域擁有較為突出的優(yōu)勢(shì)［40］。

4.1 MSA及HMM的相關(guān)概念

馬爾可夫模型（Markov Model，MM）是數(shù)學(xué)中具有馬爾可夫性質(zhì)的離散時(shí)間隨機(jī)過(guò)程，是用于描述隨機(jī)過(guò)程統(tǒng)計(jì)特征的概率模型，其狀態(tài)序列等于觀測(cè)序列。而HMM 是一種特殊的離散時(shí)間有限狀態(tài)鏈，與MM 最大的區(qū)別是：隱藏狀態(tài)與觀測(cè)狀態(tài)分離。通常來(lái)說(shuō)，HMM 可簡(jiǎn)化為一個(gè)三元組：

其中：π為初始概率向量；A為N階轉(zhuǎn)移概率矩陣；B為N×M階生成概率矩陣。

HMM 是一個(gè)輸出符號(hào)序列的統(tǒng)計(jì)模型，具有q個(gè)狀態(tài)S1，S2，…，Sq，它們被分為三組：匹配（M）、插入（I）和刪除（D）。此外，還有兩種特殊狀態(tài)：開(kāi)始狀態(tài)和結(jié)束狀態(tài)。狀態(tài)通過(guò)轉(zhuǎn)移概率aij相互連接，它按一定的周期從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)，每次轉(zhuǎn)移都會(huì)產(chǎn)生訪問(wèn)狀態(tài)的路徑和由路徑上發(fā)射的可觀察狀態(tài)組成的序列。轉(zhuǎn)移到哪一個(gè)狀態(tài)，轉(zhuǎn)移時(shí)輸出什么符號(hào)，分別由轉(zhuǎn)移概率和轉(zhuǎn)移時(shí)的輸出概率來(lái)決定。

當(dāng)HMM 應(yīng)用于MSA 時(shí)，觀察序列以未對(duì)齊的序列形式給出，在序列對(duì)齊過(guò)程中通過(guò)對(duì)HMM 中參數(shù)的不斷調(diào)整，最終找到產(chǎn)生最佳對(duì)齊的路徑。這一過(guò)程可以使用前向算法和Viterbi 算法來(lái)確定HMM 生成給定序列o的概率，并得出產(chǎn)生o的最大概率的路徑。最近研究表明，HMM 是解決MSA 問(wèn)題的強(qiáng)大工具，針對(duì)MSA 的數(shù)學(xué)模型被描述如下：

1）為序列比對(duì)符號(hào)集合，Σ中包含基本字符集，若解決DNA 序列問(wèn)題則包含A、C、G、T 四種堿基；若解決蛋白質(zhì)問(wèn)題，則包含20 種字符；“*”表示序列中的空缺。

2）S是待比對(duì)序列，具體表示為：

序列集合S包含q條序列，對(duì)于每一條序列Si，它由長(zhǎng)度為L(zhǎng)i的字符組成，序列中的sij代表一個(gè)符號(hào)。

3）擴(kuò)展矩陣A為序列集S進(jìn)行多序列比對(duì)后的結(jié)果矩陣：

其中：aij為Si序列的第j個(gè)字符的比對(duì)結(jié)果，該結(jié)果可能為“*”；M大于S集合中最長(zhǎng)序列的長(zhǎng)度。

4）F為矩陣A的度量函數(shù)，用來(lái)度量S中的各序列的相似程度。

以上就是MSA 數(shù)學(xué)模型的描述，多序列比對(duì)問(wèn)題通過(guò)在序列集合S中進(jìn)行適當(dāng)?shù)目瘴弧?”插入，構(gòu)建一個(gè)比對(duì)結(jié)果的矩陣A，使得打分函數(shù)F(A)達(dá)到最大。

4.2 基于ELMTLBO的多序列比對(duì)

更好的HMM 訓(xùn)練結(jié)果有助于得到更高質(zhì)量的對(duì)齊序列，在使用ELMTLBO 算法訓(xùn)練HMM 時(shí)，訓(xùn)練過(guò)程中要保持HMM 的長(zhǎng)度不變，只對(duì)HMM 的參數(shù)進(jìn)行優(yōu)化。HMM 的參數(shù)表示為粒子的位置，所有粒子均需要進(jìn)行歸一化處理以滿足HMM 的約束條件?；贓LMTLBO 算法求解MSA 問(wèn)題的求解步驟如下：

第一步 初始化HMM 模型，讀取需要比對(duì)的基因序列文件，計(jì)算出基因所包含的序列條數(shù)lengthdata，確定最長(zhǎng)的序列長(zhǎng)度Lmax，以及比對(duì)后的序列長(zhǎng)度L：

在確定比對(duì)后的序列長(zhǎng)度后，計(jì)算出HMM 模型所需的參數(shù)個(gè)數(shù)，由此確定HMM 模型的基本結(jié)構(gòu)，具體公式如下：

第二步 將待比對(duì)的序列和ELMTLBO 優(yōu)化后的每個(gè)學(xué)習(xí)者的數(shù)據(jù)代入HMM 模型中，這里的學(xué)習(xí)者就是HMM 中的待優(yōu)化參數(shù)。根據(jù)HMM 中數(shù)據(jù)的組成，將學(xué)習(xí)者中的Dim個(gè)數(shù)據(jù)分為HMM 模型基本要素對(duì)應(yīng)的條件：初始概率向量(π)、轉(zhuǎn)移概率矩陣(A)和釋放概率矩陣(B)。

第三步 運(yùn)用HMM 的計(jì)算原理調(diào)用Viterbi 算法求出每個(gè)學(xué)習(xí)者在該HMM 模型條件下的Viterbi 序列。

第四步 從Viterbi 算法計(jì)算得到Viterbi 序列后，相當(dāng)于得到了一系列插入、刪除、匹配狀態(tài)的隱狀態(tài)序列，根據(jù)序列匹配標(biāo)準(zhǔn)，將隱狀態(tài)序列按照插入、刪除和匹配三個(gè)狀態(tài)分別對(duì)齊，得到的是比對(duì)后的數(shù)字序列。

第五步 使用配對(duì)分?jǐn)?shù)和函數(shù)（Sum of Pairs Score，SPS）計(jì)算序列比對(duì)結(jié)果的得分情況，這里的SPS 函數(shù)就是多序列比對(duì)問(wèn)題的適應(yīng)度函數(shù)。SPS 公式如下：

其中：li是比對(duì)過(guò)的序列，lj是待比對(duì)的序列，Dis是兩個(gè)序列間的距離矩陣。

第六步 當(dāng)?shù)瓿珊?，將最?yōu)數(shù)據(jù)代入HMM 模型中，通過(guò)Viterbi 算法回溯得到得分最高的比對(duì)后的基因序列。

4.3 序列比對(duì)測(cè)試

選取的實(shí)驗(yàn)對(duì)象分別為國(guó)際基準(zhǔn)序列比對(duì)數(shù)據(jù)庫(kù)BALiBASE 基因序列數(shù)據(jù)庫(kù)中的“451c_ref1”基因序列（圖5（a））、“1ad2_ref1”基因序列（圖5（b））、截?cái)唷発inase_ref1”基因序列（圖5（c））及“kinase_ref1”基因序列（圖5（d）），同時(shí)為了驗(yàn)證ELMTLBO 算法的比對(duì)精確度，選取wPSO（weighted PSO）算法、GA、EO算法、TLBO算法作為實(shí)驗(yàn)的對(duì)照算法。

圖5 各算法在各基因序列上的得分情況Fig.5 Score of each algorithm on each gene sequence

實(shí)驗(yàn)參數(shù)設(shè)置如下：每個(gè)算法獨(dú)立運(yùn)行10 次，每次迭代1 000 次。算法初始搜索范圍為［0.2，0.8］，由于MSA 問(wèn)題解空間上下界范圍不明確，故取消各算法越界限制條件。算法參數(shù)設(shè)置如表5。

表5 算法參數(shù)設(shè)置Tab.5 Algorithm parameter setting

表6 為不同算法在各基因序列上的比對(duì)結(jié)果及相關(guān)序列信息，其中：Name 表示對(duì)比序列樣本名稱(chēng)，并在名稱(chēng)后附打分結(jié)果圖標(biāo)號(hào)；lengthdata為樣本序列組中序列數(shù)目；LSEQ(m，n)表示樣本集中序列的長(zhǎng)度范圍，其中m為最小長(zhǎng)度，n為最大長(zhǎng)度；Dim表示HMM 中需要優(yōu)化的參數(shù)個(gè)數(shù)，即優(yōu)化算法搜索空間的維度；Score為算法最優(yōu)得分。在實(shí)驗(yàn)過(guò)程中，計(jì)算SPS 得分項(xiàng)來(lái)生成算法的多序列比對(duì)結(jié)果打分圖（如圖5 所示），T為算法獨(dú)立運(yùn)行一次，即算法迭代1 000次的平均消耗時(shí)間（單位：s），加粗標(biāo)記比對(duì)精度結(jié)果。

表6 不同算法的多序列比對(duì)結(jié)果Tab.6 Results of multiple sequence alignment of different algorithms

從表6 和圖5 可以看出，ELMTLBO 在lad2、451c 及kinase序列上表現(xiàn)不俗，雖然面對(duì)維數(shù)在上千到上萬(wàn)的高維問(wèn)題，算法尋優(yōu)速度仍然較快，顯示出了卓越的問(wèn)題求解能力，同時(shí)算法在迭代后期也有繼續(xù)收斂的潛力。這一點(diǎn)也同樣在EO 算法上體現(xiàn)。與TLBO 算法相比，ELMTLBO 算法的Score得分值高，求解精度較高，說(shuō)明對(duì)算法的改進(jìn)是有效的。

圖6 和圖7 分別為截取的kinase 基因進(jìn)行序列比對(duì)前后的結(jié)果，其中①～⑤分別表示kcc2_yeast、dmk_human、kpro_maize、lcsn 和daf1_caeel，是kinase 基因中的序列段。從圖7 可以看到，EMTLBO 算法優(yōu)化后的HMM 可以精確對(duì)齊kinase 序列段。與其他優(yōu)化算法相比，ELMTLBO 算法能夠提升多序列比對(duì)精度，從而獲得較精確的基因序列比對(duì)結(jié)果，同時(shí)也驗(yàn)證了ELMTLBO 算法具有解決現(xiàn)實(shí)世界問(wèn)題的能力。

圖6 kinase的部分基因序列Fig.6 Partial gene sequences of kinase

圖7 比對(duì)后的kinase部分基因序列Fig.7 Partial gene sequences of kinase after alignment

5 結(jié)語(yǔ)

為解決標(biāo)準(zhǔn)TLBO 算法易陷入局部最優(yōu)、算法早熟、收斂精度不高等問(wèn)題，本文提出了一種改進(jìn)的基于教與學(xué)的優(yōu)化算法ELMTLBO。該算法將萊維飛行與自適應(yīng)權(quán)重融合，自適應(yīng)更新個(gè)體水平，偶爾產(chǎn)生較大的權(quán)重使算法具有跳出局部最優(yōu)的能力；融合DE 算法變異算子和GA 算法變異算子，設(shè)計(jì)了一種變異算子池，在提升種群多樣性的同時(shí)，也能夠提升算法的收斂精度。仿真結(jié)果表明，ELMTLBO 算法比其他參與測(cè)試的算法具有更強(qiáng)的尋優(yōu)能力，在實(shí)驗(yàn)提供的大部分測(cè)試函數(shù)上均能夠找到理論最優(yōu)解。最后將ELMTLBO算法應(yīng)用于多序列比對(duì)問(wèn)題中，優(yōu)化HMM 模型中存在的參數(shù)。實(shí)驗(yàn)結(jié)果表明，ELMTLBO 算法能夠有效地平衡搜索能力，即使面對(duì)高維且復(fù)雜得多序列比對(duì)問(wèn)題，仍能夠快速且精確地獲得基因序列比對(duì)結(jié)果。由于ELMTLBO 是一種多策略算法，如何合理使每種策略發(fā)揮最大效能是一個(gè)需繼續(xù)深入探究的問(wèn)題，未來(lái)EMLTLBO 應(yīng)引入更多的自適應(yīng)機(jī)制，在算法不同的搜索階段使用不同的策略進(jìn)行更高效的搜索，并將其繼續(xù)應(yīng)用于更多的實(shí)際問(wèn)題，如圖像分割、PID 控制器優(yōu)化、路徑規(guī)劃等。