張小萍

摘要：提出結(jié)合佳點(diǎn)集和烏鴉優(yōu)化算法的改進(jìn)算法：佳點(diǎn)集烏鴉算法（GCSA）.算法使用佳點(diǎn)集初始化烏鴉種群進(jìn)行二進(jìn)制編碼，使用貪心策略對(duì)編碼進(jìn)行修復(fù)和優(yōu)化，改進(jìn)烏鴉算法中個(gè)體的位置更新方式，增加檢測(cè)種群收斂性檢測(cè)：未達(dá)到收斂時(shí)利用最優(yōu)解位置來(lái)更新當(dāng)前的個(gè)體位置;達(dá)到收斂時(shí)使用隨機(jī)位置來(lái)更新當(dāng)前位置，避免算法早熟，陷入局部最優(yōu)解.測(cè)試結(jié)果表明，GCSA算法尋優(yōu)平均值大，方差小，收斂速度較快，全局尋優(yōu)能力較強(qiáng).

關(guān)鍵詞：佳點(diǎn)集;烏鴉算法;0-1背包問(wèn)題;貪心策略

[中圖分類號(hào)]TP18[文獻(xiàn)標(biāo)志碼]A

Good Point-Set Crow Optimization Algorithm

for 0-1 Knapstack Problem

ZHANG Xiaoping

（College of computer and electronic information，Guangxi University，Nanning 530004，China）

Abstract：An improved algorithm combining good point set and crow optimization algorithm is proposed： good point set crow algorithm （GCSA）.The algorithm uses the good point set to initialize the crow population for binary coding，uses the greedy strategy to repair and optimize the coding，improves the individual position update mode in the crow algorithm，and increases the detection of population Convergence：when the convergence is not reached，the optimal solution position is used to update the current individual position;When reaching convergence，the random position is used to update the current position to avoid premature algorithm and falling into local optimal solution.The test results show that GCSA algorithm has large average value，small variance，fast convergence speed and strong global optimization ability.

Key words：good point set;crow algorithm;0-1 knapstack problem;greedy strategy

0-1背包問(wèn)題[1]是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，在投資決策、資源分配和整數(shù)規(guī)劃等領(lǐng)域有很多重要的應(yīng)用.求解0-1背包問(wèn)題主要分為精確算法和近似算法.精確算法每次都可以求得最優(yōu)解，但算法的時(shí)間復(fù)雜度高，時(shí)間開(kāi)銷隨著物品的數(shù)量呈指數(shù)增長(zhǎng)，一般只能用在低維背包問(wèn)題中.近似算法可能無(wú)法每次都求得最優(yōu)解，只是求得最優(yōu)解的近似解，但近似算法的時(shí)間復(fù)雜度較低，系統(tǒng)開(kāi)銷小，可以很快獲得結(jié)果.近年來(lái)隨著仿生智能優(yōu)化算法的發(fā)展，仿生智能優(yōu)化算法在多種應(yīng)用場(chǎng)合如車間作業(yè)調(diào)度[2]、智能組卷[3]和求解0-1背包問(wèn)題中被廣泛使用并獲得了較好的效果.周洋[4]等使用粒子群算法和貪心策略設(shè)計(jì)算法（GOPSO）求解0-1背包問(wèn)題.劉雪靜[5]等利用烏鴉算法和混沌序列提出求解0-1背包問(wèn)題的混沌二進(jìn)制烏鴉算法（BCSA），算法中使用貪心策略修復(fù)不可行解，對(duì)可行解進(jìn)行優(yōu)化.徐小平[6]等利用煙花算法和Kent混沌映射序列設(shè)計(jì)算法（IFWA）求解0-1背包問(wèn)題，算法改進(jìn)了煙花爆炸半徑的計(jì)算公式，有利于快速在全局最優(yōu)解附近搜索，提高算法的收斂性.孫靜[7]等利用改進(jìn)雞群算法（DCSO）求解0-1背包問(wèn)題，通過(guò)調(diào)整動(dòng)態(tài)權(quán)重來(lái)增加種群的多樣性;為了提高算法的全局搜索性，避免陷入局部最優(yōu)解，算法在母雞和小雞的位置更新中引入慣性權(quán)重因子ω.這些算法在求解0-1背包問(wèn)題時(shí)獲得了不錯(cuò)的效果，但在一定程度上也存在全局尋優(yōu)能力不夠強(qiáng)、收斂速度不夠快等問(wèn)題.

