改進的教與學優化算法求解集合聯盟背包問題*

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

1.河北地質大學 信息工程學院，石家莊 050031

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

1 引言

集合聯盟背包問題（set-union knapsack problem，SUKP）是經典0-1背包問題的一種擴展[1-3]，屬于NP完全問題。它在投資決策[2,4]、柔性制造機器[1,5-6]、智慧城市[7]和流壓縮[8]等方面都得到了廣泛應用。然而，Goldschmidt等人[1]使用動態規劃法求解SUKP問題，由于時間復雜度太高而缺乏實用性[3]，Arulselvan提出的基于貪心策略的近似算法[2]，當問題規模較大時也難以在可接受的時間內獲得較好解。近期賀毅朝等人[3]提出用演化算法求解SUKP問題的新方法，并提出一種對SUKP問題中不可行解修復和優化的策略——S-GROA（greedy repairing and optimization algorithm）。將該策略分別與二進制蜂群算法、遺傳算法和二進制差分演化算法結合，求解三類SUKP問題。從求解速度、精度和穩定性等方面說明進化算法是解決SUKP問題的可行實用的方法。

教與學優化算法[9]（teaching-learning-based optimization，TLBO）是由Rao等人在2011年提出的一種新的進化算法。由于TLBO具有參數少、結構簡單、求解速度快等特點，已經引起很多國內外學者的關注[10-20]，并在機械設計與處理的問題優化[11]、熱交換優化處理[12]、熱冷器優化[13]、平面鋼框架設計[14]、數據聚類分組[15]經濟調度問題[16]等領域得到良好應用。

然而，TLBO算法本身也存在著對于較復雜問題尋優精度低，穩定性差，收斂速度不夠快的不足[17]。為此，國內外學者在TLBO算法的改進和優化上進行了廣泛的研究。Rao等人[17]在原算法基礎上加入了精英策略，提出了ETLBO算法（elitistTLBO，ETLBO），ETLBO算法比原始算法在收斂速度和求解精度方面都有所提高。Rajasekhar等人[18]提出了相對精英教學優化算法（elitist teaching learning opposition based algorithm，ETLOBA），該算法在尋優精度及收斂速度上比ETLBO算法有所增強。于坤杰等人[19]提出了基于反饋的精英教與學優化算法（feedback ETLBO，FETLBO），該算法在學生“學”階段之后加入“反饋”階段，使算法在尋優精度上取得了較好的效果。王培崇等人[20]通過引入混沌優化、學生動態自適應學習、精英個體的共軛梯度搜索、反向學習和高斯學習，對TLBO進行了四方面的改進，提高了算法的收斂精度。但是以上改進算法，文獻[17-19]策略較簡單，改進后的算法在性能上還有提升空間；文獻[20]中共軛梯度搜索不好確定迭代次數，而且對算法搜索全局最優解的作用不穩定。因此，針對TLBO的特點和所求解問題，恰當地選擇優化措施非常重要。

本文針對求解SUKP問題，提出一種改進的二進制教與學優化算法（modified binaryTLBO，MBTLBO）。首先將TLBO算法通過編碼轉化機制設計成能求解SUKP問題的二進制TLBO算法（BTLBO）。然后，針對SUKP問題，提出改進的貪心優化策略MS-GROA（modified S-GROA），該策略通過對可行解的二次優化，能夠進一步提升解的被優化程度，從而提高SUKP的求解精度。另外，從教與學算法角度，在算法的“教”階段和“學”階段引入差分演化算法的交叉算子，讓進化得到的臨時個體與原個體進行交叉操作，平衡算法的全局搜索和局部開發能力，避免算法早熟；通過在精英個體周圍，以自適應標準差，按正態分布進行局部搜索，進一步提高算法的求解精度和收斂速度。最后，進行了3組（每組10個實例）SUKP實例仿真。實驗結果表明，MBTLOB算法與已有的求解SUKP問題的進化算法（二進制蜂群算法、遺傳算法和二進制差分演化）相比，平均求解精度更高，改進的修復和優化策略MS-GROA比原策略在對解的優化上更有效。

2 SUKP定義

定義1給定元素集合U={u1,u2,…,un}和項集S={U1,U2,…,Um}，項集S中的每項Ui(i=1,2,…,m)是元素集合U的子集，即Ui?U，且每個項Ui擁有一個價值pi>0。U中的每個元素uj有一個重量wj>0(j=1,2,…,n)。將項集S中的項裝入載重為C的背包，如果設裝入背包的項構成的集合為A，那么A的價值P(A)是A中所有項的價值之和，A的重量W(A)是A中所有項并集中包含的元素重量之和。要解決的問題就是：如何選擇S中的項裝入背包，使得裝入集合A的重量W(A)在不超過載重C的情況下價值P(A)最大？上面的問題可以用下面的數學模型描述[1-2]：

