康佳惠，鄒 鋒，陳得寶，姜子琪

(淮北師范大學 物理與電子信息學院，安徽 淮北 235000)

0 引 言

隨著互聯(lián)網的發(fā)展，智能優(yōu)化算法在人工神經網絡、函數(shù)優(yōu)化、電商以及工程應用等領域得到了普遍的應用。傳統(tǒng)的智能優(yōu)化算法有遺傳算法(Genetic Algorithm,GA)[1]、差分進化算法(Differential Evolution,DE)[2]、粒子群算法(Particle Swarm Optimization,PSO)[3]等。它們在處理一些復雜的優(yōu)化問題上存在很多的缺陷，因此一些新的算法和改進后的算法不斷被提出。在算法改進的方面，研究人員大多是根據(jù)算法的缺陷進行針對性的改進，也有研究人員將兩個算法混合在一起來達到改進的目的。教學優(yōu)化算法(TLBO)是印度學者Rao等人[4]在2012年提出的一種群智能優(yōu)化算法，該算法實現(xiàn)簡單、容易理解、算法實現(xiàn)過程中使用參數(shù)較少，對于一些問題的優(yōu)化體現(xiàn)出很好的性能。但是，在一些高維的問題上TLBO還是存在著收斂精度不高的問題。TLBO的搜索是貪婪搜索的方式，算法收斂速度快，種群缺乏多樣性，全局搜索能力比較差。因此，可以通過增加種群的多樣性來改善TLBO的整體性能。新算法利用回溯搜索算法(BSA)[5]有較強的全局搜索能力以及保留歷史種群信息方便快速確定搜索方向的特點，將BSA分別與TLBO的兩個階段結合，改善其種群多樣性差的缺點。同時，BSA的收斂精度也不夠高。因此，在BSA的個體更新中加入了最優(yōu)值引導的思想[6]，來達到改善算法收斂精度的目的。

1 背景知識

教學優(yōu)化算法和回溯搜索算法都是應用比較廣泛的智能優(yōu)化算法，下面是對兩種算法的詳細介紹。

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

教學優(yōu)化算法主要分為“教”和“學”兩個階段[7]，在“教”的階段教師通過向學生分享知識來提高班級的平均成績；在“學”的階段，學生通過向其他同學學習來提高自己的成績。

在“教”的階段，學生(個體)根據(jù)班級平均位置與老師位置的差距進行學習。個體的更新公式如下：

Xi,new=Xi,old+rand*(Xteacher-TFXmean)

(1)

式中，Xi,new和Xi,old分別表示第i位學生的新位置和上一代的位置；rand為0～1之間的隨機數(shù)；Xteacher表示老師的位置；TF由式(2)確定；Xmean由式(3)確定。

TF=round[1+rand(1)]

(2)

(3)

式中，xi1表示第i位學生一維的位置，d表示維數(shù)。

在“學”的階段，學生(個體)從群體中隨機選擇個體k進行學習，個體的更新公式如下：

(4)

式中，f(Xi)為第i個體的適應度值，rand為0～1之間的隨機數(shù)；如果新個體的f(Xi,new)優(yōu)于上代個體f(Xi,old)，則Xi,old=Xi,new。

1.2 回溯搜索算法

回溯搜索算法(BSA)主要包括五個基本操作：初始化種群，選擇-Ⅰ，變異，交叉和選擇-Ⅱ[6]。它與其他群智能算法最大的不同是保留了歷史種群信息，既可以運用當前種群的信息又不會丟失了歷史種群中重要的信息。

1)初始化:初始化種群P和歷史種群OldP，公式如下：

(5)

2)選擇-I：依概率執(zhí)行選擇-I操作，產生一個新的OldP，接著對OldP進行隨機排序，公式如下：

(6)

式中，a,b為0～1之間分布均勻的隨機數(shù)，permuting(·)是洗牌函數(shù)。

3)變異：變異操作的公式如下：

Pop=P+F*(OldP-P)

(7)

4)交叉：BSA 的交叉有兩步。先定義一個映射矩陣Map，矩陣大小為N*D，初始值均為零。然后依據(jù)概率隨機更新Map，公式如下：

ifaMap(i,j)=1
else
Map(i,k)=1

(8)

式中，a和b均為0～1之間的隨機數(shù)，j=1:ceil(rand*D)，k=randi*D，rand為0～1之間的隨機數(shù)，randi為分布均勻的偽隨機整數(shù)。