針對(duì)求解0-1背包問(wèn)題時(shí)算法收斂速度慢、全局尋優(yōu)性能較差、容易得到局部最優(yōu)解的弱點(diǎn)，本文提出佳點(diǎn)集烏鴉算法（GCSA）求解0-1背包問(wèn)題的方法.GCSA結(jié)合佳點(diǎn)集算法、烏鴉優(yōu)化算法以及貪心策略，改進(jìn)了烏鴉個(gè)體位置的更新方式，引入種群收斂性判斷：若收斂則隨機(jī)產(chǎn)生烏鴉的位置，增加種群的多樣性;若未收斂則依據(jù)當(dāng)前找到的最優(yōu)解更新烏鴉位置，增強(qiáng)探索能力，在“開(kāi)發(fā)”和“探索”中獲得平衡.仿真實(shí)驗(yàn)表明，GCSA尋優(yōu)平均值大，方差小，收斂速度較快，全局尋優(yōu)能力較強(qiáng).

1基本烏鴉算法

烏鴉算法（CSA）是2016年伊朗學(xué)者Askarzadeh提出的一種群智能仿生算法[8]，通過(guò)模擬烏鴉藏食物和偷竊的行為來(lái)解決尋優(yōu)問(wèn)題，與其他群智能仿生算法相比較，該算法易于理解，所需要設(shè)置的參數(shù)少，實(shí)現(xiàn)簡(jiǎn)單.因此，在CSA算法提出后獲得了較多學(xué)者的關(guān)注，CSA被應(yīng)用到SVM參數(shù)優(yōu)化、車載網(wǎng)絡(luò)頻譜分配方案、 多級(jí)閾值圖像分割和軟件測(cè)試用例生成等領(lǐng)域.

烏鴉是一種非常聰明的鳥類，它能夠記住自己藏匿食物的隱蔽地方，能跟蹤其他烏鴉并試圖找到其他烏鴉藏匿食物的位置并偷走食物，而被跟蹤的烏鴉能以一定的感知概率發(fā)現(xiàn)自己被跟蹤然后飛到一個(gè)隨機(jī)位置以保護(hù)自己的食物不被找到.假定xi，iter表示烏鴉i的位置，iter是當(dāng)前迭代次數(shù)，在第iter次迭代時(shí)，藏食位置為mi，iter.CSA算法的基本步驟是：

（1）系統(tǒng)初始化：設(shè)定種群數(shù)、迭代最大次數(shù)、烏鴉的飛行長(zhǎng)度f(wàn)l和初始感知概率AP.初始化種群中烏鴉的位置，烏鴉的位置表示一個(gè)可行解.

（2）初始化藏食物的記憶值，每只烏鴉的初始記憶值設(shè)為初始位置，計(jì)算個(gè)體的適應(yīng)度值.

（3）更新烏鴉的位置.根據(jù)感知概率，烏鴉i更新位置的方式有2種：

xi，iter+1=xi，iter+r*ifli，iter*（mj，iter-xi，iter），rj≥APj，iter

a random position，rj≥APj，iter.（1）

其中，xi，iter+1表示烏鴉i的新位置，ri和rj是[0，1]區(qū)間均勻分布的隨機(jī)數(shù)，APi，iter+1表示烏鴉j在第iter次迭代后的感知概率 .

（4）檢測(cè)更新位置的可行性.若可行則更新;否則，保持原來(lái)的位置.

（5）計(jì)算新位置的適應(yīng)度值.

（6）更新記憶值.更新公式為：

mi，iter+1=xi，iter+1+f（xi，iter+1）is better than f（xi，iter）

mi，iter，otherwise.（2）

（7）重復(fù)（3）-（6）直到達(dá)到最大迭代次數(shù).

算法結(jié)束后，所有烏鴉記憶值的最好位置就是所求問(wèn)題的解.

烏鴉算法中的參數(shù)比較少，只有飛行長(zhǎng)度f(wàn)l和感知概率AP兩個(gè)參數(shù)，fl較小則局部搜索能力強(qiáng)，較大則全局搜索能力強(qiáng)，AP較小增加集約性，AP較大則增加種群的多樣性.

2佳點(diǎn)集的定義和性質(zhì)

佳點(diǎn)集理論最初由華羅庚[9]提出，佳點(diǎn)集方法可以用于高維空間的近似計(jì)算，在高維空間中構(gòu)造均勻分布的點(diǎn)集.