為了便于使用啟發式算法解決SUKP問題，文獻[3]給出了一種整形規劃的數學模型，模型如式（3）和式（4）：

其中，Y={y1,y2,…,ym}∈{0,1}m是m維的0-1向量，當yi=1(i=1,2,…,m)時表示集合S中的第i項Ui屬于集合AY，當yi=0(i=1,2,…,m)時表示集合S中的第i項Ui不屬于AY，AY是裝入背包的項構成的集合，即AY?S。

3 二進制教與學優化算法

3.1 教與學優化算法

教與學優化算法（TLBO）是根據課堂教學中教師和學生的行為提出的一種群優化算法。TLBO算法分為“教”和“學”兩個階段：“教”階段學生跟隨教師學習，“學”階段是學生之間相互學習。算法中的教師由學生中成績最好者（適應度最高的個體）來擔任，學生數量為種群規模N，學生個體為實向量Xi=[xi,1,xi,2,…,xi,m]，i=1,2,…,N，教師用實向量Tt=[t1,t2,…,tm]表示。

3.1.1 “教”階段

在“教”階段，每個學生根據班級平均狀態與教師狀態的差異進行學習。用差異向量D表示班級平均狀態與教師狀態的差異，該向量由式（5）計算得到，然后再由式（6）求得當前個體學習后的新個體Xnewi，如果新個體Xnewi的適應度更高，則由新個體代替原個體，否則原個體保持不變。

式（5）中，rt是[0,1]上的隨機數，Tt為教師個體，Mt為全班平均狀態（即），λ為教學因子，它決定平均值改變的程度，其值可以是1或2，由式（7）計算得到。

式（7）中，round表示四舍五入取整函數，rand(0,1)產生0到1之間的隨機數。

在“教”階段，實現的是群體中的個體向最優個體不斷靠攏的過程。

3.1.2 “學”階段

在此階段，學生相互學習。任意一個學生個體Xi(i=1,2,…,N)，隨機選擇其他兩個不同的學生個體Xk1、Xk2，如果Xk1的適應度高于Xk2的適應度，按式（8）學習；否則，按式（9）學習。如果學習產生的新個體Xnewi的適應度更優，則Xnewi代替Xi，否則，Xi不變。

式（8）和式（9）中，ri是每個個體學習的隨機系數，是在[0,1]上的隨機數。

“學”階段相當于對個體的變異，實現全局搜索。

3.2 二進制教與學優化算法

教與學優化（TLBO）算法是基于求解連續函數的優化問題而提出的，本文使用編碼轉換方法[21-26]，將其設計成能求解組合優化問題的二進制TLBO算法（binary TLBO）。令每個學生個體或臨時個體用一個二元組(X,Y)表示。實向量X=[x1,x2,…,xm]，xj∈[1,-1]，j=1,2,…,m，有一個與之對應的二進制向量Y=[y1,y2,…,ym]，yj∈{0,1}，j=1,2,…,m，二進制向量利用從連續空間[-1,1]d到離散空間{0,1}d的映射得到，映射關系為式（10）所示。算法中個體的進化針對個體的實數向量X進行，二進制向量Y按式（10）隨之產生，個體的適應度由二進制向量Y計算得到。

4 改進的二進制教與學優化算法求解SUKP問題

4.1 改進的貪心修復策略MS-GROA

因為SUKP問題是一個約束組合優化問題，在用進化算法求解SUKP過程中對不可行解的處理是不可避免的。文獻[3]在文獻[2]的貪心策略基礎上提出一種貪心優化算法S-GROA，和幾種進化算法結合求解SUKP實例取得了很好的效果。本文在S-GROA基礎上加入了二次優化，使得其對解的優化性能更強。

S-GROA首先要計算S中每個項的價值密度，然后按價值密度由高到低的次序對項目進行裝入處理。針對SUKP的特點，當候選解（也叫潛在解，解的可行性不知，一般是進化中的個體向量）經過S-GROA算法的處理后雖然已經是較優化的可行解，但還有再優化的可能。對于S中沒有裝入的項Uk，如果Uk中所包含的元素已經都在Az中，即滿足{uj|uj∈Uk}?，那么Uk的加入不會增加裝入項的總重量，即W(Az)=W(Az∪{Uk})，而使Az總價值增加，即P(Az)=P(Az)+pk。將符合該條件的Uk項裝入，會使Az總價值增加而總重不變，將得到更優化的可行解。由此本文設計了改進的貪心修復優化算法MSGROA（modified S-GROA）。

