多學(xué)習(xí)教與學(xué)優(yōu)化算法

李志南　南新元　李　娜　史德生

1(新疆大學(xué)電氣工程學(xué)院　新疆 烏魯木齊 830047)

2(國(guó)網(wǎng)山東利津縣供電公司　山東 東營(yíng) 257400)

?

多學(xué)習(xí)教與學(xué)優(yōu)化算法

李志南1南新元1李娜1史德生2

1(新疆大學(xué)電氣工程學(xué)院新疆 烏魯木齊 830047)

2(國(guó)網(wǎng)山東利津縣供電公司山東 東營(yíng) 257400)

摘要針對(duì)教與學(xué)優(yōu)化算法(TLBO)局部開發(fā)能力差，易陷入局部最優(yōu)的缺點(diǎn)，提出一種基于反向?qū)W習(xí)的多學(xué)習(xí)教與學(xué)優(yōu)化算法(MTLBO)。通過反向?qū)W習(xí)技術(shù)拓展搜索空間，增加解的多樣性，進(jìn)一步增強(qiáng)算法的全局搜索能力。引入多學(xué)習(xí)機(jī)制，使其更有效地進(jìn)行局部搜索，加快收斂速度。同時(shí)提出一種小概率變異策略，增加跳出局部最優(yōu)的可能性。在基準(zhǔn)測(cè)試函數(shù)上進(jìn)行驗(yàn)證實(shí)驗(yàn)，結(jié)果表明，與TLBO算法、ITLBO算法以及其他優(yōu)化算法相比，該算法在低維和高維函數(shù)上都取得了較好的優(yōu)化效果。

關(guān)鍵詞教與學(xué)優(yōu)化算法反向?qū)W習(xí)技術(shù)多學(xué)習(xí)機(jī)制變異策略

TEACHING-LEARNING-BASED OPTIMISATION ALGORITHM WITH MULTI-LEARNING STRATEGY

Li Zhinan1Nan Xinyuan1Li Na1Shi Desheng2

1(School of Electrical Engineering,Xinjiang University,Urumqi 830047,Xinjiang,China)2(Lijinxian Power Supply Company,State Grid,Dongying 257400,Shandong,China)

AbstractWe proposed a teaching-learning-based optimisation algorithm (TLBO) with multi-learning mechanism (MTLBO), which is based on the opposition-based learning, aimed at the drawbacks of basic TLBO in poor local development ability and solutions being prone to falling into local optima. It broadens the search space through opposition-based learning technology to increase the diversity of solutions and further improve the global search ability of the algorithm. The introduction of multi-learning mechanism makes the local search more effective and speeds up the convergence rate. Meanwhile we presented a small probability mutation strategy to increase the likelihood of solutions jumping out of local optima. Verification experiments were carried out on benchmark test functions, results indicated that compared with basic TLBO, ITLBO and other optimised algorithms, the proposed MTLBO algorithm achieved better optimisation effect on both low and high dimensional functions.

KeywordsTeaching-learning-based optimisation algorithmOpposition-based learning technologyMulti-learning mechanismMutation strategy

0引言

教與學(xué)優(yōu)化算法TLBO是一種新的元啟發(fā)式優(yōu)化算法，由印度學(xué)者Rao R V等人[1]在2011年提出，它主要模擬教師的教學(xué)過程和學(xué)生之間的相互學(xué)習(xí)和交流過程。TLBO算法包括兩個(gè)重要階段，第一是教學(xué)階段，教師將自己的知識(shí)傳授給學(xué)生，提高班級(jí)的整體水平；第二是學(xué)習(xí)階段，學(xué)生通過課下的交流來提高自己的學(xué)習(xí)成績(jī)。TLBO算法結(jié)構(gòu)簡(jiǎn)單，易于理解，參數(shù)少，有極強(qiáng)的收斂能力和較好的全局搜索能力，已成功應(yīng)用于很多工程問題，如非線性連續(xù)大規(guī)模優(yōu)化[2]，平面鋼框架優(yōu)化設(shè)計(jì)[3]，電力經(jīng)濟(jì)調(diào)度[4]和熱交換器優(yōu)化[5,6]等問題。

