融合渦流搜索和差分策略的教學優化算法

李子揚，劉宗堡

(東北石油大學 地球科學學院，黑龍江 大慶 163318)

0 引 言

優化技術是一種以數學為基礎，用于求解各種工程問題最優解或滿意解的應用技術。美國工程院院士何毓琦教授指出：“任何控制與決策問題本質上均可歸結為優化問題，優化是一個光彩奪目的研究領域”。對于很多工程優化問題，由于目標函數的特殊性質(如高維、多峰、不可微分)，精確的解析方法往往是不可行的。因此各種群智能、仿生智能、進化計算等優化模型應運而生并得以快速發展。然而各種智能優化算法都有其自身的優勢和局限性，任何優化算法都不可能適用于所有優化問題。一般而言，待優化的問題不同，算法的參數設置也不相同，優化算法的控制參數越多，就越不便于使用。

因此，面對實際問題時算法參數的具體選擇，是各類智能優化算法都面臨的一個問題。2011年，通過模擬教師授課的教學行為，文獻[1-2]提出了教學優化算法(teaching-learning-based optimization，TLBO)。該算法是目前少數沒有自身個性參數的優化模型(種群規模、變量個數等共性參數除外)之一，自提出之后即受到了國內外學者的廣泛關注，同時在各類工程優化中也獲得了成功應用。

在TLBO的改進方面，文獻[3]提出了基于可變種群的尋優方案，目的是減少原始TLBO的計算成本。文獻[4]提出了融合全局交叉策略的改進方案，可有效改善探索和開發之間的平衡。文獻[5]提出了一種融合模糊推理的TLBO，該方案可在全局探索和局部開發之間自適應選擇。文獻[6]提出了一種稱為動態對立學習的TLBO，它采用一種新的動態對立學習策略來克服早熟收斂。文獻[7]提出了采用多個種群的TLBO，在教師階段，將種群劃分為幾個子種群，子群平均位置和全局最優位置之間的方向信息將引導相應子種群向著高質量區域移動，不同子群之間的信息交換可有效阻止早熟收斂。

為降低早熟收斂，文獻[8]引入了交叉概率，此外，在教師階段和學生階段分別引入了八種和四種新的變異策略，以增強算法的探索和開發能力。文獻[9]在TLBO中引入了兩個新階段，即自我反饋學習階段以及變異和交叉階段，使算法保持良好的探索和開發能力。文獻[10]利用自適應指數分布的慣性權重，改變位置更新方程；此外，應用logistic映射生成一個均勻分布的種群，以提高初始種群的質量。TLBO已廣泛用于醫學診斷、優化調度、車間調度、系統辨識、工程設計、圖像處理等眾多領域。

在TLBO現有的改進方案中，融合其他經典策略的改進方案相對較少，然而這類融合其他經典策略的改進方案可以實現優勢互補。

鑒于此，該文提出一種融合渦流搜索、差分進化策略的改進方案，其中渦流搜索用于教師個體的自尋優，而差分策略用于教師階段和學生階段所有個體的調整更新。改進后的算法沒有增加個性參數，從而使算法仍然具有很好的適用性。復雜函數極值優化的仿真結果表明，改進后的算法不僅明顯優于原算法，也優于其他同類對比算法。

1 改進方案涉及的優化算法

1.1 教學優化算法

教學優化算法的靈感來源于教師向學生傳授知識的教學過程。不失一般性，以極小值優化為例，教學優化算法包括以下兩個階段。

(1)教師階段。

設為第

t

步迭代種群平均值，為第

t

步迭代最優個體(教師)，將

T

看作全班學生新的均值，可得兩均值之差，如式(1)：Difference_Mean=

r

(-

T

)

(1)

其中，

T

=round[1+rand(0,1)]∈{1,2}，

r

是區間(0,1)內均勻分布的隨機數。按式(2)計算與對應的new,。若new,優于，則=new,，否則保持不變。new,=+Difference_Mean

(2)

(2)學生階段。

每個學生個體隨機選擇學習目標。假設個體隨機選擇個體≠，首先按式(3)計算新解new,，然后按貪婪選擇決定是否保留該解。最后，若滿足終止條件則終止，否則返回教師階段。

