改進(jìn)教與學(xué)優(yōu)化算法求解0-1背包問題

張小萍,譚歡

（1.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院,廣西 南寧 530004;2.中國移動通信集團(tuán)廣西有限公司,廣西 南寧 530022）

教與學(xué)優(yōu)化算法（TLBO）[1]是由印度學(xué)者Rao在2011年提出的一種智能優(yōu)化算法,該算法模擬人類在學(xué)習(xí)過程中“教”與“學(xué)”兩個學(xué)習(xí)階段來獲取知識.TLBO算法的參數(shù)少,易于理解,實(shí)現(xiàn)簡單,具有較好的收斂性能,獲得了眾多學(xué)者的關(guān)注.目前TLBO算法在一些工程實(shí)踐領(lǐng)域如測試數(shù)據(jù)生成[2]、結(jié)構(gòu)可靠性優(yōu)化設(shè)計(jì)[3]、太赫茲圖像增強(qiáng)模型[4]和SRM轉(zhuǎn)矩分配函數(shù)優(yōu)化及控制[5]中獲得了良好的尋優(yōu)效果.但基本的TLBO算法仍然存在著容易陷入局部最優(yōu)解,收斂速度慢的問題.

0-1背包問題（0-1 knapsack problem,0-1 KP）是一個經(jīng)典的組合優(yōu)化問題,在實(shí)踐應(yīng)用中一些優(yōu)化問題如貨物裝箱、投資決策、材料切割和資源分配等都可以轉(zhuǎn)化為0-1 KP,尋找更好的方法來求解0-1 KP,不論在理論和實(shí)踐中都具有重要意義.早期,求解0-1 KP的算法主要有遞歸法、動態(tài)規(guī)劃法、枚舉法和回溯法等確定性的算法,這類算法的時間復(fù)雜度隨問題規(guī)模呈指數(shù)增長,無法用于求解高維的0-1KP.近年來,隨著智能優(yōu)化算法的發(fā)展,眾多智能優(yōu)化算法應(yīng)用于0-1 KP求解中,它的時間復(fù)雜度是多項(xiàng)式級別的,能用于求解高維的0-1 KP,但一般只能獲得問題的最優(yōu)解域.任靜敏等[6]提出帶權(quán)重的貪心螢火蟲算法（WGFA）,通過在基本螢火蟲算法加入貪心算子、自適應(yīng)權(quán)重和變異算法,提高了算法的全局搜索能力和收斂速度.孫靜等[7]提出改進(jìn)雞群優(yōu)化算法（ICSO）,在母雞和小雞位置引入慣性權(quán)重,提高了算法的求解精度.陳楨等[8]提出了混合貪婪遺傳算法（HGGA）,在0-1 KP求解中以往的貪心算子都是使用基于價值密度比較大的的物品優(yōu)先裝入背包,而該算法增加了基于物品價值優(yōu)先的混合選項(xiàng),并增加了局部搜索模塊進(jìn)一步提高了尋優(yōu)速度.

為了進(jìn)一步提高求解0-1 KP的尋優(yōu)性能,本文提出一個改進(jìn)的教與學(xué)優(yōu)化算法（ITLBO）,在“教”階段引入正余弦算子,在“學(xué)”階段引入自適應(yīng)慣性權(quán)重,并利用貪心算子提高全局搜索能力和算法的收斂速度.

1 0-1 KP模型

0-1 KP一般可以描述為：有一個具有承載重量限制的背包,有n件物品,每件物品有各自的重量和價值,選擇若干物品裝入背包,尋找一種裝入方案,使得在不超過背包承載重量的情況下裝入的物品價值和達(dá)到最大.0-1KP的數(shù)學(xué)模型表示為

式（1）、式（2）中：n表示物品數(shù)目,C表示背包的承載重量限制,W=（w1,w2,...,wn）表示物品的重量向量,P=（p1,p2,...,pn）表示物品的價值向量.當(dāng)yj=1時表示選中該物品裝入背包,否則表示未裝入.

2 基本TLBO

TLBO是模擬班級教學(xué)活動的優(yōu)化算法,在TLBO中,1個班級代表1個種群,學(xué)員數(shù)就是種群數(shù),學(xué)習(xí)分為“教”階段和“學(xué)”階段2個部分,在“教”階段,教師引導(dǎo)著班級中所有學(xué)員知識水平的提高,教師是適應(yīng)度最好的學(xué)員;在“學(xué)”階段,學(xué)員獲取知識主要通過學(xué)員之間的相互交流.假定求解優(yōu)化問題是求最大值,TLBO的基本步驟是：