令dj(j=1,2,…,n)是集合U中每個元素在子集U1,U2,…,Um(Ui∈S)中的使用頻率，令(i=1,2,…,m)，設S中的每一項的價值密度為pi/Ri。使用快速排序按價值密度的降序對S中的各項進行排序，將排序后各項序號存入數組H，對于一個二進制向量Z=[z1,z2,…,zm]∈{0,1}m，令AZ={i|zi∈Z且zi=1,1≤i≤m},zi=1表示S中項Ui加入背包中。目標函數fsukp(Y)（也是適應度函數）的值按式（3）計算，在此基礎上算法MS-GROA描述如下。

算法1MS-GROA

輸入：SUKP潛在解Y=[y1,y2,…,ym]∈{0,1}m和數組H[1…m]。

輸出：可行解Y=[y1,y2,…,ym]∈{0,1}m和該解的目標函數值fsukp(Y)。

和σfinal分別是標準差的最初值和最終值，經過多次測試，本文設置為σinitial=1，σfinal=0.3；n為非線性調和因子，一般情況下[32]ψ=3。分析得到：隨著進化，按式（12）產生的標準差是從較大標準差變化到較小標準差，使得在算法進化前期，此局部搜索在精英個體周圍以比較松散的形式進行，正符合實際情況的需要，算法進化前期，精英個體距離全局最優解一般比較遠，這種松散搜索可以提高找到最優解的機率；而到后來的標準差較小，實現了在精英個體較近處的細微搜索，此時精英個體一般離全局最優解很近，細微搜索更容易找到全局最優。

以上兩個策略分別從群體中的普通個體和精英個體兩個角度對算法進行了優化，考慮到普通個體和精英個體在群進化中所起作用的不同，對他們分別采用了不同的策略。兩種策略同時實施于教與學優化算法，可以有效平衡算法的局部開發和全局勘探的能力。加入兩個策略的BTLBO算法稱為MBTLBO算法（modified BTLBO），該算法比BTLBO具有更強的尋優能力和收斂速度，通過后面的仿真實驗也得以證明。

4.3 改進的二進制教與學優化算法求解SUKP問題

在使用MBTLBO求解SUKP問題時，每個學生個體(Xi,Yi)的二進制向量就是SUKP問題的候選解，用MS-GROA算法對每代所得候選解進行修復和優化，同時得到個體的適應度。下面給出求解SUKP問題的MBTLBO算法。

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

算法2MBTLBO for SUKP

輸入：SUKP實例數據，最大迭代次數Maxiter，種群規模N。

輸出：算法求出的近似解（或最優解）Bt和目標函數值fsukp(Bt)。

分析求解SUKP問題的MBTLBO算法的時間復雜度：首先計算pi/Ri(i=1,2,…,m)的時間復雜度為O(mn)；快速排序H[1…m]←QuickSort(S)的時間復雜度是O(mlbm)；對個體潛在解修復優化并計算適應度(Yi,fsukp(Yi))←MS-GROA(Yi,H)的時間復雜度O(mn)；在MBTLBO算法中，步驟1～4時間復雜度為O(mn+mlbm+Nm)，步驟5～33時間復雜度為Maxiter×O(Nmn)，而這里最大迭代次數Maxiter和種群規模N均為小于等于max{m,n}的數，如令Q=max{m,n}，則MBTLBO算法的時間度為O(Q4)，是多項式時間求解SUKP問題的進化算法。

5 仿真實驗和分析

仿真實驗使用文獻[3]提供的3組SUKP實例，每組由10個測試實例構成。3組SUKP實例運行結果如表1～表3所示。這3組實例分類是按S中的項目個數m和U中的元素數n的關系來確定的。第1組實例中m>n，第2組實例中m=n，第3組實例中m＜n。每個實例用一個m×n的0-1矩陣M表示項目集S={U1,U2,…,Um}，對應M中的每個元素rij，只有當元素uj∈Ui時，才有rij=1。實例的名字以sukpm_n_α_β為統一的樣式，其中m是實例中的項目數，n是元素個數，α表示在矩陣M中1出現的密度，，β是背包載重C與所有元素重量之和的比率，。

Table 1 Computing results of the first kind of SUKP instances表1 第1組SUKP實例測試結果

Table 2 Computing results of the second kind of SUKP instances表2 第2組SUKP實例測試結果

實驗在配置為Intel?Core?i5-7Y54 CPU@1.2 GHz，內存8 GB的電腦上進行，操作系統為Windows 10，編程環境VC++2010，所有代碼由C++編寫。

