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

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

0 引言

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

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

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

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

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

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

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

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

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

1.1 教學(xué)階段

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

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

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

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

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

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

2.1 均衡引導(dǎo)

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

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

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

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

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

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

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

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

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

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

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

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

2.3 變異算子池

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

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

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

3.1 測試函數(shù)

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

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

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

對比算法選擇了幾種先進(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)行對比實(shí)驗(yàn)時，每個算法的最大評價次數(shù)（MaxFEs）為5×105，種群規(guī)模設(shè)置為40，決策變量維度設(shè)置為50；而在進(jìn)行同類型TLBO 改進(jìn)算法對比實(shí)驗(yàn)時，每個算法的最大評價次數(shù)為10×105，種群規(guī)模設(shè)置為40，決策變量維度設(shè)置為100。在以上實(shí)驗(yàn)中，所有結(jié)果統(tǒng)計表中均加粗標(biāo)注表現(xiàn)最佳算法的平均值（Mean）和標(biāo)準(zhǔn)差（Std）。

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

3.3 不同類型算法的50維性能測試

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

圖2 不同類型算法針對50維問題在基準(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與不同類型算法針對50維問題在基準(zhǔn)函數(shù)上的性能比較Tab.2 Performance comparison of ELMTLBO and different types of algorithms on benchmark functions for 50-dimensional problems

從表2 可以明顯看到，ELMTLBO 在15 個測試函數(shù)上表現(xiàn)優(yōu)秀，在其中13 個測試函數(shù)上均找到了全局最優(yōu)解，而且在F8和F9上的性能最突出。在對比算法中，EO 表現(xiàn)較為優(yōu)秀，它在9 個測試函數(shù)上找到了全局最優(yōu)解，但是在F8和F9函數(shù)上表現(xiàn)不及ELMTLBO；表現(xiàn)最差的SSA 和Jaya 在任何測試函數(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ī)制以及變異算子池使算法能夠在高速收斂的同時保證算法具有的逃逸能力。在F8函數(shù)上，ELMTLBO 依靠萊維飛行機(jī)制跳出了局部最優(yōu)，從而使得收斂曲線突降；而在F9函數(shù)上，ELMTLBO算法的收斂曲線穩(wěn)定下降，避開了其他算法易陷入的停滯點(diǎn)，驗(yàn)證了ELMTLBO 較其他算法更具有全局探索能力，依靠均衡引導(dǎo)及變異算子池增強(qiáng)的種群多樣性，能避免算法陷入局部最優(yōu)；同時在ELMTLBO 陷入局部最優(yōu)且算法搜索停滯后，依靠萊維飛行使算法跳出了局部最優(yōu)，從而使得收斂曲線急速下降。以上分析表明，ELMTLBO 與幾種先進(jìn)的智能優(yōu)化算法相比，綜合求解性能突出，能夠高效求解各種問題。

3.4 同類型算法的100維性能測試

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

圖3 ELMTLBO與TLBO算法變體針對100維問題在基準(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)算法針對100維問題在基準(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與同類型改進(jìn)算法針對100維問題在基準(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 個函數(shù)上收斂到全局最優(yōu)，但在多峰函數(shù)F8、F9上性能卻不及ELMTLBO；而ELMTLBO 在13 個函數(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ù)到迭代終止。面對解空間較大的多峰函數(shù)F8，依靠萊維飛行機(jī)制，在算法搜索中期收斂曲線出現(xiàn)了明顯的跳躍，并在均衡引導(dǎo)和協(xié)同變異策略的引導(dǎo)下，算法繼續(xù)精細(xì)化搜索。而在多峰函數(shù)F9上，表現(xiàn)相對較好的CTLBO 在迭代后期陷入了局部最優(yōu)，而ELMTLBO 依靠均衡引導(dǎo)策略、萊維飛行和自適應(yīng)權(quán)重策略、變異算子池策略的相互協(xié)作，仍可以使算法逐步向最優(yōu)解逼近而不會陷入搜索停滯。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

序列集合S包含q條序列，對于每一條序列Si，它由長度為Li的字符組成，序列中的sij代表一個符號。

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

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

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

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

4.2 基于ELMTLBO的多序列比對

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

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

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

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

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

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

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

其中：li是比對過的序列，lj是待比對的序列，Dis是兩個序列間的距離矩陣。

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

4.3 序列比對測試

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

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