（计算机应用技术专业论文）多约束装箱优化模型的研究与系统开发.pdf

摘要 摘要 本文以实际的集装箱自动装载系统为研究背景，设计出一种三层逐次优化的 装箱方案。该方案以空间利用率的优化以及运算效率的提高为目标，根据装载过 程中的实际约束条件，采用分层装载思想以及空间划分合并原则，结合启发式算 法和遗传算法，提出三层逐次优化策略：组合预处理优化、底层空间优化、上层 空间优化。该方案紧密结合了装载操作实际情况，能满足实际装箱过程中的多种 约束条件，具有较强的适用性。 本文首先介绍装箱优化问题的背景和研究现状。其次分析了组合优化问题特 点，介绍了本文所涉及的启发式算法和遗传算法的基本原理和实施过程。然后结 合实际装载约束条件建立了优化模型，在此基础上设计了优化算法，提出三层优 化方案，并详细地描述了方案的算法流程图和实现过程。最后完成了基于该优化 方案的集装箱自动装载系统的设计与开发。该系统功能较完善，能完成从派车指 引到装车指引的多种功能，具有较强的适用性和推广性。 关键词：装箱优化遗传算法自动装载系统 a b s r a c t a b s t l a c t t h et h e s i si sb a s e do na u t o m a t i c1 0 a d i n gs y s t e m a tf i r s ti ti n t r o d u c e s t h et r a d i t i o n a lp e r f o m a n c ei nt h i sf i e 】d ， t h e ni th a sd e s i g n e dan e ws c h e m e w i t hs t u d i n gp r a c t i c a ll o a d i n go p e r a t i o n t h es c h e m ei sa t h r e e s t e p o p t i m i z i n ga l g o r i t h m ，i t sp u r p o s e sa r e1 0 a d i n gc a p a c i t yo p t i m i z a t i o na n d e f f i c i e n c yd f o p e r a t i o n g w i t h t h ep r a c t i c a l1 0 a d i n gr e s t r i c t i o n ，it i n t e g r a t e sh e u r i s t i ca i g o r i t h m s a n dg e n e t i ca l g o r i t h m s ， a d o p t si a y e r 1 0 a d i n g i d e aa n d s p a c ep a r t i t i o na n dc o m b i n i n gr u l e t h eo p t i m i z i n g a l g o r i t h mi sc o m p o s e do fc o m b i n a t i o np r e t r e a t m e n t ，b o t t o ms p a c eo p t i m i z e a n du ps p a c eo p t i m i z e 】tc a ns a t i s f yt h el o a d i n gr e s t r i c t i o na n d h a s p r a c t i c a b i l i t y ， a tf i r s t ，t h et h e s i si n t r o d u c e st h er e s e a r c hb a c k g r o u n da n dt h er e s e a r c h a c t u a ls t a t e s e c o n d l y ， it a n a l y z e st h ec h a r a c t e ro fc o m b i n a t o r i a i o p t i m i z a t i o n a n di n t r o d u c e st h ep r i n c i p i e sa n dp r o c e s s e so fh e u r i s t i c a l g o r i t h m sa n dg e n e t i ca l g o r i t h m s t h i r d l y ，i th a sb u i l tt h eo p t i m i z a t i o n m o d e l a c c o r d i 兀gt ot h em o d e l ，i td e s i g n e so p t i m i z i n ga l g o r i t h i n ，a n dp u t f o r w a r dt h r e e s t e p0 p t i m i z i n ga l g o r jt h 1 t h e ni n t r o d u c e st h ea l g o r it h 肪 f l o wc h a r ti nd e t a i l a tl a s t ， i td e s i g n e st h ea u t o m a t i c1 0 a d i n gs y s t e mb a s e d o nt h et h r e e s t e po p t i m i z i n gs t r a t e g y t h es y s t e mh a sp e r f e c tf u n c t i o n ，i t c a np r o v i d ed i s p a t c hg u i d a n c ea n d1 0 a d 。n gg u i d a n c e i th a sp r a c t i c a b i l i t y a n disw o r t ho fs 口r e a d i n g k e y w o r d ：l o a d i n go p t i m i z a t i o n g e n e t i ca l g o r i t h m sa u t o m a t i c l o a d i n gs y s t e 】) 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：当拉 导师签名： c 叁堑： 日期：o 。绰月7 日 第一章引言 1 1 课题的研究背景 第一章引言 集装箱装载问题是一种应用广泛，具有很强实用价值的学术研究课题，在学 术上是属于相当复杂的组合最优化问题“1 ，在实务上亦属于物流配送管理的重要课 题。 集装箱运输的产生和发展使货物运输产生了新的变革，其优越性已得到全世 界的公认。有研究。1 指出：当前的集装箱利用率非常低，而集装箱的运费非常昂贵， 因此需要有效的提高集装箱利用率，研究一种优化的集装箱装箱方案尤为熏要。 经典的装箱问题要求把一定数量的物品放入容量相同的一些箱子中，使得每 个箱子中的物品大小之和不超过箱子容量，并使所用的箱子数目最少。装箱问题 是复杂的离散组合最优化问题，属于n p 完全问题。3 ( n p 即非确定多项式n o n d e t e 硼i n i s t i cp 0 1 y n o m i a l 的缩写) ，此类问题随着问题的规模增加，其计算量将 指数性或失控地增长，求解困难。 从2 0 世纪7 0 年代初开始，装箱问题就引起了广泛的探讨和研究“1 。装箱问题 可以追溯到1 8 3 1 年高斯( g a u s s ) 开始研究布局问题，因为装箱问题和布局问题本 质上是一样的，到现在已有百余年的历史，在文献上始见于1 9 3 0 年k a n t o r o v i c h 的俄文文章。虽然经过几代人的努力，但迄今尚无成熟的理论和有效的数值计算 方法。由于目前n p 完全问题不存在有效时间内求得精确解的算法，装箱问题的求 解极为困难，因此，从7 0 8 0 年代开始，陆续提出的装箱算法都是各种近似算法， 如首次适应、下次适应、降序下次适应和调和算法等。装箱问题广泛存在于工业 生产，包括服装行业的面料裁剪、运输行业的集装箱货物装载、加工行业的板材 型材下料、印刷行业的排样和现实生活中包装、整理物件等。在计算机科学中， 多处理器任务调度、资源分配、文件分配、内存管理等底层操作均是装箱问题的 实际应用，甚至还出现在一些棋盘形、方块形的数学智力游戏中。装箱问题的研 究文献分布面很广，在运筹学、计算机辅助设计、计算机图形学、人工智能、图 像处理、大规模集成电路逻辑布线设计、计算机应用科学等诸多领域都有装箱问 题最新的研究动态和成果出现，从这个角度来讲，布局问题涉及到了工业生产的 方方面面，也足以证明了装箱问题的应用前景日趋广泛而重要。 电子科技大学硕士学位论文 从经济效益角度来讲，提高集装箱的装箱率可以节省运输成本，提高经济效 益。集装箱运输是世界上广泛使用的手段之一。集装箱码头是国际运输链和物流 链的重要环节，通过它各种货物才能顺畅地流通。现代物流被西方经济学家和企 业界称为继劳动力、自然资源之后的“第三利润源泉”、“降低成本的宝库”、“企 业发展的战略手段”，将在我国经济发展中起着越来越重要的作用。2 0 0 1 年中国加 入w t o 后，对物流的需求日益旺盛起来，外贸出口增长至6 ，0 0 0 亿美元。集装箱 装入的优化问题是物流链中可以降低运输成本，提高运输效率的一个重要问题。 它广泛的出现在铁路货车车厢装载，轮船配载，集装箱装载等情况中，在集装箱 的运输中，降低运输成本，关键是提高集装箱的装箱量，以降低单件包装产品的 运费。对可塑包装产品，要做到这点是容易的，只要按集装箱容积的尺寸设计产 品的包装即可。但对于非可塑包装产品，由于产品包装固定，难以做到满负荷运 输，所以提高集装箱的装箱率可以带来很大的经济效益。 1 2 装箱优化问题的研究现状 1 2 1 研究范畴 由于装箱问题涉及范围的多样性，在许多文献中它们有不同的名字，虽然这 些问题出现在不同的领域中，但是研究表明它们有相同的逻辑结构，其中包含了 两组基本数据，一组是大物体( o b j e c t ) ，另一组是较小物体( i t e m ) 。大物体表示 需要被切割和装入的物体，如原料、集装箱，而小物体表示要切割成或要装入的 物体，如二维条、立方体盒子。 装箱优化问题是属于“切割和装入”( c u t t i n g p a c k i n g ，简称c p ) 问题的 一种。c p 问题可以看作是一类特殊的资源利用优化问题。目标是寻求一种有效的 切割和装入方法，最大化原料利用率。由于布局的优化能导致大量的材料节省、 缩减产品价值，所以高的材料利用率能增加产品工业的利润。该问题应用的领域 非常广，最具体是对原材料面积( 二维) 和空间( 三维) 的利用。二维应用如：钢铁 制造行业，纸品加工行业，服装制造业，以及玻璃加工制造行业中。在这些行业 中，一种行之有效的切割原材料的方法可以提高原料的利用率，减少废料的产生， 对提高企业的经济效益有直接的好处。三维应用如：集装箱货物运输行业，货物 存放行业，货物的仓库存放等。有效的三维装入方式提高空间的利用率，从而提 高经济效益。 2 第一章引言 为了实现信息在不同学科的交流，d y c k h o f f ( 1 9 9 0 ) 确定了“切割和装入”问 题的分类“1 。第一类空间问题由一维切割问题，二维平面切割问题，三维装入问题 组成，它们都被定义成欧几里德空间( 例如切割杆材问题，集装箱装入和货盘装入 问题) 。另一类非空间问题涉及抽象的“切割和装入”问题，包括如重量，时间或 者金融的维度等非空间领域( 例如内存分配，资金预算，铸币及人工投入线性平衡 法) 。非空间问题应用在比较抽象的经济领域，针对它的研究相对较少，而空间闷 题则在学术界引起了一些学者的关注。其中空间问题的具体内容如下： 一维切割主要指线形的管材或杆材的下料，即指在一定长度的管材或杆材上 如何合理截取，使所剩废料最小。一维切割涉及的数据结构简单，只需用长度来 描述即可，因此一些数学优化方法很容易用来解决这一问题，并且基本上能达到 最优的切割方式。 二维平面切割指在平面板料上如何合理有效的放置各种零件，使得所剩余料 最少，原料的利用率最高。二维排料中的数据结构比较复杂，物体越多，问题就 变得更困难，需要借助一定的中间手段，一些优化算法在二维排料领域中的应用 也变得困难多了。集装箱装入问题比二维排料问题更加复杂，要想得到好的解就 更加不容易。 三维装入问题是指寻找多个较小物体合理地放入较大物体( 如集装箱) 中的布 局问题。目前研究的主要对象是长方体形状的盒式物体。根据装载工具的不同， 可分为货盘装载和集装箱装入问题。本课题主要研究的是“切割和装入”问题中 空间问题的三维装入问题。 1 2 2 研究现状 在当前的装箱优化算法研究中，常用的研究方法有线性规划、动态规划方法、 启发式算法及严谨启发式算法( 包括模拟退火算法、禁忌算法、遗传算法) 等等。 通常按照以下几种分类进行研究： 1 ) 单个集装箱装载情况 对于此类情况研究的文献比较多，一般先假定货物的体积与其运费相当，因 此问题转化为求集装箱的最大容积利用率。单集装箱装载进一步又可分为相同体 积货物和不同体积货物的装载情形。 ( a ) 相同体积货物的装载 s c u l l i 和h u i ( 1 9 8 8 ) 、h a n ( 1 9 8 9 ) 和g e o r g e ( 1 9 9 2 ) 针对同等体积大小的货物 3 电子科技大学硕士学位论文 给出了启发武装载方法。s c h e i t h a u e r ( 1 9 9 2 ) 给出了基于动态规划前向策略的近似 算法，对于1 0 0 件左右货物的装载，运算时间是可以接受的。宫佩珊( 1 9 9 7 ) 针对 单一产品且产品无摆放限制的情况提出了一种递归方法。 ( b ) 不同体积货物的装载 对于体积大小不等的货物装载，大多数方法假定装载对象为弱差异情形。从 概念上讲，弱差异情形下装箱的方法也适合于强差异情形，但根据b i s c h o f f ( 1 9 9 0 ) 分析，方法的性能取决于货物的种类和数量，同样数量达几百件的货物，如果把 针对十几种体积规格的装载方法用来解决只有两三种体积规格的货物情况，效果 并不见得理想。g e h r i n g ( 1 9 9 8 ) 提出一种适用于弱差异情形的禁忌算法( t a b u s e a r c ha l g o r i t h m ) 。用遗传算法可以很好地解决强差异和弱差异货物的装载问 题。 ( c ) 实际因素的考虑 大多数文献仅考虑了集装箱容积方面的因素，对于装载实际所涉及的因素少 有叙述。b i s c h o f f ( 1 9 9 5 ) 针对稳定性因素的考虑，将托盘装载的方法( b i s c h o f f ， j a n e ta n dr a t c l i f f ，1 9 9 5 ) 成功地应用到集装箱装载中，这种方法的特点与一 般集装箱生成“层”( 1 a y e r ) 不同之处在于：由两种不同体积的货物构成“层”， 从底面向上生成若干“层”，货物的选取和放置方向由“层”所在表面决定，利 用此方法可以阻止出现货物悬垂于下面货物边缘之外情况。与l o ha n dn e e ( 1 9 9 2 ) 及n g o i ( 1 9 9 2 ) 所介绍的方法相比，不但集装箱容积利用率相近而且具有较好的稳 定性，但对于需要考虑多目的地卸货的情形恰是该方法不足之处。对于货物多目 的地卸载情况，b i s c h o f f 提出将到到达各个目的地的货物组成相应的集合，按照 后到先装的原则装箱，给后装货物留出尽可能大的空间，它的特点在于不是沿集 装箱宽度方向构建一个完整的“层”，而是构造单个的“列”，其缺点是没有考 虑稳定性条件。实验表明，两种方法各有互补之特点。 g e h r i n g ( 1 9 9 7 ) 建议采用层交换的方法提高载重分布不均匀情况，d a v i e s ( 1 9 9 9 ) 在g e h r i n g 所提出的方法的基础上进行了改进，采用滞后处理( d o s t p r o c e s s i n g ) 策略，将集装箱沿长度方向分成几个区域，每个区域包括垂直于地 面的层，货物属于同一区域之内可以跨层放置，每个区域可以交换、旋转以及将 该区域一分为二沿集装箱横向中心先分布，以此来调节整个集装箱纵向重量分布。 但是试验表明，d a v i e s 所提出的改进办法仅当货物总体积接近集装箱容积时有明 显效果，而当多集装箱装载时应用此方法，最后的集装箱可能就会留出很多空余 空间，这在装载实务中是不允许的，当货物体积相当大时也会影响该方法的性能 4 第一章引言 发挥。另外集装箱重力方向货物重量分布也是需要考虑的问题，尽可能使重心较 低，也有利于稳定性。与d a v i e s 有所不同的是，e l e y ( 2 0 0 2 ) 应用有限搜索树方法、 贪婪方法构造一系列的同类货物块，对o r 一1 i b r a r y 的7 0 0 个测试例子以及l o ha n d n e e ( 1 9 9 2 ) 给出的1 5 个例子分别进行实验，并与其他方法在集装箱容积利用率、 运行时间、稳定性及载重分布几种指标做了比较，显示出良好的性能。 2 ) 多集装箱装载情况 对于同种规格的多集装箱装载问题，一般要求所用集装箱的数量最少。 c h e n ( 1 9 9 5 ) 针对集装箱一般装载问题( 用一定数量的集装箱装载给定的货物) 给出了0 1 整数线性规划模型，考虑了货物和集装箱的不同规格、货物的方向、 放置因素，并分析了一些特殊情况如单个集装箱装载、载重分布等。 i v a n c i c 等人( 1 9 8 9 ) 给出了一种基于整数规划的三维装箱启发式算法，对 于每个集装箱依次装载直至所有货物装完为止，但是这种方法仅适用于同种规格 的集装箱装载，而且由于变量以及约束条件随货物数量增加而迅速增多，从而使 问题难于求解。b i s c h o f f 和r a t c l i f f ( 1 9 9 5 ) 将多托盘装载情况拓展到多集装 箱装载问题。 m i c h a e le 1 e y ( 2 0 0 2 ) 分别应用串行和并行策略设计了装载方法，根据i v a n c i c 等人设计的4 7 个情景进行实验。结果显示，这两种方法可以对其中1 4 种情形得 到优化解，但不足以说明孰优孰劣。e l e y 又根据b i s c h o f f 和r a t c l i f f 的实验数 据库中取3 5 0 个例子进行实验，最后表明串行方法可以得到比较好的解，但运算 时间很长。值得注意的是两种方法对强差异货物情形都能得到很好的解。 对于不同规格的多集装箱装载，需要考虑不同规格的集装箱的运输成本，其 优化目标为所用成本最小。b o r t f e l d t ( 2 0 0 0 ) 基于串行的原则讨论了几种选择策 略。e l e y 认为可以把此问题建模为集合分割问题( s e t p a r t i t i o n ) 。 1 3 本文主要研究工作及意义 1 3 1 本文研究内容及意义 本文课题研究的最终目的是实现华为公司的集装箱自动装载系统，在收集分 析现有方案的基础上，结合华为公司的装载业务，提出一种实用的三层逐次优化 解决方案。 主要研究内容如下： 电子科技大学硕士学位论文 1 ) 介绍装箱优化问题的研究背景，分析现有的装箱优化算法。 2 ) 结合实际的集装箱装箱业务，分析装载过程中的约束条件，建立优化数学 模型。 3 ) 以空间划分合并为基础，结合了多种优化算法，提出一种具有较强实用性 的三层逐次优化方案，并对该方案的性能进行分析。 4 ) 将优化方案应用于集装箱自动装载系统，该系统应具有较高的实用性，能 以三维图示显示结果，并能指导实际的派车，装车操作，行车路线等。 研究意义： 本文通过建立多约束条件下的装箱优化模型，设计出能满足约束条件，优化 容积利用率和提高算法效率的装载方案，以此为基础开发集装箱自动装箱优化系 统，实现了集装箱装载的智能化和规范化，具有较高的实用价值和现实意义。此 外，装箱优化问题可以应用推广到很多领域，如：飞机装舱、工厂下料、计算机 的存储分配等，都存在空间分配的问题，因此该课题的研究具有很广泛的应用领 域和推广价值。 1 3 2 本文结构安排 本文共分为五个章节： 第一章介绍课题研究背景，以及国内外目前对该问题的研究现状。 第二章介绍装箱优化问题的研究基础。主要分析组合优化问题的特点，介绍 本文所涉及的启发式算法和遗传算法。 第三章进行优化模型的建立，并设计优化算法。通过分析装载过程业务和约 束条件，建立装箱优化数学模型，提出三层逐次优化方案( 组合预处理，底层空 间的启发式算法，上层空阃的遗传算法) ，其中重点介绍优化算法流程及其实现过 程。 第四章进行系统设计与实现。分析了集装箱自动装载系统的业务需求，设计 系统的总体结构，结合优化方案进行系统的详细设计，最后输出运算结果。 第五章总结本课题取得的成果，提出需要提高改进的地方。 6 第二章装箱优化问题研究基础 第二章装箱优化问题研究基础 2 1 组合优化问题分析 装箱问题是复杂的离散组合最优化问题。所谓组合优化，是指在离散的、有 限的数学结构上，寻找一个满足给定条件，并使其目标函数值达到最大或最小的 解。一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不 连续的、多维的、有约束条件的、高度非线性的n p 完全问题。 在计算机学中，问题的困难程度是由解题所需的计算时间( 机时) 所决定的。 机时是问题大小的函数。若这个函数为多项式函数，则问题可称为“多项式时间 ( p o l y n o m i a lt i m e ) ”问题；若不是，则称为“非多项式时间”问题，往往被视 作不可解问题“1 。举例来说，设解答大小为1 0 的问题需1us 时间，如果是一个机 时函数为o ( 2 n ) 的“多项式时间”问题，当问题扩大为1 0 0 时，解决需1 0 0 us ； 而如果是一个机时函数为o ( n 2 ) 的“指数时间”问题，问题扩大为1 0 0 后，解题需 3 9 1 0 1 1 世纪。 在“非多项式时间”问题中，有一部分为n p ( n o n d e t e r i n i s t i cp o l y m i a l t i m e ) 完全问题，是指它的答案可以在多项式时间内得以验证。换而言之，若存 在一个先知，告诉了我们问题的答案，我们就可以在多项式时间内验证它。n p 一完 全问题是n p 问题中最重要的子集，任何n p 问题均可以经多项式时间运算后转化 为n p 一完全问题。目前计算机学中许多重大的问题几乎都是n p - 完全问题，为了解 答它们，大小得有所限制，还不得不采用一定的近似，用牺牲精度来换取机时。 装箱问题同许多组合最优化问题，如旅行商问题、图的划分问题等都属于n p 完全问题。此类问题的特点是，随着问题涉及面增加，其计算量将指数性或失控 式地增长。虽然组合优化问题的可行解的数量有限，从理论上讲这种有限问题可 以通过简单枚举找到最优解，然而在实际情况中通常无法实现，随着问题规模的 增大，可行解数量非常多，如果全部验证一遍，计算量太大，运算时间过长。 解决这类问题的主要方法是采用启发式搜索，近年来，遗传算法受到越来越 多的关注，在组合优化问题中表现出很强的优势。当前对装箱优化问题算法的研 究趋势是以遗传算法为基础，结合其他优化算法如简单启发式算法，以到达较好 的优化效果。 电子科技大学硕士学位论文 2 2 启发式算法介绍 2 2 1 启发式算法简介 装箱问题是属于n p 完全问题。7 0 年代末，根据g a r e y 和j o h n s o n ”1 关于n p 完 全性理论的研究表明：在有限合理的时间内，不可能求得大规模n p 完全问题的精 确解，问题的求解通常依赖于各种启发式方法。 启发式算法是和问题求解及搜索相关的，也就是说，启发式算法是为了提高 搜索效率才提出的，1 9 8 4 年p e a r lj 在其专著“h e u r i s t i e s ：i n t e l l i g e n ts e a r c h s t r a t e g i e sf o rc o m p u t e rp r o b l e ms 0 1 v i n g ”中对启发式算法进行了详细的讨论。 他认为：所谓启发式算法是指一组指导算法搜索方向的、建议性质的规则集，通 常按照这个规则集，计算机可在解空间中寻找到一个较好解，但并不能保证每次 都能找到较好的解，更不能保证找到最优解。换句话说，所谓启发式算法就是那 些从大量的实验数据来看，算法的实际计算性能较好，但理论上证明这些算法在 最坏情况下解题性能并不好，或者理论上并不能证明这些算法具有优良的解题性 能。 由于启发式算法的设计不依赖于纯数学中优化理论的突破与发展因此其研 究和应用在最近2 0 多年来获得了突飞猛进的发展。尤其是在复杂的组合优化问 题上，各种各样的启发式算法更是层出不穷，但正是由于启发式算法缺乏严格的 理论推导和数学证明，决定了它的设计具有很强的随意性及创造性。 启发式算法的设计方法分为7 类，分别是： 1 ) 构造法( c o n s t r u c t i o n ) 一个优化问题的解是由若干个构造元素组成的，构造性启发式算法通过一个 一个地增加解的构造元素来求得一个可行解。“贪心法”在每一步都寻找最大的改 进其中包含了大量构造性的启发式算法。在大多数构造性启发式算法中，直到 算法结束才会找到可行解。构造性算法的循环次数与问题解的构造元素个数成正 比，而与解空间的大小无关。因此其计算速度通常很快。 2 ) 改进法( i m p r o v e m e n t ) 该算法从一个可行解开始通过在其邻域内的搜索如交换、合并结构元素等 来改进解的质量。一般来讲，在整个搜索过程中，解一直处于可行状态。将构造 法和改进法组合起来使用是很常见的，首先利用构造法得到初始解，然后利用改 进法搜索邻域内的最优点。这种组合法在所列的文献中非常普遍。 第二章装箱优化问题研究基础 3 ) 数学规划法( m a t h e m a t i cp r o g r a 唧i n g ) 该方法在问题的数学优化模型及其精确求解方法的基础上，修改求解方法以 其得到问题有效的启发式算法。 4 ) 分解法( d e c o m p o s i t i o n ) 该法指求解一系列容易求解的小问题，一个问题的输出是下一个问题的输人， 然后将这些解归纳、合并成一个解。许多规划( s c h e d u l e ) 问题的启发式算法使用 了分解法。 5 ) 分割法( p a n i t l o n i n g ) 分割法将一个问题分割为几个子问题，然后独立地解决每个子问题。这些子 问题的解再合并成整个问题的解。 6 ) 解空间限制法( s 0 1 u t i o ns p a c er e s t r i c t i o n ) 该法的思想是限制解的构造，以便问题变得容易求解。在某种意义上，所有 的启发式算法都是限制法，然而在这里，是指明确地约束解空间的方法。典型的 限制法只允许算法在具有特殊性质的解中搜索。 7 ) 松弛法( r e l a x a t i o n ) 这种方法与限制法相反，它是指为了得到容易处理的问题而扩展解空间。 虽然把启发式算法分成以上7 类，但在实际应用中很难明确划分使用的是某 一种方法。根据开发者的创造性、经验及解题方法的技巧艺术，可能将以上几种 方法结合起来使用。 根据优化机制与行为而分，目前装箱问题中常用的启发式算法主要分为：简 单遗传算法、构造型算法、计算智能算法和混合型算法等。其中计算智能算法包 括：遗传算法、模拟退火算法、禁忌搜索等方法。本文后继章节所提到的启发算 法特指简单启发式算法，并不包括智能算法等其他算法。 2 2 2 启发式算法在装箱问题中的应用 装箱问题中的启发式算法多数以贪心算法为特点，采用了某些简单规则，比 如：次优配合，优先配合或最佳配合”1 。 l i 和c h e n g 在1 9 9 0 年提出了多项式近似算法，利用盒子底部为正方形的特点， 提出了所谓“单元装箱法”，杨传民等人通过全面枚举搜索方法来研究相同大小的 立方体的装箱优化问题。m a n n c h e n 设计的树搜索算法，理论上对三维箱体布局有 效，但由于三维箱体布局属于n p 完全问题，随着布局箱体的增多，解空间急剧膨 电子科技大学硕士学位论文 胀，因而计算效率较低。h g e h r i n g 提出按阶段填充，在深度方向按层布局的启发 式算法，不仅考虑了空间利用率，而且还考虑了重心平衡。王金敏在其基于约束 的布局求解理论与方法的研究中对三维布局问题中的底盘装载问题、约束底盘装 载问题给出了启发式求解方法，研究了布局物体的定序方法、定位方法，以及布 局中的装卸问题。何大勇等则在集装箱布局问题中提出了一种利用三叉树结构表 达三维矩形物体布局状态空间的方法”1 ，将布局空间依次分解，定位规则与定序规 则并用，给出了由计算机随机产生的3 0 个长方体的布局结果，得出了集装箱的利 用率随原始布局长方体的体积与集装箱体积的比值的变化趋势的实验曲线。 在早期研究过程中，随着算法的性能越来越好，实践性也变得越来越差，方 法不易实行。当前，随着遗传算法等智能算法的应用，通常把传统的启发式算法 嵌入遗传算法等智能算法中，来增加搜索能力，从而为装箱问题寻找更接近于最 优解的答案。 2 3 遗传算法介绍 2 3 1 遗传算法的基本概念 遗传算法。1 简称g a ( g e n e t i ca 1 9 。r i t h m ) 是根据生物进化思想而启发得出的一 种全局优化算法。遗传算法的概念最早是由b a g l e yj d 在1 9 6 7 年提出的；而开 始遗传算法的理论和方法的系统性研究的是1 9 7 5 年，这一开创性工作是由 m i c h i g a n 大学的j h h 0 1 l a n d 所实行。当时其主要目的是说明自然和人工系统的 自适应过程。遗传算法在本质上是一种不依赖具体问题的直接搜索方法。遗传算 法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、 生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗 传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年 的计算技术有重大影响的关键技术”。 遗传算法的基本思想0 1 是基于d a r w i n 进化论和m e n d e l 的遗传学说的。d a r w i n 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物 种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。 在环境变化时，只有那些适应环境的个体特征方能保留下来。m e n d e l 遗传学说最 重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含 在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生 1 0 第二章装箱优化问蹶研究基础 的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。 经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在 这个算法中要用到各种进化和遗传学的概念。这些概念如下： 1 ) 串( s t r i n g ) 它是个体( i n d i v i d u a l ) 的形式，在算法中为二进制串，并且对应于遗传学中 的染色体( c h r o m o s o m e ) 。 2 ) 群体( p o p u l a t i o n ) 个体的集合称为群体，串是群体的元素 3 ) 群体大小( p o p u l a t i o ns i z e ) 在群体中个体的数量称为群体的大小。 4 ) 基因( g e n e ) 基因是串中的元素，基因用于表示个体的特征。例如有一个串s = 1 0 1 1 ，则其 中的1 ，o ，l ，1 这4 个元素分别称为基因。它们的值称为等位基因( a l l e t e s ) 。 5 ) 基因位置( g e n ep o s i t i o n ) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的 左向右计算，例如在串s = 1 1 0 1 中，o 的基因位置是3 。基因位置对应于遗传学中 的地点( l o c u s ) 。 6 ) 基因特征值( g e n ef e a t u r e ) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串s = 1 0 1 1 中， 基因位置3 中的1 ，它的基因特征值为2 ；基因位置1 中的1 ，它的基因特征值为 8 。 7 ) 适应度( f i t n e s s ) 表示某一个体对于环境的适应程度。 2 3 2 遗传算法的基本原理及特点 2 3 2 1 遗传算法基本原理 遗传算法1 是一种建立在自然选择和群体遗传机理基础上的自适应概率性搜 索算法，它根据“适者生存，优胜劣汰”等自然进化规则演化而来。与传统搜索 算法不同，遗传算法把优化问题的解的搜索空间映射为遗传空间，把每一可能的 解编码为一个称为染一色体的二进制串( 也有其它编码方法) ，染色体的每一 电子科技大学硕士学位论文 位称为基因。每个染色体( 对应一个个体) 代表一个解，一定数量的个体组成群体。 对群体执行的操作有三种： 1 ) 选择( s e l e c t i o n ) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。 故有时也称这一操作为再生( r e p r o d u e t i o n ) 。由于在选择用于繁殖下一代的个体 时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生 ( d i f f e r e n t i a l r e p r o d u c t i o n ) 。 2 ) 交叉( c r o s s o v e r ) 这是在选中用于繁殖下代的个体中，对两个不同的个体的相同位置的基因 进行交换，从而产生新的个体。 3 ) 变异( t a t i o n ) 这是在选中的个体中，对个体中的某些基因执行异向转化。例如在串s = 】o l l 中，第二位位基因为o ，产生变异时就是把它变成1 ；反亦反之。 遗传算法的重要参数介绍： 1 ) 交叉和变异的概率： 交叉的概率是说交叉行为发生的几率大小，如果几率为o ，那么子代就完完全 全和父代一样。如果存在交叉，子代的基因就由几个父代的基因的中的片段组合 而成的，所以就不完全和父代一样。如果交叉1 0 0 的发生，那么所有的子代都是 由交叉产生的。如果交叉的概率为o ，那么子代就是父代的完全复制。但是，这 并不意味着子代就和父代完全一样，交叉过程的目的就是希望新的基因是由旧的 基因中好的部分组合而成的，从而新的基因比原先的基因要好。当然把旧的种群 中的一部分基因完全保留到下一代中去也是很有意义的。 变异的概率说的是基因的某些部分发生变异的概率。如果没有变异的话，子 代就和交叉过的父代没有任何区别。只要存在变异，子代的基因就会发生改变。 如果变异的概率为1 0 0 ，那么所有的子代都会改变。如果变异的概率为o ，那 么子代就不会改变。变异的目的是为了防止遗传算法的解跑到局部极值点，所毗， 变异应该发生。但是变异不能发生的太频繁，否则的话就变成了随机搜索了。 2 ) 其他一些参数 遗传算法中还有一些其它参数，比如说种群的大小就是一个很重要的参数。 种群的大小是说每一代种群中所含基因的多少。如果其中的基因太少，则遗传算 法中进行交叉操作的机会就越少，所以导致我们的算法只是考察了搜索空间的一 部分。另一方面，如果基因太多，则遗传算法的速度就会变慢。进一步的研究表 第二章装箱优化问题研究基础 明，在一定的条件下( 这些条件主要由问题本身和编码方法决定) 增大种群的大 小是没有意义的，因为它不会加快遗传算法的计算速度。 2 3 2 2 遗传算法特点 为了解决各种优化计算问题，人们提出了各种各样的优化算法，如单纯形法、 梯度法、动态规划法、分枝定界法等。这些优化算法各有各的长处和限制，有各 自不同的适用范围。与普通的搜索算法( 如梯度算法) 一样，遗传算法也是一种迭 代算法。“。但是与其他一些优化搜索算法。2 午目比，遗传搜索要求两个存在明显冲 突的方向的平衡：挖掘( e x p l o i t a t i o n ) 最优解和探测( e x p l o r a t i o n ) 搜索空间。爬 山法( h i l lc 1 i m b i n g ) 是尽可能地改进挖掘最优解策略的例子，但它忽视了对搜 索空问的探测。随机搜索( r a n d o ms e a r c h ) 是一个注重探测搜索空间而忽视挖掘最 优解的典型例子。遗传算法则是在总体上寻求挖掘和空间探测之间的平衡的一类 算法。 遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法。与其他一些优化 算法相比，它主要有下述几个优势： 1 ) 遗传算法以决策变量的编码作为运算对象( 函数优化中有时也采用决策变 量本身作为运算对象，可以视为简单的代数编码) 。传统的优化算法往往直接利用 决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的值， 而是以决策变量的某种形式的编码为运算对象这种对决策变量的编码处理方式， 使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自 然界中生物的遗传和进化等机理，也使得我们可以方便地应用遗传操作算子。特 别是对一些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处 理方式更显示出了其独特的优越性。 2 ) 遗传算法直接以目标函数值作为搜索信息，并不利用梯度信息，无需求导 运算。传统的数值优化算法不仅需要利用目标函数值，而且往往需要目标函数的 导数值等其他一些辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值 变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需目标函数 的导数值等其他一些辅助信息。这个特性对很多目标函数是无法或很难求导数的 函数，或导数不存在的函数的优化问题，以及组合优化问题等，应用遗传算法时 就显得比较方便。因为它避开了函数求导这个障碍。再者，直接利用目标函数值 或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间 中，从而提高了搜索效率。 电子科技大学硕士学位论文 3 ) 遗传算法同时使用多个搜索点的搜索信息，是一种群体优化过程。传统的 优化算法往往是从解空间中的一个初始点开始，进行最优解的迭代搜索。单个搜 索点所提供的搜索信息毕竟不多，虽然搜索效率较高，但容易使搜索过程陷于局 部最优解而停滞不前。遗传算法从由很多个体所组成的一个初始群体开始最优解 的搜索过程，而不是从一个单一的个体开始搜索。对这个群体所进行的选择、交 叉、变异等运算，产生出的乃是新一代的群体，在这之中包括了很多群体信息。 这是遗传算法所特有的一种并行性。 4 ) 遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定性的 搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这 种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的应用范 围。而遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是 以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这种概率特 性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群体 中总会更多地产生出许多优良的个体，实践和理论都己证明了在一定条件下遗传 算法总是以概率1 收敛于问题的最优解。当然，交叉概率和变异概率等参数也会 影响算法的搜索效果和搜索效率，所以如何选择遗传算法的参数在其应用中是一 个比较重要的问题。而另一方面，与其它一些算法相比，遗传算法的鲁棒性又会 使得参数对其搜索效果的影响会尽可能地低。 根据以上分析，总结遗传算法的特点如下： 1 ) 遗传算法是对参数的编码进行操作，而不是参数本身。 2 ) 遗传算法是从许多初始点开始并行操作，而不是从一个点开始，因而可 以在一定程度上防止搜索过程收敛于局部最优解，求得全局最优解。 3 ) 遗传算法是通过目标函数来计算适配值，而不需要其它的推导和附属信 息，从而对问题的依赖性较小。 4 ) 遗传算法使用概率的转变规则，而不是确定性的规则。 5 ) 遗传算法在解空问内不是盲目的穷举或完全的随机测试，而是一种启发 式的搜索，其搜索效率往往优于其他方法。 6 ) 遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，更不要 求可微。 7 ) 遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算 速度。 第二章装箱优化问题研究基础 2 3 3 遗传算法的步骤 遗传算法的通常按照以下步骤来实施： 1 ) 初始化 选择一个群体，即选择一个串或个体的集合b i ，i = 1 ，2 ，n 。这个初始的 群体也就是问题假设解的集合。一般取n = 3 0 1 6 0 。通常以随机方法产生串或个 体的集合b i ，i = 1 ，2 ，n 。问题的最优解将通过这些初始设解进化而求出。 2 ) 选择 根据适者生存原则选择下代的个体。在选择时，以适应度为选择原则。适 应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数f ，则f ( b i ) 称为个体b i 的适应度。为选中b i 为下一代个体的次数