TLBO算法全局搜索能力強(qiáng)，收斂速度快，但局部收索能力差，易陷入局部最優(yōu)。學(xué)者們針對(duì)該缺陷先后提出了一系列改進(jìn)算法，如Rao R V等人提出了一種基于多個(gè)老師的教與學(xué)優(yōu)化算法[7](ITLBO)和帶有精英策略的教與學(xué)優(yōu)化算法[8](MO-ITLBO)，前者應(yīng)用于無約束優(yōu)化問題，后者應(yīng)用于多目標(biāo)優(yōu)化問題。這些改進(jìn)算法雖然在一定程度上提高了TLBO算法的優(yōu)化性能，但還是存在易陷入局部最優(yōu)的問題。

針對(duì)TLBO算法局部搜索能力較弱的缺陷，本文提出了一種多學(xué)習(xí)教與學(xué)優(yōu)化(MTLBO)算法。采用多種學(xué)習(xí)方式來增強(qiáng)算法的局部搜索能力；利用反向?qū)W習(xí)技術(shù)[9]擴(kuò)展解空間，增加種群的多樣性，進(jìn)一步增強(qiáng)算法的全局探索能力；同時(shí)引入小概率的擾動(dòng)策略，提高跳出局部最優(yōu)的可能性。最后，通過對(duì)比實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

1基本TLBO算法

基本TLBO算法[1]是受老師的教學(xué)過程和學(xué)生的互相學(xué)習(xí)過程的啟發(fā)而提出來的，包括教學(xué)和學(xué)習(xí)兩個(gè)階段。在教學(xué)階段，學(xué)生通過老師與學(xué)生的平均水平值之間的差異來提高自己的成績(jī)；學(xué)習(xí)階段學(xué)生根據(jù)自身情況，與優(yōu)秀學(xué)生進(jìn)行交流學(xué)習(xí)，提高自己的成績(jī)。

1.1教學(xué)階段

教學(xué)階段是模擬老師的教學(xué)過程，選擇種群中的最優(yōu)個(gè)體作為老師，老師盡最大努力使得學(xué)生的平均水平向自己靠近，提高班級(jí)的整體水平。教學(xué)過程的數(shù)學(xué)表達(dá)式如式(1)所示：

Xnew=Xold+rand·(Xteacher-TF·Mean)

(1)

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

在相互學(xué)習(xí)的過程中，從種群中隨機(jī)選擇兩個(gè)不同的個(gè)體Xr1和Xr2，比較兩個(gè)個(gè)體的優(yōu)劣，然后選擇較優(yōu)個(gè)體進(jìn)行學(xué)習(xí)。假設(shè)所要解決的問題為最小值問題，學(xué)習(xí)過程的表達(dá)式如(2)所示：

(2)

2多學(xué)習(xí)TLBO算法

由于基本TLBO算法在解決低維簡(jiǎn)單問題時(shí)，有較好的全局搜索能力，但局部搜索能力差；在解決高維復(fù)雜問題時(shí)，全局搜索能力弱，易陷入局部最優(yōu)。為了克服基本TLBO 算法的上述不足，本文提出了一種多學(xué)習(xí)策略的教與學(xué)優(yōu)化(MTLBO)算法。首先提出一種新的多學(xué)習(xí)策略，增強(qiáng)其局部開發(fā)能力；繼而采用反向?qū)W習(xí)技術(shù)，拓寬搜索空間，增加種群多樣性，提高其全局勘探能力；同時(shí)為了避免陷入局部最優(yōu)，引入小概率的變異策略，更好地均衡算法的勘探和開發(fā)能力，增加其跳出局部最優(yōu)的可能性。

2.1反向?qū)W習(xí)技術(shù)

針對(duì)TLBO算法在解決高維復(fù)雜問題時(shí)，全局搜索能力較弱，無法找到較優(yōu)解，易陷入局部最優(yōu)的缺點(diǎn)，引入反向?qū)W習(xí)技術(shù)[10,11]。反向?qū)W習(xí)的概念是在2005年由Tizhoosh[9]提出，隨后應(yīng)用于差分進(jìn)化算法[12]，其基本思想是比較當(dāng)前解和反向解，若反向解優(yōu)于當(dāng)前解，則反向解取代當(dāng)前解。反向?qū)W習(xí)技術(shù)可以快速擴(kuò)大搜索空間，豐富種群多樣性，增加尋找到全局最優(yōu)解和跳出局部最優(yōu)的可能性。

