李會(huì)榮，周亞妮

(1. 商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院, 陜西 商洛 726000；2. 商洛職業(yè)技術(shù)學(xué)院 公共基礎(chǔ)部， 陜西 商洛 726000)

求解約束優(yōu)化問題的改進(jìn)教-學(xué)優(yōu)化算法

李會(huì)榮1，周亞妮2

(1. 商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院, 陜西 商洛 726000；2. 商洛職業(yè)技術(shù)學(xué)院 公共基礎(chǔ)部， 陜西 商洛 726000)

提出了一種非線性約束優(yōu)化問題改進(jìn)的教-學(xué)優(yōu)化算法，該算法首先提出了自適應(yīng)的教學(xué)因子，對(duì)學(xué)習(xí)階段的迭代方程進(jìn)行改進(jìn)，引入了差分變異策略；其次利用約束違反度函數(shù)將約束優(yōu)化問題轉(zhuǎn)化為無約束雙目標(biāo)優(yōu)化問題，在每次迭代中按照約束違反度的大小保留部分性能較優(yōu)不可行個(gè)體，有效地維持了種群的多樣性；最后數(shù)值實(shí)驗(yàn)表明，該算法具有較快的收斂速度和較好的全局尋優(yōu)能力.

教-學(xué)優(yōu)化算法； 約束優(yōu)化； 差分變異； 教學(xué)因子

近年來群體智能優(yōu)化算法作為一種啟發(fā)式優(yōu)化算法，得到了迅猛的發(fā)展，由于實(shí)現(xiàn)簡單、收斂速度快、魯棒性強(qiáng)，而且不需要函數(shù)的任何可微、可導(dǎo)等信息，具有良好的適應(yīng)性，成為優(yōu)化領(lǐng)域的一個(gè)研究熱點(diǎn).目前，具有代表性的群體智能優(yōu)化算法有：粒子群優(yōu)化算法[1]、遺傳算法[2]、差分進(jìn)化算法[3,16]和蟻群優(yōu)化算法[4]等等.2011年Rao R V等人[5-6]提出的一種新型的群體智能優(yōu)化算法，稱為教-學(xué)優(yōu)化算法(TLBO:Teaching-Learning-Based Optimization).教-學(xué)優(yōu)化算法模擬了教師的教學(xué)過程和學(xué)生的學(xué)習(xí)過程，目的是通過教師和學(xué)生之間的相互學(xué)習(xí)來提高學(xué)習(xí)成績，其參數(shù)少、算法簡單、速度快、精度高且具有極強(qiáng)的收斂能力，因而一經(jīng)提出，就引起了國內(nèi)外很多學(xué)者的關(guān)注，目前已經(jīng)應(yīng)用到一些實(shí)際問題，例如無約束優(yōu)化問題[6]、約束優(yōu)化問題[7]、多目標(biāo)優(yōu)化問題[8]等.

考慮以下一般的非線性約束優(yōu)化(COP)問題

F={x|gi(x) ≤0,i=1,2…，q;hj(x)=0,j=q+1,…，m}.

非線性約束優(yōu)化問題廣泛存在于科學(xué)計(jì)算等領(lǐng)域，是一類比較難以解決的優(yōu)化問題，沒有普遍適用的解法.目前在求解約束優(yōu)化問題的方法主要有確定性的方法和隨機(jī)性方法2類.確定性的方法主要有罰函數(shù)方法、拉格朗日乘子法和可行方向法等，通常往往需要目標(biāo)函數(shù)和約束函數(shù)連續(xù)，可微等信息，收斂速度較快，但是容易陷入局部極小，且求解的優(yōu)化問題規(guī)模相對(duì)較小.近年來，由于進(jìn)化算法不需要目標(biāo)函數(shù)和約束函數(shù)的任何導(dǎo)數(shù)信息，同時(shí)也是全局優(yōu)化技術(shù)，受到國內(nèi)外學(xué)者的高度重視，已經(jīng)被應(yīng)用到各類優(yōu)化問題中.目前，已經(jīng)提出了一些融合進(jìn)化算法的約束處理技術(shù)求解約束優(yōu)化問題[8-11].

