文化基因算法在多约束背包问题中的应用

第26卷第4期2007年12月

计 算 技 术 与 自 动 化ComputingTechnologyandAutomation

Vol 26,No 4 Dec.2007

文章编号:1003-6199(2007)04-0061-03

文化基因算法在多约束背包问题中的应用

刘漫丹

(华东理工大学信息学院,上海 200237)

摘 要:文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题。文

化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题。通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能。

关键词:文化基因算法;背包问题;遗传算法中图分类号:TP301 文献标识码:A

AMemeticAlgorithmfortheMultidimensionalKnapsackProblems

LIUMan dan

(CollegeofInformationScienceandTechnology,EastChinaUniversityofScienceandTechnology,Shanghai 200237,China)

Abstract:Memeticalgorithmisoneofheuristicalgorithms,itismoreappropriateformultidimensionalknapsackproblems

thansomeclassicalmathematicalmethods.Itisacombinationofglobalsearchbasedonpopulationsandlocalsearchbasedonindi viduals.Tothemultidimensionalproblems,oneapproachisproposedusinggreedystrategybysortingthedegreeofcontravention,geneticalgorithmisusedforglobalsearchandsimulatedannealingisusedforlocalsearch.Theresultofsolvingmultidimensional0-1knapsackproblemsbymemeticalgorithmindicatesthatmemeticalgorithmcanobtainbettersearchperformancethannormalgeneticalgorithm.

Keywords:memeticalgorithm;knapsackproblems;geneticalgorithm

性的增加,越来越多的人采用启发式算法解决背包

1 引 言

背包问题是典型的组合优化问题,同时也是一个典型的NP完全问题。背包问题是指从若干件物品中选择部分物品,放入有一定承重限制的背

包,应如何选择物品使得装入背包中的物品价值最大。各国研究者们一直在研究如何更好地求解背包问题,因为背包问题是从很多实际应用问题,诸如资源分配、投资决策、货物装载等抽象出的数学模型。简单的背包问题可以用动态规划法、回溯法、分支界定法、贪心法等方法求解,随着问题复杂

问题,如禁忌搜索、模拟退火算法、遗传算法、蚁群

算法、粒子群算法等。

2 多约束背包问题

多约束背包问题是简单背包问题的扩展,可如下描述:

有n种物品,各物品的价值为ci(i=1,2, ,n),现有一个背包,该背包有m个约束条件,如容量限制、重量限制、数量限制等,各约束条件的最大提供量为bj(j=1,2, ,m),第i种物品针对第j

收稿日期:2007-08-29

作者简介:刘漫丹(1973 ),女,内蒙古锡盟人,副研究员,博士,研究方向:智能优化计算、模式识别(E-mail:liumandan@ecust.edu.

cn)。

62

计算技术与自动化2007年12月

个约束的量(容量、重量、数量等)为aij(i=1,2, ,n,j=1,2, ,m),希望将若干物资放入背包,在满足所有约束的条件下,使背包中的物品价值和达到最大。

该问题的模型可表示为:m xs.t.

i=1n

4 1 解的表达形式

根据0-1背包问题的特点,将解直接表示为二进制字符串,这样的形式既能够合理表达背包问

题的解,又利于遗传算子的操作。4 2 多约束条件的处理

由于多约束条件的限制,使得上述形式表达的解并非完全是可行解,必须进行进一步的约束,使得不可行解变为可行解。

一些文献[3,4]中使用贪婪策略解决了简单背包问题的解的可行性问题,对于多约束背包问题,本文提出通过约束违反度排序的方法使得解在尽量使价值最大化情况下满足所有的约束条件。

记pijci/ ij(i=1,2, ,n,j=1,2, ,m),对每一个约束条件j,将所有物品的pij从大到小进行排序:pkjj(p

1

!cixi! ijxi

bj

n

i=1

xi#{0,1},i=1,2, ,n,j=1,2, ,m其中,xi=0表示第i种物品未被装入背包,xi=1表示第i种物品被装入背包。因此,该问题被称为多约束0-1背包问题。

3 文化基因算法

牛津大学的道金斯因著作 自私的基因%(TheSelfishGene,1976)

[1]

j

k2j

( (pkjj,其中,kj1,kj2,

n

,kjn表示针对约束j,n个物品的排序号。

计算每个约束条件的违反度:qj=(

i=1

而名噪一时,在这本书中,道

! ijxi-

n

金斯提出了一个全新的概念--Meme,它是一个与Gene相对应的单词,代表一个文化传播或模仿单位。PabloMoscato于1989年首次提出memeticalgorithm的概念[2]。Memetic一词由meme而来,根据道金斯提出的本意,应理解为&文化基因 ,因此我们将Memeticalgorithm称为文化基因算法。

文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,这样的结合机制使其搜索效率在某些问题领域比传统遗传算法快几个数量级,可应用于广泛的问题领域并得到满意的结果。很多人将文化基因算法看作混合遗传算法、遗传局部搜索或是拉马克式进化算法,实际上,文化基因算法提出的是一种框架、是一个概念,在这个框架下,采用不同的搜索策略可以构成不同的文化基因算法,如全局搜索策略可以采用遗传算法、进化策略、进化规划等,局部搜索策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式局部搜索等。

bj)/bj,(j=1,2, ,m)。将m个约束条件按照违反度从小到大进行排序,先对违反度小的约束条件

进行处理,后对违反度大的约束条件进行处理。处理的方法如下:对于第j个约束条件,判断

k

j

l

i=1

! ijxi(1

l n)是否小于bj:若是,则置l=

l

l+1

l+1;若否,则置xkj=xkj4 3 适应度函数

= =xkj=0。

n

由于采用贪婪策略保证了解的可行性,每个个体的适应度函数可直接表达为f=4 4 遗传算子

选择策略采用轮盘赌的方法,同时采用精英保留策略,将当前最优个体直接保留到新种群中。

交叉算子采用单点交叉的方法,随机选择一个交叉位对两个父个体的字符串进行交换。

变异算子采用单点变异的方法,随机选择一个变异位,对该位进行0和1之间的变异。4 5 局部搜索

文化基因算法的局部搜索可以采用多种策略,本文采用模拟退火的方法,对遗传操作后的个体进行局部范围内的优化,这相当于在不同区域内选出优秀代表,这些优秀代表再进一步在全局范围内被选择并进行遗传操作。

考虑到运算速度和运算量,模拟退火可以采用i=1

!cixi。

n

4 基于文化基因算法的多约束背包问题求解

本文采用文化基因算法解决多约束背包问题,其中全局搜索采用遗传算法,局部搜索采用模拟退火策略,为了保证解的可行性,采用贪婪策略对多约束条件进行处理。

退火算法实现局部搜索的步骤如下:

STEP1 给定一个初始温度,将种群中的个体作为模拟退火算法的初始状态;

STEP2 产生新的状态,邻域函数定义为对换两物品的取舍状态;

STEP3 计算新老状态的能量函数,能量函数定义为适应度函数的倒数;

STEP4 按照Metropolis准则接受新状态;STEP5 是否满足抽样稳定准则? …… 此处隐藏：5387字，全部文档内容请下载后查看。喜欢就下载吧 ……