求解装箱问题的一种变长度染色体遗传算法

长春工程学院学报(自然科学版)2004年第5卷第2期J.ChangchunInst.Tech.(Nat.Sci.Edi.),2004,Vol.5,No.2CN　　　　　　　　　　　　　　　　　　　　　　　　　2221323/N

17/23

　　　　53　　　255

求解装箱问题的一种变长度染色体遗传算法

杨殿生

(鄂州大学,湖北鄂州436000)

摘　要:针对装箱问题提出了一种变长度染色体的

改进遗传算法,并分析了其实现的具体方法和实现步骤。

关键词:装箱问题;遗传算法;中图分类号:O22文章编号(00532,他们基本,(next-fitheuristic)、(first-fitheuristic)或最佳配合启发式方法(best-fitheuristic)等,但这些启发式算法都不能实现全局最优,只能找到局部最优解。

1　装箱问题及数学模型

装箱问题(bin-packingproblem)就是要将重量分别为w1,w2…,wn的n个物品装入许多个箱子(最多n个),且箱子有重量限制,每个箱子所装物品的总重量不超过C(C>0)。问题是寻找最优的将物品分配到箱子的方案,使每个箱子中物品的重量之和不超过其限制,而使用的箱子数量最少。

装箱问题的数学模型如下:

n

2　遗传算法求解装箱问题

遗传算法是一种模仿生物界自然选择原理和自然遗传机制的随机搜索寻优算法,在运行过程中,遗传算法不对所求解的实际决策变量直接进行操作,而是对表示可行解的个体编码施加选择、交叉、变异等遗传操作,通过这种遗传操作来达到优化的目的。

与传统的启发式算法相比,遗传算法的主要本质特征在于群体搜索策略和简单的遗传算子,群体搜索使遗传算法突破领域搜索的限制,可以实现整个解空间上的分布式信息搜索、采集和继承;遗传算子仅仅利用适应值度量作为运算指标进行染色体的随机操作,降低了一般启发式算法在搜索过程中对人机交互的依赖,这样就使得遗传算法获得了强大的全局最优解搜索能力,问题域的独立性、信息处理的隐并行性、应用的鲁棒性、操作的简明性,成为一种具有良好普适性和可规模化的优化方法。

基于遗传算法的装箱问题求解过程主要包括染色体编码结构及各种遗传算子的设计。2.1　适应值函数

minZ(y)=

n

i=1

∑y

i

s.t.

n

j=1

∑Wx

jij

≤Cyi,i∈N

i=1

∑x

ij

=1,j∈N

yi=0或1,i∈Nxij=0或1,i,j∈N

其中,yi=1表示箱子i中被装入物品,反之yi

=0表示箱子空着。

xij=1表示物品j装入箱子i中,反之xij=0表

示物品未装入箱子i中。

装箱问题是许多具有重要意义的实际优化问题的基础,在管理决策中有重要应用,它属于NP-hard问题,目前还没有在多项式时间内求得最优解的算法。

收稿日期:2004-04-01

作者简介:杨殿生(1963,8-),男(汉),安徽明光,讲师

主要研究工程数学,(0711)3853327。

确定适应值函数的原则是:最小化使用的箱子数量同时,尽量装满所有使用的箱子。具体函数如下:

n∑(F/C)

i

fBPP=

N

式中:N———解中使用的箱子数量;

Fi———i个箱子中所有物品的重量之和,即箱

子的填充程度;

54长春工程学院学报(自然科学版)2004,5(2)

C———箱子的重量限制,k是常数(k>0)表

示对装满箱子的重视程度,k越大,装

得满的箱子比一般填充的箱子受到的重视就越大,这里取k=2。

2.2　染色体编码设计

在遗传算法中如何描述问题的可行解,即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转化方法,就称为编码。

由于装箱问题的适应值函数依赖于箱子中物体的群体,因此此问题中好的编码应该包含2个部分:一部分提供关于哪个物品属于哪个箱子(群体)的信息,另一部分对使用的箱子编码。

基于此考虑,中各基因座位置(表示箱子)(的物品),排列起来,。

举例说,6对物品进行编码,染色体物品部分可写成142352,这表示:第1个物品放入箱子1,第2个物品放入箱子4,第3个和第6个物品放入箱子2,第4个物品放入箱子3,第5个物品放入箱子5;而染色体的群体部分仅表示箱子,用字母来表示箱子(这样,上面染色体就可以表示为ADBCEB)。

通过查询物品部分,可以清楚群体名称所代表的含义,即:

B={3,6},E={5},C={4},D={2},A={1}

因此,包括2个部分的染色体的集成可由下图来表示:

作称为选择,其目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体遗传到下一代,它是建立在群体中个体的适应值评估基础上的。

这里采用联赛选择算子。其基本方法是,从群体中随机选择k个个体,其中适应值最高的个体保存到下一代,这一过程反复执行,直到保存到下一代的个体数达到预先设定的数目为止。其中,参数k称为竞赛规模,常取k=2。2.3.2　交叉算子

,把,,是产生新。

由于染色体编码包含2部分:箱子和物品的群体,因此交叉需处理可变长度的染色体,具体步骤如下:

第1步:随机选择2个交叉位置,对每个父代选定交叉部分。

第2步:将第1个父代交叉部分的内容插入到第2个父代第1个交叉位置之前。由于交叉对染色体的部分群体进行操作,这就意味着从第1个父代插入一些群体

(箱子)到第2个父代中。

第3步:从产生的后代中原有的箱子中去掉所有重复出现的物品,使得这些物品原先的从属关系让位于“新”插入的箱子。

因此产生的后代中的某些群体发生了改变,他们不再包含与原先相同的物品。

第4步:如果必要,根据问题和适应值函数来调整新产生的箱子。在此步骤,可采用如FFD等局部搜索算法。

第5步:改变2个父代的角色并重新应用第2步到第4步生成第2个子代。

示例如下:

图1　染色体集成图

这种表示的原理是:对于装箱问题来说,群体是有意义的积木块,也就是最小的解片断,这些片断可以按照对其所属的解所期望的质量来转运信息。

而这种表示的关键之处就是遗传算子对于染色体的群体部分进行操作,其物品部分仅用于判定由哪些物品形成该群体。2.3　遗传操作设计

遗传操作包括以下3个基本遗传算子:选择、交叉、变异。选择和交叉基本完成了遗传算法的大部分搜索功能,变异增加了遗传算法找到接近最优解的能力。

2.3.1　选择算子

从群体中选择优胜的个体,淘汰劣质个体的操

2.3.3　变异算子

杨殿生:求解装箱问题的一种变长度染色体遗传算法55

所谓变异运算,就是将个体染色体编码中的某些基因座上的基因值用该基因座的其他等位基因来替换,从而形成一个新个体。

与前类似,装箱问题的变异算子必须针对群体(箱子)而不是物品进行操作,至于变异过程,算子的实现细节依赖于现有的特定群体问题,但可指出两条一般性策略:或启用一个新的箱子,或消除一个已经使用的箱子。如果变异后解中缺少某些物品,可以采用FF或FFD启发算法来按照随机的顺序将其重新放入箱子。

从遗传算法过程中产生新个体的能力方面来说,交叉运算是产生新个体的主要方法,它决定遗传算法的全局搜索能力,的辅助方法,,,局部搜索,成最优化问题的寻优过程。2.4　基于遗传算法的装箱问题算法描述

基于遗传算法的装箱问题算法描述如下:第1步:配合启发式算法产生初始群体。第2步:染色体基因的个体适应值计算。

第3步:利用遗传操作进行群体更新,形成新一代群体。

第4步:停止准则。如算法找到一个能接受的解,或已迭代了预置的代数,则停止;否则,转第3步,循环执行染色体基因适应值计算、群体更新等步骤,直到满足停止准则为止。

以进化思想为基础的全新的一般方法论,是解决优化等复杂问题的有利工具。随着遗传算法理论研究的不断深入,其自身的发展将得到进一步完善,它的应用范围将得到进一步扩大。参考文献

[1]　FalkenauerE.Anewrepresentationandoperatorsforgenetic

algorithmsappliedtogroupingproblems[J].EvolutionaryComputation,1994,2(02).

[2]　陈国良.北京:人民邮电出版

社[3][M].北京:科学

[4[M].北京:清华大学出版社,

1996.

Theinheritancealgorithmofa

kindofchromosomeswithchangeablelength

tosolvethebin2packingproblem

YANGDian2sheng

(OfficeofTheDeanofStudies,EzhouUniversity,Ezhou436000,China)

Abstract:Tosolvethebin2packingproblem,thispaperpresentedanimprovedinheritancealgorithmofakindofchromosomeswithchangeablelengthandanalyzedtheconcretemethodsandstepstorealizeit.

Keywords:bin2packingproblem;inheritancealgorithm;

heuristicalgorithm

3　结论

遗传算法不是一种单纯的优化算法,而是一种

本文来源：https://www.bwwdw.com/article/u7qj.html