本文提出了一種非線性約束優(yōu)化問題改進(jìn)的教-學(xué)優(yōu)化算法.該算法對(duì)教學(xué)因子進(jìn)行改進(jìn)，將差分進(jìn)化算法中的變異思想引入到學(xué)習(xí)階段的迭代方程中，有效地保持了種群的多樣性，定義了約束違反度函數(shù)將約束優(yōu)化問題轉(zhuǎn)化為無約束雙目標(biāo)優(yōu)化問題，在每次迭代中按照一定的閾值保持少部分性能較優(yōu)的不可行個(gè)體，有效的維持了種群的多樣性.數(shù)值實(shí)驗(yàn)的結(jié)果表明該算法的有效性和通用性.

1　基本教-學(xué)優(yōu)化算法(TLBO)

在教-學(xué)優(yōu)化算法中，學(xué)生的人數(shù)代表種群的規(guī)模，學(xué)生學(xué)習(xí)的科目個(gè)數(shù)表示優(yōu)化問題搜索空間的維數(shù)，學(xué)生學(xué)習(xí)的結(jié)果類似于優(yōu)化問題的適應(yīng)度，在整個(gè)群體中教師被認(rèn)為學(xué)習(xí)的最好者，代表最優(yōu)解.教-學(xué)優(yōu)化算法的搜索過程分為教學(xué)階段和學(xué)習(xí)階段.

1.1教學(xué)階段在教學(xué)階段，利用群體中當(dāng)前最優(yōu)個(gè)體對(duì)其他個(gè)體進(jìn)行教學(xué)，有效地融合了群體均值的影響.求解群體每一維的平均值mi，得到平均個(gè)體xm=(m1,m2,…，mn)，通過式(1)得到新個(gè)體xnew，然后計(jì)算其目標(biāo)函數(shù)值，并與舊的個(gè)體xold進(jìn)行比較，如果優(yōu)于舊的個(gè)體，則更新舊個(gè)體.

xnew=xold+rand·(xteacher-TF·xm) ,

(1)

其中，xteacher為當(dāng)前群體中的全局最優(yōu)個(gè)體，即表示教師的知識(shí)水平；rand為 [0,1]之間的隨機(jī)數(shù)；TF稱為教學(xué)因子，表示平均值的變化程度，通常設(shè)置為1或2，TF隨機(jī)地等概率的變化[5]

TF=round[1+rand]，

(2)

其中，round( )表示四舍五入取整.

1.2學(xué)習(xí)階段知識(shí)水平不僅通過教師的教學(xué)而提高，而且還可以通過學(xué)生之間的相互影響而提高.所以在學(xué)習(xí)階段隨機(jī)選擇2個(gè)學(xué)習(xí)者k,k′，且k≠k′，第i次迭代中由學(xué)習(xí)者k,k′相互影響而產(chǎn)生新的學(xué)習(xí)者

(3)

其中， f(xk)與f(xk′)分別表示個(gè)體k,k′的目標(biāo)適應(yīng)值.如果xnew優(yōu)于xold，則更新xold，如果xnew優(yōu)于xteacher，則更新xteacher.

2　約束的處理技術(shù)

用教-學(xué)優(yōu)化算法求解約束優(yōu)化問題時(shí)，處理約束條件是關(guān)鍵.筆者采取動(dòng)態(tài)目標(biāo)的處理方法[12]，其主要思想是將約束違反度函數(shù)作為優(yōu)化的第一個(gè)目標(biāo)，將目標(biāo)函數(shù)作為第二個(gè)目標(biāo)進(jìn)行優(yōu)化.為此定義約束違反度函數(shù)

(4)

minF(x)=min{φ(x),f(x)} .

(5)