新種群中的個體按照式(9)產生，并判斷newP中的個體是否超過了邊界，若超過了邊界，則按照式(5)重新產生新位置。

newPi,j=Pi,j+(Mapi.j*F)*(OldPi,j-Pi,j)

(9)

5)選擇-II:采用的是貪婪選擇機制，選擇公式如下：

Pi=

(10)

式中，fitness(newPi)和fitness(Pi)分別為個體Pi更新前后的適應度值。

2 基于回溯搜索的教學優(yōu)化算法

智能優(yōu)化算法廣泛應用于各個領域，但并不是對每個問題的優(yōu)化都能體現(xiàn)良好的性能。教學優(yōu)化算法雖然在進化學習過程中收斂速度較快，但是“教”階段的操作使得算法具有多樣性差、易陷入局部最優(yōu)等缺點?；厮菟阉魉惴ㄊ且环N元啟發(fā)式算法，依概率保留部分歷史種群的信息，在確定新個體的搜索方向時，會提供歷史經驗，但與此同時收斂速度慢、收斂精度低?；谶@一特點，設計了一種新的帶回溯搜索的教學優(yōu)化算法，該算法以TLBO為主體框架，在“教”與“學”兩個階段與BSA算法相融合，充分利用BSA 算法中保留的歷史種群信息，以維持算法種群的多樣性，改善了整體優(yōu)化性能。為了在引入BSA后能更好的改善TLBO的性能，在BSA更新個體時引入了最優(yōu)個體引導，有效的改善了BSA收斂精度低的缺陷。具體的算法操作描述如下。

2.1 “教”階段

由TLBO和BSA的優(yōu)缺點可知，這兩個算法在一些性能上是互補的。因此，新算法對 TLBO的兩個階段分別做了改進?！敖獭钡碾A段，首先在TLBO產生的新個體和改進后的BSA產生的新個體間進行隨機選擇，再執(zhí)行BSA第二次選擇的操作；這種混和方式，有效的改善了“教”階段的缺點，提高了優(yōu)化性能。具體如下：

先根據(jù)BSA的選擇-I、交叉和變異操作得到新種群newP1。本文中，加入最優(yōu)個體引導后的個體更新公式為：

newPi,j=Pi,j+(Mapi.j*F)*(OldPi,j-Pi,j)+

rand*(Besti,j-Pi,j)

(11)

式中，rand為0～1之間的隨機數(shù)，Besti,j為全局最優(yōu)個體。

接著，根據(jù)TLBO中式(1)更新個體，對新個體進行邊界限定，得到新種群newP2，然后對newP1和newP2進行隨機混合操作，公式如下：

(12)

式中，u為0～1之間的隨機數(shù)。最后，計算newP的適應度值，再進行選擇-II操作，確定全局最優(yōu)值。

2.2 “學”階段

“學”的階段，和“教”的階段一樣，首先在TLBO產生的新個體和改進的BSA產生的新個體間進行隨機選擇，再執(zhí)行BSA第二次選擇的操作。具體如下：

“學”階段產生newP1的方式與“教”階段一樣，產生newP1時的最優(yōu)個體是“教”階段的全局最優(yōu)。根據(jù)TLBO中式(4)產生newP2，接著對newP1和newP2進行隨機選擇操作，公式如下：

(13)

式中，m,n為0～1之間的隨機數(shù)。對newP進行邊界限定，計算newP的適應度值，再進行選擇-II操作，確定全局最優(yōu)值。

2.3 算法詳細步驟

根據(jù)以上的分析描述，提出的帶回溯搜索的教學優(yōu)化算法的具體實現(xiàn)步驟如下：

步驟一：參數(shù)初始化。設置種群大小PopSize、空間維度DimSize、最大評估次數(shù)MaxFEs、最大迭代次數(shù)Maxgen，上邊界Xmax，下邊界Xmin。

步驟二：種群初始化及評估 。按式(5)初始化種群P和歷史種群OldP，評價種群P,確定全局最優(yōu)以及計算當前種群的平均位置。

步驟三：教階段個體的更新。依據(jù)式(6)進行第一次選擇及種群OldP隨機排序；按式(11)進行個體更新，產生新的種群newP1；把全局最優(yōu)個體當作老師，按式(1)進行個體更新，產生新的種群newP2；按式(12)進行隨機混合，得到新種群newP。

步驟四：個體適應度評估及選擇。計算newP的適應度值，再按式(10)執(zhí)行第二次選擇操作，確定全局最優(yōu)。

