離散型雞群優(yōu)化算法在0-1背包中的應(yīng)用

周 洋, 潘大志

(西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院, 四川 南充 637000 )

0 引 言

隨著國內(nèi)外學(xué)者的不斷研究，現(xiàn)階段已涌現(xiàn)出了豐富多彩的群智能算法。其中較為經(jīng)典的主要包括遺傳算法(GA)、粒子群算法(PSO)、布谷鳥算法(CSO)等[1]，這些算法在一定程度上都促進(jìn)了優(yōu)化領(lǐng)域的發(fā)展。Kennedy和Eberhard于1997年對基本粒子群算法離散化處理提出了二進(jìn)制離散粒子群算法(BPSO)[2]；張晶等人采用二進(jìn)制代碼變換公式構(gòu)建了二進(jìn)制布谷鳥搜索算法(BCS)[3]；宋曉萍等人將雜草算法應(yīng)用到離散問題,提出了一種離散雜草優(yōu)化算法(DIWO)[4]；吳虎勝等人也提出了一種解決離散空間組合優(yōu)化問題的二進(jìn)制狼群算法(BWPA)[5]。上述算法具備各自的優(yōu)劣性，因此，對于算法性能的研究仍然在不斷地改進(jìn)，與此同時(shí)，一些新穎的群智能算法也在不斷地出現(xiàn)與發(fā)展。

雞群算法(CSO)是由中國學(xué)者孟獻(xiàn)兵于2014年在第五屆群體智能國際會(huì)議中提出的一種群智能優(yōu)化算法[6]。該算法模擬雞群中的等級制度和覓食行為,具有很強(qiáng)的全局搜索能力。而如何將雞群算法應(yīng)用于離散空間，優(yōu)化問題是雞群算法的主要研究方向之一。本文設(shè)計(jì)出一種離散型雞群算法(DCSO)并應(yīng)用于0-1背包問題，在公雞個(gè)體位置更新方式中，引入了自適應(yīng)權(quán)重組合變異算子，通過仿真實(shí)驗(yàn)將該算法與遺傳算法、粒子群算法、蟻群算法在解的質(zhì)量、收斂速度等方面進(jìn)行比較。

1 背包問題的數(shù)學(xué)模型

0-1背包問題的一般描述為：假設(shè)有n個(gè)物品g1,g2,…,gn和一個(gè)背包，第j件物品的重量及其價(jià)值分別為wj>0和vj>0(j=1,2,…,n)，背包的最大載重限制為C，選擇部分物品放入背包，使得在不超過背包最大載重限制的前提下，所放入物品的總價(jià)值最大[7]。為描述n個(gè)物品是否放入背包，定義決策變量xj：

(1)

(2)

(3)

2 基本雞群算法

雞群算法模擬雞群中的等級制度和覓食行為。公雞作為整個(gè)雞群的首領(lǐng)主動(dòng)去尋找食物；母雞則陪伴在公雞左右；小雞們則跟隨著雞媽媽去尋找食物。根據(jù)這些行為，CSO算法制定了以下規(guī)則[8]：

在一個(gè)雞群中，包含有若干子種群，其中每個(gè)子種群中又包括一只公雞、若干只母雞和小雞。

整個(gè)雞群的劃分以及雞的身份角色確定都取決于適應(yīng)度值。計(jì)算適應(yīng)度并降序排列，選擇適應(yīng)度值最好的若干個(gè)體作為公雞群體，適應(yīng)度值最差的若干個(gè)體作為小雞群體，剩余的若干個(gè)體就作為母雞群體。其中，母雞與公雞之間的配偶關(guān)系、小雞與母雞之間的母子關(guān)系都是隨機(jī)確定的。

在每一個(gè)子種群中，這些等級關(guān)系、配偶關(guān)系、母子關(guān)系將在一段時(shí)間內(nèi)保持不變，每隔G代重新分群并更新角色。在每一個(gè)子種群中，雞群跟隨公雞去尋找食物，并且保護(hù)自己的食物。小雞則在母雞媽媽身邊尋找食物，適應(yīng)度值越高的優(yōu)勢個(gè)體具有更強(qiáng)的競爭能力。

在CSO算法中，假設(shè)整個(gè)雞群的數(shù)量為N，公雞的數(shù)量為NR，母雞的數(shù)量為NH，稱孵化小雞的母雞為媽媽母雞，其數(shù)量為NM，小雞的數(shù)量為NC。根據(jù)等級制度以及上述規(guī)則，可以確定公雞、母雞、小雞的位置更新方式如下：

(1)公雞的位置更新方式為：

(4)

(5)

(2)母雞的位置更新方式為：

(6)

(7)

S2=exp(fr2-fi)

(8)

