改進(jìn)的教與學(xué)優(yōu)化算法求解集合聯(lián)盟背包問題*

吳聰聰，賀毅朝，趙建立,2

1.河北地質(zhì)大學(xué) 信息工程學(xué)院，石家莊 050031

2.全北國立大學(xué) 電子信息工程學(xué)院，韓國 全州 54896

1 引言

集合聯(lián)盟背包問題（set-union knapsack problem，SUKP）是經(jīng)典0-1背包問題的一種擴(kuò)展[1-3]，屬于NP完全問題。它在投資決策[2,4]、柔性制造機(jī)器[1,5-6]、智慧城市[7]和流壓縮[8]等方面都得到了廣泛應(yīng)用。然而，Goldschmidt等人[1]使用動(dòng)態(tài)規(guī)劃法求解SUKP問題，由于時(shí)間復(fù)雜度太高而缺乏實(shí)用性[3]，Arulselvan提出的基于貪心策略的近似算法[2]，當(dāng)問題規(guī)模較大時(shí)也難以在可接受的時(shí)間內(nèi)獲得較好解。近期賀毅朝等人[3]提出用演化算法求解SUKP問題的新方法，并提出一種對(duì)SUKP問題中不可行解修復(fù)和優(yōu)化的策略——S-GROA（greedy repairing and optimization algorithm）。將該策略分別與二進(jìn)制蜂群算法、遺傳算法和二進(jìn)制差分演化算法結(jié)合，求解三類SUKP問題。從求解速度、精度和穩(wěn)定性等方面說明進(jìn)化算法是解決SUKP問題的可行實(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)引起很多國內(nèi)外學(xué)者的關(guān)注[10-20]，并在機(jī)械設(shè)計(jì)與處理的問題優(yōu)化[11]、熱交換優(yōu)化處理[12]、熱冷器優(yōu)化[13]、平面鋼框架設(shè)計(jì)[14]、數(shù)據(jù)聚類分組[15]經(jīng)濟(jì)調(diào)度問題[16]等領(lǐng)域得到良好應(yīng)用。

然而，TLBO算法本身也存在著對(duì)于較復(fù)雜問題尋優(yōu)精度低，穩(wěn)定性差，收斂速度不夠快的不足[17]。為此，國內(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]通過引入混沌優(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)和所求解問題，恰當(dāng)?shù)剡x擇優(yōu)化措施非常重要。

本文針對(duì)求解SUKP問題，提出一種改進(jìn)的二進(jìn)制教與學(xué)優(yōu)化算法（modified binaryTLBO，MBTLBO）。首先將TLBO算法通過編碼轉(zhuǎn)化機(jī)制設(shè)計(jì)成能求解SUKP問題的二進(jìn)制TLBO算法（BTLBO）。然后，針對(duì)SUKP問題，提出改進(jìn)的貪心優(yōu)化策略MS-GROA（modified S-GROA），該策略通過對(duì)可行解的二次優(yōu)化，能夠進(jìn)一步提升解的被優(yōu)化程度，從而提高SUKP的求解精度。另外，從教與學(xué)算法角度，在算法的“教”階段和“學(xué)”階段引入差分演化算法的交叉算子，讓進(jìn)化得到的臨時(shí)個(gè)體與原個(gè)體進(jìn)行交叉操作，平衡算法的全局搜索和局部開發(fā)能力，避免算法早熟；通過在精英個(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問題的進(jìn)化算法（二進(jìn)制蜂群算法、遺傳算法和二進(jìn)制差分演化）相比，平均求解精度更高，改進(jìn)的修復(fù)和優(yōu)化策略MS-GROA比原策略在對(duì)解的優(yōu)化上更有效。

2 SUKP定義

定義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)并集中包含的元素重量之和。要解決的問題就是：如何選擇S中的項(xiàng)裝入背包，使得裝入集合A的重量W(A)在不超過載重C的情況下價(jià)值P(A)最大？上面的問題可以用下面的數(shù)學(xué)模型描述[1-2]：

為了便于使用啟發(fā)式算法解決SUKP問題，文獻(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。

3 二進(jìn)制教與學(xué)優(yōu)化算法

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

教與學(xué)優(yōu)化算法（TLBO）是根據(jù)課堂教學(xué)中教師和學(xué)生的行為提出的一種群優(yōu)化算法。TLBO算法分為“教”和“學(xué)”兩個(gè)階段：“教”階段學(xué)生跟隨教師學(xué)習(xí)，“學(xué)”階段是學(xué)生之間相互學(xué)習(xí)。算法中的教師由學(xué)生中成績最好者（適應(yīng)度最高的個(gè)體）來擔(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è)體不斷靠攏的過程。

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)全局搜索。

3.2 二進(jìn)制教與學(xué)優(yōu)化算法

教與學(xué)優(yōu)化（TLBO）算法是基于求解連續(xù)函數(shù)的優(yōu)化問題而提出的，本文使用編碼轉(zhuǎn)換方法[21-26]，將其設(shè)計(jì)成能求解組合優(yōu)化問題的二進(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ì)算得到。