定義1全局反向數(shù)：設(shè)x∈(a,b)是一個(gè)實(shí)數(shù)，與其對(duì)應(yīng)的全局反向數(shù)的表達(dá)式如式(3)所示：

xo=a+b-x

(3)

定義2全局反向點(diǎn)：設(shè)xi∈(x1,x2,…,xD)為D維空間內(nèi)的一個(gè)點(diǎn)，那么其全局反向點(diǎn)的表達(dá)式如下所示:

(4)

為提高TLBO算法的收斂速度和尋優(yōu)精度，在種群初始化時(shí)，應(yīng)用反向?qū)W習(xí)技術(shù)即式(4)對(duì)初始種群行反向?qū)W習(xí)，并各取一半較優(yōu)的個(gè)體來組成初始種群。在每一次迭代后，運(yùn)用反向?qū)W習(xí)技術(shù)對(duì)種群進(jìn)行反向?qū)W習(xí)，并取各種群中的一半較優(yōu)個(gè)體來組成一個(gè)新的種群，進(jìn)入下一次循環(huán)。種群在當(dāng)前解空間和反向解空間內(nèi)同時(shí)進(jìn)行搜索，保留各種群的較優(yōu)個(gè)體，使得種群始終在較優(yōu)個(gè)體附近進(jìn)行搜索，避免了在較差解鄰近區(qū)域的無效迭代，提高算法的全局收斂速度和尋優(yōu)精度。

2.2隨機(jī)多學(xué)習(xí)策略

基本TLBO算法采用向鄰近較優(yōu)個(gè)體進(jìn)行學(xué)習(xí)的方式，該學(xué)習(xí)方式比較單一，局部開發(fā)能力弱，容易陷入局部最優(yōu)。為此，本文提出了一種新的多學(xué)習(xí)策略；即個(gè)體在向鄰近較優(yōu)個(gè)體學(xué)習(xí)的同時(shí)，通過差異學(xué)習(xí)過程，彌補(bǔ)自身的不足，從而提高自己。兩種學(xué)習(xí)策略的引入，大大增強(qiáng)了算法的局部搜索能力，降低了算法易陷入局部最優(yōu)的可能。改進(jìn)的多學(xué)習(xí)方式表示如式(5)和式(6)所示：

if rand<0.5

(5)

else

(6)

end

其中，Xr1和Xr2為種群中不同于Xold的兩個(gè)隨機(jī)個(gè)體。

2.3小概率的變異策略

在多學(xué)習(xí)教與學(xué)優(yōu)化算法中，種群在當(dāng)前解空間和反向解空間內(nèi)同時(shí)進(jìn)行搜索，并各保留一半較優(yōu)個(gè)體組成新的種群，因此算法始終在種群相對(duì)較好解的鄰近區(qū)域進(jìn)行搜索。雖然反向?qū)W習(xí)技術(shù)能有效地?cái)U(kuò)大搜索空間，增加種群多樣性，加快算法的收斂速度，但搜索后期過度集中在一個(gè)相對(duì)較好的區(qū)域內(nèi)，種群容易陷入局部最優(yōu)，不能搜索到全局最優(yōu)值。針對(duì)該問題，本文引入小概率的擾動(dòng)策略,具體表達(dá)式如下：

if rand

xi,j=xj,min+rand·(xmax-xmin)

end

其中：Mr為隨機(jī)變異概率，由于這種操作是小概率事件，本文取Mr的值為0.005。

當(dāng)算法進(jìn)入迭代后期，算法搜索到一個(gè)相對(duì)較優(yōu)值時(shí)，由于鄰近區(qū)域搜索不到比其更優(yōu)的值時(shí)，就會(huì)陷入局部最優(yōu)，這時(shí)算法迫切需要跳出局部最優(yōu)。小概率發(fā)生的變異策略即隨機(jī)擾動(dòng)，可以增強(qiáng)算法跳出局部最優(yōu)的能力，有效地防止算法在搜索后期陷入局部最優(yōu)。

3多學(xué)習(xí)教與學(xué)優(yōu)化算法的基本步驟