其中，rand表示產(chǎn)生[0,1]之間的隨機(jī)數(shù)；r1表示第i只母雞的配偶公雞；r2表示從整個(gè)雞群中隨機(jī)選擇的公雞或者母雞，并且r1≠r2。

(3)小雞的位置更新方式為：

(9)

3 求解0-1背包問題的離散型雞群算法

0-1背包問題是運(yùn)籌學(xué)中經(jīng)典的組合優(yōu)化問題之一，也是一類典型的NP難問題，下面對于離散化雞群算法改進(jìn)策略作簡單闡述：

(1)對個(gè)體進(jìn)行離散化處理[9]。

(2)針對基本雞群算法中算法后期種群多樣性降低這一缺陷，采用自適應(yīng)權(quán)重組合變異更新公雞的位置。

(3)采用定向變異策略増強(qiáng)小雞對最優(yōu)個(gè)體的學(xué)習(xí)，避免陷入局部最優(yōu)。

(4)為了修復(fù)不可行解，每一代更新完成后都采用貪心修正算子(GMO)和貪心優(yōu)化算子(GOO)進(jìn)行修正與優(yōu)化[10]。

3.1 離散化策略

為實(shí)現(xiàn)離散化，基于文獻(xiàn)[11]中二進(jìn)制粒子群算法中的離散化處理方式，對更新后的每個(gè)個(gè)體位置進(jìn)行如下方式離散化處理：

(10)

3.2 自適應(yīng)權(quán)重組合變異

公雞的位置更新方式實(shí)質(zhì)上采用一種高斯變異算子，在整個(gè)迭代過程中，對于每個(gè)公雞個(gè)體而言，變異能力一直不變。隨著多樣性的下降，很可能會(huì)使算法陷入局部最優(yōu)解。為了加速算法收斂，考慮改進(jìn)變異算子去更新公雞位置，在高斯變異算子的基礎(chǔ)上融入柯西變異算子[12]。圖1直觀地反映了高斯分布和柯西分布的概率密度函數(shù)曲線。

圖1 高斯分布和柯西分布的圖形比較

Fig.1GraphicalcomparisonbetweenGuassdistributionandCauchydistribution

從圖1可看出，在相同參數(shù)下，高斯分布在垂直方向上的中心峰值略高于柯西分布，但在水平方向上柯西分布兩翼接近于0的速度卻比高斯分布緩慢。也就是說，相比柯西變異算子而言，高斯變異算子對于當(dāng)前點(diǎn)周圍領(lǐng)域范圍內(nèi)的開采利用率更高，局部搜索能力更強(qiáng)；而柯西變異算子能夠以更高的概率跳出局部最優(yōu)解，全局搜索性能更高。

為了更好地平衡算法前期與后期的“開采”與“探索”，采用組合變異算子，同時(shí)引入進(jìn)化代數(shù)t作為控制參數(shù)，動(dòng)態(tài)調(diào)整變異算子中的變異步長α，從而改進(jìn)公雞的位置更新方式為：

(11)

(12)

其中，N(0,σ2)表示均值為0，標(biāo)準(zhǔn)差為σ的高斯分布隨機(jī)數(shù)；C(0,1)表示標(biāo)準(zhǔn)柯西分布隨機(jī)數(shù)；α代表權(quán)重系數(shù)；η為小于1的正常數(shù)。多次試驗(yàn)得出η=0.5時(shí)效果最好；T為最大迭代次數(shù)。通過此方式對公雞的變異進(jìn)行動(dòng)態(tài)擾動(dòng)。

3.3 定向變異

基本雞群算法中小雞的位置更新僅僅吸收了其媽媽母雞的位置信息，一旦其媽媽母雞陷入局部最優(yōu)解，那么小雞也會(huì)陷入局部最優(yōu)，不利于算法的收斂，采用定向變異策略改進(jìn)小雞位置更新方式為[13]：

(13)

其中，best為整個(gè)雞群中的最優(yōu)個(gè)體。這樣小雞在尋優(yōu)時(shí)能夠避免盲目搜索，提高了算法的穩(wěn)定性。

3.4 修復(fù)機(jī)制

0-1背包問題的實(shí)質(zhì)為有約束優(yōu)化問題，因此，在DCSO算法雞群位置更新過程中，若新產(chǎn)生的雞群個(gè)體不滿足公式(3)，出現(xiàn)不可行解，將導(dǎo)致算法求解效率大大降低，則需要對其進(jìn)行修正與優(yōu)化。目前對于不可行解的處理方法主要有罰函數(shù)法和個(gè)體修正法。受文獻(xiàn)[10]中貪心修正算子(GMO)和貪心優(yōu)化算子(GOO)的啟發(fā)，本文將這兩種算子融入到DCSO中，不僅能對非正常編碼個(gè)體進(jìn)行修正，還能對所有個(gè)體進(jìn)一步優(yōu)化，快速找到最優(yōu)解。

