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

长春工程学院学报(自然科学版)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个箱子中所有物品的重量之和,即箱

子的填充程度;

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新工程科技求解装箱问题的一种变长度染色体遗传算法全文阅读和word下载服务。