（1）Gd表示d維歐式空間的單位立方體，x=（x1，x2，…，xd），x∈Gd，0≤xi≤1，i=1，2，…d.

（2）Gd中有一個(gè)n個(gè)頂點(diǎn)的點(diǎn)集.

Pn（k）=x（n）1（k），x（n）2（k），…，x（n）d（k），1≤k≤n，0≤x（n）i（k）≤1，1≤i≤d.

（3）給定Gd中任意一點(diǎn)r=（r1，r2，…，rd），Nn（r）表示在點(diǎn)集Pn（k）中并且滿足如下不等式的點(diǎn)的個(gè)數(shù)：0≤x（n）i（k）

（4）令r∈Gd，若Pn（k）=（{r1k}，…，{rdk}），k=1，2，…，n的偏差φ（n）滿足φ（n）= C（r，ε）n-1+ε，其中C（r，ε）是只和r，ε（ε>0）有關(guān)的常數(shù)，那么Pn（k）稱為佳點(diǎn)集，稱r為佳點(diǎn).

佳點(diǎn)集的實(shí)質(zhì)是在構(gòu)造一個(gè)在d維的單位立方體Gd中均勻分布的點(diǎn)集，使用佳點(diǎn)集選擇的點(diǎn)比隨機(jī)方法選擇的點(diǎn)偏差要小，大約只是隨機(jī)選擇方法的平方根分之一.佳點(diǎn)集良好的性質(zhì)可以用于仿生智能優(yōu)化算法的種群初始化階段，使種群的個(gè)體分布均勻.一般地，可以使用分圓域的方法來(lái)構(gòu)造佳點(diǎn)集：

γ=2cos2πp，2cos4πp，…，2cos2πdp，p≥2d+3且p是一個(gè)素?cái)?shù).

3佳點(diǎn)集烏鴉優(yōu)化算法（GCSA）

在基本烏鴉算法中隨機(jī)數(shù)rj小于AP時(shí)，更新烏鴉位置用隨機(jī)位置的方式進(jìn)行，但這種隨機(jī)的更新方式會(huì)使得搜索具有盲目性，甚至?xí)?duì)同一位置重復(fù)搜索，這會(huì)使得收斂速度變得緩慢.為了彌補(bǔ)基本烏鴉算法中搜索盲目性和收斂速度緩慢的弱點(diǎn)，筆者提出利用公式計(jì)算種群是否已經(jīng)收斂，若未收斂則利用全局最優(yōu)解來(lái)更新烏鴉的位置，使烏鴉的新位置朝著最優(yōu)解的方向移動(dòng);若收斂，則移動(dòng)到一個(gè)隨機(jī)位置，這樣可以增加種群的多樣性.GCSA算法還利用貪心策略對(duì)不可行解修復(fù)，對(duì)可行解優(yōu)化，提高其收斂速度.

3.1混合編碼

烏鴉個(gè)體位置xi，iter=[x1，x2，…，xn]的編碼方式是實(shí)數(shù)型的向量，而要求解0-1背包問(wèn)題需要的是二進(jìn)制向量，因此，要將實(shí)數(shù)型的向量xi，iter向二進(jìn)制型的向量yi，iter=[y1，y2，…，yn]轉(zhuǎn)化，編碼的方法如下：

yj=1，xj≥0

yj=0，xj<0.（3）

其中，j=1，2，…，n，種群中的個(gè)體使用（xi，iter，yi，iter）共同表示，構(gòu)成混合編碼，其xj∈[-a，a].在本文中a=5.

3.2貪心策略

經(jīng)過(guò)編碼后的二進(jìn)制向量yi，iter只是0-1背包問(wèn)題的潛在解，由于還要滿足0-1背包問(wèn)題的約束化條件，即放入物體的重量之和不能超過(guò)背包的承載量，有可能yi，iter會(huì)出現(xiàn)不可行解.貪心策略不僅可以將不可行解修復(fù)為可行解，還可以對(duì)可行解進(jìn)行優(yōu)化，提高收斂的速度，具體算法可以參考文獻(xiàn)[5]中的GROA算子.

3.3判斷種群是否收斂的方法

設(shè)定兩個(gè)常數(shù)K，TH，假設(shè)在iter次迭代找到的最大適應(yīng)度值是fbestiter，計(jì)算連續(xù)K代最大適應(yīng)度值的方差，若方差等于小于閾值TH，則認(rèn)為算法達(dá)到了收斂階段，若大于TH則認(rèn)為算法未達(dá)到收斂階段.方差公式計(jì)算如下：