(3)

1.2 渦流搜索算法

(1)產生初始解。

在渦流搜索算法(vortex search，VS)中，通過以搜索空間中心點為中心的球型高斯分布隨機產生初始解(0)={,,…,}。球形高斯分布的初始標準差可按下式計算。

(4)

其中，upperlimit和lowerlimit分別為搜索空間的上下邊界，

σ

可看作渦流外環初始半徑。

(2)當前解的更新。

用最好的候選解∈(0)替換初始解，并將其作為半徑

σ

的內環中心，產生新的候選解集(1)，若最好解∈(1)好于迄今為止的最好解，則更新最好解。再將最好解作為縮減半徑后的第三個環中心，重復上述過程直至滿足終止條件，如圖1所示。

圖1 渦流算法的搜索過程

(3)半徑縮減方法。

在渦流算法中，每步迭代按如下逆不完全伽馬函數縮減半徑的值。

(5)

其中，

λ

>0

.

1為隨機變量，

a

>0為分辨率參數。

每步迭代渦流半徑按式(6)縮減。

σ

=

σ

λ

γ

(

λ

,

a

-

t/

MaxItr)

(6)

其中，

a

=1，

t

為當前步數，MaxItr為限定步數。

1.3 差分進化算法

目前，差分進化(differential evolution，DE)算法中的變異方案存在多種版本，下面以文獻[20]中提出的DE/rand/1/bin方案為例，給出DE的實施步驟。

(1)參數及種群初始化。

DE的控制參數包括：種群規模NP，變量個數

D

及范圍，縮放因子

F

，交叉概率CR。所有個體均初始化為搜索空間內均勻分布的隨機數，置當前代數為

t

=1。

(2)生成變異向量。

計算所有個體目標函數值，根據式(7)為每個個體生成變異向量。

(

t

+1)=(

t

)+

F

[(

t

)-(

t

)]

(7)

其中，

i

,

r

,

r

,

r

∈{1,2,…,NP}為隨機選擇且互不相同的個體序號。

(3)交叉操作。

對變異向量(

t

+1)，生成試探向量(

t

+1)=[(

t

+1),…,(

t

+1)]，其中：

(8)

其中，rand為在(0,1)均勻分布的隨機數，rand{1,2,…,}為按均勻分布在{1,2,…,

D

}中隨機選取的一個整數。

(4)選擇操作。

比較(

t

+1)和(

t

)的目標函數值，按貪婪選擇方法替換當前個體。(

t

+1)=

(9)

若滿足終止條件則終止；否則置

t

=

t

+1，轉(2)。

2 改進的教學優化算法

2.1 實施改進的基本思路

關于TLBO的兩個核心階段，在教師階段，學生向教師學習，而教師自身不能進行有效的學習；在學生階段，學生之間采用偏向式學習(即先對比兩個體優劣，再使劣者向優者學習)，這種學習方式容易降低種群多樣性，從而使算法有早熟收斂的傾向。

在TLBO中，作為當前最優解的教師具有優化路標的作用，有必要增加“教師自學”環節使其實施自尋優。而對于單解尋優，渦流搜索顯然是一種可行方案。因此，在TLBO中融合VS，將其應用于教師的自尋優，是該文采用的第一種改進策略。在TLBO的教師階段和學生階段，將體現不同個體之間信息共享的差分策略融合到個體的更新中，同時在學生階段采用輪盤賭策略，以便增加優良個體的更新機會，是該文采用的第二種改進策略。綜上，改進后的TLBO每步迭代分為三個階段：教師自學；向教師學；學生互學。

2.2 改進算法的實現方法

為便于描述，將改進后的教學優化算法簡稱為ITLBO(improved TLBO)，其實現方法如下所述。

(1)種群規模設置及初始化。

改進后的算法沒有增加新的個性控制參數，但對于共性參數，增加了1個用于渦流搜索的候選解數。換言之，ITLBO包括兩個種群；用于教師自學(渦流搜索)的種群NP，用于教學階段的種群NP。為增強算法的實用性，經過多次重復實驗，該文建議NP=2NP。實際使用時，令種群規模為NP，則NP=NP/3，NP=2NP/3。因此，與TLBO比較，ITLBO的控制參數沒有增加，且初始化時，只需要隨機初始化種群NP。對于初始化后的種群(0)={,,…,NP}，計算目標函數值，確定最優個體。

