（计算机应用技术专业论文）基于遗传和递归的装箱算法研究.pdf

摘要 摘要 装箱问题就是将不同尺寸的物品摆放入有一定容量的容器中，以获得某种最 佳的效益。装箱问题广泛地用于机械生产和交通运输等行业当中。对该问题求解 方法的研究无论是在理论上，还是在实践中都具有一定的意义。装箱问题属于组 合最优化问题和n p 完全问题，具有高度复杂性，用一般的数学方法很难求解， 目前研究得最多的是用启发式方法解决装箱问题。 本文为求解二维装箱问题提出了g a + h r 、g a + i h r 和g a + o i h r 三个算法。 这三个算法是在已提出的h r 算法的基础上改进的。g a + h r 算法是h r 算法结合遗 传算法的全局搜索能力，通过遗传算法搜索到更优的排列顺序，使得解的效果进 一步提高。g a + i h r 算法中，定义了参考矩形和结合层的概念，通过找出所有结 合层，然后计算每个结合层数所产生的解，最后从这些解中找出最优的解和最佳 结合层数。g a + o i h r 算法中，在h r 算法中加入了穷举的思想，即对每一层的 第一块矩形的放置都考虑水平放置和垂直放置两种情况，然后分别计算出这两种 放置方式所带来的空间利用率。采用利用率比较大的方式作为该层的放置方式。 而且在每一层子空间采用h r 递归算法时，先搜索那些长或宽要么和子空间的高 度相同要么和子空间的宽度相同的矩形，先把这些矩形放置好，这样放置后该子 空间还是只被划分成一个更小的子空间，可以减少子空间的个数。从而减少因为 不断递归划分成两个子空间，使得一些小空间因为再也放置不下任何一块矩形而 造成的浪费。 在本文中我们还把计算二维装箱问题的h r 算法和g a + h r 算法运用到三维 装箱问题中。计算结果显示h r 算法运行时间短，但所带来的空间利用率并不理 想；g a + h r 算法运行时间较长，但有较高的空间利用率。特别地，6 + h r 算法 的平均结果比著名的b i s c h o f f 算法要好。 关键词：遗传算法；装箱问题；启发式算法 a b s t r a c t t h eb i np a c k i n gp r o b l e mi st op u ts o m eo b j e c t sw i t hv a r i o u ss i z e si n t oad e f i n e d s p a c ei no r d e rt oo b t a i nt h es p e c i f i e do p t i m a lb e n e f i t b i np a c k i n gi sac o m b i n a t o r i a l o p t i m i z a t i o n a n dn p - c o m p l e t ep r o b l e ma n dw i d e l ya p p l i e dt ot h em e c h a n i c a l m a n u f a c t u r ea n dt r a f f i ct r a n s p o r t a t i o ni n d u s t r i e s t h es t u d yo fa l g o r i t h mf o rb i n p a c k i n gp r o b l e mi so fg r e a ts i g n i f i c a n c en o to n l yi nt h e o r yb u ta l s oi np r a c t i c e u pt o n o w , t h eh e u r i s t i ca l g o r i t h mi so n eo ft h em o s te f f i c i e n ta l g o r i t h m sf o rt h ep a c k i n g p r o b l e mb e c a u s et h ep r o b l e mi so fh i g hc o m p l e x i t y i nt h i sp a p e r , w ep r o p o s eg a + h r a l g o r i t h m , g a + i h ra l g o r i t h ma n dg a + o i h r a l g o f i t h r af o r2 d - p a c k i n gp r o b l e m t h e ya l eb a s e do nt h eh e u r i s t i cr e c u r s i v e a l g o r i t h m ( 卸r ) g a + h ra l g o r i t h mi st oc o m b i n eg e n e t i ca l g o r i t h mw i t hg l o b a l s e a r c hc a p a b i l i t yw i t hh ra l g o r i t h m i tc a ns e a r c ht h eb e t t e rs e q u e n c et om a k et h e s o l u t i o nf u r t h e ri m p r o v e m e n t i nt h eg a + i h ra l g o r i t h m , w ed e f i n et h ec o n c e p t so f t h er e f e r e n c er e c t a n g l ea n dt h ec o m b i n e dl a y e r w ef i n da l lc o m b i n e dl a y e r sa n d c a l c u l a t et h es o l u t i o n so fe a c hc o m b i n e dl a y e r s ，a n dt h e nf i n dt h eb e s ts o l u t i o na n dt h e b e s tc o m b i n e dl a y e r sf r o mt h e s es o l u t i o n s i nt h eg a + o i h ra l g o r i t h m ，w ei n t e g r a t e t h ee x h a u s t i v ei d e ai n t ot h eh ra l g o r i t h m , t h a ti s , t h ef i r s tr e c t a n g l eo fe a c hl a y e rc a l l b ep l a c e dh o r i z o n t a l l yo rv e r t i c a l l y c a l c u l a t et h es p a c eu t i l i z a t i o no ft w op l a c e m e n t sa n d t h e nu ：辩t h ep l a c e m e n tw i t l lt h eg r e a t e ru t i l i z a t i o nt of o r mt h el a y e r f u r t h e r m o r e ，w e s e a r c ht h er e c t a n g l ew h o s eh e i g h to rw i d t hi st h e $ a n l ea st h eh e i g h to rw i d t ho f s u b s p a c ef i r s t l y t h i sm e t h o dc a nr e d u c et h en u m b e ro fs u b s p a c ea n di m p r o v et h e s p a c eu t i l i z a t i o n i nt h i sp a p e rw ea l s od e v e l o ph ra n dg a + h rt os o l v et h e3 d - p a c k i n gp r o b l e m t h ec o m p u t a t i o n a lr e s u l t so nw e l l - k n o w nb e n c h m a r kp r o b l e m ss h o wt h a tt h er u n n i n g t i m eo fh ra l g o r i t h mi ss h o r tb u tt h es p a c eu t i l i z a t i o ni sn o ti d e a l ，t h en m n i n gt i m eo f g a + h r a l g o r i t h mi sl o n g e rb u tt h es p a c eu t i l i z a t i o ni sh i g h e rt h a nh r e s p e c i a l l y ， t h er e s u l to fg a + h rc a nc o m p l e t e 、析n 1b i s e h o f f a l g o r i t h m k e y w o r d s ：g e n e t i ca l g o r i t h m ；p a c k i n gp r o b l e m ；h e u r i s t i ca l g o r i t h m 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：妙知粉上- 叫年易月) ，日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门 大学有权保留并向国家主管部门或其指定机构送交论文的纸质版 和电子版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅，有权将学位论文的内容编入有关数据 库进行检索，有权将学位论文的标题和摘要汇编出版。保密的学 位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( o 彳 ( 请在以上相应括号内打“4 ) 日期：洚乡月2 曰 日期。1 州肥日 第一章绪论 装箱问题是理论计算机科学与组合优化领域的一个重要问题1 1 1 。随着计算机 科学、管理科学和现代化生产技术等的日益发展，组合优化问题日益增多，越来 越受到运筹学、应用数学、计算机科学及管理科学等诸多学科的重视。装箱问题 作为其重要分支在近几十年来得到了广泛而深入的研究，得到了一些较好的结 果，对实际应用有很好的指导意义。 装箱问题在理论上属于n p 完全问题【2 j ，直接利用数学中的优化方法比较困 难，因为数学优化方法一般是对量的优化，通过对方程进行求解得到目标解。但 是装箱问题不仅是量的问题，而且还需要对物体以及剩余空间进行形状的描述， 从而增加了问题的复杂度，使得该问题很难用纯数学方法进行描述，进而通过数 学的公式进行求解。因此该问题更多的是通过一些近似方法来解决。目前对装箱 问题的研究从容器的维数上可分为维装箱问题、二维装箱问题和三维装箱问 题。 1 1 装箱问题综述 这三类装箱问题根据装箱之前全部物体的信息是否己知都可分为离线装箱 问题( o f f - l i n eb i np a c k i n g ) 和在线装箱问题( o n - l i n eb i np a c k i n g ) 。如果一个装箱算 法在装入物品a i 肘，只利用辑前面物品a j ( 1 ，s ，) 的信息，面不知道后继元素的 任何信息，即按照元素到达顺序随到随装，则称该算法为在线算法。这种情况下 的装箱问题称为在线装箱问题【3 j 。例如对从传送带上下来的物体进行装载；计算 机内存的分配，在存储当前的数据时，下一个存储任务的信息并不可知。物品装 载以前就已得到所有物品信息，之后统一处理所有物品的近似算法称为离线装箱 算法。这种情况下的装箱问题称为离线装箱问题。 1 1 1 一维装箱问题 一维装箱问题是许多具有重要意义的实际优化问题的基础。在建筑中经常需 要从长度一定的棍子上切割不同长度的棒和管；电气布线中电线来自长度一定的 基于遗传和递归的装箱算法研究 线卷；贴墙纸需要从改订长度的纸卷中得到；具有相同宽度，不同长度的材料需 要用平板架运送到建筑工地；在金属制造工业中，钢片需要从大块钢片中切除。 这些都是具有几何尺寸的典型一维装箱问题。 当然物品的尺寸不一定是几何尺寸，比如，电子工业中不同长度( 字节) 的微 代码程序需要存储至具有固定尺寸的存储器中；在娱乐工业中，把歌曲集发布在 给定容量的媒质( 光盘，磁带) 中；在作业管理中，不同执行时间的任务需要在满 足所有任务时间限制的前提之下被分配到不同的工人；在运输工业中，要把不同 重量的货物装入一定载重量的卡车中。所有这一切问题都可以归结为一维装箱问 题。因此，找到一个高效的一维装箱问题的算法具有非常重要的现实意义。经典 的一维装箱问题是这样描述的： 给定n 个物品的序列厶= 口1 ，口2 ，口3 ， ，物品a l ( 1 f 哟的大小 j ( 嘶) ( o ，i l ，局，b 2 ，为一个由单位容积的箱子组成的无限序列。我们要求：每一 个物品口。只能装入到唯一的箱子里，每一个箱子中的数字和不超过1 ，如何用最 少的单位容积的箱子才能装下所有的物品呢? 用线性规划的方式来描述一维装箱问题如下： 糟 m i n z = y ， j = l 靠 5 上 s ( a j ) x 扩y j 江( 1 2 一，帕 i l b = l j = o 纠2 一，哟 i = i y f = o 或1，= ( 1 ，2 ，刀) 勃= o 或i f ，_ ，= ( 1 ，2 ，功 其中y 严l 表示箱子f 被使用，反之则表示箱子i 空着；x = l 表示物品j 放入 箱子i ，反之表示物品_ ，未放入箱子i 。 一维装箱问题是研究比较早的一类问题，早在七八十年代就提出了n f ( n e x t f i o t 4 1 、f f ( f i r s tf i o t 5 1 、b f ( b e mf i o t 5 1 、w f ( w o r s tf i o 、f f d ( f i r s tf i td e c r e a s i n g ) 、 2 绪论 b f d ( b e s tf i r s td e c 托雒i n 曲 6 1 等著名的近似算法。这些算法或者算法的变形也常用 到二维和三维装箱问题中。 1 1 2 二维装箱问题 二维装箱问题在工业领域有着广泛的应用。在木材和玻璃工业中，如何从大 的材料板上切下不同的矩形板；在报纸排版上，文章和广告如何在页面上合理安 排；在超大规模集成电路板的规划上，集成电路如何布置等这些问题都可以描述 成二维装箱问题。如果能够找到一种好的解决方案，那么就会节约生产成本，提 高效益，可以说，这个问题的解决是很有现实意义的。 根据装箱条件的不同，又可以把二维装箱问题分成两种。第一是关于物体可 旋转与否，例如报纸排版要求排放的文字块不能旋转，这种装箱方式被称为定位 装箱( o r i e n t a t i o np a c k i n g ) 。与之相反，若对待排放物体无此要求，则称装箱方式 为可旋转装箱( r o t a t i o np a c k i n g ) 。第二是由于现代工业的自动化特征，要求在切 割矩形时，每切一刀都必须使原来的矩形分为两个矩形，这个规则被称为一刀切 ( g u i l l o t i n ec u t t i n g ) 。相反，装箱或切割时并不附加此种要求的切割方式被称为 自由切( f r e ec u t t i n g ) 。综上所述，二维离线装箱问题可分为： 2 - d b p r g ：待排放物体可以旋转，而且排放满足一刀切的条件； 2 巾b p o g ：待排放物体不可旋转，而且排放满足一刀切的条件； 2 - d b p r f ：待排放物体可以旋转，而且排放不必满足一刀切的条件； 2 - d b p o f ：待排放物体不可旋转，而且排放不必满足一刀切的条件。 本文研究的二维装箱问题是属于2 一d b p r g 该问题的数学描述如下： 给出一个固定宽度的矩形板和一组大小各异的小矩形，装箱问题就是把每个 小矩形装到板中，使得任意两个小矩形都不重叠，而且使得板的高度尽可能低。 这个问题的具体描述如下： 给出宽度为矿的矩形容器和刀个长度和宽度分别为和嵋，( 1sjs 一) 的小 矩形。定义( ，耽) 为矩形f 的左上角坐标，( 靠，y 一) 为矩形f 的右下角坐标。对所 有isjs 刀，矩形的坐标必须满足如下条件： 1 ( 靠一嘞= 且虼一靠= 心) 或( h 一黾= 川且虼一儿- - - i , ) 基于遗传和递归的装箱算法研究 2 对所有1 歹s 刀，_ ，i ，矩形f 和矩形j 不能重叠，即靠嘞或嘞b 或 yr i 2y b 或y i i y 口o 3 x 工嘞x r ，x 工x ，f x r g y r 蜘 ，y r y 一h 。 在装箱的过程中所有被放置的矩形都是可旋转的，并且放置时矩形的长边或 宽边要与容器的底边平行。 目前，解决二维装箱问题的一些最优算法有：1 9 6 1 年，g i l m o r e 和g o m o 巧 利用线形规划来求解 7 1 ；1 9 7 7 年，c h r i s t o f i d e s 和w h i f l o e k 提出树搜索方法来求 解嘲；2 0 0 0 年，c u n g 等人在h i f i 和z i s s i m o p o l o u s 的最佳优先分支定界法的基 础上提出了一种新的求解二维切割问题的最优算法嘲。但这些方法对数据量大的 问题并不实用，因此人们开始逐渐研究一些近似算法。目前，对二维装箱问题提 出的一些启发式算法有：1 9 8 0 年，b a k e r 等人提出了b o t t o m - l e f t ( b l ) 算法t 1 0 1 ；1 9 8 3 年，c h a z e l l e 在b l 算法的基础上提出了b o t t o m l e r - f i l l ( b l f ) 算法【l l l ；1 9 9 4 年 h w a n g 提出最速降法( f f d h ) ，1 9 9 5 年c h e n 提出分层式放置法( i l p ) 【1 2 1 。在这些 算法中，b l 算法由于利用矩形的长度和宽度进行放置，要求被放置矩形尽可能快 地到达容器底部的同时尽可能快的到达容器的左侧，不用确定放置点的坐标，因 而是研究比较多的方法之一。1 9 9 5 年，k r o g e t 利用遗传算法来求解该问题【1 3 1 ； 1 9 9 6 年j a k o b s 提出基于b l 的g a 算法f 1 4 1 ，并给出了g a 与b l 结合的算法流 程。近年来，更是提出了一些新的模型和算法，例如，拟人启发式算法【1 5 】、构造 方法【1 6 1 、启发式递归算法【1 7 1 、混合启发式算法【1 8 ，1 9 】等。随着研究的不断深入， 二维装箱问题出现了一些高效的算法，对一些问题可以很容易就求得最优解。 1 1 3 三维装箱问题 三维装箱问题是一个更为复杂的问题，该问题碰到最多的实例就是集装箱装 载问题。目前，物流业正处在快速发展的时期，集装箱运输将会有大幅度的增长。 集装箱装载作为物流配送过程中的一个关键性环节，可提高配送业务的自动化水 平、提高货物装载的优化程度、提高配送业务的工作效率和规范业务流程等。因 此，研究此类装箱算法，提高装箱效率，将极大减少物流配送成本。此外，在飞 机装舱，码头装货，列车装箱，机械行业中箱体和钟表等布局，航空、航天工业 4 绪论 中导弹仓的布局，以及建筑、电子、造船业、纺织业等诸多领域中也有着广泛的 应用。 三维装箱问题可分成以下几类： 箱柜装载( 3 d b p p ) ：给定，价长方体物品的序列b = a l ，口2 ， ，每一个 长方体物品a , 0 s f 帕都具有宽度嘶，高度岛和深度喀。给定无限个具有相同的 宽度w ，高度h ，深度d 的长方体箱子，要求用最少的箱子装下所有的长方体物 品，在装箱过程中必须满足以下两个条件： 1 长方体物品要全部装入箱子中，并且其各边要与箱子的各边平行； 2 任何两个长方体物品不能重叠装箱。 文献 2 0 提出了该问题的一个启发式算法。 带状装载( 3 d s p p ) ：在该问题中，容器有固定的宽度和高度，但有无限的深 度，装箱问题是把所有的物品都装入容器中，而且使得容器的深度尽可能的小。 b i s c h o f f 和m a r r i o t t 在文献 21 中对该问题的几种算法做了比较。文献 2 2 介绍了 该问题的具体应用。 背包装载( 3 d j ) ：给定一个容器，装入容器中的每个箱子都有一定的价 值，背包装载问题是选择一部分箱子装入容器中使得装入容器中的箱子总价值最 大。 本文所研究的三维装箱问题属于3 d k l p ，该问题是把箱子的体积作为价值， 求解目标则转化为使得装入容器中的箱子总体积最大。它的形式化定义如下： 给定一个长方体容器c 和一个长方体箱子的集合伊 b ，“ ，容器c 长日、 宽肌高d ，每个箱子b i 有长鬼、宽w i 和高磊，每个箱子的体积为协= 办而。令 0 1 标志嘶，o h i 、d 函分别表示是否允许箱子尺寸h ，、w i 、西作为垂直方向尺寸。 设s 为b 的一个子集，定义s 中所有箱子体积之和为v s ，即： = y ， b je s 问题的目标是选择b 的一个子集s ，使得珞最大，并且满足以下条件： 1 对任何箱子b ，芍，在容器c 中对应有一个装填位置；s e e 的所有箱子必须全 部包含在c 中； 2 s 中任何两个箱子都不重叠； 5 基于遗传和递归的装箱算法研究 3 s 中箱子b ，的方向必须和方向标志o w ，、o h s ，d 西一致。 对于3 d k l p 这类问题，根据文献 2 3 的分类，常用的启发式算法有：砌墙 算法、建堆算法、立方体排列算法和切割算法。1 9 6 5 年，e c g i l m o r e 在文献 2 6 中提出了建堆启发式算法，该方法先把箱子放入合适的堆中，再通过解决一个二 维装箱问题把这些堆摆放入容器中；1 9 8 0 年，j a g e o r g e 在文献 2 4 中提出了砌 墙算法，该算法把容器分成层，层再分成条，最终转化为一维背包问题；1 9 9 4 年，r m o r a b i t o 在文献 2 8 中提出了切割算法，该方法利用分治的思想，用切割 树来表示装填，每棵切割树代表把一个容器切割成小的容器，树叶代表箱子；1 9 9 5 年，e e b i s e h o f f 在文献 2 5 中，根据层和条的选择策略，提出了按层布局的贪 婪算法；1 9 9 7 年，a b o r t f e l d t 提出了立方体排列算法阱1 ，通过一些立方体的排列( 相 似箱子的排列) ，递归地填充容器；2 0 0 2 年，d p s i n g e r 提t b 了基于砌墙策略的树 搜索算法1 ；2 0 0 5 年，a l i m 在文献 2 9 中通过组织装填树把大空间分成小空间 进行装填，最后再对剩余空间进行处理，取得了不错的效果。 1 2 论文研究的内容 本文主要研究的是二维装箱问题。在张德富老师提出的启发式递归策略( h 鼬 的基础上，提出了与遗传算法结合的混合遗传算法来求解装箱问题，目标是尽可 能地提高箱子的空间利用率并且最大限度地提高收敛速度。在此基础上又进一步 改进了h r 算法，提出了i h r 算法和o i h r 算法。最后还把h r 算法和g a + h r 算法应用到三维装箱问题上。 具体的内容安排如下： 第一章绪论 简要概述了三类装箱问题在各领域中的应用，问题的数学描述，目前各类问 题的研究情况以及本文所研究的内容。 第二章遗传算法 详细介绍了遗传算法的思想来源、算法的作用以及算法的基本步骤和特点。 第三章二维装箱问题的启发式算法 简要介绍了b l f 算法、b f 算法、h r 算法。详细介绍了本文提出的i h r 算 法和o i h r 算法。 6 第四章混合遗传算法的实现 给出了改进的遗传算法，利用h r 算法、i h r 算法、o i h r 算法计算适应度 值来实现混合的遗传算法。 第五章二维装箱问题的计算结果 给定几类数据，把各种算法实现的结果进行比较，并画出了一些数据的装箱 效果图。 第六章三维装箱问题的算法及测试结果 利用求解二维装箱问题的h r 算法和g a + 量珉算法来求解三维装箱问题。与 前沿的算法做比较并实现了一个集装箱装载系统，把装箱的效果图显示出来。 第七章结束语 7 第二章遗传算法 第二章遗传算法 遗传算法( g e n e t i ca l g o r i t h m ) 是一类借鉴生物界的进化规律( 适者生存，优胜 劣汰遗传机制) 演化而来的随机化搜索方法。它是由美国的j h o l l a n d 教授1 9 7 5 年首先提出，随着人们不断的深入研究，目前遗传算法已被人们广泛地应用于组 合优化、机器学习、信号处理、自适应控制等领域。它是现代有关智能计算中的 关键技术之一。 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。 它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+ 检测一的迭代 过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术 指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗 传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作 设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局优 化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用 等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的 智能算法之一。 2 1 传统遗传算法的基本步骤 我们习惯上把h o l l a n d l 9 7 5 年提出的g a 称为传统的g a 。它的主要步骤如下： 编码：g a 在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串 结构数据，这些串结构数据的不同组合便构成了不同的点。 初始群体的生成：随机产生n 个初始串结构数据，每个串结构数据称为一个 个体，n 个个体构成了一个群体。g a 以这n 个串结构数据作为初始点开始迭 代。 适应度值评估检测：适应度函数表明个体或解的优劣性。不同的问题，适应 度函数的定义方式也不同。 选择算子：选择的目的是为了从当前群体中选出优良的个体，使它们有机会 作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择 的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了 9 基于遗传和递归的装箱算法研究 达尔文的适者生存原则。 交叉算子：交叉算子是遗传算法中最主要的遗传操作。通过交叉算子可以得 到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。 变异算子：变异首先在群体中随机选择一个个体，对于选中的个体以一定的 概率随机地改变串结构数据中某个串的值。同生物界一样，g a 中变异发生的 概率很低，通常取值在0 0 0 1 , 4 ) 0 1 之间。变异为新个体的产生提供了机会。 传统的g a 流程框图： 图2 1 遗传算法具有进化计算的所有特征，同时又具有自身的特点： 1 直接处理的对象是决策变量的编码集而不是决策变量的实际值本身，搜索过 1 0 第二章遗传算法 程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。 2 遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性。 3 遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概 率方式来进行，从而增加了搜索过程的灵活性，同时能以很大的概率收敛于 最优解，具有较好的全局优化求解能力。 4 遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的 普适性和易扩充性；同时，我们可以把搜索范围集中到适应度较高的部分搜 索空间中，从而提高了搜索效率。 5 遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。 2 2 遗传算法中的基本实现技术 编码：编码是连接闯题与算法的桥梁。编码方法除了决定个体的染色体排列 形式外，还决定了个体从遗传空间的基因型变换到搜索空间的表现型时的解码方 法；编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。由此可见， 编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算 的效率。一个好的编码方法，有可能会使得交叉算子、变异算子等遗传操作可以 简单的实现和执行。反之，可能使得交叉算子、变异算子等遗传操作难以实现， 也可能产生很多无效解。h o l l a n d 的编码方法是二进制编码，但对于许多遗传算 法的应用，特别是在工业工程中的应用，这种简单的编码方法很难直接描述问题 的性质。近十年来，针对特殊问题，人们提出了其它编码方法。例如：格雷编码、 浮点编码、符号编码。 二进制码编码、解码操作简单易行，不仅便于实现交叉、变异等进化操作， 而且便于利用模式定理对算法进行理论分析。格雷码是二进制码的变形，具有与 二迸制码相似的特点。其编码、解码操作相对复杂，但基于格雷编码的算法局部 搜索能力有较大提高。浮点编码方式编码长度等于参数向量的维数，在达到同等 精度要求的情况下，编码长度远小于二进制码和格雷码。此外，浮点编码使用的 决策变量的真实值，不需反复进行数据转换。符号编码方法是指染色体编码串中 的基因值取一个无数值含义、而只有代码含义的符号集。这些符号可以是字符， 也可以是数字。符号编码的主要优点是便于在遗传算法中用所求问题的专门知识 基于遗传和递归的装箱算法研究 及相关算法。 适应度函数：遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数 ( f i t n e s sf u n c t i o n ) 为依据，利用种群中每个个体的适应度值来进行搜索。因此适 应度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优 解。此外，它对遗传算法的终止搜索条件也有影响。值得提出的是，作为一种随 机搜索方法，遗传算法的适应度函数或目标函数不受连续可微的约束，而且函数 的定义域可以是任意集合。对目标函数的唯一要求是对于输入可以计算出能加以 比较的输出。当然适应度函数设计应尽可能简单，以减少计算时间和空间上的复 杂性。 一般而言，适应度函数是由目标函数变换而成的。对目标函数值域的某种映 射变换称为适应度的尺度变换( f i t n e s ss c a l i n g ) 。常用的变换方法有：线性尺度变 换、方差缩放技术、乘幂尺度变换和指数尺度变换。基本遗传算法中采用的是线 性尺度变换。 选择算子：选择策略对算法性能的影响会起到举足轻重的作用。不同的选择 策略对算法的性能也有较大的影响。不同的选择策略将导致不同的选择概率，即 下一代中父代个体的复制数目的不同分配关系。较大的选择概率使最优个体具有 较高的复制数目，从而使得算法收敛速度较快，但也较容易出现过早收敛现象。 相对而言，较小的选择概率一般能使群体保持足够的多样性，从而增大了算法收 敛到全局最优的概率，但算法的收敛速度一般较慢。选择算子设计的内容就是确 定如何从父代群体中按某种方法选取个体遗传到下一代群体中。常用的选择算子 包括：比例选择、最优保存策略、确定式采样选择、无回放随机选择、无回放余 数随机选择。比例选择方法简单，但容易出现早熟收敛，速度慢现象。无回放余 数随机选择降低了选择误差，保证优秀个体的遗传，但操作相对复杂。确定式采 样选择降低了选择误差，操作相对于无回余数随机选择简单。基本遗传算法中采 用的是比例选择。 交叉算子：遗传算法中所谓交叉算子，是指对两个相互配对的染色体按某种 方式相互交换其部分基因，从而形成两个新的个体。交叉算子是遗传算法区别于 其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方 法。遗传算法中，在交叉算子之前还必须对群体中的个体进行配对，目前常用的 1 2 第二章遗传算法 配对策略是随机配对。然后在配对染色体中随机选择杂交位置进行杂交。杂交的 目的是为了产生适应值更高的染色体，从而使各代染色体都向前进化。通常交叉 的方式组合出新个体，在串空间进行有效搜索，同时降低对有效模式的破坏概率。 交叉算子的设计包括两个方面的内容：1 如何确定交叉点的位置? 2 如何进 行部分基因的交换? 设计的指导原则是既不要太多的破坏表示优良性状的基因， 又要产生一些较好的新个体模式。常用的交叉方法有单点交叉、双点交叉、多点 交叉、均匀交叉和算术交叉。其中前三者适合于二进制编码方式，后两种适合浮 点数编码方式。基本遗传算法中采用的是单点交叉。 变异算子：遗传算法中所谓变异算予，是指将个体编码串中的某些基因值用 其它基因值来替换，从而形成一个新的个体。变异算子的主要目的是改善算法的 局部搜索能力，并维持群体的多样性，防止出现早熟现象。当产生的后代并不比 前辈更为优秀且又未达到可行性解，就会产生不成熟的收敛。为了克服这种情况， 只有依赖于变异。当算法陷入局部搜索时，可以通过变异算子，使个体跳出局部 空间，寻求全局最优。变异的过程通常是在一定概率下进行的，而且只变动染色 体中某一个或几个基因。遗传算法中的变异算子是产生新个体的辅助方法，它决 定了遗传算法的局部搜索能力。交叉算子和变异算子的相互配合，共同完成对搜 索空间的全局搜索和局部搜索。 变异算子的设计包括两方面：1 如何确定变异点的位置? 2 如何进行基因值 替换? 下面介绍几种常用的变异算子方法，常用的变异方法有基本位变异、均匀 变异、非均匀变异、二元变异、高斯变异。均匀变异适合于遗传算法运行的初期 阶段，它可以在整个搜索空间随机游动，能够增加种群的多样性，但不利于重点 区域内的搜索。而非均匀变异这可以克服这个缺点。高斯变异也是提高重点区域 局部搜索性能的变异方法。其中基本位变异适合于二进制编码方式，后四种适合 于浮点数编码方式。基本遗传算法中采用的是基本位变异。 1 3 第三章二维装箱问题的启发式算法 第三章二维装箱问题的启发式算法 3 1 b l ( b o t t o m l e f t ) 和b l f ( b o t t o m l e f t - f i l l ) 算法 b l 算法【3 0 】的主要思想是：每个物体从容器的右上角开始尽可能向容器底部 滑动，然后尽可能向左滑动。重复这种连续的垂直和水平移动操作直至所有物体 都有一个固定的位置。图3 1 展示了一矩形序列( 2 ，6 ，4 ，3 ，0 ，1 ，5 ) 用b l 算法的装箱过程。 图3 - 1 ：b l 算法 这种规则的主要缺点是当移动大的矩形时会产生一些空隙。但是它的时间复 杂度只有o ( n z ) ，其中n 是所有要装入矩形的数量。 b l f 算法1 3 0 1 的主要思想是：从右上角开始，每次把矩形放到容器的剩余空间 的最低可放置空间中，然后再尽可能的左移，直到不能再移动为止，重复此操作 直到所有矩形都放入到容器中。图3 2 展示了一矩形序列( 2 ，6 ，4 ，3 ，0 ，l ， 5 ) 用b l f 算法的装箱过程。 基于遗传和递归的装箱算法研究 图3 - 2 ：b l f 算法 因为布局的生成是基于每次找最低可放置的空间，而不是一序列的b l 移动 操作，因此，它能够在装箱布局中填充部分的空隙。和b l 算法相比，这种方法 能够生成更紧凑的装箱布局，但是该算法的缺点是复杂度为o ( n 3 ) 。 3 2b e s tf i t 算法 b e s tf i t 算法【3 1 】的每一步都需要搜索容器最低空间的位置和最佳适应的矩形， 对于任意顺序的一组矩形序列来说，将需要大量的计算时间。为了提高计算效率， 可以把算法分成三部分：预处理阶段、装箱阶段、后处理阶段。 3 2 1 预处理阶段 首先，把容器存储为一维数组，数组的大小与容器宽度的大小相同，数组的 下标就是容器的x 坐标值。而数组的元素就是x 坐标对应的在该位置所填充的高 度。图3 3 显示一个有9 个单元的容器，未装填时的情况以及装填过程中的情况。 采用这种方法就可以很容易找到容器的最低点位置，即为数组元素的最小值。而 间隙的宽度就是数组中有连续相同元素的个数。 1 6 第三章二维装箱问题的启发式算法 0 1234 6 7s 0 l23 4j 6 7 8 图3 - 3 其次，当用到b e s tf i t 方法时，如果这些矩形都没有排序的话，那么每次放 置一块矩形时，都得从全部的刀个矩形中搜索才能找到最佳的矩形。如果事先把 矩形按规则排好序的话，则平均每放置一块矩形只需要搜索呈次就可以了。具 体的规则如下： 1 把所有高度大于宽度的矩形旋转过来，使得所有矩形的高度都不大于宽度。 例如： ( 3 ，5 ) ，( 5 ，2 ) ，( 1 ，1 ) ，( 7 ，3 ) ，( 1 ，2 ) ) 变成 ( 5 ，3 ) ，( 5 ，2 ) ，( 1 ，1 ) ，( 7 ，3 ) ( 2 ，1 ) ； 2 按照矩形的宽度递减排序( 宽度相同的按照高度递减排序) 。例如： ( 5 ，3 ) ，( 5 2 ) ，( 1 ，1 ) ，( 7 ，3 ) ，( 2 ，1 ) ) 变成 ( 7 ，3 ) ，( 5 ，3 ) ，( 5 ，2 ) ，( 2 ，1 ) ，( 1 ，1 ) ) ； 这样排序的目的是不用搜索整个序列就能找出最佳适应矩形。 3 2 2 装箱阶段 对于容器当前的一个空隙，把搜索到的最佳矩形放置进去有多种规则，这里 采用如下三种规则： 1 最左端策略，把最佳的矩形放到空隙的左边。 2 紧邻最高边策略，找出容器中两块矩形间的最低空隙，然后把最佳适应的矩 形放到紧邻最高边的位置上。如果最低空隙是在一块矩形和容器的边之间， 则把矩形放到紧邻容器边的位置上。 3 紧邻最低边策略，和紧邻最高边策略相反，每次把矩形放到紧邻最低边的位 置上。 每一次的装箱操作都是找出最低点空隙的位置和宽度，找到最佳适应的矩 形，按照当前放置策略把矩形装入，并把矩形从矩形序列中删除。更新数组元 素的值。如果最佳适应的矩形不能完全装满该空隙的话，则没必要为下一个矩 形查找最低点空隙，因为它就是当前空隙的一部分，从图3 4 中可以看出。 1 7 基于遗传和递归的装箱算法研究 当旧空隙不能完全装满时找到一个新空隙的计算方式为： 如果矩形放在空隙的左端则，新空隙的位置= 旧空隙的位置+ 矩形的宽度； 如果矩形放在空隙的右端则，新空隙的位置= l f l 空隙的位置； 空隙的宽度计算方式为：新空隙的宽度= i b 空隙的宽度矩形的宽度； 1一 位置= 3 宽度= 4 新位置= 旧位置+ 矩形宽度= 3 + 2 = 5 新宽度= l f l 宽度矩形宽度= 4 2 = 2 图3 - 4 如果找到一条空隙，所有的矩形都不能装入的话，则它属于浪费空间。存放 该段的数组元素值就得提高到和相邻最低位置一样的大小。例如，从图3 - 5 中 看出，最低点间隙有2 个单元，但是找不到矩形能够装入，找到左边的矩形的 位置是最低的，因此把那两个单元所对应的数组元素值提高到和左边矩形对应 的数组值相同。 图3 - 5 1 8 第三章二维装箱问题的启发式算法 3 2 3 后处理阶段 当装完所有的矩形后，查找容器顶部所有突起的并影响解的质量的矩形。如 果找到最高位置的矩形的宽边是平行于容器底边的话，就把它旋转过来，使得 容器的整体高度下降。如图3 - 6 所示： 一 卅 3黝 卜 i 图3 - 6 1 9 基于遗传和递归的装箱算法研究 整个算法流程如下： b e s tf i t o b e g i n 对所有矩形进行旋转排序，使得所有矩形的宽度都不小于高度，并且按照宽 度的大小降序排序，宽度相同的按照高度降序排序； 初始化刀个元素的一维数组； 对每种装箱策略( 最左端策略，紧邻最高边策略，紧邻最低边策略) d o w h i l e 矩形没被全部装完d 0 找到最低位置； 若找到最佳矩形，则 利用装箱策略把最佳矩形放入容器中； 提高对应的水平线数组的值； 否则 把该位置提高到和相邻的最低位置相同： w h i l e 没完成最优化d 0 找到最高的物品； 若物品的宽度不小于物品的高度，则 最优化完成； 去掉最高物品； 减少参考水平线数组的值； 9 0 度旋转该物品； 若该物品能装得下，则 利用当前的装箱策略把该物品装入； 提高对应的水平线数组的值； 否则 把该位置提高到和相邻的最低位置相同； 若不能得到更好的解，则 最优化完成； 返回最好的解； e n d 2 0 第三章二维装箱问题的启发式算法 3 3 启发式递归策略0 m ) 在文献 1 7 】中提出了矩形装箱问题的启发式递归算法( h 】r ) ，它是非常简单和 有效的算法，具体描述如下： 1 把一个矩形装入一个被装的空间中，把未装的空间分成两个子空间( 如图3 7 ) 。 2 在每个子空间中按照步骤1 的方法递归的装入矩形。如果子空间的大小只能 装一个矩形，那么，就把那个矩形直接装入子空间中。 3 把每个子问题的解结合起来就是矩形装箱问题的解。 从图3 7 中可看出，分层后会出现两种情况：( a ) 当有一个矩形装入空间s 时， 空间s 可被划分为一个无界空间s l 和一个有界空间s 2 ，此时s l 和s 一样都是无 界空间。( b ) 当有一个矩形装入空闻s 2 时，空间s 2 可被划分成s 3 和s 4 ，此时， s 3 和s 4 与s 2 类似，都是有界空间。因此可递归调用填充s 2 的过程。函数 r c c u r s i v e p a c k i n g ( s 2 ) 显示了填充s 2 的过程。在填充有界空间s 2 时，该递归过程 被调用。同样地，s 3 、s 4