遗传变异蝙蝠算法在0_1背包问题上的应用
网络出版时间:2012-10-11 10:19
网络出版地址:http://www.cnki.net/kcms/detail/11.2127.TP.20121011.1019.027.html
Computer Engineering and Applications 计算机工程与应用
遗传变异蝙蝠算法在0-1背包问题上的应用1
李枝勇,马良,张惠珍
LI Zhiyong, MA Liang, ZHANG Huizhen 上海理工大学 管理学院,上海 200093
School of Management,University of Shanghai for Science and Technology, Shanghai 200093,China
LI Zhiyong, MA Liang, ZHANG Huizhen. Genetic mutation bat algorithm for 0-1 knapsack problem.Computer Engineering and Applications
Abstract:0-1 knapsack problem is a typical NP-hard combinatorial optimization problem. Genetic mutationbat Keywords:
摘要:0-1背包问题是经典组合优化NP 0-1背包0-1背包问题. 关键词:蝙蝠算法;0-1
1 引言
0-1,已被应背包问题可被描述为:给定n 个物品和一个背包, 物品i 的价值为p i 、重量为
⎧n
⎪∑w i x i ≤C s.t. ⎨i =1(i=1,2," ,n) (2)
⎪x ∈{0,1}⎩i
就计算复杂性而言,背包问题属于NP 难题,随着问题规模的增大,求解时间随指数增长, 在最坏的情况下, 时间复杂度为
O (2n ) .因此,设计新的高效算法来求解背
包问题具有重要的理论和实际意义.从已有的研究成果来看,求解背包问题的方法主要有精确算法和启发式算法两大类.其中,精确算法包括分支界定法、动态规划法、递归法和回溯法等.启发式算法主要包括贪心算法、遗传算法、蚁群算法、蜂群算法
[2]
[3]
[4]~[5]
" ,n) ,背包能容纳的最大物品w i (i=1,2,
重量为C ,现要求从这n 个物品中选出若干件放入背包,使得放入物品的总重量不超过
C ,且总价值达到最大:
max Z=∑p i x i (1)
i =1
n
、
基金项目:国家自然科学基金资助项目(70871081)资助;上海市研究生创新基金项目(JWCXSL1202)资助.
作者简介:李枝勇(1986-),男,硕士研究生,研究方向为系统工程和智能优化;马良(1964-),男,博士,教授,博士生
导师,研究方向为系统工程和智能优化.Email:[email protected]
粒子群算法、模拟退火算法、禁忌搜索算法、量子群算法及以上几种算法的改进算 法
[7]~[8]
[6]
物时的最小. 研究表明, 微型蝙蝠利用发出和探测回声的时间延迟和双耳的时间差以及回声的响度变化去建立周围环境的三维场景. 蝙蝠能够探测出目标物的距离、方向、种类和移动速度, 哪怕只是一只小昆虫. 事实上, 它们通过将所有的感官联合运用使探测猎物的效率最大化, 使飞行能够顺利无误. 受启发于微型蝙蝠这种回声定位行为方式与优化目标功能的相关联性,Xin-She Yang 于2010年提出一种新型的启发式算法---蝙等.精确算法虽然可以得到精确解,
但是当物品数目较大时,精确算法并没有可行性.启发式算法虽然不一定得到精确解,但可以得到次优解,时间复杂度也比较低. 蝙蝠算法(Bat Algorithm,简称BA ) 是Xin-She Yang 于2010年提出的一种新型启发式算法.自该算法提出以来,已有学者将
[9]
变异2.1(变化取决于物种, 并经常通过使用更多谐波来提高, 但是它们探测猎物和避免障碍的原理都是基于回声定位的声学原理. 由于声音在空气中的速度通常为v = 340 m/s,而超声波在f 频率下的波长为:λ =v/f.研究显示, 蝙蝠通常发出的频率为25kHz 到150kHz, 波长λ的范围在2mm 到14mm 之间, 这样的波长类同于它的猎物的大小. 蝙蝠发出在超声波范围内的声波, 其响度能达到110dB, 且响度可以从搜索猎物时的最高变化到靠近猎
择一只蝙蝠, 并根据公式(6)更新该蝙蝠相应的位置,这个过程可被理解为一个局部搜索过程, 即在被选择的产生一个新解.x new (i ) =x old +εA (6)
其中,x old 表示从当前最优解集中随机选择的一个解,A 表示在t 时刻前i 只蝙蝠响度的平均值,随机向量ε的元素是区间[−1,1]的随机数.
2.1.2响度和脉冲速率
t
t
通常,蝙蝠在接近猎物的过程中,响度会逐渐降低,脉冲发射的速率会逐渐提高.蝙蝠i 脉冲的响度A (i ) 和发射速率R (i ) 可根据下述公式(7)更新:
算法可以视为标准粒子群优化和由响度和脉冲速率控制的集中局部搜索的一种均衡组合.
[9]
3 遗传变异蝙蝠算法(GMBA) 3.1主动进化算子
为了引导当前最优蝙蝠能够主动地产生适应环境的变异,本文引入诱变因子来设计主动进化算子.针对0-1背包问题,诱变因子是由D 个0~1之间的小数组成的数字串
A t +1(i ) =αA t (i ), R t +1(i ) =R 0(i ) ×[1−e x p (−γt )](7)
其中,0
0,均为常量.A (i ) =0
时意味着蝙蝠i 刚刚发现一只猎物,暂时停止发出任何声音.不难发现:当t →∞时,
A (i ) →0, R (i ) =R (i ) .
2.2 蝙蝠算法
假设求函数
t t 0
f (x ) 的最小值,种群大小
(m 1m 2" m D ) i 表示根据先验知识,物品
i _value i , _i 为n ,第i 只蝙蝠的位置为x (i ) , 其中,
x (i ) =(x i 1, x i 2, " , x iD ), i =1, 2, " , n .蝙蝠
算法的基本步骤可以概括为如下伪代码:
初始化种群蝙蝠位置x (i ) ,速度v (i ) , 脉冲发射速率R (i ) ,脉冲响度A (i ) 率F (i ) ,个体评价
vc i =i /avg _value i 越大越好,而vc i fitness (i ) =f (x (i )) , (i =1,2, while for
i =1:n
q i _value i −vc i (8)
=(q i −min{q i })/(max{q i }−min{q i })(9)
其中,t , MAXGEN 分别表示当前代数和最大循环代数,ρ(t ) 用来调整avg _value i 和
x new if rand
>i endif
vc i 的关系.由上式可以看出,m i 和物品i
放入背包的概率成正比关系.
根据诱变因子,可以对当前最优蝙蝠进行主动进化:将每个蝙蝠所处位置的每一个变量定义为一个基因位.当该基因位的进化概率m i 大于产生的随机数,就对该基因位取反,从而生成一个最优蝙蝠的备选解,并将其与先前最优蝙蝠进行比较,取较优者作为当前最优蝙蝠.
如果一个蝙蝠表示的所选物品的总重量超过了背包的最大重量容量,则称其为无效蝙蝠.对于无效蝙蝠,可以根据计算出来的诱变因子判断无效蝙蝠的基因是否应该由1变成0.如果该基因位的变异概率m i 小于产生
fnew f x ) if rand
x (i ) =x new
fitness (i ) =fnew
通过式(7)更新R (i ) 和A (i ) endif endfor
更新当前最佳解x *及其对应参数 endwhile
可以看出,蝙蝠的速度及位置的更新策略和标准粒子群算法更新速度和位置的策略有些相似之处,从某种程度上来讲,蝙蝠
的随机数,就对该基因位进行取反操作.基因位变异后,再次判断该蝙蝠是否有效,如果仍是无效蝙蝠,继续重复前面的操作,直到该蝙蝠成为有效蝙蝠为止.
对当前最优解进行主动进化策略 endwhile
为了保持种群的多样性,改善算法的收敛性能,上述算法中当有多只蝙蝠均停留在当前最优位置时,在保留一个最优蝙蝠的前提下随机生成新的有效蝙蝠替代停留在当前最优位置的其他蝙蝠.
3.2遗传变异蝙蝠算法(GMBA)
通过将上述主动进化因子引入蝙蝠算法,本文提出了一种新的混合智能优化算 法---遗传变异蝙蝠算法。假设蝙蝠种群数为
4 仿真试验
算法的运行环境是Win7系统下.参数设置为:频率下界fmin=0,
率
上
界
fmax=1, αγ0.9, 速度下界始速度
v A ∈[0,1]
n ,第i 只蝙蝠的位置为
x (i ) =(x i 1, x i 2, " , x iD ) ,其中,
i =1,2, " , n . 遗传变异蝙蝠算法的基本步
骤可以概括为如下伪代码:
初始种群中第i 只蝙蝠位置:x (i ) =
round (rand (1, D )) ,判断种群中
每只蝙蝠是否为有效蝙蝠,如果是无效蝙蝠,初始速度v (i ) ,初始化脉冲发射速率R (i ) 脉冲响度A (i ) ,脉冲频率F (i ) [0,0.5]均用随机rand 1D =10,最大重量限制C w =[95,4,60,32,23, p=[55,10, 295.
[11]
2物件个数D =20,最大重量限制w =[92,4,43,83,84, 68,92,82,6,44,32,18,56,83,25,96,7048, 14,58],各个物件价值p =[44,46,90,72,91, 40,75,35,8,54,78,40,77,15,61,17,75, 29,75,63],最优值1024.
[7]
例3物件个数D =50,最大重量限制C =11258,各个物件重量w =[438,754,699, 587,789,912,819,347,511,287,541,784, 676,198,572,914,988,4,355,569,144, 272,531,556,741,489,321,84,194,483, 205,607,399,747,118,651,806,9,607, 121,370,999,494,743,967,718,397,589, 193,369],各个物件价值p =[72,490,651, 833,883,489,359,337,267,441,70,934, 467,661,220,329,440,774,595,98,424,37,807,320,501,309,834,851,34,459,111, 253,159,858,793,145,651,856,400,285,405,95,391,19,96,273,152,473,448,231], 最优值为16102.
为了验证算法的寻优精度,对上述三个例子
fitness (i ) =Z (x (i )) , (i =1while for
i =
1if (
1endif
判断蝙蝠是否为有效蝙蝠并处理
Znew =Z (x new )
() &&Z n e w >fitn e ss (i ) if ra n d
x (i ) =x new
fitness (i ) =fnew
通过式(7)更新R (i ) 和A (i ) endif endfor
更新当前最佳解x *及其对应参数
分别运行50次,结果如表1所示.表1中,"比值"指算法寻优最好值与实际最优值的比值,“‐Inf”表示在初始化蝙蝠位置时不关注蝙蝠是否有效情况下, 在规定的循环次数内所有蝙蝠均为无效蝙蝠,”---“表示在出现”‐Inf”的情况下数据不做统计.
表1 GMBA和BA 寻优结果
Tab.1 the optimizing results of GMBA and BA
例 1 2 3
种群数 2 4 100
最大迭代次数600 600 600
GMBA
最差值 295 943 13636
平均 值 295 1013.114667
最好值 295 102416055
比值 1 1 0.9971
最差值 ‐Inf 517 10269
平均 值
BA
最好值
比值
295 1 ---
775.94 1024 1 12954 16005 0.9940
[3]马良,王龙德.背包问题的蚂蚁优化算法[J].计
算机应用,2001,21(8):4-5.
[4]樊小毛,马良.0-1背包问题的蜂群优化算法[J].
数学的实践与认识,2010,40(6):155- 160.
[5]吴迪,姜永增,宋广军.基于蜂群遗传算法的0-1
背包问题[J].计算机工程与科学,2011, 33(5):102-105.
[6]柳寅,马良.0-1背包问题的模糊粒子群算法求
解[J].计算机应用研究,2011,28(11): 4026-4028.
[7]金慧敏,马良.遗传退火进化算法在背包问题中
本文将诱变因子引入到变异策略中,设计出主动进化算子,不仅实现了最优蝙蝠的主动进化,同时也丰富了种群的多样性,使得本文提出的遗传变异蝙蝠算法在求解0-1背包问题时,在收敛速度和精度上均优于基本的蝙蝠算法,且具有一定的可行性和较好的寻优能力,但是与其他改进的智能算法相比,本文提出的新算法在稳定性和收敛速度上还存在明显的不足,其中的原因是作者今后要研究的内容.
参考文献
的应用[J].上海理工大学学报,2004,26 (6):561-564.
[8]何小锋,马良.求解0-1背包问题的量子蚁群算
29-31.
[9]Xin-She Yang. A new metaheuristicbat-inspired
algorithm[J], in: Nature Inspired Cooperative Strategies for Optimization( NICSO2010)(Eds.
J. R. Gonzalez et al.), SCI 284, 2010:65-74. [10]Xin-She Yang. Bat algorithm for multi-objective
optimization[J]. Int. J. Bio-Inspired Computation, 2011,3(5):267-274.
[11]马良,朱刚,宁爱兵.蚁群优化算法[M].北京:
科学出版社,2008.