由式(4)可以看出，φ(x)=0的所有解構(gòu)成了約束優(yōu)化問題的可行域，因此只有當(dāng)φ(x)=0時(shí)，才開始優(yōu)化minf(x).但是許多優(yōu)化問題的最優(yōu)解就在可行域的邊界附近，位于最優(yōu)解附近的不可行解對(duì)于尋找最優(yōu)解是很有幫助.因此設(shè)置一個(gè)約束違反度δ≥0，使得φ(x)≤δ時(shí)，就開始優(yōu)化f(x).如果子代個(gè)體在可行域的外面，即φ(x)>δ，則此個(gè)體以φ(x)為其優(yōu)化目標(biāo)，否則此個(gè)體以目標(biāo)函數(shù)f(x)進(jìn)行優(yōu)化.

如果某個(gè)學(xué)習(xí)者逃離搜索空間，將按式(6)在搜索空間內(nèi)進(jìn)行隨機(jī)賦值.

xnew=xl+rand·(xu-xl)，

(6)

其中，xu,xl分別表示搜索空間的上下界.

3　改進(jìn)教-學(xué)優(yōu)化算法(ITLBO)

3.1自適應(yīng)的教學(xué)因子在基本的教-學(xué)優(yōu)化算法中，教學(xué)因子TF的大小決定著平均值的變化情況，由式(2)可以看出，TF要么取值為1，或者取值為2，即學(xué)習(xí)者要么從教師那里沒有學(xué)到知識(shí)，要么學(xué)習(xí)者從教師那里學(xué)到全部知識(shí).但是在實(shí)際的教學(xué)中過程并不是這樣，而是介于兩者之間.在優(yōu)化算法中，TF越小則表示搜索的步長較小，收斂速度比較慢；而TF越大則加速算法的收斂速度，但減少算法局部探測能力.為了解決此問題，將TF設(shè)置隨著迭代次數(shù)而自適應(yīng)變化

(7)

其中，Imax表示最大的迭代次數(shù)，t表示當(dāng)前的迭代次數(shù).從式(7)可以看出，算法開始時(shí)教學(xué)因子TF取值為2，表示學(xué)習(xí)者接受知識(shí)的能力比較大，有利于加強(qiáng)算法的全局搜索能力，隨著迭代進(jìn)行TF取值為1，最后TF取值為0，表示隨著迭代的進(jìn)行，知識(shí)難度的逐漸增加，學(xué)習(xí)者學(xué)習(xí)知識(shí)的能力開始下降，有利于加強(qiáng)算法的局部搜索能力.

3.2差分變異策略學(xué)習(xí)者不僅可以從教師那里學(xué)到知識(shí)，還可以通過教師的引導(dǎo)自己的學(xué)習(xí)或與其他學(xué)習(xí)者的討論而提高學(xué)習(xí)能力.在基本的教-學(xué)優(yōu)化算法的學(xué)習(xí)階段中，新的學(xué)習(xí)個(gè)體只受2個(gè)學(xué)習(xí)者的影響，其實(shí)目前最好的學(xué)習(xí)者(即教師)的影響也不容忽視.因此，受差分進(jìn)化算法中變異策略DE/best/1思想的啟發(fā)，將學(xué)習(xí)階段迭代方程(3)改進(jìn)

xnew=xteacher+rand·(xk1-xk2)，

(8)

其中，xk1,xk2為在第i次迭代中2個(gè)互異的學(xué)習(xí)者，若xnew優(yōu)于xold，則更新xold；若xnew優(yōu)于xteader，則更新xteacher.

3.3隨機(jī)變異階段教-學(xué)優(yōu)化算法與其他智能優(yōu)化算法一樣，容易出現(xiàn)早熟收斂現(xiàn)象，特別是求解高維復(fù)雜的優(yōu)化問題.為此在教-學(xué)優(yōu)化算法中加入隨機(jī)變異策略，即在每次迭代的中按照一定的變異概率Pm產(chǎn)生如下新的變異個(gè)體

xnew=xr1+rand·(xr2-xr3)，

(9)

其中，r1,r2和r3為種群中隨機(jī)選擇的3個(gè)互異的個(gè)體，若xnew優(yōu)于xteacher，則更新xteacher.

3.4改進(jìn)教-學(xué)優(yōu)化算法(ITLBO)的實(shí)現(xiàn)步驟

