求解0-1背包问题的佳点集乌鸦优化算法

张小萍

摘要：提出结合佳点集和乌鸦优化算法的改进算法：佳点集乌鸦算法（GCSA）.算法使用佳点集初始化乌鸦种群进行二进制编码，使用贪心策略对编码进行修复和优化，改进乌鸦算法中个体的位置更新方式，增加检测种群收敛性检测：未达到收敛时利用最优解位置来更新当前的个体位置;达到收敛时使用随机位置来更新当前位置，避免算法早熟，陷入局部最优解.测试结果表明，GCSA算法寻优平均值大，方差小，收敛速度较快，全局寻优能力较强.

关键词：佳点集;乌鸦算法;0-1背包问题;贪心策略

[中图分类号]TP18[文献标志码]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背包问题[1]是一个经典的组合优化问题，在投资决策、资源分配和整数规划等领域有很多重要的应用.求解0-1背包问题主要分为精确算法和近似算法.精确算法每次都可以求得最优解，但算法的时间复杂度高，时间开销随着物品的数量呈指数增长，一般只能用在低维背包问题中.近似算法可能无法每次都求得最优解，只是求得最优解的近似解，但近似算法的时间复杂度较低，系统开销小，可以很快获得结果.近年来随着仿生智能优化算法的发展，仿生智能优化算法在多种应用场合如车间作业调度[2]、智能组卷[3]和求解0-1背包问题中被广泛使用并获得了较好的效果.周洋[4]等使用粒子群算法和贪心策略设计算法（GOPSO）求解0-1背包问题.刘雪静[5]等利用乌鸦算法和混沌序列提出求解0-1背包问题的混沌二进制乌鸦算法（BCSA），算法中使用贪心策略修复不可行解，对可行解进行优化.徐小平[6]等利用烟花算法和Kent混沌映射序列设计算法（IFWA）求解0-1背包问题，算法改进了烟花爆炸半径的计算公式，有利于快速在全局最优解附近搜索，提高算法的收敛性.孙静[7]等利用改进鸡群算法（DCSO）求解0-1背包问题，通过調整动态权重来增加种群的多样性;为了提高算法的全局搜索性，避免陷入局部最优解，算法在母鸡和小鸡的位置更新中引入惯性权重因子ω.这些算法在求解0-1背包问题时获得了不错的效果，但在一定程度上也存在全局寻优能力不够强、收敛速度不够快等问题.

针对求解0-1背包问题时算法收敛速度慢、全局寻优性能较差、容易得到局部最优解的弱点，本文提出佳点集乌鸦算法（GCSA）求解0-1背包问题的方法.GCSA结合佳点集算法、乌鸦优化算法以及贪心策略，改进了乌鸦个体位置的更新方式，引入种群收敛性判断：若收敛则随机产生乌鸦的位置，增加种群的多样性;若未收敛则依据当前找到的最优解更新乌鸦位置，增强探索能力，在“开发”和“探索”中获得平衡.仿真实验表明，GCSA寻优平均值大，方差小，收敛速度较快，全局寻优能力较强.

1基本乌鸦算法

乌鸦算法（CSA）是2016年伊朗学者Askarzadeh提出的一种群智能仿生算法[8]，通过模拟乌鸦藏食物和偷窃的行为来解决寻优问题，与其他群智能仿生算法相比较，该算法易于理解，所需要设置的参数少，实现简单.因此，在CSA算法提出后获得了较多学者的关注，CSA被应用到SVM参数优化、车载网络频谱分配方案、 多级阈值图像分割和软件测试用例生成等领域.

乌鸦是一种非常聪明的鸟类，它能够记住自己藏匿食物的隐蔽地方，能跟踪其他乌鸦并试图找到其他乌鸦藏匿食物的位置并偷走食物，而被跟踪的乌鸦能以一定的感知概率发现自己被跟踪然后飞到一个随机位置以保护自己的食物不被找到.假定xi，iter表示乌鸦i的位置，iter是当前迭代次数，在第iter次迭代时，藏食位置为mi，iter.CSA算法的基本步骤是：