為了測試新算法的性能，將本文提出的MBTLBO算法與文獻[3]中求解SUKP問題的較好算法（包括遺傳算法GA（genetic algorithm）、二進制蜂群算法BABC（binary artificial bee colony）、二進制差分演化算法BinDE）以及BTLBO進行比較。為測試本文對貪心修復策略改進的效果，將二進制差分演化算法BinDE[33]與本文的MS-GROA算法結合求解SUKP，與文獻[3]中使用S-GROA求解SUKP的二進制差分演化算法BinDE算法進行比較。為便于區分，將本文的二進制差分演化算法命名為BinDE2。

BinDE2參數設置與文獻[3]中BinDE相同；MBTLBO算法中交叉因子Cr=0.8,σinitial=1和σfinal=0.3,ψ=3。所有實例獨立運行50次，最大迭代次數設置和文獻[3]相同，即Maxiter=max{m,n}。表 1～表 3 中Best、Mean、Std是50次運行實例所得結果的最優值、均值和標準差。表中粗體表示所有實驗結果中的最好值。

Table 3 Computing results of the third kind of SUKP instances表3 第3組SUKP實例測試結果

從表1～表3可以看出，六種算法中，MBTLBO、BinDE2和BTLBO三種算法，在修復和優化候選解時使用本文提出的MS-GROA策略，其他三種算法使用了文獻[3]的S-GROA策略，由于MS-GROA中加入了對可行解的二次優化，盡最大可能性將項目放入背包，進一步提高了解的精度，使得在30個實例的求解中，MBTLBO、BinDE2和BTLBO求解性能排在前三位，均超過其余三種算法。從BinDE和BinDE2的實驗數據比較中也明顯看出MS-GROA的作用。在三組實例中，BinDE2在27個實例上求得的最優值高于BinDE，在29個實例上求得的均值高于BinDE2。而兩種算法都是使用BinDE[33]算法在相同參數配置下求解SUKP問題，不同之處是，文獻[3]使用S-GROA對候選解進行修復優化，本文使用MS-GROA。由此可見，MS-GROA策略是一種比S-GROA更有效的對SUKP候選解修復和優化的策略。

另外，在三種求解較好的算法中，MBTLBO求解的效果明顯好于其他兩種算法，是求解能力最強的算法。MBTLBO與BinDE2相比：MBTLBO有17個實例的最優值高于BinDE2，有27個實例的均值高于BinDE2。MBTLBO與BTLBO相比：MBTLBO有19個實例求得的最優值好于BTLBO，有30實例求解的均值都高于BTLBO，有23個實例的標準差好于BTLBO。由此說明，MS-GROA策略的使用提高了進化算法求解SUKP問題的性能，而同樣使用MSGROA策略的三種進化算法MBTLBO、BinDE2和BTLBO中，MBTLBO由于對普通個體引入了差分算法中的交叉算子，并實施了精英局部搜索策略，提高了算法的求解精度，增強了算法求解的穩定性。

為更直觀地反映交叉算子和自適應精英局部搜索策略對二進制教與學算法的優化作用，圖1～圖3給出了二進制教與學算法BTLBO和改進的二進制教與學算法MBTLBO求SUKP實例的平均收斂曲線圖，由于篇幅有限，只給出了每組中的四個實例的收斂曲線圖。

從這12個平均收斂曲線圖明顯看出，MBTLBO由于引入了針對普通個體的交叉算子和針對精英個體的自適應搜索，在迭代前期就可以非常明顯增加算法的局部搜索能力，使算法的收斂效率得以提高。對普通個體的交叉操作，使得整個種群均勻地提高了算法向各個個體周圍的開發能力，增強了跳出局部極值的可能性，從而使MBTLBO的收斂穩定性得到了加強。而對精英個體的自適應局部搜索，隨著迭代次數的增加，搜索的寬度由大到小，在算法中前期也起到了跳出局部優值的作用，同時提高了算法的尋優精度，使MBTLBO始終保持高于BTLBO的精度和收斂趨勢。由此可見，本文提出的MBTLBO確實加快了算法的收斂速度，提高了算法獲取全局最優解的概率，算法的尋優性能得到了改善。

綜上所述，本文提出的改進二進制教與學優化算法（MBTLBO）是求解SUKP問題的有效算法。MS-GROA策略是一種更有效修復和優化SUKP解的方法。

Fig.1 Average convergence plot for 4 instances of the first kind of SUKP using MBTLBO and BTLBO圖1 MBTLBO和BTLBO在第1組中四個實例的平均收斂曲線圖

Fig.2 Average convergence plot for 4 instances of the second kind of SUKP using MBTLBO and BTLBO圖2 MBTLBO和BTLBO在第2組中四個實例的平均收斂曲線圖

Fig.3 Average convergence plot for 4 instances of the third kind of SUKP using MBTLBO and BTLBO圖3 MBTLBO和BTLBO在第3組中四個實例的平均收斂曲線圖

6 結束語

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