步驟1設(shè)置班級(jí)學(xué)習(xí)人數(shù)n，學(xué)習(xí)的科目m，最大迭代次數(shù)Imax，初始化的約束違反度δ，設(shè)置當(dāng)前迭代代數(shù)t=1；

步驟2在搜索空間中初始化教學(xué)優(yōu)化種群，由式(4)計(jì)算初始個(gè)體的約束違反度φ(xi),若φ(xi) ≤δ，將第i個(gè)個(gè)體加入到初始種群，否則，繼續(xù)初始化，直到產(chǎn)生n個(gè)個(gè)體為止，將這n個(gè)個(gè)體作為初始種群；

步驟3計(jì)算每門課程的平均值xm，按照式(1)和(7)計(jì)算教學(xué)階段產(chǎn)生新的學(xué)習(xí)者xnew，若xnew優(yōu)于xold，則更新xold；若xnew還優(yōu)于xteacher，則更新xteacher；

步驟4按照式(8)計(jì)算學(xué)習(xí)階段產(chǎn)生新的學(xué)習(xí)者xnew，若xnew優(yōu)于xold，則更新xold；若xnew優(yōu)于xteacher，則更新xteacher；

步驟5按照式(9)產(chǎn)生新的變異個(gè)體，則更新全局最優(yōu)個(gè)體xteacher；

步驟6置t=t+1，返回到步驟3，直到t達(dá)到設(shè)定的最大迭代次數(shù),輸出全局最優(yōu)值.

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

4.1測試函數(shù)為了驗(yàn)證改進(jìn)教-學(xué)優(yōu)化算法的有效性，選取13個(gè)常見的約束問題測試函數(shù)[13-15]進(jìn)行試驗(yàn)，13個(gè)測試函數(shù)都是被認(rèn)為是用進(jìn)化算法很難優(yōu)化的復(fù)雜函數(shù),主要特性如表1所示.在表1中, ρ=│F│/│S│是估計(jì)可行域占整個(gè)搜索空間的比率，│F│表示可行解的個(gè)數(shù)，│S│表示整個(gè)搜索空間隨機(jī)產(chǎn)生解的個(gè)數(shù)，在實(shí)驗(yàn)中│S│=1 000 000，其中LI，NI，LE，NE分別表示約束優(yōu)化問題約束條件中線性不等式、非線性不等式和線性等式和非線性等式的個(gè)數(shù).

表1中的測試函數(shù)被認(rèn)為利用隨機(jī)優(yōu)化算法很難優(yōu)化的約束測試函數(shù)[14-15].問題g02，g03，g08和g12是極大化問題，利用-f(x)將其轉(zhuǎn)化為極小化問題.問題g03，g05，g11和g13包含等式約束hj(x)=0，j=1，2，…，l，將其轉(zhuǎn)化為不等式約束│hj(x)│-σ≤0，在本文中，σ=0.001.

表1　測試函數(shù)的主要性質(zhì)[15]

4.2測試結(jié)果與分析實(shí)驗(yàn)參數(shù)設(shè)置：種群大小n=500, 最大迭代次數(shù)Imax=3 000.從表1可以看出問題g05，g07和g13可行域的范圍非常小(ρ=0.000 0)，在初始化過程中很難產(chǎn)生可行個(gè)體，因此約束違反度δ在g05中設(shè)為δ=0.15，在g07中為δ=0.015，在g13中為δ=0.025，其余的問題設(shè)為δ=10e-10.在問題g01，g10 和g13中，隨機(jī)變異概率Pm=1，其余問題中變異概率pm=0.6.在方正臺(tái)式機(jī)Intel(R)Pentium(R) D CPU 2.80 GHz,2.80 GHz, 內(nèi)存1.00 GB上用Matlab 2010a進(jìn)行實(shí)驗(yàn)，每個(gè)測試函數(shù)在相同的條件下獨(dú)立運(yùn)行30次，函數(shù)的最優(yōu)值(記為Opt)以及30次實(shí)驗(yàn)的最好結(jié)果(記為Best)、中間值(記為Median)、最優(yōu)值平均值(記為Mean)、最差結(jié)果(記為Worst)以及標(biāo)準(zhǔn)差(記為Std)如表2所示.