本文提出的多學(xué)習(xí)教與學(xué)優(yōu)化算法的實(shí)現(xiàn)步驟如下：

步驟1種群初始化

根據(jù)式(7)進(jìn)行種群初始化，得到一個(gè)初始種群。按式(4)對(duì)初始種群進(jìn)行反向?qū)W習(xí)，得到一個(gè)反向群體。計(jì)算兩個(gè)種群中個(gè)體的適應(yīng)值，取各自種群一半的較優(yōu)個(gè)體組成新的初始種群。

xi,j=xj,min+rand·(xmax-xmin)

(7)

步驟2老師教學(xué)過程

找出種群中的最優(yōu)個(gè)體作為老師，每個(gè)學(xué)生根據(jù)式(2)向種群中最好的個(gè)體即老師進(jìn)行學(xué)習(xí)，提高自己的知識(shí)水平，從而提高全體學(xué)生的整體水平。

步驟3學(xué)生互相學(xué)習(xí)過程

經(jīng)過老師教學(xué)之后，同學(xué)之間進(jìn)行隨機(jī)的交流和學(xué)習(xí)，并進(jìn)行小概率的隨機(jī)擾動(dòng)，其具體流程如下所示：

if rand<0.5

if f(Xr2)

else

end

else

if f(Xold)

else

end

end

if rand

xi,j=xj,min+rand·(xmax-xmin)

end

步驟4種群更新

相互學(xué)習(xí)完成以后，利用式(4)對(duì)新產(chǎn)生的種群進(jìn)行反向?qū)W習(xí)，得到反向種群。計(jì)算兩個(gè)種群中個(gè)體的適應(yīng)值，取各自種群一半的較優(yōu)個(gè)體組成新的種群，進(jìn)入下一次迭代循環(huán)。

步驟5終止判斷

判斷是否滿足終止條件，若不滿足，繼續(xù)循環(huán)執(zhí)行步驟2到步驟4，若滿足，則終止迭代過程。

4數(shù)值實(shí)驗(yàn)及分析

4.1實(shí)驗(yàn)方法

本文選取文獻(xiàn)[7]和文獻(xiàn)[15]中的13個(gè)測(cè)試函數(shù)對(duì)本文提出的改進(jìn)算法進(jìn)行函數(shù)優(yōu)化測(cè)試，并選擇基本TLBO算法[1]、I-TLBO算法[7]、ABC算法[13]、I-ABC算法[14]進(jìn)行對(duì)比實(shí)驗(yàn)。測(cè)試的硬件環(huán)境為聯(lián)想筆記本電腦，主板CPU為i5-3230M-2.6 GHz，內(nèi)存為4 GB，采用Matlab2009b軟件平臺(tái)編程實(shí)現(xiàn)。實(shí)驗(yàn)中對(duì)比算法的參數(shù)設(shè)置按原文獻(xiàn)進(jìn)行設(shè)置，仿真結(jié)果亦直接取自各文獻(xiàn)。本文算法參數(shù)設(shè)置如下：NP=20，D=30、50、100，Mr=0.005，每組實(shí)驗(yàn)獨(dú)立運(yùn)行30次。

13個(gè)測(cè)試函數(shù)的具體表達(dá)式如下所示：

F1.Sphere function:

F2.Schwefel 2.22 function:

F3.Schwefel1.2 function:

F4.Schwefel 2.21 function:

F5.Step function:

F6.Quaritic function:

F7.Rastrigin function:

F8.Ackley function:

F9.Griewank function:

F10.Penalized function:

F11.帶有噪音的 shifted Schwefel’s problem 1.2:

F12.Rotated hyper-ellipsoid function:

F13.Zakharov function:

4.2仿真結(jié)果與分析

表1所示為函數(shù)F1-F10在維數(shù)為30和50時(shí)的比較結(jié)果，其中最優(yōu)結(jié)果進(jìn)行了加粗處理。從表1可以看出，對(duì)于所測(cè)函數(shù),除函數(shù)F6和F10外，MTLBO均能找到其最優(yōu)值，而ABC算法無法找到其中的任何一個(gè)，其他算法僅能找到其中的少數(shù)幾個(gè)。對(duì)于函數(shù)F1、F2和F9，除ABC外，其余4種算法均能找到其最優(yōu)值。雖然MTLBO在函數(shù)F6和F10上略差于I-TLBO，但I(xiàn)-TLBO無法找到函數(shù)的最優(yōu)值，而MTLBO也能搜索到最優(yōu)解附近的較優(yōu)解。對(duì)于函數(shù)F4-F5，MTLBO能搜索到其全局最優(yōu)值，性能優(yōu)于其他幾種算法。MTLBO算法能找到函數(shù)F7-F9的全局最優(yōu)值，具有較好的尋優(yōu)能力和較快的收斂速度。從整體上看，MTLBO優(yōu)于其他對(duì)比算法。

