资源描述：
《求解装箱问题的遗传算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、南昌航空工业学院学报1998年第2期JournalofNanchangInstituteofAeronauticalTechnology№21998求解装箱问题的遗传算法方平李娟(南昌航空工业学院)(西北工业大学)摘要:本文提出了两种求解装箱问题(BinPacking)的遗传算法。一种是简单遗传算法,它采用等长度字符代码编码方法,使用常规的遗传操作算子。另一种是混合遗传算法,它综合运用解装箱问题的FFD(FirstFitDe2creasing)近似算法和简单遗传算法。试算结果表明,由这两种遗传算法所得到的装箱方案较一些近似算法所得到的装箱方案都要
2、好。关键词:遗传算法;装箱问题;组合;优化中图分类号:TP30116前言管理工程、工业工程等领域中的一些问题(例如人力资源分配、运输计划等)均可建议为装箱(BinPacking),对其求解方法的研究具有一定的应用价值。装箱问题的一般提法如下所述:设有n个物品u1,u2,⋯,un要装箱发送,已知每个物品的体积为v(ui)∈(0,1],(i=1,2,⋯,n)现规定每个箱子的容量为1,问如何确定装箱方案可使得装完这n个物品所需要用的箱子数目为最小?从计算复杂性理论来讲,装箱问题是一个NP难题,很难精确求解。目前的求解方法主要是一些近似算法,如NF(Ne
3、xtFit)近似算法、FF(FirstFit)近似算法、FFD(FirstFitDecreas2[1]ing)近似算法等。近似算法的求解结果与物品的体积数据有较大关系,有时在极端情况下的求解结果很不理想。本文分别用二种遗传算法对该问题进行了求解,一种是用简单遗传算法,另一种是用由简单遗传算法和FFD近似算法组成的混合遗传算法。1求解装箱问题的简单遗传算法111染色体编码方法假设k个箱子的编号分别为B1,B2,⋯,Bk,(K≤n)。n件物品要装入这k个箱子中,要说明的是,有时几件物品可以装入同一个箱子中,所以不一定要全部用完这k个箱子。各个物品ui
4、(i=1,2,⋯,n)所装入箱子之编号的顺序排列就构成该问题的染色体编码,即我们使用的收稿日期:1988-04-10第一作者:方平,男,1962年出生,讲师21是等长度的字符代码编码方法。例如:B3B1B8B1⋯⋯⋯⋯⋯⋯B3B1n就代表一个装箱方案(群体中的一个个体),表示将第1、n-1件物品装入B3箱;第2、4、n件物品装入B1箱;第3件物品装入B8箱,等等。初始种群可以由B1,B2,⋯,Bk的随机排列产生。由个体的染色体编码串可统计出某一装箱方案用了几只箱子。112目标函数和适应函数设m为某一装箱方案中所用箱子的数目,B(ui)为物品ui所
5、装入箱子的编号,Sj为考虑了罚函数之后的Bj箱所装物品的体积之和。要使所用箱子数目最少,可以取下式为优化目标函数:mmf(X)=mõ(m-∑sj)=mõ{m-∑[∑v(ui)-Aõmax(0,∑v(ui)-1)]}j=1j=1B(u)=BB(u)=Bijij式中A为某一箱子Bj中所装物品的体积之和超出箱子规定容积时的惩罚因子。该目标函数既考虑了使用箱子的数目最小,又考虑了使每个箱子装完物品后所剩余的容积尽可能的小。适应函数取为下式:Cmax-f(X),f(X)6、总取非负值。113遗传算子的选用[2]可使用通过的一些遗传操作算子,如交叉操作使用单点交叉算子或双叉算子;变异操作使用字符集范围内均匀变异算子;选择操作使用比例选择算子。2求解装箱问题的混合遗传算法上述解装箱问题的简单遗传算法的缺点是,初始种群和进化过程中可能会产生一些无效染色体,这些无效染色体所表示的装箱方案中,某一箱子所装物品的体积之和超过箱子的规定容量,从而使得运算效率降低,也会导致得不到好的运算结果。这里我们将求解装箱问题的FFD近似算法与简单遗传算法相结合,构成一种混合遗传算法,使得进化过程能够借鉴FFD近似算法的思想,修正无效染色体为
7、合理的染色体,从而提高遗传算法的运行效率和解的质量。FFD近似算法的主要思想是:将物品按体积大小降序排列,然后依该秩序来对各个物品装箱;对某一物品,它总是装到第一个能装下它的箱子中。将上述思想应用到遗传算法的解码过程中。这个具有FFD思想的解码过程的主要步骤可描述如下:(1)将物品按体积大小降序排列。(2)依上秩序处理各个箱子中的所有物品。若箱子Bi中所装物品的体积之和超出限制,则将超出部分装到Bi+1箱子中。22(3)若Bm箱中所装物品的体积之和已超出其规定的容量,则取一只新的箱子装入超出部分的物品,且m←m+1。对染色体编码串使用上述解码过程
8、之后,所表示的装箱方案既符合FFD近似算法的思想,同时各个箱子所装物品的体积之和也不会超过其规定的容积。这样,计算目标函数时,无需再引入