(2)教師自學階段。

令渦流中心=，以為中心，按高斯分布產生NP個候選解。高斯分布的一般形式如式(10)：

(10)

(3)向教師學階段。

該階段在標準TLBO教師階段的基礎上，增加了差分策略，同時為降低計算復雜度，對于每個候選解，只隨機更新1個維度。

對于個體(

i

=1,2,…,NP)，設為第

t

步迭代種群NP的平均值，=為第

t

步迭代最優個體(教師)，將看作種群NP的新均值，先置new,=，再按式(11)修正new,。new,(

d

)=(

d

)+rand((

d

)-(

d

))+rands(

X

(

d

)-

X

(

d

))

(11)

其中，

T

∈{1,2}；rand∈(0,1),rands∈(-1,1)為均勻分布的隨機數；

j

∈{1,2,…,NP}且

j

≠

i

；

d

∈{1,2,…,

D

}。個體

j

和維度

d

均隨機產生。最后，按貪婪選擇策略實現當前個體的更新。

(4)學生互學階段。

該階段也將在個體的更新式中融入差分變異策略。為降低計算復雜度，對于每個候選解，也只隨機更新1個維度。同時，為提高優良個體的更新機會，本階段采用了輪盤賭策略。以極小值優化為例，根據目標函數構造的適應度函數如式(12)：

Fitness=(1+

F

)

(12)

其中，

F

為目標函數值。按式(13)構造種群中每個候選解的選擇概率。

(13)

首先，依概率選擇個體，然后實施更新，直到選出并更新NP個個體為止。具體方法如下：對所選個體(

i

=1,2,…,NP)，首先置new,=，在集合{1,…,

i

-1,

i

+1,…, NP}中隨機選擇

j

,

k

且

j

≠

k

，然后按式(14)計算

X

new,。

(14)

其中，rand∈(0,1),rands∈(-1,1)為均勻分布的隨機數；

d

∈{1,2,…,

D

}為隨機產生的整數。最后，按貪婪選擇策略實現當前個體的更新。

(5)算法終止條件。

終止條件通常可以設置為精度閾值或目標函數計算次數。對于精度閾值，當最優解的目標值達到預先設置的某種精度要求后，終止算法的運行；對于目標函數計算次數，當且僅當目標函數計算次數小于預先設定的最大次數時，算法繼續運行，否則不論優化結果是否滿足精度要求，都將終止運行。該文選擇目標函數計算次數作為終止條件。

不選擇迭代步數作為終止條件的原因是，不同優化算法在1步迭代內個體的尋優次數一般會有不同，因此，單純考察相同迭代步數下的尋優結果有失公平。然而每次尋優都會通過計算目標函數值來考察其效果，因此，考察相同目標函數計算次數下的優化結果才是相對公平的。

3 對比實驗

為充分展示ITLBO的優勢，本節將針對標準函數極值優化問題設計實驗，同時與普通TLBO、自適應差分進化(adaptive DE，ADE)、人工蜂群(artificial bee colony，ABC)、粒子群(particle swarm optimization，PSO)、渦流搜索VS五種算法進行綜合對比。所有實驗均在64 位操作系統，主頻2.40 GHz，內存8.0 GB的筆記本電腦上采用Matlab2017B實現。

3.1 測試函數

采用文獻[24]提供的10個測試函數為仿真對象，它們均通過若干基本函數復合而成，基本特性如表1所示。所有函數均為極小值優化。

表1 10個測試函數的基本特性

對于函數

F

～

F

，

F

～

F

，變量個數分別取

D

=5, 10, 15, 20；對于函數

F

，

F

，變量個數分別取

D

=10, 15, 20。所有函數的變量取值范圍均為[-100, 100]。由于不同算法在一次迭代中目標函數的計算次數可能不同，因此對比相同迭代步數下的優化結果有失公平，而對比相同目標函數計算次數下的優化結果更為合理。根據文獻[24]，當