4 改進(jìn)的二進(jìn)制教與學(xué)優(yōu)化算法求解SUKP問題

4.1 改進(jìn)的貪心修復(fù)策略MS-GROA

因?yàn)镾UKP問題是一個(gè)約束組合優(yōu)化問題，在用進(jìn)化算法求解SUKP過程中對(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)過S-GROA算法的處理后雖然已經(jīng)是較優(yōu)化的可行解，但還有再優(yōu)化的可能。對(duì)于S中沒有裝入的項(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)過多次測(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ī)率；而到后來的標(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)化算法，可以有效平衡算法的局部開發(fā)和全局勘探的能力。加入兩個(gè)策略的BTLBO算法稱為MBTLBO算法（modified BTLBO），該算法比BTLBO具有更強(qiáng)的尋優(yōu)能力和收斂速度，通過后面的仿真實(shí)驗(yàn)也得以證明。

4.3 改進(jìn)的二進(jìn)制教與學(xué)優(yōu)化算法求解SUKP問題

在使用MBTLBO求解SUKP問題時(shí)，每個(gè)學(xué)生個(gè)體(Xi,Yi)的二進(jìn)制向量就是SUKP問題的候選解，用MS-GROA算法對(duì)每代所得候選解進(jìn)行修復(fù)和優(yōu)化，同時(shí)得到個(gè)體的適應(yīng)度。下面給出求解SUKP問題的MBTLBO算法。

首先使用快速排序QuickSort算法對(duì)上文提到的S中各項(xiàng)按價(jià)值密度pi/Ri(i=1,2,…,m)從大到小排序，并將排序后的序號(hào)存入數(shù)組H[1…m]中。此過程描述為H[1…m]←QuickSort(S)。算法2給出了用MBTLBO求解SUKP問題的偽代碼。

算法2MBTLBO for SUKP

輸入：SUKP實(shí)例數(shù)據(jù)，最大迭代次數(shù)Maxiter，種群規(guī)模N。

輸出：算法求出的近似解（或最優(yōu)解）Bt和目標(biāo)函數(shù)值fsukp(Bt)。

分析求解SUKP問題的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問題的進(jìn)化算法。

5 仿真實(shí)驗(yà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)系來確定的。第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問題的較好算法（包括遺傳算法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求解性能排在前三位，均超過其余三種算法。從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問題，不同之處是，文獻(xiàn)[3]使用S-GROA對(duì)候選解進(jìn)行修復(fù)優(yōu)化，本文使用MS-GROA。由此可見，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。由此說明，MS-GROA策略的使用提高了進(jìn)化算法求解SUKP問題的性能，而同樣使用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è)體周圍的開發(fā)能力，增強(qiáng)了跳出局部極值的可能性，從而使MBTLBO的收斂穩(wěn)定性得到了加強(qiáng)。而對(duì)精英個(gè)體的自適應(yīng)局部搜索，隨著迭代次數(shù)的增加，搜索的寬度由大到小，在算法中前期也起到了跳出局部優(yōu)值的作用，同時(shí)提高了算法的尋優(yōu)精度，使MBTLBO始終保持高于BTLBO的精度和收斂趨勢(shì)。由此可見，本文提出的MBTLBO確實(shí)加快了算法的收斂速度，提高了算法獲取全局最優(yōu)解的概率，算法的尋優(yōu)性能得到了改善。

綜上所述，本文提出的改進(jìn)二進(jìn)制教與學(xué)優(yōu)化算法（MBTLBO）是求解SUKP問題的有效算法。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í)例的平均收斂曲線圖

6 結(jié)束語

本文提出了一種改進(jìn)的二進(jìn)制教與學(xué)優(yōu)化算法（MBTLBO）求解SUKP問題。針對(duì)SUKP問題本身，提出一種改進(jìn)的修復(fù)優(yōu)化策略（MS-GROA），MSGROA在原修復(fù)優(yōu)化策略（S-GROA）的基礎(chǔ)上增加了對(duì)可行解的二次優(yōu)化，進(jìn)一步提高了求解精度。MS-GROA是一種通用的方法，可用于求解SUKP問題的其他進(jìn)化算法中。通過分析基本教與學(xué)優(yōu)化算法和現(xiàn)實(shí)中學(xué)生學(xué)習(xí)的行為，對(duì)學(xué)生的學(xué)習(xí)做出了改進(jìn)。在學(xué)生學(xué)習(xí)過程中，引入差分演化算法中的二項(xiàng)式交叉算子，平衡了教與學(xué)優(yōu)化算法進(jìn)化過程中的全局勘探能力和局部開發(fā)能力；借鑒雜草算法中雜草的繁衍方式，在精英個(gè)體（教師）周圍按正態(tài)分布進(jìn)行自適應(yīng)搜索，提高了算法的尋優(yōu)能力和收斂速度。仿真實(shí)驗(yàn)表明改進(jìn)的二進(jìn)制教與學(xué)優(yōu)化算法是求解SUKP問題的有效方法。