（1）系统初始化：设定种群数、迭代最大次数、乌鸦的飞行长度fl和初始感知概率AP.初始化种群中乌鸦的位置，乌鸦的位置表示一个可行解.

（2）初始化藏食物的记忆值，每只乌鸦的初始记忆值设为初始位置，计算个体的适应度值.

（3）更新乌鸦的位置.根据感知概率，乌鸦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]区间均匀分布的随机数，APi，iter+1表示乌鸦j在第iter次迭代后的感知概率 .

（4）检测更新位置的可行性.若可行则更新;否则，保持原来的位置.

（5）计算新位置的适应度值.

（6）更新记忆值.更新公式为：

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

mi，iter，otherwise.（2）

（7）重复（3）-（6）直到达到最大迭代次数.

算法结束后，所有乌鸦记忆值的最好位置就是所求问题的解.

乌鸦算法中的参数比较少，只有飞行长度fl和感知概率AP两个参数，fl较小则局部搜索能力强，较大则全局搜索能力强，AP较小增加集约性，AP较大则增加种群的多样性.

2佳点集的定义和性质

佳点集理论最初由华罗庚[9]提出，佳点集方法可以用于高维空间的近似计算，在高维空间中构造均匀分布的点集.

（1）Gd表示d维欧式空间的单位立方体，x=（x1，x2，…，xd），x∈Gd，0≤xi≤1，i=1，2，…d.

（2）Gd中有一个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中任意一点r=（r1，r2，…，rd），Nn（r）表示在点集Pn（k）中并且满足如下不等式的点的个数：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）有关的常数，那么Pn（k）称为佳点集，称r为佳点.

佳点集的实质是在构造一个在d维的单位立方体Gd中均匀分布的点集，使用佳点集选择的点比随机方法选择的点偏差要小，大约只是随机选择方法的平方根分之一.佳点集良好的性质可以用于仿生智能优化算法的种群初始化阶段，使种群的个体分布均匀.一般地，可以使用分圆域的方法来构造佳点集：

γ=2cos2πp，2cos4πp，…，2cos2πdp，p≥2d+3且p是一个素数.

3佳点集乌鸦优化算法（GCSA）

在基本乌鸦算法中随机数rj小于AP时，更新乌鸦位置用随机位置的方式进行，但这种随机的更新方式会使得搜索具有盲目性，甚至会对同一位置重复搜索，这会使得收敛速度变得缓慢.为了弥补基本乌鸦算法中搜索盲目性和收敛速度缓慢的弱点，笔者提出利用公式计算种群是否已经收敛，若未收敛则利用全局最优解来更新乌鸦的位置，使乌鸦的新位置朝着最优解的方向移动;若收敛，则移动到一个随机位置，这样可以增加种群的多样性.GCSA算法还利用贪心策略对不可行解修复，对可行解优化，提高其收敛速度.

3.1混合编码

乌鸦个体位置xi，iter=[x1，x2，…，xn]的编码方式是实数型的向量，而要求解0-1背包问题需要的是二进制向量，因此，要将实数型的向量xi，iter向二进制型的向量yi，iter=[y1，y2，…，yn]转化，编码的方法如下：

yj=1，xj≥0

yj=0，xj<0.（3）

其中，j=1，2，…，n，种群中的个体使用（xi，iter，yi，iter）共同表示，构成混合编码，其xj∈[-a，a].在本文中a=5.

3.2贪心策略

经过编码后的二进制向量yi，iter只是0-1背包问题的潜在解，由于还要满足0-1背包问题的约束化条件，即放入物体的重量之和不能超过背包的承载量，有可能yi，iter会出现不可行解.贪心策略不仅可以将不可行解修复为可行解，还可以对可行解进行优化，提高收敛的速度，具体算法可以参考文献[5]中的GROA算子.

3.3判断种群是否收敛的方法

设定两个常数K，TH，假设在iter次迭代找到的最大适应度值是fbestiter，计算连续K代最大适应度值的方差，若方差等于小于阈值TH，则认为算法达到了收敛阶段，若大于TH则认为算法未达到收敛阶段.方差公式计算如下：

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

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

其中，fave表示连续K代最大适应度值的平均值，fstd表示表示连续K代最大适应度值的方差.

