基于均匀设计抽样遗传算法求解背包问题

陈明华, 任 哲, 周本达

(1.皖西学院数理系,安徽六安 237012; 2.合肥学院数理系,安徽合肥 230022)

基于均匀设计抽样遗传算法求解背包问题

陈明华1, 任 哲2, 周本达1

(1.皖西学院数理系,安徽六安 237012; 2.合肥学院数理系,安徽合肥 230022)

众所周知,遗传算法的运行机理及特点是具有定向制导的随机搜索技术,其定向制导的原则是：导向以高适应度模式为祖先的“家族”方向.以此结论为基础,利用均匀设计抽样的理论和方法,对遗传算法中的交叉操作进行了重新设计,给出了一个新的GA算法,称之为均匀设计抽样遗传算法.最后将均匀设计抽样遗传算法应用于求解背包问题,并与简单遗传算法和文献[2]中的佳点集遗传算法进行比较.通过模拟比较,可以看出新的算法不但提高了算法的速度和精度,而且避免了其它方法常有的早期收敛现象.

遗传算法(GA);均匀设计抽样(UDS);均匀设计抽样遗传算法(UDSGA)

1 引 言

0/1背包问题(Knapsack Problem)是著名的NP完备类困难问题,许多理论和实际工作者对此问题作了深入的研究,提出了不少的求解这个问题的经典方法,用这些方法求解该问题时确实能得到很好的结果,但是这些传统的优化方法在求解较大规模的0/1背包问题时,都存在计算量大、迭代时间长的弱点.近年来蓬勃发展起来的遗传算法凭借它的全局最优性、可并行性、高效性,已被广泛应用于组合优化领域.遗传算法克服了传统优化方法的缺点,借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制.所以,如何运用遗传算法求解大规模的0/1背包问题已成为当前研究的一个热点.

2 0/1背包问题描述

式中xi为0/1决策变量,xi=1时表示将物品放入背包中,xi=0表示不将物品放入背包中.

解决0/1背包问题,一般是采取递归回溯法和贪婪法.递归回溯法是一种基于穷尽的思想,即问题的求解空间范围从000…0(l个二进制位)到111…1(l个二进制位),共计2l种组合.用递归回溯法解决0/1背包问题的优点在于它算法简单,而且它能完全遍及搜索空间,肯定能找到问题的最优解.由于此问题解的总组合数有2l个,随着物件数l的增大,其解的空间将以指数级增长,当l大到一定程度时,用此算法解决0/1背包问题将是不现实的.贪婪法的基本思路是从问题的某一个初始解出发逐步逼近给定的目标,尽可能快地求得更好的解,当达到算法中的某一步不能再继续前进时,算法停止.使用贪婪法求解时难以得到整体最优解,有时所得解与最优解相差甚远,因此,不少学者探索使用遗传算法解决物件数较大的背包问题.

3 均匀设计抽样遗传算法

文献[1]对GA算法中的两个理论基石“模式定理”和“隐性并行性质”进行了分析,指出GA算法的本质是：遗传算法是一个具有定向制导的随机搜索技术,其定向制导的原则是：导向以高适应度模式为祖先的“家族”方向.文献[2]根据此机理,利用数论中的佳点集理论和方法[3]设计了一个新的交叉算法,提高了GA算法的效率.这种算法称为佳点集遗传算法.但佳点集的选取在n取定后是确定的,不带随机性.为了克服此不足,我们提出均匀设计抽样遗传算法.本文就是利用均匀设计抽样[4]来设计一个新的交叉算法,以提高GA算法的效率,然后将之应用到0-1背包问题的求解.实验证明无论是在求解精度上还是在求解速度上,均匀设计抽样遗传算法不仅优于GA算法,也优于佳点集遗传算法.为此先简单介绍一下文中要用的均匀设计抽样理论方面的内容.

3.1 均匀设计抽样.

均匀设计抽样这样进行[4]：