表1　F1-F10維數(shù)為30和50時(shí)的比較結(jié)果

針對(duì)上述10個(gè)測(cè)試函數(shù)，MTLBO能夠搜索到其中8個(gè)函數(shù)的全局最優(yōu)值，也搜索到其他2個(gè)函數(shù)最優(yōu)解附近較好的解，這充分說明了算法的有效性。綜上分析，本文算法具有較強(qiáng)的局部搜索能力，能夠有效地跳出局部最優(yōu)。

由于教與學(xué)優(yōu)化算法在解決高維復(fù)雜問題時(shí)，其全局搜索能力差，易陷入局部最優(yōu)，本文引入反向?qū)W習(xí)技術(shù)，增加了種群的多樣性，提高其全局收索能力，還增加了一種相互學(xué)習(xí)方法，提高了局部搜索能力，避免陷入局部最優(yōu)。接下來在6個(gè)高維復(fù)雜測(cè)試函數(shù)上對(duì)MTLBO算法進(jìn)行測(cè)試，并與最近文獻(xiàn)中較優(yōu)的NGHS[15]算法和OLHS[16]算法進(jìn)行比較。所選的6個(gè)測(cè)試函數(shù)中，F(xiàn)7-F9多峰函數(shù)，F(xiàn)11為帶噪聲和偏移的函數(shù)，F(xiàn)12是旋轉(zhuǎn)函數(shù)，F(xiàn)13函數(shù)是測(cè)試高維復(fù)雜函數(shù)的經(jīng)典函數(shù)。

從表2可以看出，本文提出的MTLBO算法每次均能夠準(zhǔn)確地找到相對(duì)應(yīng)的全局最優(yōu)解。這說明本文算法無論在優(yōu)化高維多峰函數(shù)，還是帶噪音和偏移的函數(shù)，都有較好的尋優(yōu)能力。對(duì)于函數(shù)F13，本文算法能找到其全局最優(yōu)值，進(jìn)一步說明本文算法在優(yōu)化高維復(fù)雜問題具有較好的尋優(yōu)能力。而NGHS算法僅能找到函數(shù)F11的全局最優(yōu)解，對(duì)于其他4個(gè)函數(shù)無法找到比較靠近全局最優(yōu)解的解，易陷入維數(shù)災(zāi)難。對(duì)于OLHS算法，不僅無法找到函數(shù)F8和F13的全局最優(yōu)解，同時(shí)多次運(yùn)行的方差較大，搜索到最優(yōu)解的成功率低，算法穩(wěn)定性差。

從尋優(yōu)效率看，NGHS、OLHS在尋優(yōu)過程中最大迭代次數(shù)均超過50 000次，而本文算法僅需40 000次，這說明本文算法收斂速度快、搜索效率高，具有較好的全局搜索和局部鄰域搜索能力。

綜上，本文所提算法具有較強(qiáng)的魯棒性和較好的穩(wěn)定性，同時(shí)具有較快的收斂速度和較高的搜索效率，該算法為優(yōu)化問題的求解提供了一種新的選擇，具有廣闊的發(fā)展前景。

表2　高維復(fù)雜測(cè)試函數(shù)對(duì)比結(jié)果(d=100)

5結(jié)語(yǔ)

本文針對(duì)基本教與學(xué)優(yōu)化算法中學(xué)習(xí)方式單一的問題，提

