吳聰聰,賀毅朝,趙建立,2
1.河北地質(zhì)大學(xué) 信息工程學(xué)院,石家莊 050031
2.全北國(guó)立大學(xué) 電子信息工程學(xué)院,韓國(guó) 全州 54896
集合聯(lián)盟背包問(wèn)題(set-union knapsack problem,SUKP)是經(jīng)典0-1背包問(wèn)題的一種擴(kuò)展[1-3],屬于NP完全問(wèn)題。它在投資決策[2,4]、柔性制造機(jī)器[1,5-6]、智慧城市[7]和流壓縮[8]等方面都得到了廣泛應(yīng)用。然而,Goldschmidt等人[1]使用動(dòng)態(tài)規(guī)劃法求解SUKP問(wèn)題,由于時(shí)間復(fù)雜度太高而缺乏實(shí)用性[3],Arulselvan提出的基于貪心策略的近似算法[2],當(dāng)問(wèn)題規(guī)模較大時(shí)也難以在可接受的時(shí)間內(nèi)獲得較好解。近期賀毅朝等人[3]提出用演化算法求解SUKP問(wèn)題的新方法,并提出一種對(duì)SUKP問(wèn)題中不可行解修復(fù)和優(yōu)化的策略——S-GROA(greedy repairing and optimization algorithm)。將該策略分別與二進(jìn)制蜂群算法、遺傳算法和二進(jìn)制差分演化算法結(jié)合,求解三類SUKP問(wèn)題。從求解速度、精度和穩(wěn)定性等方面說(shuō)明進(jìn)化算法是解決SUKP問(wèn)題的可行實(shí)用的方法。
教與學(xué)優(yōu)化算法[9](teaching-learning-based optimization,TLBO)是由Rao等人在2011年提出的一種新的進(jìn)化算法。由于TLBO具有參數(shù)少、結(jié)構(gòu)簡(jiǎn)單、求解速度快等特點(diǎn),已經(jīng)引起很多國(guó)內(nèi)外學(xué)者的關(guān)注[10-20],并在機(jī)械設(shè)計(jì)與處理的問(wèn)題優(yōu)化[11]、熱交換優(yōu)化處理[12]、熱冷器優(yōu)化[13]、平面鋼框架設(shè)計(jì)[14]、數(shù)據(jù)聚類分組[15]經(jīng)濟(jì)調(diào)度問(wèn)題[16]等領(lǐng)域得到良好應(yīng)用。
然而,TLBO算法本身也存在著對(duì)于較復(fù)雜問(wèn)題尋優(yōu)精度低,穩(wěn)定性差,收斂速度不夠快的不足[17]。為此,國(guó)內(nèi)外學(xué)者在TLBO算法的改進(jìn)和優(yōu)化上進(jìn)行了廣泛的研究。Rao等人[17]在原算法基礎(chǔ)上加入了精英策略,提出了ETLBO算法(elitistTLBO,ETLBO),ETLBO算法比原始算法在收斂速度和求解精度方面都有所提高。Rajasekhar等人[18]提出了相對(duì)精英教學(xué)優(yōu)化算法(elitist teaching learning opposition based algorithm,ETLOBA),該算法在尋優(yōu)精度及收斂速度上比ETLBO算法有所增強(qiáng)。于坤杰等人[19]提出了基于反饋的精英教與學(xué)優(yōu)化算法(feedback ETLBO,F(xiàn)ETLBO),該算法在學(xué)生“學(xué)”階段之后加入“反饋”階段,使算法在尋優(yōu)精度上取得了較好的效果。王培崇等人[20]通過(guò)引入混沌優(yōu)化、學(xué)生動(dòng)態(tài)自適應(yīng)學(xué)習(xí)、精英個(gè)體的共軛梯度搜索、反向?qū)W習(xí)和高斯學(xué)習(xí),對(duì)TLBO進(jìn)行了四方面的改進(jìn),提高了算法的收斂精度。但是以上改進(jìn)算法,文獻(xiàn)[17-19]策略較簡(jiǎn)單,改進(jìn)后的算法在性能上還有提升空間;文獻(xiàn)[20]中共軛梯度搜索不好確定迭代次數(shù),而且對(duì)算法搜索全局最優(yōu)解的作用不穩(wěn)定。因此,針對(duì)TLBO的特點(diǎn)和所求解問(wèn)題,恰當(dāng)?shù)剡x擇優(yōu)化措施非常重要。
本文針對(duì)求解SUKP問(wèn)題,提出一種改進(jìn)的二進(jìn)制教與學(xué)優(yōu)化算法(modified binaryTLBO,MBTLBO)。首先將TLBO算法通過(guò)編碼轉(zhuǎn)化機(jī)制設(shè)計(jì)成能求解SUKP問(wèn)題的二進(jìn)制TLBO算法(BTLBO)。然后,針對(duì)SUKP問(wèn)題,提出改進(jìn)的貪心優(yōu)化策略MS-GROA(modified S-GROA),該策略通過(guò)對(duì)可行解的二次優(yōu)化,能夠進(jìn)一步提升解的被優(yōu)化程度,從而提高SUKP的求解精度。另外,從教與學(xué)算法角度,在算法的“教”階段和“學(xué)”階段引入差分演化算法的交叉算子,讓進(jìn)化得到的臨時(shí)個(gè)體與原個(gè)體進(jìn)行交叉操作,平衡算法的全局搜索和局部開(kāi)發(fā)能力,避免算法早熟;通過(guò)在精英個(gè)體周圍,以自適應(yīng)標(biāo)準(zhǔn)差,按正態(tài)分布進(jìn)行局部搜索,進(jìn)一步提高算法的求解精度和收斂速度。最后,進(jìn)行了3組(每組10個(gè)實(shí)例)SUKP實(shí)例仿真。實(shí)驗(yàn)結(jié)果表明,MBTLOB算法與已有的求解SUKP問(wèn)題的進(jìn)化算法(二進(jìn)制蜂群算法、遺傳算法和二進(jìn)制差分演化)相比,平均求解精度更高,改進(jìn)的修復(fù)和優(yōu)化策略MS-GROA比原策略在對(duì)解的優(yōu)化上更有效。
定義1給定元素集合U={u1,u2,…,un}和項(xiàng)集S={U1,U2,…,Um},項(xiàng)集S中的每項(xiàng)Ui(i=1,2,…,m)是元素集合U的子集,即Ui?U,且每個(gè)項(xiàng)Ui擁有一個(gè)價(jià)值pi>0。U中的每個(gè)元素uj有一個(gè)重量wj>0(j=1,2,…,n)。將項(xiàng)集S中的項(xiàng)裝入載重為C的背包,如果設(shè)裝入背包的項(xiàng)構(gòu)成的集合為A,那么A的價(jià)值P(A)是A中所有項(xiàng)的價(jià)值之和,A的重量W(A)是A中所有項(xiàng)并集中包含的元素重量之和。要解決的問(wèn)題就是:如何選擇S中的項(xiàng)裝入背包,使得裝入集合A的重量W(A)在不超過(guò)載重C的情況下價(jià)值P(A)最大?上面的問(wèn)題可以用下面的數(shù)學(xué)模型描述[1-2]:
為了便于使用啟發(fā)式算法解決SUKP問(wèn)題,文獻(xiàn)[3]給出了一種整形規(guī)劃的數(shù)學(xué)模型,模型如式(3)和式(4):
其中,Y={y1,y2,…,ym}∈{0,1}m是m維的0-1向量,當(dāng)yi=1(i=1,2,…,m)時(shí)表示集合S中的第i項(xiàng)Ui屬于集合AY,當(dāng)yi=0(i=1,2,…,m)時(shí)表示集合S中的第i項(xiàng)Ui不屬于AY,AY是裝入背包的項(xiàng)構(gòu)成的集合,即AY?S。
教與學(xué)優(yōu)化算法(TLBO)是根據(jù)課堂教學(xué)中教師和學(xué)生的行為提出的一種群優(yōu)化算法。TLBO算法分為“教”和“學(xué)”兩個(gè)階段:“教”階段學(xué)生跟隨教師學(xué)習(xí),“學(xué)”階段是學(xué)生之間相互學(xué)習(xí)。算法中的教師由學(xué)生中成績(jī)最好者(適應(yīng)度最高的個(gè)體)來(lái)?yè)?dān)任,學(xué)生數(shù)量為種群規(guī)模N,學(xué)生個(gè)體為實(shí)向量Xi=[xi,1,xi,2,…,xi,m],i=1,2,…,N,教師用實(shí)向量Tt=[t1,t2,…,tm]表示。
3.1.1 “教”階段
在“教”階段,每個(gè)學(xué)生根據(jù)班級(jí)平均狀態(tài)與教師狀態(tài)的差異進(jìn)行學(xué)習(xí)。用差異向量D表示班級(jí)平均狀態(tài)與教師狀態(tài)的差異,該向量由式(5)計(jì)算得到,然后再由式(6)求得當(dāng)前個(gè)體學(xué)習(xí)后的新個(gè)體Xnewi,如果新個(gè)體Xnewi的適應(yīng)度更高,則由新個(gè)體代替原個(gè)體,否則原個(gè)體保持不變。
式(5)中,rt是[0,1]上的隨機(jī)數(shù),Tt為教師個(gè)體,Mt為全班平均狀態(tài)(即),λ為教學(xué)因子,它決定平均值改變的程度,其值可以是1或2,由式(7)計(jì)算得到。
式(7)中,round表示四舍五入取整函數(shù),rand(0,1)產(chǎn)生0到1之間的隨機(jī)數(shù)。
在“教”階段,實(shí)現(xiàn)的是群體中的個(gè)體向最優(yōu)個(gè)體不斷靠攏的過(guò)程。
3.1.2 “學(xué)”階段
在此階段,學(xué)生相互學(xué)習(xí)。任意一個(gè)學(xué)生個(gè)體Xi(i=1,2,…,N),隨機(jī)選擇其他兩個(gè)不同的學(xué)生個(gè)體Xk1、Xk2,如果Xk1的適應(yīng)度高于Xk2的適應(yīng)度,按式(8)學(xué)習(xí);否則,按式(9)學(xué)習(xí)。如果學(xué)習(xí)產(chǎn)生的新個(gè)體Xnewi的適應(yīng)度更優(yōu),則Xnewi代替Xi,否則,Xi不變。
式(8)和式(9)中,ri是每個(gè)個(gè)體學(xué)習(xí)的隨機(jī)系數(shù),是在[0,1]上的隨機(jī)數(shù)。
“學(xué)”階段相當(dāng)于對(duì)個(gè)體的變異,實(shí)現(xiàn)全局搜索。
教與學(xué)優(yōu)化(TLBO)算法是基于求解連續(xù)函數(shù)的優(yōu)化問(wèn)題而提出的,本文使用編碼轉(zhuǎn)換方法[21-26],將其設(shè)計(jì)成能求解組合優(yōu)化問(wèn)題的二進(jìn)制TLBO算法(binary TLBO)。令每個(gè)學(xué)生個(gè)體或臨時(shí)個(gè)體用一個(gè)二元組(X,Y)表示。實(shí)向量X=[x1,x2,…,xm],xj∈[1,-1],j=1,2,…,m,有一個(gè)與之對(duì)應(yīng)的二進(jìn)制向量Y=[y1,y2,…,ym],yj∈{0,1},j=1,2,…,m,二進(jìn)制向量利用從連續(xù)空間[-1,1]d到離散空間{0,1}d的映射得到,映射關(guān)系為式(10)所示。算法中個(gè)體的進(jìn)化針對(duì)個(gè)體的實(shí)數(shù)向量X進(jìn)行,二進(jìn)制向量Y按式(10)隨之產(chǎn)生,個(gè)體的適應(yīng)度由二進(jìn)制向量Y計(jì)算得到。
因?yàn)镾UKP問(wèn)題是一個(gè)約束組合優(yōu)化問(wèn)題,在用進(jìn)化算法求解SUKP過(guò)程中對(duì)不可行解的處理是不可避免的。文獻(xiàn)[3]在文獻(xiàn)[2]的貪心策略基礎(chǔ)上提出一種貪心優(yōu)化算法S-GROA,和幾種進(jìn)化算法結(jié)合求解SUKP實(shí)例取得了很好的效果。本文在S-GROA基礎(chǔ)上加入了二次優(yōu)化,使得其對(duì)解的優(yōu)化性能更強(qiáng)。
S-GROA首先要計(jì)算S中每個(gè)項(xiàng)的價(jià)值密度,然后按價(jià)值密度由高到低的次序?qū)?xiàng)目進(jìn)行裝入處理。針對(duì)SUKP的特點(diǎn),當(dāng)候選解(也叫潛在解,解的可行性不知,一般是進(jìn)化中的個(gè)體向量)經(jīng)過(guò)S-GROA算法的處理后雖然已經(jīng)是較優(yōu)化的可行解,但還有再優(yōu)化的可能。對(duì)于S中沒(méi)有裝入的項(xiàng)Uk,如果Uk中所包含的元素已經(jīng)都在Az中,即滿足{uj|uj∈Uk}?,那么Uk的加入不會(huì)增加裝入項(xiàng)的總重量,即W(Az)=W(Az∪{Uk}),而使Az總價(jià)值增加,即P(Az)=P(Az)+pk。將符合該條件的Uk項(xiàng)裝入,會(huì)使Az總價(jià)值增加而總重不變,將得到更優(yōu)化的可行解。由此本文設(shè)計(jì)了改進(jìn)的貪心修復(fù)優(yōu)化算法MSGROA(modified S-GROA)。
令dj(j=1,2,…,n)是集合U中每個(gè)元素在子集U1,U2,…,Um(Ui∈S)中的使用頻率,令(i=1,2,…,m),設(shè)S中的每一項(xiàng)的價(jià)值密度為pi/Ri。使用快速排序按價(jià)值密度的降序?qū)中的各項(xiàng)進(jìn)行排序,將排序后各項(xiàng)序號(hào)存入數(shù)組H,對(duì)于一個(gè)二進(jìn)制向量Z=[z1,z2,…,zm]∈{0,1}m,令A(yù)Z={i|zi∈Z且zi=1,1≤i≤m},zi=1表示S中項(xiàng)Ui加入背包中。目標(biāo)函數(shù)fsukp(Y)(也是適應(yīng)度函數(shù))的值按式(3)計(jì)算,在此基礎(chǔ)上算法MS-GROA描述如下。
算法1MS-GROA
輸入:SUKP潛在解Y=[y1,y2,…,ym]∈{0,1}m和數(shù)組H[1…m]。
輸出:可行解Y=[y1,y2,…,ym]∈{0,1}m和該解的目標(biāo)函數(shù)值fsukp(Y)。
和σfinal分別是標(biāo)準(zhǔn)差的最初值和最終值,經(jīng)過(guò)多次測(cè)試,本文設(shè)置為σinitial=1,σfinal=0.3;n為非線性調(diào)和因子,一般情況下[32]ψ=3。分析得到:隨著進(jìn)化,按式(12)產(chǎn)生的標(biāo)準(zhǔn)差是從較大標(biāo)準(zhǔn)差變化到較小標(biāo)準(zhǔn)差,使得在算法進(jìn)化前期,此局部搜索在精英個(gè)體周圍以比較松散的形式進(jìn)行,正符合實(shí)際情況的需要,算法進(jìn)化前期,精英個(gè)體距離全局最優(yōu)解一般比較遠(yuǎn),這種松散搜索可以提高找到最優(yōu)解的機(jī)率;而到后來(lái)的標(biāo)準(zhǔn)差較小,實(shí)現(xiàn)了在精英個(gè)體較近處的細(xì)微搜索,此時(shí)精英個(gè)體一般離全局最優(yōu)解很近,細(xì)微搜索更容易找到全局最優(yōu)。
以上兩個(gè)策略分別從群體中的普通個(gè)體和精英個(gè)體兩個(gè)角度對(duì)算法進(jìn)行了優(yōu)化,考慮到普通個(gè)體和精英個(gè)體在群進(jìn)化中所起作用的不同,對(duì)他們分別采用了不同的策略。兩種策略同時(shí)實(shí)施于教與學(xué)優(yōu)化算法,可以有效平衡算法的局部開(kāi)發(fā)和全局勘探的能力。加入兩個(gè)策略的BTLBO算法稱為MBTLBO算法(modified BTLBO),該算法比BTLBO具有更強(qiáng)的尋優(yōu)能力和收斂速度,通過(guò)后面的仿真實(shí)驗(yàn)也得以證明。
在使用MBTLBO求解SUKP問(wèn)題時(shí),每個(gè)學(xué)生個(gè)體(Xi,Yi)的二進(jìn)制向量就是SUKP問(wèn)題的候選解,用MS-GROA算法對(duì)每代所得候選解進(jìn)行修復(fù)和優(yōu)化,同時(shí)得到個(gè)體的適應(yīng)度。下面給出求解SUKP問(wèn)題的MBTLBO算法。
首先使用快速排序QuickSort算法對(duì)上文提到的S中各項(xiàng)按價(jià)值密度pi/Ri(i=1,2,…,m)從大到小排序,并將排序后的序號(hào)存入數(shù)組H[1…m]中。此過(guò)程描述為H[1…m]←QuickSort(S)。算法2給出了用MBTLBO求解SUKP問(wèn)題的偽代碼。
算法2MBTLBO for SUKP
輸入:SUKP實(shí)例數(shù)據(jù),最大迭代次數(shù)Maxiter,種群規(guī)模N。
輸出:算法求出的近似解(或最優(yōu)解)Bt和目標(biāo)函數(shù)值fsukp(Bt)。
分析求解SUKP問(wèn)題的MBTLBO算法的時(shí)間復(fù)雜度:首先計(jì)算pi/Ri(i=1,2,…,m)的時(shí)間復(fù)雜度為O(mn);快速排序H[1…m]←QuickSort(S)的時(shí)間復(fù)雜度是O(mlbm);對(duì)個(gè)體潛在解修復(fù)優(yōu)化并計(jì)算適應(yīng)度(Yi,fsukp(Yi))←MS-GROA(Yi,H)的時(shí)間復(fù)雜度O(mn);在MBTLBO算法中,步驟1~4時(shí)間復(fù)雜度為O(mn+mlbm+Nm),步驟5~33時(shí)間復(fù)雜度為Maxiter×O(Nmn),而這里最大迭代次數(shù)Maxiter和種群規(guī)模N均為小于等于max{m,n}的數(shù),如令Q=max{m,n},則MBTLBO算法的時(shí)間度為O(Q4),是多項(xiàng)式時(shí)間求解SUKP問(wèn)題的進(jìn)化算法。
仿真實(shí)驗(yàn)使用文獻(xiàn)[3]提供的3組SUKP實(shí)例,每組由10個(gè)測(cè)試實(shí)例構(gòu)成。3組SUKP實(shí)例運(yùn)行結(jié)果如表1~表3所示。這3組實(shí)例分類是按S中的項(xiàng)目個(gè)數(shù)m和U中的元素?cái)?shù)n的關(guān)系來(lái)確定的。第1組實(shí)例中m>n,第2組實(shí)例中m=n,第3組實(shí)例中m<n。每個(gè)實(shí)例用一個(gè)m×n的0-1矩陣M表示項(xiàng)目集S={U1,U2,…,Um},對(duì)應(yīng)M中的每個(gè)元素rij,只有當(dāng)元素uj∈Ui時(shí),才有rij=1。實(shí)例的名字以sukpm_n_α_β為統(tǒng)一的樣式,其中m是實(shí)例中的項(xiàng)目數(shù),n是元素個(gè)數(shù),α表示在矩陣M中1出現(xiàn)的密度,,β是背包載重C與所有元素重量之和的比率,。
Table 1 Computing results of the first kind of SUKP instances表1 第1組SUKP實(shí)例測(cè)試結(jié)果
Table 2 Computing results of the second kind of SUKP instances表2 第2組SUKP實(shí)例測(cè)試結(jié)果
實(shí)驗(yàn)在配置為Intel?Core?i5-7Y54 CPU@1.2 GHz,內(nèi)存8 GB的電腦上進(jìn)行,操作系統(tǒng)為Windows 10,編程環(huán)境VC++2010,所有代碼由C++編寫。
為了測(cè)試新算法的性能,將本文提出的MBTLBO算法與文獻(xiàn)[3]中求解SUKP問(wèn)題的較好算法(包括遺傳算法GA(genetic algorithm)、二進(jìn)制蜂群算法BABC(binary artificial bee colony)、二進(jìn)制差分演化算法BinDE)以及BTLBO進(jìn)行比較。為測(cè)試本文對(duì)貪心修復(fù)策略改進(jìn)的效果,將二進(jìn)制差分演化算法BinDE[33]與本文的MS-GROA算法結(jié)合求解SUKP,與文獻(xiàn)[3]中使用S-GROA求解SUKP的二進(jìn)制差分演化算法BinDE算法進(jìn)行比較。為便于區(qū)分,將本文的二進(jìn)制差分演化算法命名為BinDE2。
BinDE2參數(shù)設(shè)置與文獻(xiàn)[3]中BinDE相同;MBTLBO算法中交叉因子Cr=0.8,σinitial=1和σfinal=0.3,ψ=3。所有實(shí)例獨(dú)立運(yùn)行50次,最大迭代次數(shù)設(shè)置和文獻(xiàn)[3]相同,即Maxiter=max{m,n}。表 1~表 3 中Best、Mean、Std是50次運(yùn)行實(shí)例所得結(jié)果的最優(yōu)值、均值和標(biāo)準(zhǔn)差。表中粗體表示所有實(shí)驗(yàn)結(jié)果中的最好值。
Table 3 Computing results of the third kind of SUKP instances表3 第3組SUKP實(shí)例測(cè)試結(jié)果
從表1~表3可以看出,六種算法中,MBTLBO、BinDE2和BTLBO三種算法,在修復(fù)和優(yōu)化候選解時(shí)使用本文提出的MS-GROA策略,其他三種算法使用了文獻(xiàn)[3]的S-GROA策略,由于MS-GROA中加入了對(duì)可行解的二次優(yōu)化,盡最大可能性將項(xiàng)目放入背包,進(jìn)一步提高了解的精度,使得在30個(gè)實(shí)例的求解中,MBTLBO、BinDE2和BTLBO求解性能排在前三位,均超過(guò)其余三種算法。從BinDE和BinDE2的實(shí)驗(yàn)數(shù)據(jù)比較中也明顯看出MS-GROA的作用。在三組實(shí)例中,BinDE2在27個(gè)實(shí)例上求得的最優(yōu)值高于BinDE,在29個(gè)實(shí)例上求得的均值高于BinDE2。而兩種算法都是使用BinDE[33]算法在相同參數(shù)配置下求解SUKP問(wèn)題,不同之處是,文獻(xiàn)[3]使用S-GROA對(duì)候選解進(jìn)行修復(fù)優(yōu)化,本文使用MS-GROA。由此可見(jiàn),MS-GROA策略是一種比S-GROA更有效的對(duì)SUKP候選解修復(fù)和優(yōu)化的策略。
另外,在三種求解較好的算法中,MBTLBO求解的效果明顯好于其他兩種算法,是求解能力最強(qiáng)的算法。MBTLBO與BinDE2相比:MBTLBO有17個(gè)實(shí)例的最優(yōu)值高于BinDE2,有27個(gè)實(shí)例的均值高于BinDE2。MBTLBO與BTLBO相比:MBTLBO有19個(gè)實(shí)例求得的最優(yōu)值好于BTLBO,有30實(shí)例求解的均值都高于BTLBO,有23個(gè)實(shí)例的標(biāo)準(zhǔn)差好于BTLBO。由此說(shuō)明,MS-GROA策略的使用提高了進(jìn)化算法求解SUKP問(wèn)題的性能,而同樣使用MSGROA策略的三種進(jìn)化算法MBTLBO、BinDE2和BTLBO中,MBTLBO由于對(duì)普通個(gè)體引入了差分算法中的交叉算子,并實(shí)施了精英局部搜索策略,提高了算法的求解精度,增強(qiáng)了算法求解的穩(wěn)定性。
為更直觀地反映交叉算子和自適應(yīng)精英局部搜索策略對(duì)二進(jìn)制教與學(xué)算法的優(yōu)化作用,圖1~圖3給出了二進(jìn)制教與學(xué)算法BTLBO和改進(jìn)的二進(jìn)制教與學(xué)算法MBTLBO求SUKP實(shí)例的平均收斂曲線圖,由于篇幅有限,只給出了每組中的四個(gè)實(shí)例的收斂曲線圖。
從這12個(gè)平均收斂曲線圖明顯看出,MBTLBO由于引入了針對(duì)普通個(gè)體的交叉算子和針對(duì)精英個(gè)體的自適應(yīng)搜索,在迭代前期就可以非常明顯增加算法的局部搜索能力,使算法的收斂效率得以提高。對(duì)普通個(gè)體的交叉操作,使得整個(gè)種群均勻地提高了算法向各個(gè)個(gè)體周圍的開(kāi)發(fā)能力,增強(qiáng)了跳出局部極值的可能性,從而使MBTLBO的收斂穩(wěn)定性得到了加強(qiáng)。而對(duì)精英個(gè)體的自適應(yīng)局部搜索,隨著迭代次數(shù)的增加,搜索的寬度由大到小,在算法中前期也起到了跳出局部?jī)?yōu)值的作用,同時(shí)提高了算法的尋優(yōu)精度,使MBTLBO始終保持高于BTLBO的精度和收斂趨勢(shì)。由此可見(jiàn),本文提出的MBTLBO確實(shí)加快了算法的收斂速度,提高了算法獲取全局最優(yōu)解的概率,算法的尋優(yōu)性能得到了改善。
綜上所述,本文提出的改進(jìn)二進(jìn)制教與學(xué)優(yōu)化算法(MBTLBO)是求解SUKP問(wèn)題的有效算法。MS-GROA策略是一種更有效修復(fù)和優(yōu)化SUKP解的方法。
Fig.1 Average convergence plot for 4 instances of the first kind of SUKP using MBTLBO and BTLBO圖1 MBTLBO和BTLBO在第1組中四個(gè)實(shí)例的平均收斂曲線圖
Fig.2 Average convergence plot for 4 instances of the second kind of SUKP using MBTLBO and BTLBO圖2 MBTLBO和BTLBO在第2組中四個(gè)實(shí)例的平均收斂曲線圖
Fig.3 Average convergence plot for 4 instances of the third kind of SUKP using MBTLBO and BTLBO圖3 MBTLBO和BTLBO在第3組中四個(gè)實(shí)例的平均收斂曲線圖
本文提出了一種改進(jìn)的二進(jìn)制教與學(xué)優(yōu)化算法(MBTLBO)求解SUKP問(wèn)題。針對(duì)SUKP問(wèn)題本身,提出一種改進(jìn)的修復(fù)優(yōu)化策略(MS-GROA),MSGROA在原修復(fù)優(yōu)化策略(S-GROA)的基礎(chǔ)上增加了對(duì)可行解的二次優(yōu)化,進(jìn)一步提高了求解精度。MS-GROA是一種通用的方法,可用于求解SUKP問(wèn)題的其他進(jìn)化算法中。通過(guò)分析基本教與學(xué)優(yōu)化算法和現(xiàn)實(shí)中學(xué)生學(xué)習(xí)的行為,對(duì)學(xué)生的學(xué)習(xí)做出了改進(jìn)。在學(xué)生學(xué)習(xí)過(guò)程中,引入差分演化算法中的二項(xiàng)式交叉算子,平衡了教與學(xué)優(yōu)化算法進(jìn)化過(guò)程中的全局勘探能力和局部開(kāi)發(fā)能力;借鑒雜草算法中雜草的繁衍方式,在精英個(gè)體(教師)周圍按正態(tài)分布進(jìn)行自適應(yīng)搜索,提高了算法的尋優(yōu)能力和收斂速度。仿真實(shí)驗(yàn)表明改進(jìn)的二進(jìn)制教與學(xué)優(yōu)化算法是求解SUKP問(wèn)題的有效方法。