我们称这样的抽样方法为均匀设计抽样(Uniform Design Sampling(UDS)),所得到的样本Xk=xk1,…,xkt,k=1,…,n称为均匀设计抽样的样本,并记为

3.2 均匀设计抽样遗传算法.

1)均匀设计抽样交叉操作

设在传统的GA算法基础上,在进行过复制后,对池中的元素按赌轮法选择两个元素A1,A2进行均匀设计抽样交叉操作.

令

由A1,A2进行交叉(不管是单点交叉或是多点交叉)其子孙必属于H,于是要在“高适应度模式为祖先的家族方向”上搜索出更好的样本,就是要在H中搜索出更好的样本.均匀设计抽样遗传算法就是在H上利用均匀设计抽样方法找出好样本来,其方法是[4]：

将H的前t个分量看成一个t维的立方体(仍记为H)然后在H上进行均匀设计抽样.在t维空间中进行均匀设计抽样交叉的方法如下：

〈a〉表示：若a的小数部分小于0.5,则〈a〉=0;否则〈a〉=1.

这样,在其“家族”中,产生了n个后代,取其中适应值最大者(或最大的几个),作为交叉后的后代.

上述交叉操作,称为均匀设计抽样交叉操作.

2)均匀设计抽样遗传算法

给定交叉概率pc和突变概率pm,均匀设计抽样遗传算法如下：

(i)每次进行遗传操作,以概率fi/Σfi复制Ai,其中fi是Ai的适应度值.

(ii)以赌轮法随机取两个染色体,以概率pc对其进行均匀设计抽样交叉操作(产生n个后代,n为待定参数).

(iii)以概率pm进行变异遗传操作.

(iv)把经过遗传操作后得到的染色体都放到染色体池中,对新得到的染色体,计算其适应度值.若假定染色体的容量一定,当染色体的个体超过容量时,就将适应度小的染色体从池中删去(或按a%进行删除).

(v)进行上述的遗传算法至第T代后(T是预先给定的常数),在第T代的染色体中取适应度最大的染色体,即为所求的染色体.

4 0/1背包问题的均匀设计抽样遗传算法求解

4.10/1背包问题的均匀设计抽样遗传算法.

均匀设计抽样遗传算法解决0/1背包问题,采用传统的二进制编码,符号同2中,求解过程为

1)随机产生初始群体X(0).

2)利用赌轮法随机进行遗传算法的选择、复制,

3)利用均匀设计抽样遗传算法进行交叉、变异等遗传操作.

4)重复2),3)步至第T代后(T是预先给定的常数),在第T代的染色体中取适应度最大的染色体,即为所求的染色体.

4.2 求解过程及实验结果分析.

对均匀设计抽样遗传算法、佳点集遗传算法、简单遗传算法在同样条件下(只是利用各自的交叉操作)解决0/1背包问题,并比较、分析实验结果.

在P4 3.0G PC机器上,在Matlab 7.0计算平台上,利用遗传算法工具箱中“简单遗传算法”、文献[2]中的“佳点集遗传算法”和这里的“均匀设计抽样遗传算法”按文献[2]中提供的测试用例以及按文献[5]提供的模拟用例生成方法生成测试算例进行了计算比较.

1)文献[2]中算例的价值V,体积W,以及背包容量C如下：

用传统的简单遗传算法、佳点集遗传算法和均匀设计抽样遗传算法分别对问题进行1000次求解,其中取交叉概率Pc=0.9,变异概率Pm=0.001,惩罚系数β=2.5,群体规模为100,终止代数为500,佳点集中的佳点个数取10(即取10个中使适应度最大的).结果见表1.

表1

表1中GA表示简单遗传算法;GGA表示佳点集遗传算法;UDSGA表示均匀设计抽样遗传算法.

由以上数据表和在线、离线性能比较图可以得出：均匀设计抽样遗传算法在搜索能力、收敛速度以及避免早熟等各项指标上均好于简单遗传算法和佳点集遗传算法.

2)模拟结果