Step1初始化階段.初始化系統(tǒng)參數(shù),m是學(xué)員數(shù)目,隨機(jī)初始化m位學(xué)員,Xi=（xi1,xi2,...,xin）,i=1,2,...,m,n是學(xué)習(xí)的科目數(shù),代表了問題求解變量的維數(shù),計(jì)算所有學(xué)員的適應(yīng)度.

Step2“教”階段.選擇最優(yōu)（即適應(yīng)度最大）的學(xué)員作為教師,用Xteacher表示,計(jì)算所有成員的平均水平Mean,每個學(xué)員都向教師學(xué)習(xí),學(xué)習(xí)方式是利用教師和所有學(xué)員的平均水平的差異進(jìn)行學(xué)習(xí),學(xué)習(xí)過程用公式（3）、（4）、（5）來表示

3 ITLBO模型

3.1 二進(jìn)制離散化

0-1 KP是二進(jìn)制離散化問題,而基本TLBO是用于求解連續(xù)問題的,因此要進(jìn)行二進(jìn)制編碼,將實(shí)數(shù)型的向量Xi=（xi1,xi2,...,xin）變?yōu)槎M(jìn)制向量Yi=（yi1,yi2,...,yin）,編碼的方式如公式（7）所示

種群中的個體由（Xi,Yi）共同表示,構(gòu)成了實(shí)數(shù)向量和二進(jìn)制向量構(gòu)成的混合編碼.

3.2 貪心算子

0-1 KP是帶約束性條件的優(yōu)化問題,在二進(jìn)制編碼之后得到的向量有可能不符合約束性條件,這些解成為不可行解.對于不可行解通常用兩種方法來處理,一是使用懲罰函數(shù),即在不可行解減去一個較大的數(shù),使其適應(yīng)度值減小,二是使用貪心算子對不可行解進(jìn)行修復(fù).測試研究表明,使用貪心算子的方法要比使用懲罰函數(shù)好,因?yàn)槭褂脩土P函數(shù)只是降低了不可行解的適應(yīng)度使它被選中的概率降低,但沒有改變不可行解的實(shí)質(zhì),而貪心算子不僅將不可行解轉(zhuǎn)變?yōu)榭尚薪?還對可行解進(jìn)一步優(yōu)化,將更多不超過背包承載重量的物品盡可能地放入背包,這將加快算法的收斂速度.先將物品按照價值重量比按降序排列,貪心算子（greedy operator,GO）偽代碼可以表示如下：

算法1 GO

偽代碼中2-6步驟的作用是修復(fù),將不可行解轉(zhuǎn)變?yōu)榭尚薪?7-11步驟的作用是優(yōu)化,在不超過背包承載重量的前提下將價值重量比大的物品優(yōu)先裝入背包.

3.3 正余弦算子

在基本TLBO的“教”階段,個體更新利用的是教師和所有成員的平均值差異進(jìn)行的,當(dāng)算法收斂到一定階段,進(jìn)入局部最優(yōu)解時,難以跳出局部最優(yōu)解,為了加強(qiáng)算法的全局搜索能力,引入了正余弦算子.正余弦優(yōu)化算法[9]是2016年提出的一種智能優(yōu)化算法,利用正弦和余弦函數(shù)的周期震蕩來平衡局部搜索和全局搜索,更好地實(shí)現(xiàn)探索階段到開發(fā)階段的平穩(wěn)過渡.這里利用正余弦算法作為ITLBO的算子改進(jìn)“教”階段對學(xué)員更新,如公式（8）所示

式（8）中:r1=a-a*t/T,a是一個常數(shù),t是當(dāng)前迭代次數(shù),T是最大迭代次數(shù),r2是[0,2π]之間的隨機(jī)數(shù),r3是[0,2]之間的隨機(jī)數(shù),r4是[0,1]之間的隨機(jī)數(shù).當(dāng)正余弦函數(shù)幅度在[-1,1]之間時,進(jìn)行局部搜索,當(dāng)正余弦幅度大于1或小于-1時,進(jìn)行全局搜索.

3.4 自適應(yīng)慣性權(quán)重

對于一個好的優(yōu)化算法,在迭代前期應(yīng)該偏重于全局搜索,以便盡快確定最優(yōu)解的范圍,迭代后期偏重于局部搜索,提高尋優(yōu)的精度.為了加強(qiáng)在“學(xué)”階段迭代前期的全局搜索能力,引入了自適應(yīng)的慣性權(quán)重.算法是否達(dá)到收斂階段需要一定的迭代次數(shù)才能檢測出來,設(shè)定一個常數(shù)cycle作為檢測周期,t表示當(dāng)前迭代次數(shù)且是cycle的倍數(shù),f maxt表示當(dāng)前種群的最大適應(yīng)度值,當(dāng)f maxt=f maxt-cycle即當(dāng)前周期和上一周期的最大適應(yīng)度值沒有發(fā)生變化時認(rèn)為種群達(dá)到收斂階段,以此為依據(jù)將“學(xué)”階段的更新變?yōu)楣剑?）和（10）