3.5 DCSO算法的實(shí)現(xiàn)步驟

Step1隨機(jī)初始化雞群，設(shè)置相關(guān)參數(shù)N,NR,NH,NM,NC,G,ε以及0-1背包數(shù)據(jù)的輸入。

Step2當(dāng)t=0時(shí)，計(jì)算雞群的適應(yīng)度值fitness，利用GMO和GOO算子修復(fù)不可行解并初始化當(dāng)前個(gè)體最優(yōu)pbest和全局最優(yōu)gbest。

Step3判斷mod(t,G)=0是否成立。若成立，則對個(gè)體適應(yīng)度降序排列。根據(jù)第3節(jié)闡述的分群策略以及等級制度劃分子群，并隨機(jī)建立配偶關(guān)系和母子關(guān)系。

Step4利用式(11)、(6)和(13)分別對公雞、母雞和小雞進(jìn)行位置更新。

Step5當(dāng)前迭代時(shí)刻中的雞群全部更新完成后，采用3.1節(jié)中方式對所有個(gè)體的位置xi,j離散化處理。

Step6再次用GMO和GOO貪心算子對不可行解進(jìn)行修正。

Step7重新計(jì)算所有個(gè)體的適應(yīng)度值，并更新全局最優(yōu)gbest。

Step8令t=t+1，當(dāng)t>T時(shí)，則停止迭代，輸出最優(yōu)解。否則返回Step 3。

4 實(shí)驗(yàn)與仿真

為了驗(yàn)證DCSO算法的可行性與高效性，下面選用了被廣泛使用的4個(gè)經(jīng)典0-1背包問題來測試算法的尋優(yōu)性能，其維數(shù)從20維至100維，可較全面地反映算法的性能。表1中已知最優(yōu)解采用A/B的形式，A為背包中物品總價(jià)值，B為物品總重量。

表1 0-1背包問題的5個(gè)仿真實(shí)例

為了保證測試的客觀性與公平性，設(shè)置種群規(guī)模為100，最大迭代次數(shù)為200。仿真實(shí)驗(yàn)所選擇的測試環(huán)境為：處理器為Intel(R) Xeon(R) CPU E3-1240 v5，3.50 GHz，內(nèi)存為8G，操作系統(tǒng)為Windows10，利用Matlab2014a編程求解。根據(jù)表1中的背包數(shù)據(jù)，對比以下4種算法，參數(shù)設(shè)置見表2，每種算法各運(yùn)行30次，從最優(yōu)解、最差解、平均值、成功率等指標(biāo)來分析，結(jié)果見表3。

從表3可以看出，在求解4個(gè)經(jīng)典0-1背包問題時(shí)，DCSO算法都能找到理論最優(yōu)解，特別是對于Q1-Q4，該算法都能在較低的迭代次數(shù)中求得問題最優(yōu)解，且對于Q3和Q4而言，無論從標(biāo)準(zhǔn)差還是成功率來分析，DCSO算法的求解精度和穩(wěn)定性都遠(yuǎn)遠(yuǎn)優(yōu)于BPSO算法。

表2 4種算法的參數(shù)設(shè)置

為了進(jìn)一步說明4種算法的尋優(yōu)性能，圖2給出了各算法迭代收斂曲線。從圖中可以直觀地看出，相比于其它3種算法，DCSO均表現(xiàn)出了優(yōu)越的收斂性能。綜合所有指標(biāo)充分說明本文提出的新算法具有較強(qiáng)的尋優(yōu)能力，適合于求解0-1背包問題，具有可行性。

表3 0-1背包問題的4個(gè)仿真實(shí)例的結(jié)果對比

(a) Q1在T=200時(shí)的收斂曲線比較

(c) Q3在T=200時(shí)的收斂曲線比較

(b) Q2在T=200時(shí)的收斂曲線比較

(d) Q4在T=200時(shí)的收斂曲線比較

圖2DCSO、BPSO、GA和AC對4個(gè)仿真實(shí)例的收斂曲線比較

Fig.2ComparisonofconvergencecurvesofDCSO,BPSO,GAandACfor4simulationcases

5 結(jié)束語

在基本雞群算法的基礎(chǔ)上，基于離散思想，在公雞位置更新中引入自適應(yīng)權(quán)重變異算子，對小雞的位置更新采用定向變異的策略，與此同時(shí)，融入貪心修復(fù)算子對不可行解進(jìn)行修復(fù)與優(yōu)化，提出了一種求解0-1背包問題的離散型雞群算法。通過4個(gè)經(jīng)典0-1背包實(shí)例的仿真實(shí)驗(yàn)，對比BPSO、GA、AC等算法，顯著提高了解的質(zhì)量，驗(yàn)證了該算法的可行性以及高效性。