李子揚(yáng)，劉宗堡

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

0 引 言

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

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

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

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

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

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

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

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

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

(1)教師階段。

設(shè)為第

t

步迭代種群平均值，為第

t

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

T

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

r

(-

T

)

(1)

其中，

T

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

r

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

(2)

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

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

(3)

1.2 渦流搜索算法

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

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

(4)

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

σ

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

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

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

σ

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

圖1 渦流算法的搜索過(guò)程

(3)半徑縮減方法。

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

(5)

其中，

λ

>0

.

1為隨機(jī)變量，

a

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

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

σ

=

σ

λ

γ

(

λ

,

a

-

t/

MaxItr)

(6)

其中，

a

=1，

t

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

1.3 差分進(jìn)化算法

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

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

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

D

及范圍，縮放因子

F

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

t

=1。

(2)生成變異向量。

計(jì)算所有個(gè)體目標(biāo)函數(shù)值，根據(jù)式(7)為每個(gè)個(gè)體生成變異向量。

(

t

+1)=(

t

)+

F

[(

t

)-(

t

)]

(7)

其中，

i

,

r

,

r

,

r

∈{1,2,…,NP}為隨機(jī)選擇且互不相同的個(gè)體序號(hào)。

(3)交叉操作。

對(duì)變異向量(

t

+1)，生成試探向量(

t

+1)=[(

t

+1),…,(

t

+1)]，其中：

(8)

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

D

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

(4)選擇操作。

比較(

t

+1)和(

t

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

t

+1)=

(9)

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

t

=

t

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

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

2.1 實(shí)施改進(jìn)的基本思路

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

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

2.2 改進(jìn)算法的實(shí)現(xiàn)方法

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

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

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

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

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

(10)

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

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

對(duì)于個(gè)體(

i

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

t

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

t

步迭代最優(yōu)個(gè)體(教師)，將看作種群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ī)數(shù)；

j

∈{1,2,…,NP}且

j

≠

i

；

d

∈{1,2,…,

D

}。個(gè)體

j

和維度

d

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

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

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

Fitness=(1+

F

)

(12)

其中，

F

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

(13)

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

i

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

i

-1,

i

+1,…, NP}中隨機(jī)選擇

j

,

k

且

j

≠

k

，然后按式(14)計(jì)算

X

new,。

(14)

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

d

∈{1,2,…,

D

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

(5)算法終止條件。

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

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

3 對(duì)比實(shí)驗(yàn)

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

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

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

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

對(duì)于函數(shù)

F

～

F

，

F

～

F

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

D

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

F

，

F

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

D

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

D

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

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

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

.

5NP，此時(shí)ITLBO和TLBO的目標(biāo)函數(shù)計(jì)算次數(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沒(méi)有需要設(shè)置的個(gè)性參數(shù)。

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

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

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

續(xù)表2

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

D

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

F

、

F

、

F

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

F

)；當(dāng)

D

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

F

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

F

、

F

)；當(dāng)

D

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

F

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

F

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

F

、

F

、

F

)；當(dāng)

D

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

F

、

F

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

F

、

F

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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