基于協同變異與萊維飛行策略的教與學優化算法及其應用

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

（山東師范大學 信息科學與工程學院，濟南 250358）

0 引言

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

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

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

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

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

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

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

1 教與學優化算法

TLBO 算法主要靈感來源于課堂上學生學習進步的過程。在TLBO 中，一組學習者或一類學習者構成了整個種群，種群中的每一個個體通過成績或水平來評價其優劣，種群的最佳個體被選擇為老師，老師即為目前最佳解決方案，肩負著引領種群迭代的任務。基于以上描述，算法工作流程被分為兩個階段：教學階段和學習者階段。

1.1 教學階段

在教學階段，老師會根據學習者們的平均水平進行教學任務。教學階段老師的教學過程描述如下：

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

1.2 學習者階段

在學習者階段，一名學習者通過隨機挑選另一名學習者進行相互交流學習。低水平者將向高水平者學習，而高水平者將吸取低水平者的經驗教訓。這個過程通過以下公式加以描述：

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

2 基于教與學優化算法的改進

2.1 均衡引導

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

2.2 基于萊維飛行的自適應權重

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

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

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

其中：σ是通過復雜運算得到的一個標量；Γ 為伽馬函數。

在調研國內外相關研究時，無一例外地發現很多有關于萊維飛行的改進算法均使用式（7）［31］進行個體更新。

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

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

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

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

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

2.3 變異算子池

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

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

3 實驗與結果分析

3.1 測試函數

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

表1 測試函數Tab.1 Test functions

3.2 實驗環境設置及評價標準

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

由于算法的不穩定性，為了使實驗真實、公平，每組實驗獨立運行20 次，結果取平均值。在與先進的智能優化算法進行對比實驗時，每個算法的最大評價次數（MaxFEs）為5×105，種群規模設置為40，決策變量維度設置為50；而在進行同類型TLBO 改進算法對比實驗時，每個算法的最大評價次數為10×105，種群規模設置為40，決策變量維度設置為100。在以上實驗中，所有結果統計表中均加粗標注表現最佳算法的平均值（Mean）和標準差（Std）。

各算法在15 個函數上均進行了測試，但為方便展示，僅列出有代表性的4 個測試函數的收斂曲線及箱圖，其中：F4代表單峰函數，F8和F9代表復雜多峰函數，F14代表簡單多峰函數。

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

與先進智能優化算法的對比結果如表2，圖2 為部分函數的收斂曲線圖。

圖2 不同類型算法針對50維問題在基準函數上的平均適應度值誤差收斂曲線比較Fig.2 Comparison of fitness convergence curves of different types of algorithms on benchmark functions for 50-dimensional problems

表2 ELMTLBO與不同類型算法針對50維問題在基準函數上的性能比較Tab.2 Performance comparison of ELMTLBO and different types of algorithms on benchmark functions for 50-dimensional problems

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

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

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

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

圖3 ELMTLBO與TLBO算法變體針對100維問題在基準函數上的平均適應度值誤差收斂曲線比較Fig.3 Comparison of fitness error convergence curves of ELMTLBO and TLBO algorithm variants on benchmark functions for 100-dimensional problems

圖4 ELMTLBO與經典TLBO改進算法針對100維問題在基準函數上的箱圖比較Fig.4 Comparison of box plots of ELMTLBO and classic improved algorithms of TLBO on benchmark functions for 100-dimensional problems

表3 ELMTLBO與同類型改進算法針對100維問題在基準函數上的性能比較Tab.3 Performance comparison of ELMTLBO and improved algorithms of the same type on benchmark functions for 100-dimensional problems

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

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

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

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

3.5 完整性消融實驗

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

表4 不同改進策略的結果對比Tab.4 Comparison of results of different improvement strategies

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

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

4.1 MSA及HMM的相關概念

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

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

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

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

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

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

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

3）擴展矩陣A為序列集S進行多序列比對后的結果矩陣：

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

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

以上就是MSA 數學模型的描述，多序列比對問題通過在序列集合S中進行適當的空位“*”插入，構建一個比對結果的矩陣A，使得打分函數F(A)達到最大。

4.2 基于ELMTLBO的多序列比對

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

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

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

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

第三步 運用HMM 的計算原理調用Viterbi 算法求出每個學習者在該HMM 模型條件下的Viterbi 序列。

第四步 從Viterbi 算法計算得到Viterbi 序列后，相當于得到了一系列插入、刪除、匹配狀態的隱狀態序列，根據序列匹配標準，將隱狀態序列按照插入、刪除和匹配三個狀態分別對齊，得到的是比對后的數字序列。

第五步 使用配對分數和函數（Sum of Pairs Score，SPS）計算序列比對結果的得分情況，這里的SPS 函數就是多序列比對問題的適應度函數。SPS 公式如下：

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

第六步 當迭代完成后，將最優數據代入HMM 模型中，通過Viterbi 算法回溯得到得分最高的比對后的基因序列。

4.3 序列比對測試

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

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

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

表5 算法參數設置Tab.5 Algorithm parameter setting

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

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

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

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

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

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

5 結語

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