步驟五：學階段個體的更新。依據(jù)式(6)進行第一次選擇及種群OldP隨機排序；按式(11)進行個體更新，產生新的種群newP1；按式(4)進行個體更新，產生新的種群newP2；按式(13)進行隨機選擇，得到新種群newP，對newP進行邊界限定。

步驟六：重復步驟四。

步驟七：算法終止條件判斷。當前評價次數(shù)FEs是否小于MaxFEs，若小于MaxFEs，則返回步驟三，否則迭代結束。

3 仿真實驗及其分析

為了驗證帶回溯搜索的教學優(yōu)化算法的有效性和可行性，將選取18個典型的測試基準函數(shù)[14]進行仿真實驗，實驗中將帶回溯搜索的教學優(yōu)化算法與BSA[8],TLBO[4],ETLBO[9],PSOFDR[10],PSOwFIPS[11],jDE[12],SaDE[13]等典型的優(yōu)化算法進行比較分析。

3.1 參數(shù)設置

下面是其他算法的相關參數(shù)，都來自于參考文獻：

ETLBO[9]：elitesize=2；

PSOFDR[10]：wmin=0.4,wmax=0.9,ψ1=1,ψ2=1,ψ3=2；

PSOwFIPS[11]：w=0.7298；

jDE[12]：F=0.5，CR=0.9；

SaDE[13]：F～N(0.5,0.3),CR0=0.5,CR～N(CRm,0.1),LP=50；

3.2 結果分析

為了比較TLBO-BSA算法與其他優(yōu)化算法(BSA,TLBO,ETLBO,PSOFDR,PSOwFIPS,jDE,SaDE)之間性能的優(yōu)劣，各個算法獨立運行10次，在函數(shù)中進行了測試。為了進一步測試算法的穩(wěn)定性，不僅在10維的函數(shù)上進行了實驗，對30維的函數(shù)也進行了實驗。在測試的過程中，記錄了每個算法在函數(shù)上的最好解(Best)、平均解(Mean)、標準差(Std)比較分析。最后得到的結果如表1和表2所示，表1是10維函數(shù)的運行結果，表2是30維函數(shù)的運行結果，表中的最優(yōu)值用粗體表示。圖1給出了30維函數(shù)運行結果中具有代表性的函數(shù)收斂曲線。

表1 10維函數(shù)的測試結果

算法F4BestMeanStdF5BestMeanStdF6BestMeanStdTLBO-BSA9.9E-1053.6E-991.08E-980.28031.34670.80983.6E-153.6-150BSA0.00110.01380.01950.45282.22741.17251.5E-071.5E-061.4E-06TLBO2.5E-524.7E-501.34E-490.01510.10290.110903.2E-151.1E-15ETLBO1.4E-506.1E-491.09E-480.01370.07610.07793.6-153.6-150PSOFDR9.7E-324.4E-306.09E-300.29080.39860.09923.6-153.9E-151.1E-15PSOwFIPS2.2E-064.0E-061.93E-064.75615.35310.24641.1-052.2-059.0E-06jDE1.8E-211.3E-183.06E-186.7E-050.03240.03703.6-153.6-150SaDE3.9E-282.2E-246.46E-240.03621.53291.79863.6-153.6-150

算法F7BestMeanStdF8BestMeanStdF9BestMeanStdTLBO-BSA05.96986.006500.67212.125400.07230.0459BSA9.3-050.16030.32050.00010.00030.00030.00010.00800.0077TLBO0.99502.92131.661200000.00120.0039ETLBO3.1E-111.99191.818200000.00830.0153PSOFDR1.1-093.38291.76740000.05650.07850.0165PSOwFIPS1.08562.57720.79000.00120.00150.00030.02030.11710.0535jDE00003.1E-109.7E-10000SaDE00000001.1E-142.4E-14

算法F10BestMeanStdF11BestMeanStdF12BestMeanStdTLBO-BSA355.3151611.0203208.08781.5E-1471.4E-1393.9E-1394.7E-1106.8E-982.1E-97BSA0.00010.0004080.0005211.0E-131.2E-101.7E-100.00020.01740.0339TLBO236.8768570.8403198.77411.3E-1084.0E-1031.1E-1022.6E-536.7E-501.4E-49ETLBO236.8768658.1206261.53592.0E-983.2E-929.9E-921.7E-524.9E-498.0E-49PSOFDR355.3151548.7655141.36931.0E-566.4E-521.9E-515.7E-341.4E-302.5E-30PSOwFIPS127.6030384.2049175.96397.2E-115.9E-106.9E-108.9E-073.0E-062.1E-06jDE0.00010.000104.5E-454.3E-361.4E-353.1E-215.1E-181.5E-17SaDE0.00010.000103.7E-442.3E-347.3E-343.8E-312.0E-245.5E-24

