（应用数学专业论文）利用混合单新遗传算法求解二维装箱问题.pdf

原创性声明一 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文 已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得凼墓直太 堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 学位论文作者签名：蕴皇：! 遁指导教师签名：芝二i 竺 日 期：】翌1 2 ：12 日期：2 立f ! ，：! 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位论文的 全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行 检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作 者在学期间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须 征得内蒙古大学就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公 开发表。 学位论文作者 日 签名：丛指导教师签名： 利用混合单亲遗传算法求解二维装箱问题 摘要 装箱问题是指将一些给定的不同尺寸的物品按照要求摆放入有一定容积的 容器中，以获得某种最佳的效益。装箱问题涉及多学科、多领域的知识，在生 产实践中被广泛的应用。二维装箱问题在现实生活中随处可见，与人们的生产 生活密切相关，找到二维装箱问题的有效算法可以节省资源，提高生产效率， 对人们的生产生活产生重大影响，从而对人类社会产生积极的推动作用。同时 求解二维装箱问题的各种算法也能应用到求解三维装箱问题中，因此研究二维 装箱问题有着重要的理论意义和应用价值。 装箱问题是一个具有复杂约束条件的组合优化问题，在理论上属于 n p _ h a r d 问题。其求解是极为困难的。从2 0 世纪7 0 年代初开始，装箱问题就 引起了人们的关注。到目前为止，世界上研究的比较多的是一维及二维装箱问 题，人们提出了大量的求解装箱问题的算法，其中最主要的算法有启发式算法 和遗传算法。 本文首先对装箱问题的种类及研究现状进行了综述，总结了现有的关于装 箱问题的一些算法，包括启发式算方法和遗传算法。阐述了遗传算法的基本实 现机理，并对单亲遗传算法进行了概述，然后针对二维矩形装箱问题，对现有 的f f a 算法及其改进算法i f f a 进行了分析，并对i f f a 算法进一步加以改进， 提出了一种i f f a 2 算法，在i f f a 2 算法中，考虑了碎片的利用，并通过举例说 明了碎片的产生及表示方法，最后尝试把i f f a 2 算法与单亲遗传算法结合起来 构成混合单亲遗传算法来实现对二维装箱问题的求解，并给出了算法实现的流 i i 程图。在算法中，提出了同时考虑物品装箱顺序及物品放置方向的编码方案， 并设计了新的适应度函数和遗传操作，在解码过程中引入了i f f a 2 算法，使启 发式算法与遗传算法有机的结合在一起。 关键词：二维装箱问题，单亲遗传算法，i f f a 算法，碎片 i i i s o l v i n gt w o d i m e n s i o n a lp a c k i n gp r o b l e m b a s e do nh y b r i dp a r t h e n o g e n e t i c a l g o r i t h m a b s t r a c t p a c l ( i n gp r o b l e mi sg i v e nt os o m eo fm ei t e m si na c c o r d a n c ew i t ht h e r e q u i r e m e n t so f d i f j e i e r e ms i z e sp l a c e di n t oac e r t a i nv o l u m eo fc o n t a i n e rt og e tam e b e s tr e s u l t s p a c k i n gp r o b l e mi n v o l v e sm u l t i - d i s c i p l i n a r y ，m u l t i d o m a i nk n o w l e d g e ， i nm e p r o d u c t i o np r a c t i c ei sw i d e l yu s e d t w o d i m e n s i o n a lp a c k i n gp r o b l e mc a nb e s e e ne v e 呻e r ei nr e a l l i f e ，a n dp e o p l e sp r o d u c t i o na n dl i f ea r ec l o s e l yr e l a t e d f i n da ne 髓c t i v ea l g o r i t h l nf o rt w o d i m e n s i o n a lp a c k i n gp r o b l e mc a ns a v e r e s o u r c e sa n d i m p r o v ep r o d u c t i o ne 伍c i e n c y ， h a v ea s i g n i f i c a n ti m p a c t o n p r o d u c t i o na n dl i v i n go ft h ep e 叩l e ，a n dt h u sh a v eap o s i t i v er o l ei np r o j n o t i n gf o r h u m 锄s o c i e 够a t t h es 锄et i m et w o - d i m e n s i o n a lp a c 虹n gp r o b l e ms o l v i n gc a i la l s o b e 印p l i e dt 0v a r i o u sa l g o r i t h m sf o rs o l v i n gt h r e e d i m e n s i o n a lp a c k i n gp r o b l e m s ， t h es t u d yt 、v o d i m e n s i o n a lp a c k i n gp r o b l e mh a si m p o i r t a n tt 1 1 e o r e t i c a ls i g n i f i c a n c e a n d 印p l i c a t i o nv a l u e p a c h n gp r o b l e mi sac o m p l e xc o m b i n a t i o no fc o n s t r a i n to p t i m i z a t i o np r o b l e m ， i n l e o t l l ep r o b l e mi sn p - h a r d i t ss o l u t i o ni se x t r e m e l yd i 伍c u l t 7 0y e a r s 舶m t h eb e 西n n i n go ft h e2 0 t i lc e n t u r y ，p a c k i n gp r o b l e mh a sa r o u s e dc o n c e m s of 札 m o r es t u d yo fm ew o r l di so n e d i m e n s i o n a la n dt w o - d i m e n s i o n a lp a c k i n g p r o b l e m ， “m a d ean 啪b e ro fa l g o r i t h m sf o rs o l v i n gp a c k i n gp r o b l e m s ，o f 、v h i c hm em o s t i m p o r t a i l ta l g o r i t h m sa r eh e u r i s t i ca r l dg e n e t i ca l g o r i t s f i r s t l y t h e 够p e o fp a c k i n g p r o b l e ma n d t h er e s e a r c hw a sr e v i e w e d ， s u m m 耐z e ds o m eo ft h ee x i s t i n ga l g o r i m m so nt h ep a c k i n gp r o b l e m s ，i n c l u d i n g h e u r i s t i cc a l c u l a t i o nm e t h o d sa n d g e n e t i ca i g o r i t h m s d e s c r i b e st h eb a s i c i m p l e m e n t a t i o nm e c h a n i s mo fg e n e t i ca l g o r i m m s a n dp a r t h e n o g e n e t i ca l g o r i t h m i so u t l i n e d t h e nf o r 也e 觚。一d i m e n s i o n a lr e c t a n g u l a rp a c k i n gp r o b l e m ，t h ee x i s t i n g a l g o r i t h m sf f a a n di t si r n p r o v e da l g o r i t h mi f f aw e r ea n a l y z e d a l g o r i t h mi f f ai s n j r t h e ri n l p r o v e da n dp r 叩o s e dai f f a 2a l g o r i t h m i ni f f a 2a l g o r i t h m ，c o n s i d e r m eu s eo ff 靼皿e n t a t i o n ，a n dd e s c r i b e st h e 仔a g m e n t a t i o na n dr e p r e s e n t a t i o nb y e x 锄p l e f i n a l l y ，时t oi f f a 2c o m b i n e dw i t hp 矾h e n o g e n e t i ca l g o r i t t of o m h y b r i dp a 门c h e n o g e n e t i ca l g o r i t h mt oa c h i e v et 1 1 e “o d i m e n s i o n a lp a c k i n gp r o b l e m t os 0 1 v e a n di m p l e m e n t a t i o no ft h ea l g o r i t h mn o wc h a r t i nt h ea l g o r i t h m ，a n d i m p l e m e n t a t i o no ft h ea l g o r i t h mf l o wc h a r t i nt h ea l g o r i t h m ，p r o p o s e dt a k i n gi n t o a c c o u n tt h eo r d e ro fi t e m sa n d g o o d sp a c k i n g o r i e n t a t i o no ft h ec o d i n gs c h e m e a n d d e s i g n i n gan e wf i t n e s sr m c t i o na n dg e n e t i co p e r a t i o n s i n t r o d u c e di nt h ed e c o d i n g p r o c e s si f f a 2a l g o r i t h m ，t h eh e u r i s t i ca l g o t h ma n dg e n e t i ca l g o r i t h mc o m b i n e d v k e yw o r d s ：铆o - d i m e n s i o n a lp a c 姑n gp r o b l e m ，p a r t h e n o g e n e t i ca l g o r i t l u l l ，i f f a a l g o r i t h m ，厅a g m e n l = a ：t i o n 目录 第一章绪论l 1 1 装箱问题简介1 1 1 1 一维装箱问题1 1 1 2 二维装箱问题2 1 1 3 三维装箱问题2 1 2 装箱问题的研究现状3 1 2 1 装箱问题的启发式算法3 1 2 2 装箱问题的遗传算法9 1 3 选题意义1 2 1 4 本文的内容及文章结构1 2 1 4 1 本文的主要内容1 2 1 4 2 文章结构1 2 1 4 3 本文的创新点1 3 第二章遗传算法的原理和实现1 4 2 1 遗传算法的基本思想瓯伽1 4 2 2 遗传算法的关键参数与操作的设计汹j 1 5 2 2 1 确定问题的编码方案1 5 2 2 2 初始群体的选取与规模1 6 2 2 3 确定适应度函数，1 6 2 2 4 控制参数的选择1 6 2 2 5 遗传操作1 7 2 2 6 算法终止条件2 1 2 3 遗传算法的特点及应用呻一2 2 2 3 1 遗传算法的特点2 2 2 3 2 遗传算法的应用2 3 2 4 标准遗传算法的基本流程h 2 5 i 第三章单亲遗传算法2 6 3 1 单亲遗传算法的提出m 2 6 3 2 单亲遗传算法的描述蜘2 6 3 2 1 单亲遗传算法的编码方式和个体评价2 7 3 2 2 单亲遗传算法的遗传算子2 7 3 3 单亲遗传算法的运行流程阍3 0 第四章基于混合单亲遗传算法的二维装箱问题研究3 2 4 1i f f a 2 算法3 2 4 1 1i f f a 2 算法的提出3 2 4 1 2i f f a 2 算法的数据结构3 3 4 1 3 碎片的产生及表示3 4 4 1 4 算法举例3 7 4 2 基于i f f a 2 算法的混合单亲遗传算法在二维装箱问题中的实现4 0 4 2 1 编码与解码4 0 4 2 2 初始种群的产生4 4 4 2 3 适应度函数4 4 4 2 4 选择算子4 5 4 2 5 变异算子4 6 4 2 6 终止条件4 8 4 2 7 算法流程图4 8 第五章结论5 0 参考文献5 1 致谢5 4 v i i i 第一章绪论 1 1 装箱问题简介 装箱问题是指将一些给定的不同尺寸的物品按照要求摆放入有一定容积的容器中，以 获得某种最佳的效益。装箱问题涉及多学科、多领域的知识，在生产实践中被广泛的应用。 装箱问题是理论计算机科学与组合优化领域的一个重要问题【1 】。随着计算机科学、管理科学 与现代化生产技术等的日益发展，组合优化问题日益增多，越来越受到运筹学、应用数学、 计算机科学与管理科学等诸多学科的重视。装箱问题作为其重要分支在近几十年来得到了 广泛而深入的研究，得到了一些较好的结果，对实际应用有很好的指导意义。 从不同角度可对装箱问题进行不同的分类，目前对装箱问题的研究从装箱物体所属空 间进行分类，可分为一维装箱问题、二维装箱问题及三维装箱问题，具体描述如下： 1 1 1 一维装箱问题 经典的一维装箱问题是这样描述的【2 】：给定刀个物品的序列厶= 口l ，口：，口，口。 ， 物 品q ( 1 f ”) 的大小丑( 0 ，1 】，b 。，b ：，为一个由单位容积的箱子组成的无限序列，我们要求 每一个物品口，只能装入到唯一的箱子里，每一个箱子中的数字和不超过1 ，目的是如何用最 少的单位容积的箱子装下所有的物品。 一维装箱问题是许多具有重要意义的实际优化问题的基础。日常生活中的例子很多。 比如，在建筑中经常需要将一定长度的管材、线卷切割成不同长度；具有相同宽度、不同 长度的材料需要用平板架运送到建筑工地；在金属制造工业中，长度不同的钢片需要从大 块钢片中切除，等等。这些都是具有几何尺寸的典型的一维装箱问题。另外，物体的长度 不定是几何尺寸，比如，电视台要在规定的时间内插播片长不等的广告，在运输工业中， 要把不同重量的货物装入具有一定载重量的卡车中，电子工业中，要将字节数不同的文件 存入存储容量一定的磁盘中，等等。所有这一切问题都可以归结为一维装箱问题【3 j 。 1 1 2 二维装箱问题 在二维装箱问题中，被装箱的对象可以是矩形、梯形、三角形、圆形或者其他一些不 规则图形，其中，研究最为广泛的是二维矩形装箱问题，根据装箱条件的不同，二维矩形 装箱问题可分为以下两类【4 5 】： 1 给定n 个矩形物品集合三= 口l ，口2 ，口。 和一个宽度为有限值w ，高度无限的箱子， 其中第f 个物品的宽度为m ，高度为，f = 1 ，2 ，聆。要求将所有的物品装入箱子中而使所 占箱子高度为最小，在具体填装时，对每个小矩形物品装入后的状态可有直角填装，定向 等限制。 2 给定刀个矩形物品集合三= 口，口2 ，口。 和无穷多个尺寸相同的矩形箱子，其中第f 个 物品的宽度为嵋，高度为魂，f = 1 ，2 ，刀。矩形箱子宽度为，高度为日，要求将所有的 物品装入箱子中而使所用箱子数量最少。 本文所研究的二维装箱问题属于第一种。在具体填装时，对每个小矩形物品装入后的 状态有直角填装限制，即矩形物品的边要与箱子的边平行，另外在填装时可以对每个小矩 形物品进行旋转。 一直以来，二维装箱问题在工业领域有着广泛的应用。装载问题，印刷排版问题，电 路板设计问题，特别是裁剪问题，应用实例很多，如服装裁剪、玻璃和木材的切割等问题 都可归结为二维装箱问题。如果能够找到一种高效的解决办法，就能够相应的节约成本， 提高效益，因此说，这个问题的解决是很有现实意义的。 1 1 3 三维装箱问题 三维装箱问题是一个更为复杂的n p 完全问题。三维装箱问题应用最多的实例就是物流 业中的集装箱装载问题，此外，在飞机装舱，码头装货，列车装箱，以及建筑昂、电子、 纺织业等诸多领域中也有着广泛的应用。与上述二维装箱问题类似，根据装箱条件的不同， 可把三维装箱问题分为以下两类【5 】： 1 给定刀个长方体物品集合三= 口。，口：，口。 和一个宽度为有限值形，高度为有限值 日，深度无限的箱子，其中第f 个物品的长度为，宽度为，高度为吃，f = 1 ，2 ，刀，要 求将所有的长方体物品装入箱子中而使所占箱子深度为最小。 2 2 给定刀个长方体物品集合和无穷多个尺寸相同的长方体箱子，其中第f 个物品的长度 为，宽度为m ，高度为，f = 1 ，2 ，刀。矩形箱子宽度为形，高度为日，深度为d ，要 求将所有的物品装入箱子中而使所用箱子数量最少。 1 2 装箱问题的研究现状 装箱问题是一个具有复杂约束条件的组合优化问题，在理论上属于n p i 删问题【6 】。其 求解是极为困难的。 从2 0 世纪7 0 年代开始，装箱问题就引起了广泛的探讨和研究【7 ，8 1 。然而装箱问题可以 追溯到1 8 3 1 年高斯( g a u s s ) 1 9 】开始研究布局问题，因为装箱问题和布局问题本质上是一样的， 到现在已有百余年的历史，在文献上始见于1 9 3 0 年k a n t o r o v i c h 的俄文文章( 1 9 6 0 年译为英 语刊登在m a i l a g e r n e n ts c i e n c e 【1 0 】上) 。经过几代人的努力，到目前，人们提出了大量的解决 装箱问题的方法。其中常见的主要有启发式算法( 也称近似算法) 和遗传算法等。 1 2 1 装箱问题的启发式算法 启发式算法是和求解的问题及搜索相关的，也就是说，启发式算法是为了提高搜索效 率才提出的。在计算机科学、人工智能、智能工程、运筹学及其它一些工程学科中，我们 经常会遇到启发式算法这个词。在不同学科中，对该词的定义可能不同。 生活经验告诉我们【l l 】，使用“窍门 求解问题，往往能达到事半功倍的目的。这种窍 门来自经验，与求解的问题密切相关，尽管不保证一定奏效，但好的窍门往往一用就灵， 在大多数情况下能很快解决问题。这就是说，对许多任务来说，有可能使用与任务或问题 相关的信息而大大减少搜索的代价，并找到比较满意的解。这种窍门实质上就是启发式方 法。 1 一维装箱问题的启发式算法【1 2 1 3 】 关于一维装箱问题的研究结果是丰富的。直到目前有关文献大约有3 0 0 4 0 0 之多。目 前，一维装箱问题求解算法主要是一些近似算法，如n f ( n e x tf i t ) 近似算法，f f ( f i r s tf i t ) 近 似算法，f f d ( f i r s tf i td e c e 鹊i n g ) 近似算法，( b e s tf i t ) 近似算法，b f d ( b e s tf i td e c e a s i n 曲 近似算法等。 在装箱过程中我们假设物品之间是独立的，根据对装箱物品信息的了解程度的不同， 我们可将装箱算法分为在线( o nl i l l e ) 装箱算法和离线( o f r l i n e ) 装箱算法。 如果某一近似装箱算法依次处理各输入物品，在处理当前物品的时候，不知道任何后 续物品的信息，并立即给出当前物品的装箱方案，则称的这样的近似装箱算法为在线装箱 算法；而首先得到所有物品信息之后，统一处理所有物品装箱方案的近似算法则为离线装 箱算法。 b f 算法是较优的在线算法，b f d 算法是较优的脱线算法，在现实中，这两种算法是经 常采用的算法。b f 算法的大致思想是：把箱子分成空箱和已用箱，对于每一个物品，按照 最优适配算法先在已用箱子中找合适的箱子，如果没有合适箱子，则再在空箱中找，找到 后，修改该箱数据，并把该箱插入到已用箱中，直到装完所有的物品。如果在装箱前将物 品按体积降序排列，即为b f d 算法，b f d 算法在很多情况下可取得很优的结果，甚至最优 解，但在极端的情况下结果却不理想。 2 二维装箱问题的启发式算法 对于二维装箱问题，自从p a u l l 【1 4 】在1 9 5 6 年提出新闻排版问题后，该领域一直是一个 研究的课题。到目前为止，已经出现了很多启发式算法能够在合理的时间内计算出较好的 结果。二维装箱问题的启发式算法一般分为两种：分层算法和不分层算法【1 5 】。 分层算法处理起来比较方便，但面积浪费较大，分层算法一般包括n f d h 算法，f f d h 算 法，b f d h 算法等，在每一个算法中，矩形物品事先已经按高度递减进行了排序，设k 为要放 入的矩形物体，s 为刚建立的层。 5 阳 ， 卜 i 2 n 咖 ( a ) ， 卜 l l l z h 列m h b f d h ( b )( c ) 图1 1 分层装箱算法 f i g1 1h i e 豫r c h i c a lp a c k i n ga l g o r i t h m 4 n e x t _ f i td e c r e a s i n gh e i g h ts 觚e g y 算法( n f d h ) ：如果适合的话，把k 放入s 层的左边，否 则创建一新层，把k 放入新层的最左边，如图1 1 ( a ) ： f i r s t f i td e c r e 2 l s i n gh e i g h ts 位i t e g ) r 算法( f f d h ) ：在所有已创建的层中，找见第一个可以放 入k 的层，如果没有这样的层，则产生一个新层，把k 放入新层的最左边，如图1 1 ； b e s t - f i td e c r e a s i n gh e i g h t s n i a t e g y 算法( b f d h ) ：在所有已创建的层中，找出可以放入k ， 且剩余高度最小的层，如果没有这样的层，则产生一个新层，把k 放入新层的最左边，如图 1 1 ( c ) ； 很明显，以上三种算法很简单，也很容易实现，但是从以上的图中我们可以看出，面积 的浪费较大，效率较低，因此，又有人提出了不分层算法。 不分层算法有b l ( b o 们m - l e 哟算法，b l f ( b o 仕0 m l e f t f i l l ) 算法，b f ( b e s tf i t ) 算法， f f a ( f a l l - f r e e a l g o r i t l l i n ) 算法等等。其中最典型的就是b l 算法和f f a 算法。下面就其中几种算 法作简单概述。 1 ) b l 和f f a 算法 b l 算法是1 9 8 0 年由b a l ( e r 【1 6 】等人提出的，它是一种利用相同的装箱模式来处理每次矩形 放置位置及过程的算法。它的主要思想是：每个物体从容器的右上角开始尽可能向容器底部 滑动，然后尽可能向左滑动。重复这种连续的垂直和水平移动操作直到所有的物体都有一个 固定的位置。例如，设口l ，口：，口，口。为矩形装箱物品的顺序，则利用b l 算法的装箱过程可 以描述如下【1 5 ，1 7 】： ( 1 ) 放置口。到箱子的左下角； ( 2 ) 移动吼，从箱子的右上角开始尽可能快的到达底部，到达底部后尽可能快的到达左 侧。 b l 算法的时间复杂度只有d ( 2 ) ，其中是要装箱的矩形的个数。但这种算法有一些缺 陷： ( 1 ) b l 算法在有些情况下是不合适的，为了阐述方便，这里首先引入了区间的概念，每 装入一个物品时，该物品的上部的面积即可作为一个区间，如图1 2 ，在新的矩形物体装入之 前，共有a 、b 、c 三个区间。如图，在a 区间( 左边物体的上边区间) 和b 区间( 中间物体的 上边区间) 均可放下该物体时，一般选b 区间比较合理，但如果采用b l 算法，则物品将被放 入a 区间。 5 图1 2b l 算法的缺陷图1 3 一个优秀的装箱模式 f i g1 2b la l g o r i t h md e f e c t sf i g1 3a9 0 0 dp a c k i n gm o d e ( 2 ) 有时对于一些优秀的装箱模式，如果采用b l 算法，则该模式不会产生。如图1 3 中所 示，1 ，2 ，3 物品放入后，若采用b l 算法，4 号物品则必须放在1 号物品的上面，显然这是不 合理的。 针对以上问题，有些学者提出了f f a 算法。该算法的步骤如下【1 8 】： ( 1 ) 放置口。到箱子的左下角； ( 2 ) 针对任意的吼，在装箱的时候寻找位置最低的合适区间装入，当存在多个高度相等 的最低合适区间时，选择最左边的区间放入。 这样，在图1 2 中，由于b 区间最低，故将物品放入区间b ，显然，针对此图这是一种较好 的装箱模式。对于图1 3 也是如此。 2 ) i f f a 算法( 改进的f f a 算法) 【1 8 1 9 】 f f a 算法虽然是一种性能较优秀的近似算法，但它仍然有如下的缺点： 对于高度相同的各个方案，算法没有指出该如何选择，我们假设算法默认采用找到的 第一个方案。如图1 4 ( 其中阴影部分为浪费面积，在现实生活中浪费面积就是碎片，很明 显，在高度相同的情况下，碎片面积越小越好) 。 从图中我们可以直观的看出，( b ) 是一个比( a ) 优秀的方案。 6 图1 4 f f a 算法的缺陷 f i g1 4f f aa l g o r i m md e f e c t s 针对上述问题，汤岩掣1 川对f f a 算法进行了如下改进，提出了i f f a 算法： ( 1 ) 从左到右扫描各个区间，对于每个区间均执行以下操作：如果区间的宽度小于物品 的宽度，则依次与右侧区间进行合并，直到合并的区间的宽度大于等于物品的宽度，并取所 合并区间的最大的高度与物品的高度之和为合并后区间的高度，类似的，该区间也依次与左 侧区间进行合并； ( 2 ) 所得到的所有区间组中，寻找高度最小的区间组，如果高度相同，则优先使用浪费面 积最小的方案。 显然，改进后的f f a 算法是较复杂的，在实现是可以对算法进行简化： ( 1 ) 由于高度是首要考虑的问题，所以在合并时，如果当前合并的区间的高度大于已知 方案的高度，则不再考虑此合并方案； ( 2 ) 如果目前合并的方案的高度与已知方案的高度相同，但浪费面积已经超过了已知方 案的浪费面积，则不再考虑此合并方案。 i f f a 算法在实现时，区间的表示是一个重要而且困难的问题。由于频繁的插入和删除， 按照前面的描述，区间有时要向左或向右进行合并，所以这里采用了双向链表的形式来定 义区间，并且按照从左到右的顺序将区间连接在一起： 定义区间结点： p o i n t l = a r e a ： a r e a2r e c o r d w i d t h ：i n t e g e r ：区间的宽度 7 h e i g h t l o w e s t ：i n t e g e r ：区间的最低的高度 n e x t ：p o i n t l ： 向前的指针 p r i o r ：p o i n t l ： 向后的指针 e n d ： 定义物品结点： p o i n t 2 = o b j e c t ： o b j e c t = r e c o r d w i d t h _ 0 b j e c t ：i n t e g e r ： 物品的宽度 h e i g h t o b j e c t ：i n t e g e r ： 物品的高度 n e x t ：p o i n t 2 ： 向前的指针 e n d ： 3 三维装箱问题的启发式算法 三维装箱问题由于其复杂性和难度大，因此研究相对较少，且各种算法都是基于一定的 假设基础之上的，这些研究大都没有给出能够实际应用的具体算法，理论贡献也不多。而且 主要是基于空间分解和层的思想。下面从实用角度介绍几种三维装箱算法【l l 】。 l i 和c h e n g 【2 0 】在1 9 9 0 年提出了多项式近似算法c l ，其渐进性能比尺( q ) = 2 6 8 7 5 。沈灏口1 1 根据算法c 。的思想，进一步利用盒子底部为正方形的特点，提出了所谓“单元装箱法”，使 新算法的渐进性能比得到改进：尺( d ) 2 3 2 0 1 5 。 杨传民【2 2 】等人通过全面枚举搜索方法来研究相同大小的立方体的装箱优化问题。 m a n n c h e n s 瞄1 设计的树搜索算法，理论上对三维箱体布局有效，但由于三维箱体布局属于n p 完全问题，随着布局箱体的增多，解空间急剧膨胀，因而计算效率较低。h g e h r i n g 【2 4 1 提出按 阶段填充，在深度方向按层布局的启发式算法，不仅考虑了空间利用率，而且还考虑了重心 平衡。王金敏2 5 1 在其基于约束的布局求解理论与方法的研究中对三维布局问题中的底盘装载 问题、约束底盘装载问题给出了启发式求解方法，研究了布局物体的定序方法、定位方法， 以及布局问题中的装卸问题。何大勇，鄂明成口6 】等则在集装箱布局问题中提出了一种利用三 叉树结构表达三维矩形物体布局状态空间的方法，将布局空间依次分解，定位规则与定序规 则并用，给出了由计算机随机产生的3 0 个长方体的布局结果，得出了集装箱的利用率随原始 布局长方体的体积与集装箱的体积的比值的变化趋势的实验曲线。 8 1 2 2 装箱问题的遗传算法 除了启发式算法，近来解决装箱问题研究较多的是遗传算法。早在1 9 8 4 年就有学者将 遗传算法应用于求解装箱问题中【1 2 1 。但是对于装箱问题这类离散的组合最优化问题，往往 无法直接采用简单遗传算法进行求解。一般来说，遗传算法对解的编码方案大多采用二进 制编码方式，但是对于装箱这类排序问题显然是不合适的，物品的坐标用二进制表示编码 太长，会导致搜索空间急剧增大，算法性能降低，并且经典的交叉变异操作常会产生无意 义的解。因此，必须对简单的遗传算法进行适当的改进以适应装箱问题的特殊情况。此外， 为了提高遗传算法的收敛性和性能，常常将其与其他一些启发式搜索算法相结合形成混合 遗传算法来对装箱问题进行求解。一些学者对此进行了研究并取得了一定成果。 1 9 9 5 年，g e r 【2 7 】提出了利用遗传算法来求解二维装箱问题。由于存在大量的装箱模 式，为了简化问题，有效地减少可能的装箱模式的数量，1 9 9 6 年j a k o b s 【2 8 】提出了以装箱顺 序为编码，采用b l 算法进行解码的新思路，并给出了g a 与b l 结合的算法流程，这样当 一个装箱顺序确定后，一种装箱模式也就确定了，那么它的适应度函数值也就确定了，这 样就很大程度的简化了问题。但由于b l 算法的一些缺陷，h w a n gs l l i a l l m i i n 【2 9 】等人提出了 采用f f a 算法替换b l 算法的混合遗传算法，并通过数据模拟详细说明了该算法相对于 j a k o b s 算法的优越性。 在国内，1 9 9 8 年西北工业大学的李娟和南昌航空工业学院的方平【3 0 1 提出了两种求解装 箱问题的遗传算法。一种是简单遗传算法，它采用等长度字符代码编码方法，使用常规的 遗传操作算子。另一种是混合遗传算法，它综合运用解装箱问题的f f d 近似算法和简单遗 传算法。 2 0 0 0 年，中国科学技术大学的曹先彬【3 1 】等提出了用免疫遗传算法来研究装箱问题。免 疫遗传算法是在传统遗传算法的全局随机搜索基础上，借鉴生物免疫机制中抗体的多样性 保持策略，大大提高了算法的群体多样性。 2 0 0 4 年大连海事大学的汤岩【3 2 】等提出了混合遗传算法在装箱问题中的应用研究，文中 针对装箱问题，提出了b f ( b e s tf i t ) 算法与遗传算法相结合的混合遗传算法，并在实现上 进行了改进。 2 0 0 6 年2 月合肥工业大学的程浩【3 3 】等提出了一种用遗传算法求解一维装箱问题的新编 码方法：把所有要装箱的物品按顺序编号，随机排成一个序列，从而组成一个染色体。染 色体长度为要装箱的物品的个数。装箱时依次从每个染色体中按顺序取出每个基因( 即物 9 品) 放入一个箱子中，如果该箱子满了，则放入下一个箱子中，直到所有物品放完为止。 并且该文中采用了单亲遗传算法实现了装箱问题的求解。 2 0 0 6 年9 月大连海事大学的汤岩【1 9 1 等对f f a 算法加以改进，提出了i f f a 算法，并提 出了i f f a 近似算法和遗传算法相结合的混合遗传算法。该文中染色体编码是由装箱物品的 序号组成，每一个编码代表各个矩形物品的装箱顺序。以装载率作为适应度函数：m a x h e i 曲t 一| l ，其中m a x h e i 曲t 为一个较大的常数，办为某一方案装箱后的高度。选择染色体时，为 了提高效率采用了折半查找的方法，确保了该过程的时间复杂度为d ( 1 0 9 ，z ) 8 。交叉时采用 了陈国良教授提出的一种交叉方法瞰】，例如，对于两个染色体： a _ 1 2 3 4 5 6 1 7 8 9 ，b _ - 9 8 1 7 6 5 4 1 3 2 1 ，把b 的交配区域加到a 前面，a 的交配区域加到b 前面， 产生a l 一7 6 5 41 2 3 4 5 6 7 8 9 ，b 1 3 4 5 69 8 7 6 5 4 3 2 1 ，然后在a 1 、b 1 中自交配区域后依次删除 与交配区相同的项，得到a 2 7 6 5 4 i1 2 3 8 9 ，b 2 3 4 5 6 1 9 8 7 2 1 ；变异时随机在一个染色体中 取出两位进行交换。 2 0 0 7 年5 月厦门大学的陈胜达【2 】提出了基于遗传和递归的混合遗传算法来求解二维装 箱问题，其中对张德富【3 5 】老师提出的启发式递归算法h r 作了简要介绍，并在此基础上提 出了两种改进算法i h r 算法和o i h r 算法，给出了改进的遗传算法，分别利用h r 算法、 i h r 算法和o i h r 算法计算适应度值来实现混合遗传算法。文中仍以物品的装箱顺序为编 码，适应度值就是装箱的目标函数值，即为装箱后的高度，为了获得一个初始种群，该文 中首先利用排序后的顺序编码作为一个初始染色体，然后把该染色体基因分成相等的两部 分，并各自对这两部分基因作序列改变，即在两个基因段中分别随机产生两个基因位，然 后各自和相邻的基因进行交换，用此方法来获得另外一1 个染色体( 是种群的数量) 。 选择算子是采用比较父代和中间子代，如果中间子代的适应度值大于父代，则直接接受它 为新的子代，否则按概率忍接受它或以概率卜只接受父代作为新的子代。交叉时，在一个 种群中随机选择两个父个体p a r e n t l 及p a r e n t 2 ，个体c h i l d l 的元素分别从p a r e n t l 和 p a r e n t 2 中交替取得。即如果c h i l d l 的基因位是奇数，就按顺序在p a r e n t l 中找一个项， 直到这个项不同于c h i l d l 中所有的项，否则，就按顺序在p 8 r e n t l 中找一个项，直到这个 项不同于c h i l d l 中所有的项。当c h i l d l 的个数为即时，就成功的产生了一个个体。采用了 逆序变异算子。 2 0 0 8 年1 月南昌大学的李捷【3 6 】分析了矩形物品给定排放顺序的排放算法，提出了最低 水平线旋转搜索法，并针对遗传算法和蚂蚁算法在矩形件布局问题中的实际特点，将这种 1 0 算法和遗传算法以及遗传蚁群算法相结合应用于矩形装箱问题的求解。在文中采用了整数 顺序编码方式，先将要装箱的物品统一进行编号，矩形的编号可以为正也可以为负，文中 规定，矩形的编号为正表示矩形横排，矩形的编号为负表示矩形竖排，一个矩形的编号对 应一个基因的编码，例如，染色体( 一2 ，1 ，5 ，一3 ，4 ) 表示装箱顺序为2 1 5 3 4 ，其中2 号 和3 号物品要竖排，其余的横排。适应度函数为f _ a r e a o a r e a ，其中a r e a o 为要排放的矩 形件的总面积，a r e a 为所生成的排样图最大高度以下的箱体面积。选择时采用了轮盘赌法 和最优保存策略。在交叉时，先选一个固定的交叉位置，在该点之前的基因不变，在该点 以后的基因部分进行交叉。将两条染色体的不交叉的基因部分进行比较，在去掉两个基因 片断中相同的基因后，将染色体不交叉部分按原来的顺序分别放入两个数组p 口和q 中。 在对染色体的交叉部分的基因片段进行操作时，对不等于数组p 或q 口中的基因直接进行 交换，对于与数组中的基因相同的基因，则先换成对应的数组p 或q 中的基因后再进行 交换。变异时产生 1 ，4 之间的随机整数r a n d n u m b e r ，若r a n d n u m b e r = 1 ，则进行交换变异； 若r a n d n u m b e r = 2 ，则进行反转变异；若r a n d n u m b e r = 3 ，则进行插入变异；若r a n d n u m b e r = 4 ， 则进行位置变异。 2 0 0 8 年7 月华南理工大学的蒋金山【3 7 】等提出了用自适应遗传算法求解二维装箱问题， 算法模拟生物面对恶劣环境时行为，构造了两个函数，使得交叉率与变异率具有自适应性， 克服