3.4乌鸦位置更新的改进

为了避免基本乌鸦算法中乌鸦频繁随机移动位置会使得搜索失去方向性的问题，改进了乌鸦位置的更新方式，当随机数rj小于AP时，对种群是否收敛进行判断，若未收敛，就沿着全局最优解移动，若收敛，则移动到随机位置，公式为：

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是當前搜索到的全局最优解所对应的位置，fstd是连续K代最大适应度值的方差，TH是一个阈值常数.

3.5GCSA的具体实现步骤

（1）初始化系统参数，设置种群数目pop，求解问题的维度n，最大迭代次数itermax，以及fl，AP，K，TH.

（2）使用分圆域的方法构造佳点集初始化种群，并用公式（3）对乌鸦位置二进制编码，然后使用贪心策略GROA算子进行修补和优化，计算出个体的适应度.

（3）使用公式（4）计算出连续K代的最大适应度的方差，并用公式（5）对乌鸦位置进行更新.

（4）检测更新位置的可行性.若可行则更新;否则，保持原来的位置.

（5）对更新位置用公式（3）对乌鸦位置二进制编码，然后使用贪心策略GROA算子进行修补和优化，并计算出新位置的适应度.

（6）使用公式（2）更新记忆值.

（7）保存当前适应度值最大的个体位置、二进制编码和适应度值.

（8）若迭代数iter小于最大迭代数则iter加1回到步骤3继续执行，否则输出找到最优解，算法

结束.

4仿真实验和分析

有200个物品，背包载重限制为71 893，其中P向量代表各物品的价值，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，

测试案例在MATLABR2020b下进行仿真实验，GCSA算法分别与GOPSO，BCSA，DCSO，IFWA算法比较.种群数目设为30，最大迭代次数为200，独立运行20次，AP=0.4，fl=0.2，K=5，TH=10，实验结果见表1.GCSA算法可以找到最优解，且方差是所有算法中最小的，具有较强的稳定性和全局寻优能力.

图1是案例五种算法的进化迭代曲线图，BCSA，GOPSO，IFWA，DCSO都没有找到最优解，只有GCSA找到了最优解，且也比其他四种算法的收敛速度快.

5总结

本文针对传统CSA算法求解0-1背包问题时收敛速度慢、容易早熟陷入局部最优解的问题，提出结合佳点集和乌鸦优化算法的改进算法：佳点集乌鸦算法（GCSA）.GCSA利用佳點集初始化种群，贪心策略修复和优化潜在解，通过判断种群的收敛性判断，改进了个体的位置更新公式：在未达到收敛阶段沿全局最优解的方向更新，达到收敛阶段则随机更新，增加种群的多样性.实验结果表明，GCSA算法具有较强的稳定性和较高的全局搜索性，易于跳出局部最优解，寻找到全局最优解.

参考文献

[1]乐天.遗传算法求解0/1背包问题的综述[J].浙江海洋学院学报：自然科学版，2013（1）：71-74.

[2]郑林，柴宝杰，蔡静颖.改进的粒子群算法在车间作业调度中的应用研究[J].牡丹江师范学院学报：自然科学版，2012（2）：3-5.

[3]金玉苹，李春雨.一种改进的遗传算法在智能组卷上的应用[J].牡丹江师范学院学报：自然科学版，2017（2）：38-40.

[4]周洋， 潘大志.求解0-1背包问题的贪心优化粒子群算法[J].西华师范大学学报：自然科学版，2018，39（3）：102-107.

[5]刘雪静，贺毅朝，吴聪聪，等.求解0-1背包问题的混沌二进制乌鸦算法[J].计算机工程与应用，2018，54（10）：178-184.

[6]徐小平，庞润娟，王峰，等.求解0-1背包问题的烟花算法[J].计算机系统应用，2019，028（2）：164-170.

[7]孙静，舒敬荣，方新明，等.基于改进鸡群优化算法的0-1背包问题研究[J].宝鸡文理学院学报：自然科学版，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]华罗庚，王元.数论在近似分析中的应用[M].北京：科学出版社，1978.83-86.

编辑：琳莉