李子揚，劉宗堡

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

0 引 言

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

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

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

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

在TLBO現(xiàn)有的改進方案中，融合其他經(jīng)典策略的改進方案相對較少，然而這類融合其他經(jīng)典策略的改進方案可以實現(xiàn)優(yōu)勢互補。

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

1 改進方案涉及的優(yōu)化算法

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

教學(xué)優(yōu)化算法的靈感來源于教師向?qū)W生傳授知識的教學(xué)過程。不失一般性，以極小值優(yōu)化為例，教學(xué)優(yōu)化算法包括以下兩個階段。

(1)教師階段。

設(shè)為第

t

步迭代種群平均值，為第

t

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

T

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

r

(-

T

)

(1)

其中，

T

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

r

是區(qū)間(0,1)內(nèi)均勻分布的隨機數(shù)。按式(2)計算與對應(yīng)的new,。若new,優(yōu)于，則=new,，否則保持不變。new,=+Difference_Mean

(2)

(2)學(xué)生階段。

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

(3)

1.2 渦流搜索算法

(1)產(chǎn)生初始解。

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

(4)

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

σ

可看作渦流外環(huán)初始半徑。

(2)當(dāng)前解的更新。

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

σ

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

圖1 渦流算法的搜索過程

(3)半徑縮減方法。

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

(5)

其中，

λ

>0

.

1為隨機變量，

a

>0為分辨率參數(shù)。

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

σ

=

σ

λ

γ

(

λ

,

a

-

t/

MaxItr)

(6)

其中，

a

=1，

t

為當(dāng)前步數(shù)，MaxItr為限定步數(shù)。

1.3 差分進化算法

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

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

DE的控制參數(shù)包括：種群規(guī)模NP，變量個數(shù)

D

及范圍，縮放因子

F

，交叉概率CR。所有個體均初始化為搜索空間內(nèi)均勻分布的隨機數(shù)，置當(dāng)前代數(shù)為

t

=1。

(2)生成變異向量。

計算所有個體目標(biāo)函數(shù)值，根據(jù)式(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)均勻分布的隨機數(shù)，rand{1,2,…,}為按均勻分布在{1,2,…,

D

}中隨機選取的一個整數(shù)。

(4)選擇操作。

比較(

t

+1)和(

t

)的目標(biāo)函數(shù)值，按貪婪選擇方法替換當(dāng)前個體。(

t

+1)=

(9)

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

t

=

t

+1，轉(zhuǎn)(2)。

2 改進的教學(xué)優(yōu)化算法

2.1 實施改進的基本思路

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

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

2.2 改進算法的實現(xiàn)方法

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

(1)種群規(guī)模設(shè)置及初始化。

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

(2)教師自學(xué)階段。

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

(10)

(3)向教師學(xué)階段。

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

對于個體(

i

=1,2,…,NP)，設(shè)為第

t

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

t

步迭代最優(yōu)個體(教師)，將看作種群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)為均勻分布的隨機數(shù)；

j

∈{1,2,…,NP}且

j

≠

i

；

d

∈{1,2,…,

D

}。個體

j

和維度

d

均隨機產(chǎn)生。最后，按貪婪選擇策略實現(xiàn)當(dāng)前個體的更新。

(4)學(xué)生互學(xué)階段。

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

Fitness=(1+

F

)

(12)

其中，

F

為目標(biāo)函數(shù)值。按式(13)構(gòu)造種群中每個候選解的選擇概率。

(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)為均勻分布的隨機數(shù)；

d

∈{1,2,…,

D

}為隨機產(chǎn)生的整數(shù)。最后，按貪婪選擇策略實現(xiàn)當(dāng)前個體的更新。

(5)算法終止條件。

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

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

3 對比實驗

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

3.1 測試函數(shù)

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

表1 10個測試函數(shù)的基本特性

對于函數(shù)

F

～

F

，

F

～

F

，變量個數(shù)分別取

D

=5, 10, 15, 20；對于函數(shù)

F

，

F

，變量個數(shù)分別取

D

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

D

=5, 10, 15, 20時，限定目標(biāo)函數(shù)的計算次數(shù)分別為5×10,10,3×10,10。

3.2 參數(shù)設(shè)置

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

.

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

.

5NP。ADE的縮放因子

F

隨迭代步數(shù)從0

.

2線性增加到0

.

9，交叉概率CR根據(jù)種群方差自適應(yīng)確定。PSO的

c

=

c

=2，慣性因子從0

.

9隨迭代步數(shù)線性下降到0

.

4。VS沒有需要設(shè)置的個性參數(shù)。

3.3 優(yōu)化結(jié)果對比

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

表2 30次優(yōu)化結(jié)果的平均誤差對比

續(xù)表2

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

D

=5時為3個基本函數(shù)(

F

、

F

、

F

)，1個復(fù)合函數(shù)(

F

)；當(dāng)

D

=10時為1個基本函數(shù)(

F

)，2個復(fù)合函數(shù)(

F

、

F

)；當(dāng)

D

=15時為1個基本函數(shù)(

F

)，1個混合函數(shù)(

F

)，3個復(fù)合函數(shù)(

F

、

F

、

F

)；當(dāng)

D

=20時為2個基本函數(shù)(

F

、

F

)，2個復(fù)合函數(shù)(

F

、

F

)，如表2中粗體數(shù)字所示?？傮w看來，對于不同類型和維度的38種組合，ITLBO獲得最好結(jié)果的組合數(shù)是最多的。

3.4 實驗結(jié)果分析

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

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

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

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

4 結(jié)束語

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