表2 ITLBO算法的實(shí)驗(yàn)結(jié)果

從表2中可以看出，改進(jìn)教-學(xué)優(yōu)化算法對(duì)于大多數(shù)約束優(yōu)化問題基本上都找到了最優(yōu)解，并且標(biāo)準(zhǔn)差也比較小.問題g02,g03,g04,g06,g07,g08,g09,g11和g12，改進(jìn)教-學(xué)優(yōu)化在30次獨(dú)立試驗(yàn)中都達(dá)到了最優(yōu)值；問題g05，g010和g13是很難用進(jìn)化算法求解的優(yōu)化問題，g05和g13包含有等式約束，而且可行域也非常小，雖然改進(jìn)教-學(xué)優(yōu)化算法沒有達(dá)到最優(yōu)解，但是與最優(yōu)解的誤差相對(duì)較??；問題g01有2個(gè)局部極小-13.000和-12.453 125，但是改進(jìn)教-學(xué)優(yōu)化算法30次獨(dú)立實(shí)驗(yàn)算法都跳出這2個(gè)局部極小點(diǎn).

為了比較算法的性能，將教-學(xué)優(yōu)化算法與最新的3種算法ASCHEA[15]，SAVPSO[14]，IADE[11]已有的數(shù)值結(jié)果進(jìn)行比較，比較結(jié)果見表3～5,其中NA表示沒有公布的數(shù)據(jù).

表3　改進(jìn)教-學(xué)優(yōu)化算法(ITLBO)與ASCHEA結(jié)果的比較表

表4　改進(jìn)教-學(xué)優(yōu)化算法(ITLBO)與SAVPSO結(jié)果的比較表

表5　改進(jìn)教-學(xué)算法(ITLBO)與IADE結(jié)果的比較表

表3是改進(jìn)教-學(xué)優(yōu)化算法與ASCHEA算法的比較結(jié)果，對(duì)于函數(shù)g02，g03，g04，g05，g07，g08，g09和g10，改進(jìn)教-學(xué)優(yōu)化算法不僅從30次運(yùn)行的最好值，還是平均最優(yōu)值，都比ASCHEA算法的尋優(yōu)性能好，精度比較高，g12，g13以及最差值A(chǔ)SCHEA算法沒有提供.SAVPSO算法是利用自適應(yīng)速度改進(jìn)的PSO算法來求解約束優(yōu)化問題，是近年來提出的比較新穎的算法，從表4中可以看出，改進(jìn)教-學(xué)優(yōu)化算法的結(jié)果大部分優(yōu)于或接近于SAVPSO算法.IADE算法是利用自適應(yīng)改進(jìn)差分進(jìn)化算法求解約束優(yōu)化問題，從表5中可以看出除過g01函數(shù)外，改進(jìn)教-學(xué)優(yōu)化算法的運(yùn)行結(jié)果要優(yōu)于IADE算法.所以從表3～5中可以看出改進(jìn)教-學(xué)優(yōu)化算法是有效的，可以求解大量的約束優(yōu)化問題，同時(shí)對(duì)于測試函數(shù)g01以及含有等式約束的優(yōu)化問題，但是改進(jìn)教-學(xué)優(yōu)化算法計(jì)算結(jié)果并不理想，如何提高算法的計(jì)算精度是今后進(jìn)一步研究的課題.

5　結(jié)　論

針對(duì)約束優(yōu)化問題，提出了一種求解約束優(yōu)化問題的改進(jìn)教-學(xué)優(yōu)化算法.改進(jìn)教-學(xué)優(yōu)化算法提出了自適應(yīng)的教學(xué)因子，受差分進(jìn)化算法中變異策略的啟發(fā)，對(duì)學(xué)習(xí)階段的迭代方程進(jìn)行改進(jìn)，使得學(xué)習(xí)者的學(xué)習(xí)能力不僅受到學(xué)習(xí)者之間的相互影響，而且還受到當(dāng)前最好學(xué)習(xí)者的影響，最后加入了隨機(jī)變異策略，提高了算法的收斂速度，并應(yīng)用于求解約束優(yōu)化問題.通過13個(gè)測試函數(shù)實(shí)驗(yàn)表明，改進(jìn)教-學(xué)優(yōu)化算法具有較快的收斂速度和較好的全局尋優(yōu)能力.

