《工业控制计算机》2021年第34卷第5期83基于离散二进制粒子-模拟退火算法求解0-1背包问题
Solv i ng0-1Kn apsack Problem Based on Part i c le B in a ry Swarm-S i mulated
Anneali ng Algor ithm
汤飞何永义（上海大学机电工程与自动化学院，上海300444）
摘要：0-1背包问题是最典型的组合优化问题之一遥目前，有很多算法来解决这个问题，主要分为两类：一个是传统的算法，虽然它在低维和小规模的背包问题中有一个良好的寻优性能，但对于高维大规模的背包问题解决能力显然不占优势；另一个是仿生智能算法，它虽然能够很好地解决高维大规模的背包问题，但使用单一算法总是存在一定的局限性。在搜索解的过程中缺乏全局搜索能力，易陷入局部最优解。针对这一问题，提出了BPSO-SA算法，利用BPSO算法的全局搜索的优点，再引入了SA算法的退火过程中思想，使算法避免陷入局部最优解。通过大量的实验测试，验证了该文提出的算法的可行性，并且具有更好的寻优能力。
关键词：粒子；模拟退火；0-1背包问题
Abstract:The0-1knapsack problems one of the most typ i c al comb i n ator i a l opt i m i z at i o n problems.At present,there are many algor i t hms to solve th i s problem,ma i n ly d i v i dednto two c
ategor i es：one is the trad it i o nal algor i thm,although it has s good opt i m i z at i o n performance in low-d i m ens i o nal and small-scale knapsack problems,but for h i g h-d i m ens i o nal large-scale knapsack problems,the solut i o n ab il ity is obv i o usly not the dom inant one;the others the b ion i c intell i g ent algor i t hm.Although it can solve the h igh-d imens i o nal and large-scale knapsack problem well,the use of a s i n gle algor i t hm always has certa i n l i m i t at i o ns.In the process of search i n g the solut i o n,i t lacks the global search ab il ity,and it is easy to fallnto the local opt imal solut ion.A i m i n g at th i s problem,th i s paper proposes the BPSO-SA algor i thm,wh i c h uses the advantages of the BPSO algo­rithm's global search,and then introduces the SA algor i thm's anneal i n g process idea,so that the algor i t hm avo i d s fall ing into the local opt i m al solut i o n.Through a large number of exper i m ental tests,the feas i b il i t y of the algor i t hm proposed in th i s paper is ver i f i ed,and it has better opt i m i z at i o n ab il ity.
Keywords:part i c le swarm,s i m ulated annealing,0/1knapsai
0-1背包问题(0-1Knapsack Problem,0-1KP)是运筹学中经典的组合优化问题［1］，其最终的目的是到满足背包约束的最有价值的物品加载方案咱y」。在现实中有许多复杂难以求解的问题，都可以近似转化为背包问题，例如在商业中的资源分配问题、投资决策问题、工业物流中的装载问题等［4］。因此研究背包问题的求解算法具有重要的价值。
求解0-1背包问题的算法有很多，总体上可以分为两类：一类是传统算法，另一类是智能算法。传统算法是较为精确的求解方法，主要包括动态规划法、回溯法和分支定界法等。传统算法主要适用于求解低维度小规模的背包问题，但当规模较大维度过高时，传统算法的求解复杂度和时间呈指数型增长，并且求解的精确度也大大降低，而智能算法可以很好地解决这个问题，因此被广泛运用到求解0-1背包问题中去。智能算法是一种非精确算法或近似求解算法，通过对自然界生物的体行为的模仿或受社会实践活动的启发，主要包括遗传算法(Genet i c Al­gor i t hm,GA)［5］、粒子优化算法(Part i cle Swarm Opt i m i z a-tion,PSO)冏、蚁优化算法(Ant Colony Opti m ization,ACO)［7］、模拟退火算法(Si mulated Anneali ng,SA)及其混合算法等。
粒子算法最早是由Kennedy和Eberhart在1995年提岀的。该算法受鸟类在捕食过程中的行为启发，模拟鸟类个体之间的相互合作和信息共享的方式来寻最优解遥PSO算法其优点在于简单易操作，收敛速度快，没有过多的参数，但容易陷入局部最优解。SA算法的思想来源于固体退火过程。SA算法的核心思想其实是一种贪婪算法，只是在搜索解的过程中增加了一个随机因素。在退火的过程中根据当前解随机挑选一个，通过解中的位置problem
随机交换而产生新的解，并接受具有一定几率的比当前解较差，使粒子有机会跳岀局部最优解，从而收敛于全局最优解。
本文将BPSO算法和SA算法融合，以BPSO算法主体框架，嵌入模拟退火的思想，提岀一种离散粒子-模拟退火算法(Di srete B i nary Part i cle Swarm Opt i m i z at i o n-Si mulated An­neal i ng Algor i t hm,BPSO-SA)遥在不同尺度上的实验表明，本文提岀的算法能够在一定程度上避免早熟收敛，具有跳岀局部最优解的能力，提高了全局寻优能力。
10-1背包问题的数学描述
1.1问题描述
0-1背包问题可以简单描述为：给定一个限制承载重量的背包袁对于一组给定的货物，货物有重量和价值两种属性，要求在背包限制的承载重量范围内，如何选择合适的货物进行装载，最终使背包中装载的货物的价值达到最大价值。
1.2数学模型
设n个物品的重量为W i(i=1,2，噎,n)，对应的价值为V(= 1,2，噎,n)，背包容量为C。设X j为0或1的变量，当货物能装入背包时X=1，否则x j=0遥那么背包中总重量为移x*W「，总价
i=1
值为移曾鄢W：。装载时的约束条件是背包中货物的总重量要小i=1
于背包承载量。所以0-1背包问题的目标是在不超过容量的条件下尽可能地装满背包，使背包中的货物价值最大化。该背包问题的模型如(1)所示遥
n
f=max移x鄢V
84基于离散二进制粒子-模拟退火算法求解0-1背包问题
sJ移曾*宰臆悦(1)嗓X i m{0,1|(i=1,2,…,n)
2离散二进制粒子-模拟退火算法的设计
2.1标准粒子算法
将鸟抽象为一组没有质量和体积的粒子，并扩展到N维空间。粒子i在N维空间中的位置表示为X i(X1,X2，噎,X n)，飞行速度表示为v,=(V1,V……，V n)。每个粒子都可以通过目标函数确定自己的适应度值。在0-1背包问题中，公式(1)中的适应度值为f，即寻约束条件下的最大价值。每个粒子经过随机初始化后就已知个体最优值(pbest)，和当前所处的位置X，这个是粒子自身的飞行经验。每个粒子通过种间的信息共享，获得整个体中的最优解(gbast)，这是体的飞行经验遥通过比较自己的
经验和团队的经验，他们可以一起决定下一个动作的方向遥标准PSO算法首先通过初始化得到一个随机解，然后使用公式(2)更新自己的速度，使用公式(3)更新自己的位置。同时，它继续迭代，直到到两个极值pbast和gbast，满足最终条件或达到设定迭代次数的最优解。公式(2)和(3)构成了PSO算法的标准形式:
淄越淄+c1*rand()*(pbest i-X i)+c2*rand() *(gbest i-x,)(2) X i=X i+淄,(3)在公式(2)和(3)中，i=1,2,…N,N是这个中粒子的总数。粒子飞行速度用v，表示,0和C2是学习个体经验和体经验的因子，rand()代表0到员之间的随机数，粒子的当前位置用X蚤表示。公式(2冤中有3个组成部分：第一部分v，是粒子本身的记忆项，代表粒子自己的速度趋势；第二部分是粒子的飞行经验项，代表粒子的历史飞行经验，凭借自身的飞行经验向最优的位置飞行；第三部分是粒子体经验项，代表体中的搜索经验，可以为其他单个粒子起到指导的作用，粒子的速度更新公式就是在这三项综合作用的结果朝着最优的位置飞行。公式(3)由两部分组成：第一部分X，是粒子自身所处的位置；第二部分是v,，表示单位时间的速度变化，时间无限小，表现了粒子位置更新的更加灵活。
2.2离散二进制粒子算法
离散二进制算法(Di srata B i nary Part i cla Swarm Opt i m i z a- t i o n Algor i t hm,BPSO)由Kennady和Ebarhart在1997年设计, BPSO算法主要优化离散空间约束问题，具有很强的全局搜索能力，但不能
收敛于全局最优值。BPSO算法是在标准PSO算法的基础上设计提岀的。BPSO算法的速度更新公式和PSO算法一样，仅仅更换了位置更新公式，采用概率映射的方式改变粒子的位置，利用si gmo i d函数(4)将速度映射到［0,1暂区间作为概率，粒子下一步的位置变化由这个概率决定。BPSO算法的位置更新公式见(5)所示。
s(”,)=」^(4) 1+e
X」1,rand()<s(淄,)
10,esle
2.3模拟退火思想
SA算法的接受准则是Metropol i s，通过控制温度、降温速率、终止温度等参数来模拟固体退火的过程。本文选取传统模拟退火算法中模拟机制，即在降温的过程中，根据马尔科夫链长重复执行以下过程:
1)根据随机交换机制产生新解。即在当前的所有解当中随机选择一个解，因为解都是二进制编码的，所以可以让这个解中的任意两个位置进行交换，就可以产生新解；
2)新解和旧解的比较。即根据目标函数分别计算新解和旧解的适应度值，再将二者作差，若差值大于0，就将新解替换旧解；否则根据概率计算公式判断是否接受这个比旧解差的新解；
3)更新粒子体极值gbast；
4)重复1),2)步骤，直到退火过程完成。
2.4BPSO-SA算法的提岀
通过以上的分析，在BPSO算法和SA算法的基础上，提岀了本文的融合算法BPSO-SA，结合对0-1背包问题的分析，算法以BPSO算法为整体框架，在BPSO算法的内部嵌入模拟退火算法中退火过程，使得本文提岀的算法兼具了二者的优势。BPSO-SA算法的具体流程见图1。
图1BPSO-SA算法流程图
3实验与分析
实验环境为Wi n10操作系统,Intel Core i7-7700HQ CPU处理器,8GB内存，Matlab2017A开发环境。BPSO-SA算法中的参数设置为：种规模大小为100，迭代循环次数为200，学习因子C1=C2=1.5，速度最大值为V max=6，初始温度T°= 1000，马尔科夫链长L=80，降温速率琢=0.95终止温度为Tend=
1a-3遥为测试BPSO-SA算法在不同维度中的0-1背包问题上的寻优能力，引入文献［8］中的10维到100维的9组数据进行测试，同时也对PSO算法、BPSO算法和SA算法测试进行比较。每组数据的算法独立运行50次，取其中最优解，测试结果见表1。
表1实验结果
(5)
■-I'SC
tFfiv耒
r
t；卜口「rF:
L|>v::/ji--
I：
••汀.忙-■：■：：1=：#I.'K•：=I i.~.宀：3n1>
v-II-
：1：1■
%K:■j'.m.'iwL1 6Il II1.■；1'1：1V I;■-1.：■：>1:1.1.1■■:ii.r'i 7:;:■:5：-11H:•:.：.即卅：.%.：心A"
■-；；1/1-1：1■-■：!•11V■.1
'；■!■Il1-1-I：-；.'；；；■■-.；1........■r,r：.i：1■!>：-.；?•■■-.■-I；--实验测试结果表明本文所提岀的算法BPSO-SA，无论在低维度还是高纬度的背包问题求解过程，都取得了很好的表现。在求解低维度的背包问题中，即实验编号1到4的四组实验，本
(下转第86
页)
86一种有效的系统软件故障定位方法
名到第三等级;Och iai定位方法虽然将错误与语句2排名到了
第4等级，但是将错误语句7排名到了第10等级，这两种方法
会使故障定位结果恶化。
2新的故障定位方法
根据以上叙述，拟提岀新的故障定位方法，一般分为三步：
Step1：用多个不同测试用例执行程序的语句，将测试用例
和语句之间建立测试程序语句集。
Step2：建立语句与测试用例之间的贡献度集合。然后在测
试成功用例和失败用例分别剔除执行相同语句用例，这些相似
用例只留一个测试用例。
Step3：根据测试程序语句集和贡献度集合计算岀每个语
句怀疑度，并进行排名。
2.1模型矩阵建立
为了表示语句的贡献度，我们将每个语句贡献度视为相等,
对于失败案例，我们将贡献度总和视为琢，成功案例贡献度总和
视为茁(其中琢＞茁)。假如在某次测试时候，一个失败用例共执行
l个语句，一个成功案例共执行q个语句，故语句j贡献度为：
越严/l t，语句j执行失败用例
孜躁-b=10，其他情况
|茁/q，语句j执行成功用例
孜j-c=l0，其他情况
2.2计算语句的怀疑度
假设一个程序有A个测试用例执行语句，在这些用例中失
败测试用例有A1个，共A；个测试执行相同的语句，有成功测试
用例有A2个，共A2个测试执行相同的语句，语句j失败的用例
所占的比例是为h j-澡，成功测试用例的所占的比例为h j-。。
令语句j的怀疑度为H jew，根据定义它应该是h j-b和h j-G的
比值，那么语句j的最终是怀疑度为：
new
粤：原粤
移孜-遭
h j-c A?%
(3)
H 2.3结果论证
为了说明文中提岀的新的方法的有效性，拟采用表格3中求岀三个数的中位数的例子，用本文方法分别求岀程序的每个语句对测试用例的贡献度，如表3所示：
表3程序语句怀疑度排名
tftk12345E7Q ID111213
0.495仙20110.5330.533-0.53S
11>599g10122255-5129
由于错误语句为语句7和语句2，故应该尽可能靠前，从表3可知，错误语句7排名和语句6都处于领先位置，错误语句2的排名也比较Tarantula方法保持了比较持平位置，说明本文方法比语句上面更有效，更好满足测试人员的要求。
3结束语
由于在系统运行时候，有时候会岀现软件故障问题，在讨论了Tarantula定位方法和Ochiai定位方法之后，发现这两种方法在故障定位时，有冗余岀现的时候，有效性不够，本文提岀的软件故障定位方法经实际论证比上述两个方法都要有效。
参考文献
[1]A Jones,M J Harrold.EmpiricalEvaluation of the Tarantula Au­
tomatic Fault-localization Tech-nique[C]/Proceedings of the 20th IEEE/ACM Inter-national Conference on Automated Software Eng-ineering,New York,NY,USA,2005:273-282 [2]A da Silva Meyer,A A Franco Farcia,A Pereira de Souza.
数学二进制的算法Comparison of Similarity Coefficients Used for Cluster Analy­sis with Dominant Markers in Maize(Zea mays L)[J].Genet-ics and Mol-ecular Biology,2004,27(1):83-91
[3]Wong W E,Wei T,Qi Y,et al.A Crosstab-based Statistical
Method for Effective Fault Localization[C]/International con­ference on software testing,ver-ification,and validation,2008: 42-51
[4]汪荣•一种关于振动台活动部件故障定位的新方法[J].中国设备工
程,2020(24)：49-53
[5]蔡艳•输入域缺陷定位技术实证研究[D].南京：南京邮电大学,2020
[收稿日期2021.1.13]
(上接第84页)
文所提岀的算法BPSO-SA求解的结果，均能达到目前已知的最优解。在实验编号5到9的五组高维度的实验中，BPSO-SA 算法同样取得与已知最优解一样的结果，并且在实验编号5中，BPSO-SA算法取得结果(3108/1000)优于已知解(3103/ 1000)，也优于文献[8]中的解。与PSO、BPSO及SA算法相比，本文提岀的BPSO-SA算法整体解的质量更高。
4结束语
本文提岀了BPSO-SA算法，该算法利用BPSO算法对于离散问题全局搜索的优点，以此作为BPSO-SA算法的主体框架，并嵌入退火机制，利用SA算法在退火过程中随机产生新的解，并以一定的概率接受新的解，使算法具有跳岀局部最优解的能力。通过大量实验证明，本文提岀的BPSO-SA算法无论在低维还是高维的背包问题中，求解的质量都较为岀。
参考文献
[1]周钱.多选择多约束背包问题的进化求解策略[D].合肥：中国科学技
术大学, 2011[2]Fayard D,Plateau G.Resolution of the0-1knapsack prob­
lem comparison of methods[J].Mathematical Programming, 1975,8(1):272-307
[3]Rong A Y,Figueira J R,Klamroth K.Dynamic programming
based algorithms for the discounted(0-1)knapsack problem [J].Applied mathematics and computation,2012,218(12):6921-6933
[4]He Y C,Zhang X L,Li W B,et al.Algorithms for random­
ized time-varying knapsack problems[J].Journal o f combina­torial optimization,2016,31(1):95-117
[5]贺毅超，宋建明，张敬敏，等•利用遗传算法求解静态与动态背包问题
的研究[J]•计算机应用研究,2015,32(4)：1011-1015
[6]包广清，毛开富.改进粒子算法及其在风电系统中的应用[J].控制
工程,2013,20(2)：262-266
[7]廖灿星，李行善，张平，等•一种求解背包问题的正态分布蚁算法
[J].系统仿真学报,2011,23(6)：1156-1160
[8]吴虎胜，张凤鸣，战仁军，等•求解0-1背包问题的二进制狼算法
[J]•系统工程与电子技术,2014,36(8)：1660-1668
[收稿日期：2021.1.18]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。