fave=（fbestiter+fbestiter-1+…+fbestiter-K+1）/K.

fstd=（fbestiter-fave）2+（fbestiter-1-fave）2+…+（fbestiter-K+1-fave）2/K. （4）

其中，fave表示連續(xù)K代最大適應(yīng)度值的平均值，fstd表示表示連續(xù)K代最大適應(yīng)度值的方差.

3.4烏鴉位置更新的改進(jìn)

為了避免基本烏鴉算法中烏鴉頻繁隨機(jī)移動(dòng)位置會(huì)使得搜索失去方向性的問(wèn)題，改進(jìn)了烏鴉位置的更新方式，當(dāng)隨機(jī)數(shù)rj小于AP時(shí)，對(duì)種群是否收斂進(jìn)行判斷，若未收斂，就沿著全局最優(yōu)解移動(dòng)，若收斂，則移動(dòng)到隨機(jī)位置，公式為：

xi，iter+1=xi，iter+r*ifli，iter*（mj，iter-xi，iter），rj≥APj，iter

xi，iter+r*ifli，iter*（xbestiter-xi，iter），rjTH

a random position，rj

其中，xbestiter是當(dāng)前搜索到的全局最優(yōu)解所對(duì)應(yīng)的位置，fstd是連續(xù)K代最大適應(yīng)度值的方差，TH是一個(gè)閾值常數(shù).

3.5GCSA的具體實(shí)現(xiàn)步驟

（1）初始化系統(tǒng)參數(shù)，設(shè)置種群數(shù)目pop，求解問(wèn)題的維度n，最大迭代次數(shù)itermax，以及fl，AP，K，TH.

（2）使用分圓域的方法構(gòu)造佳點(diǎn)集初始化種群，并用公式（3）對(duì)烏鴉位置二進(jìn)制編碼，然后使用貪心策略GROA算子進(jìn)行修補(bǔ)和優(yōu)化，計(jì)算出個(gè)體的適應(yīng)度.

（3）使用公式（4）計(jì)算出連續(xù)K代的最大適應(yīng)度的方差，并用公式（5）對(duì)烏鴉位置進(jìn)行更新.

（4）檢測(cè)更新位置的可行性.若可行則更新;否則，保持原來(lái)的位置.

（5）對(duì)更新位置用公式（3）對(duì)烏鴉位置二進(jìn)制編碼，然后使用貪心策略GROA算子進(jìn)行修補(bǔ)和優(yōu)化，并計(jì)算出新位置的適應(yīng)度.

（6）使用公式（2）更新記憶值.

（7）保存當(dāng)前適應(yīng)度值最大的個(gè)體位置、二進(jìn)制編碼和適應(yīng)度值.

（8）若迭代數(shù)iter小于最大迭代數(shù)則iter加1回到步驟3繼續(xù)執(zhí)行，否則輸出找到最優(yōu)解，算法

結(jié)束.

4仿真實(shí)驗(yàn)和分析

有200個(gè)物品，背包載重限制為71 893，其中P向量代表各物品的價(jià)值，W向量代表各物品的重量，其中：

P=[1 048，565，972，917，1 046，544，277，789，164，372，142，1 083，819，188，965，350，724，778，1 015，721，1 093，1 058，271，669，1 090，1 024，486，919，354，1 083，478，694，208，09，876，155，1 005，128，

557，413，404，574，177，1 014，425，1 032，1 046，618，296，797，167，411，920，961，428，169，591，184，

245，895，176，833，802，163，591，1 056，963，875，809，1 071，271，196，796，1 044，644，930，1 027， 237，

415，932，1 003，578，319，424，775，173，871，768，720，474，548，424，791，845，407，397，854，631，754，917，556，880，106，674，126，417，649，922，954，211，1 039，587，169，360，959，108，621，610，1 049，516，930，942，660，708，793，540，624，1 001，182，885，896，137，471，482，474，810，910，547，816，704，263，389，614，701，235，1 005，497，1 033，143，615，341，687，600，655，173，973，901，166，510，409，480，894，

962，617，302，832，313，191，190，917，102，417，930，632，357，215，775，404，266，997，351，554，1 043，

580，628，110，201，274，955，198，646，1 071，984，560，849，1 068，322，708，486，827];