[1] Kenedy J，Eberhart R.Particle warm optimization:proceedings of IEEE International Conference on Neural Network 1995，Perth，November 27-December 1，1995[C].[S.l.]:IEEE.1995.

[2] 李敏強(qiáng),冦紀(jì)淞,林丹，等.遺傳算法的基本理論與應(yīng)用[M].北京:科學(xué)出版社,2002.

[3] Storn R, Price K V. Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization 1997,11: 341-359.

[4] Blum C.Ant colony optimization: Introduction and recent trends[J].Physics of life reviews, 2005,2(4): 353-373.

[5] 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:303-315.

[6] 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-15.

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

[8] 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: 1 147-1 162.

[9] He Q, Wang L. An effective co-evolutionary particle swarm optimization for constrained engineering design problems[J]. Engineering Applications of Artificial Intelligence, 2007, 20(1):89-99.

[10] Runarsson T P, Yao X. Stochastic ranking for constrained evolutionary optimization[J]. IEEE Trans. Evol. Comput, 2000, 4(3):284-294.

[11] 李會(huì)榮.非線性約束優(yōu)化問題的自適應(yīng)差分進(jìn)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(25):44-48.

[12] Lu H, Chen W. Dynamic-objective particle swarm optimization for const rained optimization problems[J]. J Glob Optim, 2006, 12:409-419.

[13] Koziel S, Michalewicz Z. Evolutionary algorithms, homomorphous mapping and constrained parameter optimization[J]. Evolutionary computation, 1999,7(1):19-44.

[14] Lu H, Chen W. Self-adaptive velocity particle swarm optimization for solving constrained optimization problems[J]. Journal of Global Optimization，2008, 41(3): 427-445.

[15] Hamida B，Shoenauer M.ASCHEA:new results using adaptive segregational constraint handling:proceedings of the Congress on Evolutionary Computation 2002，Honolulu，May 12-17，2002[C].[S.l.]:IEEE，2002.

[16] 李會(huì)榮.基于單純形局部搜索的自適應(yīng)差分進(jìn)化算法[J].海南大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,31(2):143-148.

Improved Teaching-learning Based Optimization Algorithm for Constrained Optimization Problems

Li Huirong1, Zhou Yani2

(1. Department of Mathematics and Computer Application, Shangluo University, Shangluo 726000, China; 2. Department of Public Infrastructure, Shangluo Vocational and Technical College, Shangluo 726000, China)

In our report, an improved Teaching-Learning-Based Optimization (TLBO) algorithm for constrained optimization problems was proposed. Firstly, the adaptive teaching factor was proposed, which modified the iterative equation of learner phase and introduced the mutation strategy in the differential evolution algorithm; Secondly, the constraint violation function was used to convert the constrained optimization problems into unconstrained bi-objective optimization problem, in each iteration, keeping a part of the performance of better infeasible individuals is to maintain the diversity of the swarm. The numerical experiments showed that the proposed algorithm has faster convergence speed and better ability of global optimization.

Teaching Learning-Based Optimization (TLBO) Algorithm; constrained optimization; differential mutation; teaching factor

2015-03-14

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目(2014JM2-6098);陜西省教育廳科研計(jì)劃(15JK1221);商洛學(xué)院博士團(tuán)隊(duì)服務(wù)地方科技創(chuàng)新與經(jīng)濟(jì)社會(huì)發(fā)展能力提升專項(xiàng)(SK2014-01-22)

李會(huì)榮(1979-),男,陜西洛南人,副教授,碩士,研究方向：計(jì)算智能以及機(jī)器學(xué)習(xí)， E-mail:lihuirong417@163.com

1004-1729(2015)04-0333-07

TP 18

ADOl：10.15886/j.cnki.hdxbzkb.2015.0059