出多學(xué)習(xí)策略，有效地增強(qiáng)了算法局部開發(fā)能力；引入反向?qū)W習(xí)技術(shù)，充分挖掘反向種群中個(gè)體包含的信息；提出小概率的擾動(dòng)策略，有效降低了迭代后期陷入局部最優(yōu)的可能性。實(shí)驗(yàn)結(jié)果表明，本文算法不僅對(duì)低維簡(jiǎn)單問題有較好的尋優(yōu)能力，而且在解決高維復(fù)雜優(yōu)化問題時(shí)展現(xiàn)出了更明顯的優(yōu)勢(shì)，有效地解決了基本TLBO算法在解決高維問題易陷入局部最優(yōu)的問題，為解決高維復(fù)雜問題提供了一個(gè)良好的選擇。在今后的研究工作中，繼續(xù)對(duì)算法的學(xué)習(xí)階段作進(jìn)一步的探索和改進(jìn)，同時(shí)對(duì)算法的參數(shù)自適應(yīng)問題進(jìn)行探究，進(jìn)一步提高算法的性和應(yīng)用領(lǐng)域。

參考文獻(xiàn)

[1] Rao R V,Savsani V J,Vakharia D P.Teaching-learning-based optimization: a novel method for constrained mechanical design optimization problems[J].Computer-Aided Design,2011,43(3):303-315.

[2] Rao R V,Savsani V J,Vakharia D P.Teaching-learning-based optimization:An optimization method for continuous non-linear large scale problems [J].Information Sciences,2012,183(1):1-15.

[3] Togan V.Design of planar steel frames using teaching-learning based optimization[J].Engineering Structures,2012,34(1):225-232.

[4] Wu Wei,Hu Jingtao,Zhang Jilong.Prognostics of machine health condition using an improved ARIMA-based prediction method[C].Proc of the 2nd IEEE Conference on Industrial Electronics and Applications,2007:1062-1067.

[5] Rao R V,Patel V.Multi-objective optimization of heat exchangers using a modified Teaching-learning-based optimization algorithm[J].Applied Mathematical Modeling,2013,37(3):1147-1162.

[6] Rao R V,Patel V.Multi-objective optimization of two stage thermoelectric coolers using a modified teaching-learning-based optimization algorithm [J].Engineering Applications of Artificial Intelligence,2013,26(1):430-445.

[7] Rao R V,Patel V.An improved teaching-learning-based optimization algorithm for solving unconstrained optimization problems[J].Scientia Iranica,2013,20(3):710-720.

[8] Rao R V,Patel V.An elitist teaching-learning-based optimization algorithm for solving complex constrained optimization problems[J].International Journal of Industrial Engineering Computations,2012,3(4):535-560.

[9] Tizhoosh R.Opposition-based learning:a new scheme for machine intelligence[C]//Proceeding of International Conference on Computational Intelligence Modeling Control and Automation,Vienna,2005:695-701.

[10] Rahnamayan S,Tizhoosh H R,Salama M M A.Quasi-oppositional differential evolution[C]//Proceeding of the IEEE congress on evolutionary computation,2007:29-36.

[11] Roy P K,Mandal D.Quasi-oppositional biogeography-based optimization for multi-objective optimal power flow[J].Electric Power Components and Systems,2011,40(2):236-56.

[12] Rahaamayan S,Tizhoosh H R,Salama M M A.Opposition-Based differential evolution[J].IEEE Transations on Evolutionary Computation,2008,12(1):64-79.

[13] Li G,Niu P,Xiao X.Development and investigation of efficient Artificial Bee Colony algorithm for numerical function optimization[J].Applied Soft Computing,2012,12(1):320-332.

[14] Yang J G,Zhuang Y B.An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem[J].Applied Soft Computing,2010,10(2):653-660.

[15] Zou Dexuan,Gao Liqun,Wu jianhua,et al.Novel global harmony search algorithm for unconstrained problems[J].Neurocomputing,2010,73(16-18):3308-3318.

[16] 歐陽(yáng)海濱,高立群,鄒德旋,等.反向?qū)W習(xí)和聲搜索算法優(yōu)化高維函數(shù)問題[J].小型微型計(jì)算機(jī)系統(tǒng),2014,35(3):571-578.

中圖分類號(hào)TP3

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.02.057

收稿日期：2014-06-29。新疆“十二五”制造業(yè)信息化科技示范工程項(xiàng)目(201130110)。李志南，碩士生，主研領(lǐng)域：智能優(yōu)化算法。南新元，副教授。李娜，碩士生。史德生，本科生。