算法F13BestMeanStdF14BestMeanStdF15BestMeanStdTLBO-BSA1.13423.89221.94073.6E-153.6E-150010.44715.4748BSA3.02234.48721.23791.3E-065.4E-065.6E-063.79727.74002.4719TLBO0.10260.95350.727202.9E-151.5E-151.00033.29502.0923ETLBO0.02421.14001.630803.2E-151.1E-153.8E-054.00773.9202PSOFDR0.24883.21863.42203.6E-153.6E-1504.97487.36272.2100PSOwFIPS4.42045.51240.70461.8E-052.2E-056.6E-064.73328.73832.4794jDE0.00380.37400.38963.6E-153.6E-1502.51045.23541.5672SaDE0.05803.67862.34543.6E-153.6E-1503.00357.05022.2043

算法F16BestMeanStdF17BestMeanStdF18BestMeanStdTLBO-BSA0000.01970.11860.0909355.31511018.917389.2821BSA0.01840.19710.28510.00590.03250.02450.0007192.6907160.6673TLBO00000.01150.01350.0001439.9805280.1722ETLBO00000.00230.00500.0001467.1592252.9469PSOFDR00.06630.09730.01230.08850.0501118.4385468.7662258.2942PSOwFIPS0.00160.00360.00100.02100.18850.1125262.6322569.8324265.9330jDE04.9E-131.5E-121.5E-110.01820.01980.0001224.3375261.2260SaDE00000.00910.00860.000192.783470.8898

由上表1的結果可以看出，當函數(shù)維度為10時，TLBO-BSA在函數(shù)F1～F4,F11～F12上的最優(yōu)解、平均值、標準差均優(yōu)于其他算法。對于函數(shù)F7～F10，jDE和SaDE的性能要優(yōu)于其他幾個算法，而TLBO-BSA在函數(shù)F7～F9和F15的最優(yōu)解也達到了理論上的最優(yōu)值。在函數(shù)F16上，TLBO-BSA和TLBO,ETLBO以及SaDE相當，都達到了理論上的最優(yōu)值。jDE在F5和F13上的性能要優(yōu)于其他算法，但是也不能收斂到最優(yōu)值。TLBO-BSA對函數(shù)F5,F10,F13,F18的優(yōu)化性能比較差，存在一定的不足。為了進一步測試算法在高維函數(shù)中的優(yōu)化能力，對30維的函數(shù)進行了實驗，實驗結果如下表2所示。

表2 30維函數(shù)的測試結果

算法F4BestMeanStdF5BestMeanStdF6BestMeanStdTLBO-BSA8.4E-1832.4E-175019.420121.34340.83383.6E-153.6E-150BSA3.13586.12682.982021.236522.08790.57455.3E-102.7E-092.4E-09TLBO3.2E-374.5E-367.4E-3615.885217.33831.18133.6E-153.6E-150ETLBO5.7E-378.0E-351.6E-3416.229017.76391.22013.6E-153.6E-150PSOFDR4.6E-102.0E-083.9E-0811.652512.78720.86777.1E-159.2E-153.4E-15PSOwFIPS0.59410.91560.226425.286725.51920.17970.00010.00025.3E-05jDE2.1E-091.8E-072.9E-079.831511.10361.28023.6E-155.3E-151.9E-15SaDE3.4E-092.4E-082.6E-0823.168823.76460.38063.6E-153.6E-150

算法F7BestMeanStdF8BestMeanStdF9BestMeanStdTLBO-BSA4.974841.489720.4662000000BSA0.06001.60990.72142.8E-081.3E-062.4E-0602.5E-108.0E-10TLBO08.15876.7774000000ETLBO013.01507.1441000000PSOFDR17.909329.25187.16257.1E-050.15730.475000.017220.0144PSOwFIPS33.127250.828310.32450.00980.01350.00229.87E-060.00010.0001jDE00001.1E-053.60E-05000SaDE00.09950.3146000000