W=[949，466，873，818，947，445，178，690，65，273，43，984，720，89，866，251，625，679，916，622，994，959，172，570，991，925，387，820，255，984，379，595，109，810，777，56，906，29，458，314，305，475，78，915，326，933，947，519，197，698，68，312，821，862，329，70，492，85，146，796，77，734，703，64，492，957，864，776，710，972，172，97，697，945，545，831，928，138，316，833，904，479，220，325，676，74，772，669，621，375，449，325，692，746，308，298，755，532，655，818，457，781，7，575，27，318，550，823，855，112，940，488，70，261，860，9，522，511，950，417，831，843，561，609，694，441，525，902，83，786，797，38，372，383，375，711，811，448，717，605，164，290，515，602，136，906，398，934，44，516，242，588，501，556，74，874，802，67，411，310，381，795，863，518，203，733，214，92，91，818，3，318，831，533，258，116，676，305，

測(cè)試案例在MATLABR2020b下進(jìn)行仿真實(shí)驗(yàn)，GCSA算法分別與GOPSO，BCSA，DCSO，IFWA算法比較.種群數(shù)目設(shè)為30，最大迭代次數(shù)為200，獨(dú)立運(yùn)行20次，AP=0.4，fl=0.2，K=5，TH=10，實(shí)驗(yàn)結(jié)果見(jiàn)表1.GCSA算法可以找到最優(yōu)解，且方差是所有算法中最小的，具有較強(qiáng)的穩(wěn)定性和全局尋優(yōu)能力.

圖1是案例五種算法的進(jìn)化迭代曲線圖，BCSA，GOPSO，IFWA，DCSO都沒(méi)有找到最優(yōu)解，只有GCSA找到了最優(yōu)解，且也比其他四種算法的收斂速度快.

5總結(jié)

本文針對(duì)傳統(tǒng)CSA算法求解0-1背包問(wèn)題時(shí)收斂速度慢、容易早熟陷入局部最優(yōu)解的問(wèn)題，提出結(jié)合佳點(diǎn)集和烏鴉優(yōu)化算法的改進(jìn)算法：佳點(diǎn)集烏鴉算法（GCSA）.GCSA利用佳點(diǎn)集初始化種群，貪心策略修復(fù)和優(yōu)化潛在解，通過(guò)判斷種群的收斂性判斷，改進(jìn)了個(gè)體的位置更新公式：在未達(dá)到收斂階段沿全局最優(yōu)解的方向更新，達(dá)到收斂階段則隨機(jī)更新，增加種群的多樣性.實(shí)驗(yàn)結(jié)果表明，GCSA算法具有較強(qiáng)的穩(wěn)定性和較高的全局搜索性，易于跳出局部最優(yōu)解，尋找到全局最優(yōu)解.

參考文獻(xiàn)

[1]樂(lè)天.遺傳算法求解0/1背包問(wèn)題的綜述[J].浙江海洋學(xué)院學(xué)報(bào)：自然科學(xué)版，2013（1）：71-74.

[2]鄭林，柴寶杰，蔡靜穎.改進(jìn)的粒子群算法在車間作業(yè)調(diào)度中的應(yīng)用研究[J].牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2012（2）：3-5.

[3]金玉蘋，李春雨.一種改進(jìn)的遺傳算法在智能組卷上的應(yīng)用[J].牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2017（2）：38-40.

[4]周洋， 潘大志.求解0-1背包問(wèn)題的貪心優(yōu)化粒子群算法[J].西華師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2018，39（3）：102-107.

[5]劉雪靜，賀毅朝，吳聰聰，等.求解0-1背包問(wèn)題的混沌二進(jìn)制烏鴉算法[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（10）：178-184.

[6]徐小平，龐潤(rùn)娟，王峰，等.求解0-1背包問(wèn)題的煙花算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2019，028（2）：164-170.

[7]孫靜，舒敬榮，方新明，等.基于改進(jìn)雞群優(yōu)化算法的0-1背包問(wèn)題研究[J].寶雞文理學(xué)院學(xué)報(bào)：自然科學(xué)版，2020，40（4）：20-24.

[8]Askarzadeh A.A novel metaheuristic method for solving constrained engineering optimization problems：Crow search algorithm[J].Computers & Structures，2016，169：1-12.

[9]華羅庚，王元.數(shù)論在近似分析中的應(yīng)用[M].北京：科學(xué)出版社，1978.83-86.

編輯：琳莉