D

=5, 10, 15, 20時，限定目標函數的計算次數分別為5×10,10,3×10,10。

3.2 參數設置

種群規模：在種群規模NP的每步迭代中，關于目標函數計算次數，TLBO為2NP次，ITLBO為NP/3+4NP/3=5NP/3次，ADE、ABC、PSO、VS均為NP次。為保證ITLBO和TLBO每步迭代與其他算法有相同的目標函數計算次數，該文將ITLBO和TLBO的種群規模分別設置為0.6NP和0

.

5NP，此時ITLBO和TLBO的目標函數計算次數均為NP。該文取NP=100。其他參數：ABC的觀察閾值limit=100，采蜜蜂和跟蹤蜂均為0

.

5NP。ADE的縮放因子

F

隨迭代步數從0

.

2線性增加到0

.

9，交叉概率CR根據種群方差自適應確定。PSO的

c

=

c

=2，慣性因子從0

.

9隨迭代步數線性下降到0

.

4。VS沒有需要設置的個性參數。

3.3 優化結果對比

對于表1中的10個函數，考慮到不同維度的情況，共有38種組合。對于每種組合分別采用6種算法獨立優化30次，然后對比30次優化結果的平均誤差。具體結果如表2所示。

表2 30次優化結果的平均誤差對比

續表2

從實驗結果可以看出，沒有一種算法適合所有類型(單峰、基本、混合、復合)的函數。以ITLBO獲得最好結果的函數為例，當

D

=5時為3個基本函數(

F

、

F

、

F

)，1個復合函數(

F

)；當

D

=10時為1個基本函數(

F

)，2個復合函數(

F

、

F

)；當

D

=15時為1個基本函數(

F

)，1個混合函數(

F

)，3個復合函數(

F

、

F

、

F

)；當

D

=20時為2個基本函數(

F

、

F

)，2個復合函數(

F

、

F

)，如表2中粗體數字所示。總體看來，對于不同類型和維度的38種組合，ITLBO獲得最好結果的組合數是最多的。

3.4 實驗結果分析

綜合以上實驗結果，ITLBO的整體優化性能不僅明顯高于TLBO，同時也高于其他對比算法，從而驗證了改進方案的有效性及可行性。對于實驗結果，給出如下分析：

第一，ITLBO在原始TLBO的算法結構中，通過增加最優個體自尋優策略，突出了最優個體的“路標”指引作用。對于最優個體而言，其自尋優過程應側重于局部開發，這恰好是尋優后期渦流搜索的長處。因此該策略有助于提升算法的性能，這與表2中的實驗結果是一致的。

第二，ITLBO在原始TLBO的教學階段中，通過引入差分和輪盤賭策略，實現了經典算法的優勢互補。在個體更新中引入差分策略，可以通過融入隨機選取的候選解的差分向量，實現信息共享，并提高種群的多樣性，抑制早熟收斂。而引入輪盤賭策略可以提升高質量候選解獲得進化的機會。這是使ITLBO獲得高性能的重要原因。從算法結構看，ITLBO與ABC有相似之處，其階段2(向教師學)相當于ABC的采蜜蜂搜索，而階段3(學生互學)相當于ABC的跟蹤蜂搜索。這就是對比實驗結果中ITLBO和ABC的搜索性能較為相似的原因。

第三，ITLBO在提升優化性能的同時，由于引入了其他算子，提高了算法的計算復雜度。對于絕大多數群智能優化算法，優化性能和優化效率二者是不能兼得的。性能的提升一般都會伴隨著計算效率的降低，這與“無免費午餐定理”的結論是一致的。

4 結束語

提出了一種改進的教學優化算法，改進算法增加了基于渦流搜索的最優個體自尋優過程，同時在個體更新中增加了差分策略和輪盤賭選擇機制，目的在于通過優勢互補提升原算法的優化性能。采用不同維度的10個標準測試函數考察了改進算法的優化性能，通過與原始教學優化算法及其他同類算法的優化結果對比，驗證了改進算法的優勢。仿真實驗及實際應用結果揭示出該改進方案能夠有效提升目前教學優化算法的尋優能力。