算法F10BestMeanStdF11BestMeanStdF12BestMeanStdTLBO-BSA2824.3524266.151789.6590004.3E-1931.7E-1750BSA0.00040.04840.14012.8E-102.0E-054.2E-052.26555.97922.5105TLBO2942.8973848.990580.43679.2E-2647.1E-25401.7E-391.0E-352.9E-35ETLBO3299.7484021.033586.61794.1E-2262.1E-21903.2E-385.7E-361.1E-35PSOFDR2232.1093370.669725.45216.5E-645.4E-451.7E-441.4E-092.0E-082.6E-08PSOwFIPS2149.2023341.729616.14779.0E-070.00010.00020.52150.79070.1722jDE0.00040.000403.5E-447.4E-202.4E-197.4E-109.8E-082.8E-07SaDE0.00040.000406.3E-442.6E-108.2E-102.3E-093.4E-085.0E-08

算法F13BestMeanStdF14BestMeanStdF15BestMeanStdTLBO-BSA22.436533.348314.61283.6E-153.6E-15020.894142.086717.3923BSA18.193032.765913.30211.1E-097.8E-097.8E-0929.471145.72758.0619TLBO14.402446.121126.30053.6E-153.6E-1501.59679.51554.2538ETLBO21.094148.765126.39793.6E-153.6E-1502.4E-0612.63606.3975PSOFDR19.284228.43467.66457.1E-150.73240.863423.879039.30089.0978PSOwFIPS24.457226.04780.79030.00020.00035.8E-0580.7142106.173312.7774jDE15.633616.62060.92483.6E-155.0E-151.8E-1528.852536.28215.5822SaDE22.484941.147218.70783.6E-153.6E-15045.618159.92468.0698

算法F16BestMeanStdF17BestMeanStdF18BestMeanStdTLBO-BSA0000003938.7994995.957699.1020BSA0.01400.34240.31051.7E-121.8E-065.4E-061551.1922383.833577.0682TLBO00003.5E-061.1E-052533.1494423.295741.5239ETLBO0000003692.5114622.922778.9898PSOFDR1.50841.99380.566000.00980.01233080.4583545.435494.2407PSOwFIPS0.03280.05830.018810.0E-060.00030.00032497.3113521.220746.6243jDE02.33964.253301.1E-173.5E-171696.1262294.650409.7542SaDE0000001225.4762528.721733.1159

由上表2所可知。對函數(shù)F1,F3,F8,F9,F11,F16,F17的優(yōu)化，TLBO-BSA在最優(yōu)解、平均值以及標準差上都達到了理論最優(yōu)值，且在F1,F3,F11上的優(yōu)化性能要比其他的算法好。TLBO-BSA在函數(shù)F2,F4,F12上的三個性能指標要優(yōu)于其他算法，其中標準差達到了0，可看出TLBO-BSA的魯棒性比較好。在函數(shù)F6,F14上TLBO-BSA的優(yōu)化性能與TLBO,ETLBO,jDE,SaDE相當，且標準差都為0。但是,對于函數(shù)F5,F10,F13,F18的優(yōu)化不論是10維還是30維都不能體現(xiàn)出很好的優(yōu)化性能，在優(yōu)化復雜函數(shù)的問題上還存在一定的不足，需要進一步改進。

綜上分析，TLBO-BSA算法的性能整體要優(yōu)于TLBO算法，且在大多數(shù)基準函數(shù)上TLBO-BSA的優(yōu)化性能要比其他算法好。由表中的最優(yōu)值和方差以及收斂圖可看出，在大部分測試函數(shù)中TLBO-BSA的收斂性和穩(wěn)定性要優(yōu)于其他算法。這樣的分析結果表明，這種改進策略能夠提高TLBO算法的求解精度和穩(wěn)定性。

4 結 語

提出了一種新的帶回溯搜索的教學優(yōu)化算法，新算法針對教學優(yōu)化算法的一些不足，結合回溯搜索算法的一些特點，將引入了最優(yōu)個體引導的回溯搜索算法和教學優(yōu)化算法混合在一起，既保留了教學優(yōu)化算法原本收斂速度快的特點，又保持了種群多樣性，改善了算法原本易陷入局部最優(yōu)的缺點，同時也提高了算法的收斂精度，較好的提升了算法整體的優(yōu)化性能。通過18個基準函數(shù)的測試，可以看出新算法在處理單模函數(shù)時有明顯的優(yōu)勢，處理多數(shù)旋轉函數(shù)以及一些多模函數(shù)時不能體現(xiàn)出明顯的優(yōu)勢，這也為TLBO以后的改進提供了方向。