b是慣性權(quán)重,最大適應(yīng)度值在一個cycle周期檢測一次,在周期內(nèi)b不發(fā)生變化.最大適應(yīng)度值發(fā)生變化,表示種群還沒收斂,公式（10）能保證b的值大于1,使得個體在一個大的范圍進(jìn)行全局搜索,否則b的值變?yōu)?,在一個小的范圍內(nèi)進(jìn)行局部搜索,就平衡開發(fā)和探索的關(guān)系.

3.5 ITLBO的基本步驟

Step1初始化階段.初始化系統(tǒng)參數(shù),初始化所有學(xué)員,進(jìn)行二進(jìn)制編碼,用貪心算子對二進(jìn)制編碼修復(fù)和優(yōu)化,計(jì)算出所有個體的適應(yīng)度值.

Step2“教”階段.選擇最優(yōu)的學(xué)員作為教師,用Xteacher表示,用公式（3）計(jì)算所有成員的平均水平Mean,學(xué)習(xí)過程用公式（8）來表示,對更新后的個體編碼和用貪心算子修復(fù)優(yōu)化,計(jì)算出所有個體的適應(yīng)度值.

4 仿真測試結(jié)果和分析

為了測試提出的ITLBO算法的性能,使用來自文獻(xiàn)[10]提供的4個0-1背包測試案例進(jìn)行仿真實(shí)驗(yàn),實(shí)驗(yàn)環(huán)境為Windows 7操作系統(tǒng),內(nèi)存12 G,編程軟件為Matlab2020b,使用WGFA、ICSO和HGGA作為對比算法.ITLBO中參數(shù)設(shè)定為cycle=10,α=0.7,a=2.為了避免實(shí)驗(yàn)的偶然性,各算法在每個案例中單獨(dú)測試30次,4個算法的種群數(shù)都設(shè)為50,迭代次數(shù)為200次,分別計(jì)算各算法的最小值、最大值、平均值、方差和30次測試中能夠命中理論最優(yōu)值的比率,測試結(jié)果如表1所示.

表1 仿真測試數(shù)據(jù)Tab.1 Simulation test data

從表1可以觀察到ITLBO在Q1中每次都能找到理論最優(yōu)值,與ICSO、HGGA性能相當(dāng),在Q2中,只有ITLBO和HGGA每次都能命中理論最優(yōu)解,而隨著背包問題規(guī)模的增大,在Q3和Q4中,ITLBO的平均值是4個算法中最大的,而且命中比率也是4個算法中最高,特別是在Q3中,80.00%的命中比率比第二名的30.00%的命中比率高出許多.綜合分析來看,ITLBO的平均值、方差和命中比率在4個案例中都是第一或并列第一的,體現(xiàn)出ITLBO不論在低維和高維0-1 KP中都具有良好的尋優(yōu)性能和魯棒性.

為了進(jìn)一步分析ITLBO的收斂性,利用2個高維背包問題Q3和Q4畫出4個算法的平均收斂曲線,如圖1和圖2所示.

圖1 Q3的平均收斂曲線Fig.1 Average convergencecurve of Q3

圖2 Q4的平均收斂曲線Fig.2 Averageconvergencecurveof Q4

從Q3和Q4的平均收斂曲線觀察到,ITLBO比ICSO和WGFA兩種算法的優(yōu)越性更明顯,ITLBO在迭代初期就很快收斂到最優(yōu)解域,雖然HGGA和ITLBO比較接近,但是ITLBO最終迭代到的解精度更高一些,說明ITLBO的收斂性更強(qiáng),能很快迭代到理論最優(yōu)解附近,能有效求解0-1 KP.

5 小結(jié)

文章利用正余弦算子和自適應(yīng)的慣性權(quán)重改進(jìn)了基本TLBO算法用于求解0-1 KP,使算法在迭代過程的“教”階段和“學(xué)”階段都能平衡開發(fā)和探索的關(guān)系,并通過利用貪心算子,能夠加快算法的收斂速度,可以較快地搜索到全局最優(yōu)解,避免進(jìn)入局部最優(yōu)解,并且具有較強(qiáng)的魯棒性.