下面结合实例将简单、佳点、均匀设计抽样遗传算法进行有效比较,实例中问题规模为50个变量,随机产生系数值,按以下步骤生成一个背包问题,共生成10个.

(i)50个系数vi,wi在区间(0,999]内随机产生.

(iii)若wi＜C,(i=1,2,…,l.)则结束;否则转第(i)步.

图1 离线性能比较图

图2 在线性能比较图

表2

从上表中可以看到,简单遗传算法对于模拟的10个背包问题都没有得到贪心算法的解,而佳点集遗传算法对于模拟的10个问题有部分超出贪心算法的解,但对于均匀设计抽样遗传算法全部超出贪心算法解,并且在提高率上大大高于佳点集遗传算法,所以,可以说均匀设计抽样遗传算法的全局搜索能力大大强于简单遗传算法和佳点集遗传算法.

5 结 论

遗传算法是一个具有定向制导的随机搜索技术,其定向制导的原则是：导向以高适应度模式为祖先的“家族”方向,所以任何一种交叉操作都无非是在以其父代为“祖先”的“家族”中寻找一个适应值高的后代.现有的交叉算法：如单点交叉、多点交叉、树交叉[6]等,都只能保证求到的后代落在上述的家族中,但其搜索适应值高的后代的能力不强;佳点集法利用求得的子集的均匀散布性,使它们最能代表其“家族”的性能,所以佳点集遗传算法构造的交叉操作提高了搜索适应值高的后代的能力,但佳点集布点有方向性,并且不是统计意义下的抽样,这导致了其整体搜索能力仍不够强.均匀设计抽样就克服了此不足,均匀设计抽样所得的样本具有同佳点集一样的均匀散布性,并且每次取得的样本集是随机均匀散布的,这样可以取到所有的格子点.所以均匀设计抽样遗传算法具有极强的整体搜索能力.实验证明不管在求解精度上还是在求解速度上,均匀设计抽样遗传算法不仅优于GA算法,也优于佳点集遗传算法,并能较好地避免早熟现象,收敛到最优解.

[1] 张铃,张钹.遗传算法机理的研究[J].软件学报,2000,11(7)：945-952.

[2] 张铃,张钹.佳点集遗传算法[J].计算机学报,2001,24(9)：917-922.

[3] 华罗庚,王元.数论在近似分析中的应用[M].北京：科学出版社,1978.

[4] 张润楚,王兆军.均匀设计抽样及其优良性质[J].应用概率统计,1996,12(4)：337-347.

[5] 王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安：西安交通大学出版社,2002.

[6] 吴少岩,张青富,陈火旺.基于家族优生学的进化算法[J].软件学报,1997,8(2)：137-144.

[7] 陈国良,等.遗传算法及其应用[M].北京：人民邮电出版社,1996.

Based on Genetic Algorithm Uniform Design Sampling Solution Knapsack Question

CH EN Ming-hua1, R EN Zhe2, Z HOU Ben-da1
(1.Dept.of Mathematics and Physics,West Anhui University,Lu’an 237012,China;
2.Dept.of Mathematics and Physics,Hefei University,Hefei 230022,China)

It is well known that the GA is a guided random search and the guiding direction always aims at the family whose ancestors have schemata with high fitness.Based on the results,the crossover operation in GA is redesigned by using the principle of uniform design sampling.Then a new Gacalled Genetic Algorithm based on Uniform Design Sampling is presented.The new GA is applied to solve the knapsack question.Compared to simple GA and Good Point GA for solving this problem,the simulation results show that the new GA has superiority in speed,accuracy and overcoming premature.

genetic algorithm(GA);uniform design sampling(UDS);genetic algorithm based on uniform design sampling(UDSGA)

TP301

A

1672-1454(2011)03-0044-06

2008-08-28

安徽省高校省级自然科学研究项目(KJ2007B152);安徽省教育厅自然科学研究项目(2005KJ222, 2006KJ046B);安徽省高校青年教师资助计划项目(2007jq1179)