（计算机软件与理论专业论文）遗传算法在物流业装箱环节中的应用研究.pdf

山东大学硕士学位论文 摘要 随着社会经济和i n t e r n e t 技术的飞速发展，物流成为人们生活中不 可缺少的一部份，作为一种新兴且先进的技术，它越来越显示出其在 社会经济发展中的重要作用。物流过程是一个企业在创造利润的过程 中比较重要的环节。所以在这个环节中最大限度地降低企业投入，可 为企业降低不少成本。而在物流过程的各环节中，物品装箱是一个必 不可少的，在此环节中为了节省开支，最大程度地利用资源，存在诸 多要求，例如：如果采用的是同一尺寸的纸箱，在装下所有物品的前 提下，所用箱子数量越少越好。这就是著名的装箱问题。传统的工作 方法主要是工人根据自己的判断而进行的，并没有技术支持，其结果 往往不是最优的。 本文从实际出发，在调研了国内外大量文献的基础上，全面研究 了装箱问题。其中主要是对一维装箱问题和二维装箱问题进行了讨论 和研究。而对于三维装箱，只做了简单的概念性的介绍。所做的工作 主要包括一下几个方面： 首先，在详细介绍了各类装箱问题( 一维装箱问题、二维装箱问 题、三维装箱问题) 及其研究现状，并阐述了目前国内外对于装箱问 题的研究方法。 接着在对遗传算法的基本思想和实现机理进行了介绍，提出了用 遗传算法的思想求解装箱问题。 然后，针对一维装箱问题，利用基本遗传算法s g a 的思想进行了 问题求解。由一维装箱问题，论文进一步延伸到二维装箱问题。二维 装箱问题有很多提法，论文主要研究了条形装箱问题，论文中首先对 现有的自由落体算法进行分析，并对该算法进行了改进，并尝试把改 进后自由落体算法和遗传算法相结合来求解二维装箱问题。 由于装箱问题的自身的复杂性决定了精确求解是很困难的，在很 多情况下，精确求解也是不必要的，因此研究的重点一般在于如何尽 山东大学硕士学位论文 快的找到一个满意解。 论文中所提出的几种主要算法均通过了实际数据的验证，希望在 今后的实际工作能够将其运用实践，为企业带来效益。 关键词：物流；装箱问题；遗传算法：条形装箱；自由落体算法 i i 山东大学硕士学位论文 a b s t r a c t t h et r a n s m i s s i o na n dd i s p a t c h i n gi nl o g i s t i c ss y s t e ma r et h eh o t i s s u e sc o n c e r n e db yp e o p l ei nt h ef i e l da n dt h er e l a t e dr e s e a r c h e r s h o w t oe f f e c t i v e l yi m p r o v et h ec a r r y i n gc a p a c i t yo ft r a n s p o r t a t i o ni so n eo ft h e k e yf a c t o r so fi n c r e a s i n gt h ee f f i c i e n c yo ft r a n s p o r t a t i o na n dr e d u c i n gt h e c o s to ff l o wo fm a t e r i a l ，w h i c hi sc o n c l u d e da so n ed i m e n s i o n a lb i n p a c k i n gb ya c a d e m i cf i e l d i t sr e t u r n sa r ew i d e l ya p p l i e di nt h er e a ll i f e m yp a p e ra i m st oc a r r yo u tt h er e s e a r c ho fo n ed i m e n s i o n a lb i np a c k i n g f r o mt h ep r a c t i c a lp e r s p e c t i v e i te n d sw i t ht h es t u d yo ft w od i m e n s i o n a l b i np a c k i n ga n di t sa p p l i c a t i o ni n c l u d e sm a t e r i a lc u t t i n gp r o b l e m s ( s u c ha s c u t t i n gw o o do rg la s s ) ，d r e s sc u t t i n g ，p a c k i n g ，c i r c u i tb o a r dd e s i g n ，t y p e s e t t i n g ，e t c b e c a u s et h ec o m p le x i t yo fb i np a c k i n gl e a d st ot h ed i f f i c u l t yo f p r e c i s eu n n e c e s s a r yi nm a n ys i t u a t i o n ，t h ep o i n tw i t h as a t i s f a c t o r y s o l u t i o na ss o o na sp o s s i b l e t h ep a p e rf ir s t l yd i s c u s s e so p t i m i z a t i o no fc o m b i n a t i o na n dt h e b a s i cr e a l i z i n gm e c h a n i s mo fg e n e t i ca l g o r i t h m ，t h e np u t sf o r w a r d h y b r i dg e n e t i cc o m b i n e db fa l g o r i t h ma n dg e n e t i ca l g o r i t h mt o g e t h e r w i t ho n ed i m e n s i o n a lb i np a c k i n ga n dt h e np r o v e si t sp r i v i l e g et og e n e t i c a l g o r i t h mo fp e n a l t yf u n c t i o na n db f da l g o r i t h mb ya c t u a ld a t a o p e r a t m n l a t e rt h ep a p e re x p a n d so n ed i m e n s i o n a lb i np a c k i n gf u r t h e rt ot w o d i m e n s i o n a lb i np a c k i n g t h e r ea r em a n yw o r d i n g so ft w od im e n s i o n a l b i np a c k i n g t h ep a p e rm a i n l yd i s c u s s e st r i pb i no fb o t t o ml e f t a l g o r i t h ma n df a l lf r e ep a c k i n gp r o b l e m a f t e ra l g o r i t h m ，t h ep a p e rp u t s f o r w a r di m p r o v e df a l lf r e ea l g o r i t h m ，w h i c hm a i n l yb r i n g sf o r w a r dt h e c o n c e p to fc o m b i n e da r e aa n dt h el e a s tw a s t e da r e a i tt r i e st oc o m b i n e i i i 山东大学硕十学位论文 i m p r o v e df a l l f r e ea l g o r i t h mw i t hg e n e t i ca l g o r i t h mt o e x p l a i nt h e a d v a n t a g eo fi m p r o v e df a l lf r e ea l g o r i t h mt of a l lf r e ea l g o r i t h mb y a c t u a ld a t ao p e r a t i o na n dt r i e st oe x p l a i nt h er e a s o n i na d d i t i o n ，t h e r ei st h r e ed i m e n s i o n a lb i np a c k i n gp r o b l e m b e c a u s e t h i sk i n do fp r o b l e mi sm o r ec o m p l i c a t e da n dt h ea u t h o r st i m ei sl i m i t e d ， t h ep a p e ro n l yi n t r o d u c et h ep r o b l e ma n di t ss t u d y i n gs t a t u ss i m p l yi n d o c u m e n ts u m m a r i z a t i o n ，a n dd o n tc a r r yo nr e s e a r c ht ot h i sp r o b l e ma n d p u tf o r w a r das o l u t i o n t h em a i na l g o r i t h m sp u tf o r w a r di nt h i sp a p e rh a v eb e e np r o v e db y a c t u a ld a t ao p e r a t i o n ih o p et h e yc a nb eu s e di np r a c t i c ea n db r i n gp r o f i t f o rt h ee n t e r p r i s e s k e yw o r d s ：l o g i s t i c ss y s t e m ； o n ed i m e n s i o n a lb i np a c k i n g ； g e n e n e t i ca l g o r i t h m ；f a l lf r e ea l g o r i t h m 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：墨垂硷日期：丝丝笙幽 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：圣垂丝! 导师签 ：卯口啪r 山东大学硕士学位论文 1 1 课题的研究背景 第1 章引言 随着社会经济的飞速发展，物流业已成为我国重要的产业之一。 物流过程也越来越复杂，在物流过程的各环节中如何最大限度地利用 资源、节省开支已经成为亟待解决的问题之一。在物流过程的各环节 中，集装箱货运站也是一个比较重要的环节，它负责备箱、配箱、装 箱，被认为是二十一世纪企业降低成本的最后手段。而在其中的装箱 环节中，降低装箱成本对整个物流过程最优化利用资源起着举足轻重 的作用。如何降低装箱成本? 这就是著名的装箱问题，即找出最优的 装箱方案，使得在装下所有物品的前提下，所用箱子数量最少。以此 来节省成本，达到最大化利用资源的目的。 七十年代中期，遗传算法( g e n e t i ca l g o r i t h m ) 由美国m i c h i g a n 大学的j o h nh o l l a n d 教授提出。这是一类借鉴生物界的进化规律( 适 者生存，优胜劣汰，遗传机制) 演化而来的随机化搜索方法。它是一 种有效的解决最优化问题的方法。遗传算法作为人工智能领域比较热 门的话题之一，已被广泛应用于各种领域。用遗传算法的思想来解决 物流业中的装箱问题是值得研究的。论文选题由此而来。 本文就物流过程中的装箱环节进行了分析，针对其中存在的一维 装箱、二维装箱问题进行分析并利用遗传算法的基本思想进行了求解。 1 2 遗传算法的研究历史与现状 遗传算法是美国著名科学家j o h nh o l l a n d 教授于七十年代中期 首先提出来的，该算法是从生物进化的过程中得到灵感与启迪，模拟 大自然中“物竞天择，适者生存”的自然选择法则而创立。在当时， 由于计算机的发展水平低，容量小，计算速度慢，而遗传算法计算量 山东大学硕士学位论文 大，需要存贮的信息多，难以实际应用，因而没有得到重视。但h o l l a n d 与他的学生们直坚持不懈地努力，进行了大量的理论研究并致力于 开拓应用领域八十年代中期以来，由于计算机容量和计算速度的不断 提高，以及遗传算法本身的逐步成熟，它引起了国际学术界的普遍重 视，得到了迅速地发展。现在，其应用遍布于计算机科学、物理科学、 社会科学、图象处理、企业经营、生产管理、土木工程和电力工程等 领域。遗传算法还可以应用于科学研究和工程实际的各种搜索过程和 优化问题，它能较有效地求解常规优化方法难于解决的组合优化问题 和复杂函数优化问题，因此适用范围极广。 6 0 年代，是遗传算法研究的起步阶段。简单的遗传算法被提出， 但它们缺乏求解问题相关的特定问题，它们未被设计用于求解特定类 型的问题。 7 0 年代，是关于遗传算法发展的经验探索阶段。遗传算法被用来 解决两类主要问题，其一是设计出针对特定问题的求解系统，其二就 是理解这些系统是如何求解问题的。我们知道在实现遗传算法时，选 择群体的数目、内部的遗传表达以及所采用的遗传算子，对于算法的 运行效果有很大的影响。通过这一阶段的探索，人们对遗传算法的自 适应特性有了较好的理解，积累了一定的经验，为遗传算法的发展奠 定了良好的基础。 进入8 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还 是应用研究都成了十分热门的课题。尤其是遗传算法的应用领域也不 断扩大，主要领域有自动控制、规划设计、组合优化、图象处理、信 号处理、人工生命等。可见，遗传算法的应用研究已从初期的组合优 化求解拓展到了许多更新、更工程化的应用方面。 随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新 动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法 从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功 能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知 识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益 和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和 2 山东大学硕士学位论文 结合，这对开拓21 世纪中新的智能计算技术将具有重要的意义。三是 并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身 的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。 四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。遗 传算法在此领域将会发挥一定的作用。五是遗传算法、进化规划以及 进化策略等进化计算理论日益结合。进化规划以及进化策略几乎是和 遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然 界生物进化机制的智能计算方法。目前，这三者之间的比较研究和彼 此结合的探讨正形成热点。 人们开始认识到，对h o l l a n d 的基本遗传算法的改进后，可大大改 变了遗传算法的特性。因而对于有关遗传算法一些基本假设有待进一 步改变，以求得关于遗传算法的研究和应用能进一步深入。 至今，遗传算法得到了更广泛的应用，有的还与其他算法相结合 来解决现实中存在的问题。例如：有人把模拟退火算法与遗传算法相 结合提出了一种解决一维装箱问题的方案等等。 1 3 遗传算法在物流业各环节中应用的研究情况 目前遗传算法无论理论研究还是在应用研究上都得到了飞速的发 展，已经成为人工智能领域比较热门的话题之一。应用领域也比较广 泛，包括：自动控制、规划设计、组合优化、图象处理、信号处理、 人工生命等。在物流业各环节中也得到了广泛的应用，大多是用来进 行求解优化方案。例如：物流业装箱环节中的应用、物流配送车辆路 径优化问题研究、物流系统运输优化问题研究、供应链物流能力优化 模型、物流卸箱作业优化算法研究、基于遗传算法的物流配送系统的 设计与实现、基于遗传算法的物流配送车调度优化算法等等各方面多 个环节。下面列举以下遗传算法在国内物流业中应用的情况： 贾福龙、唐吉洪3 1 等运用基于精英个体的二次遗传、自适应的混 合遗传算法来改进传统遗传算法，提出了一种解决物流配送系统优化 的重要组成部分之一一一车辆路径问题的方案，该方案能够以较大的 概率得到质量更优的满意解，从而降低了物流业中的车辆运输成本。 山东大学硕士学位论文 杜波、何世伟“引等从全局的角度建立了以制造商为核心的供应链 整体利润的物流能力优化模型，并结合混合遗传算法加以计算，求出了 最优配置方案。 谭前进、林和平钉等提出了利用遗传算法解决物流中车辆调度的 优化方案，此方案对解决大规模客户的物流配送获得了良好的效果。 证明了遗传算法在解决诸如车辆路径问题确实具有优良的性能。但在 求解大规模客户群的配送问题时，搜索过慢，这也是简单遗传算法的缺 陷之一。 当然遗传算法在物流中的装箱环节得到了更为广泛的应用，例如， 武晓今、朱仲英佰5 1 等提出了一种基于b l 算法和g a 算法相结合来解决 二维装箱问题的解决方案。程浩、刘心报 5 6 1 等用单亲遗传算法进行了 一维装箱问题的求解并取得了不错的效果。陈迎春、吴晓平5 7 1 等用混 合遗传算法对约束型装箱问题进行了求解。江宝钏等 5 8 1 设计了一个混 合遗传算法，从而对三维集装箱装箱问题进行了求解，这个算法继承 了遗传算法的全局搜索好的优点，也克服了遗传算法局部搜索能力差 的缺点，能够较好地解决集装箱这类多目标多约束的三维装箱问题。 由此可见，遗传算法在物流业中得到了非常广泛的应用，国内外 也出现了很多研究成果，但鉴于遗传算法自身仍存在一些缺陷，比如， 早熟收敛问题、对于大规模群体搜索速度慢问题等等，故在物流业中 具体实践运用的比较少。遗传算法在物流业中的应用还有待进一步研 究。 1 4 本文的研究内容 物流业中装箱环节是一个重要的环节之一，在此环节中如何最大 化的利用各种资源、节省开支，对整个物流过程的优劣起着举足轻重 的作用。本论文对此环节中存在的各种装箱问题进行了分析，并提出 了利用遗传算法进行求解的方案。包括对一维装箱问题的求解、二维 装箱问题的求解等等。从而为最大化的节省装箱环节的装箱成本提供 参考。 4 山东大学硕士学位论文 m n umu n _nn_n _ n 鼍量皇量皇曼舅舅 1 5 本文的内容组织 本文第二章详细介绍了各类装箱问题( 一维装箱问题、二维装箱 问题、三维装箱问题) 及其研究情况。并阐述了目前国内外对于装箱 问题的研究方法。 第三章中对遗传算法的基本思想和实现机理进行了介绍，提出了 用遗传算法的思想求解装箱问题。 在第四章内容中，针对一维装箱问题，利用基本遗传算法s g a 的 思想进行了问题求解。根据一维装箱问题，论文进一步延伸到二维装 箱问题，二维装箱问题有很多提法，论文主要研究了条形装箱问题， 论文中首先对现有的自由落体算法进行分析，并对自由落体算法进行 了改进，并尝试把改进后自由落体算法和遗传算法相结合来求解二维 装箱问题。 最后对全文进行总结，并对今后的工作提出一些设想。 山东大学硕士学位论文 2 1 装箱问题简介 第2 章装箱问题 装箱问题是指将不同尺寸的物品摆放入有一定容量的容器中，以 获得某种最佳的效益。装箱问题是一个具有复杂约束条件的组合优化 问题n - 引，在理论上属n p h a r d 问题，其求解是极为困难的。所谓组 合优化，是指在离散的、有限的数学结构上，寻找一个满足给定条件， 并使其目标函数值达到最大或最小的解。一般来说，组合优化问题通 常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有 约束条件的、高度非线性的n p 完全问题。装箱问题也不例外，同许多 组合最优化问题，如旅行商问题、图的划分问题等一样属于n p h a r d 阳1 问题。经典的装箱问题要求把一定数量的物品放入容量相同的一些箱 子中，使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱 子数目最少。 装箱问题到现在已有百余年的历史，但迄今尚无成熟的理论和有 效的数值计算方法。由于目前n p 完全问题不存在有效时间内求得精确 解的算法，装箱问题的求解极为困难，因此，从7 0 - 8 0 年代开始，陆 续提出的装箱算法都是各种近似算法，如下次适应、首次适应、降序 下次适应和调和算法等1 。 装箱问题早己在实际生产、生活中显示出重要的应用价值，它广 泛存在与生产和生活中，包括线料类( 如钢筋) 、板类( 例如金属板，木 板，玻璃大理石) 、切割行业，服装裁剪行业等中的下料问题；运输业 中的装卸货物，建筑业中的房间布局；工业中的模板布局、新闻报纸、 广告等版面设置，集成电路分别图设计及其他一些工程设计等。而且 一系列装箱问题的衍生问韪也逐步被关注和研究，如箱子覆盖问题， 最大基数装箱问题和最小基数箱子覆盖问题装箱问题的研究文献分 布面很广，在运筹学、计算机辅助设计、计算机图形学、人工智能、 图像处理、大规模集成电路逻辑布线设计、计算机应用科学等诸多领 6 山东大学硕士学位论文 鼍皇曼鼍量舅皇皇曼皇量皇皇量量曼量量量皇皇_ ml _ i 量曼量量皇鼍寡鼍量皇量鼍| 曼皇曼皇曼罾量曼鼍曼量曼量皇量置一 域都有装箱问题最新的研究动态和成果出现，这足以证明了装箱问题 的应用前景日趋广泛而重要。 2 2 装箱问题的分类 随着经济的不断发展，装箱问题在生产实践中广泛出现，已涉及 到现实生活中的方方面面，也涉及到多学科、多领域的知识。下面我 们从不同角度对装箱问题进行分类： 2 2 1 按照装箱物体所述装箱空间对装箱问题的分类 一、一维装箱问题 直观而言，一维装箱问题是如下问题：设有足够多同样大小( 尺寸) 的空箱子，容积皆为1 。现有n 个物体u = “，材：，。 ，其大小( 尺寸) 皆小于等于1 ，即每一件物体玑均可以放入到任一个空箱中。所考虑的 问题是要寻求一种装法，使得可以用最少数目的箱子将n 个物体 u = 扣。，：，材。) 全部装下( 要求每个物体不得超出箱子之外) 。上述是 经典一维装箱问题，但生产实践中存在着各种异于上述的装箱问题。 例如工厂零件加工耗时最少问题，装配线问题，背包问题等等。 目前，一维装箱问题的求解算法主要是一些近似算法，如n f ( n e x t f i t ) 近似算法，f f ( f i r s tf i t ) 近似算法，f f d ( f i r s tf i td e c r e a s i n g ) 近似算 法，b f ( b e s tf i t ) ，b f d ( b e s tf i td e c e a s i n g ) 等。表1 列出了部分著名一 维装箱问题近似算法的研究现状n 引。 山东大学硕十学位论文 表1 经典一维装箱问题的几种著名近似算法 t a b l e1s e v e r a lf a m o u sa p p r o x i m a t ea l g o r i t h m so ft y p i c a lo n e d i m e n s i o n a lb i np a c k i n gp r o b l e m 从表中可以看出，b f 是较优的在线算法，b f d 是较优的脱线算法。 现实中，这两种算法是经常采用的算法。 二、二维装箱问题 二维装箱问题有下述两类阳1 ： 1 ) 给定n 个矩形l = a l , a 2 a 。l ( 其中a i = ( x i , y i ) ；x i , y i ( 0 ，1 1 ， i = l ，2 n ) 装入一宽度为l ，高无限大的矩形a ( 箱子) ，要求将n 个矩形 a l , a ：a 。互不叠迭地装填入a 中，使布局的总高度最小。对每个小矩形 a ；装填入a 后的姿态也有直角装填，定向等限制； 2 ) 给定n 个矩形l = a 。，a ：a 。l 及无限多大小都相等的大矩形( 箱 子) ，要求将铂，a 2 a n 直角定向莓填入箱子中，使所占用的箱子个数最 少。 对第一类二维装箱问题，若设小矩形的高度都相等，限制装填方 式为直角定向，则问题蜕化为一维装箱问题；对第二类问题若设小矩 形之宽与箱子宽相等，也退化为一维情形。 二维装箱问题的研究，主要从实际工作的角度出发，如应用于板 类( 金属板，木板，玻璃、大理石板等) 切割行业，服装剪裁行业等中 的下料问题；建筑业中的房间布局，工业中的模板布局、新闻报纸、 广告等版面布置，集成电路布图设计及其它一些工程设计等虽然也有 些理论成果，但是并不太深入，主要是问题太难，使人无从下手。 【i j 东大学硕士学位论文 三、三维装箱问题 与二维装箱问题相似，三维装箱问题也有下述两种形式阳3 ： 1 ) 给定n 个矩形体l = a l , a 2 a 。 ( 其中a i = ( x i , y i ，z i ) ；) 【i ，y i ，弓( o ，1 】， i = 1 ，2 n ) 装入一底为1 1 ，高为正无穷的柱形箱子a ，要求将n 个矩形 体a 】，a 2 a n 互不叠迭地装填入a 中，使布局的总高度z 最小。对每个矩 形体a ：装填入a 后的姿态也有直角装填，定向等限制。 2 ) 给定n 个矩形体a l ，a l 2 a i l 及无限多大小都相等的箱子，要求 a l , a ：a 。直角定向装填入箱子中，使所占用的箱子个数最少。 对第一类三维装箱问题，若设矩形体的高度都相等，限制装填方 式为直角定向，则问题蜕化为二维装箱问题；对第二类问题若设矩形 体之宽与箱子宽相等，也退化为二维情形。因此三维装箱问题可以看 作是一维、二维装箱问题的一个泛化一们。 2 2 2 按照装箱物体的形状对装箱问题的分类 一、规则物体的装箱 又可分为二维规则物体的装载和三维规则物体的装载。规则物体 是指具有规则外形的物体，例如圆柱体、矩形体等。在以前及现在的 装载研究中，研究较多的仍然是规则体的装载问题，如：工业应用中 的底盘装载问题；三维布局中的集装箱的货物摆放问题等等。 二、不规则物体的装箱 包括二维不规则物体的装载和三维不规则物体的装载。不规则物 体是指具有任意几何形状的物体。不规则物体的装箱问题在工业生产 中大量存在，但同时也是难度最大的装箱问题。如服装样本的下料、 皮革下料、如向具有任意几何形状的容器中放置任意几何外形的装箱 物体，并满足特定的约束条件等等。 另外，根据待装物品的到达顺序，又可将装箱问题分为在线装箱 问题和离线装箱问题；按照装载过程是否有惩罚值，可将装箱问题分 为带拒绝装箱问题和不带拒绝装箱问题等等。并且随着装箱问题在实 际中的不断应用，出现了许多装箱问题的变形问题，例如：向量装箱、 带装箱、条形装箱、盒装箱、变尺度装箱等。 9 山东大学硕士学位论文 2 3 装箱问题的研究情况及方法 截止到目前，装箱问题的研究工作都是集中在一维、二维装箱问 题的解决方案上而不是三维。部分原因归结于一维、二维装箱问题有 着大量的实际应用背景，同时也归结为三维装箱问题的复杂性上。一 维、二维装箱问题已经是n p c o m p l e t e 问题，同样三维装箱问题也是。 对三维装箱问题的研究大都没有给出能够实际应用的具体算法，某些 算法也存在一些限制，如计算量过大、排列没有规则等，而且主要都 是基于空间分解或层的思想；目前国内较好的装箱软件几乎寥寥无几。 对于装箱问题，求解方法主要有数学规划法、象域模型、 图论 算法、形态与形态法则、优化算法、数值优化方法、模拟退火、启发 式算法、遗传算法等等。其中遗传算法是通过模拟生物进化的过程来 求解复杂的优化问题h l4 2 1 的一种方法。由于利用了交叉和变异等遗传 算子，该方法的求解范围可以遍布整个解空间，有可能求出全局最优 解。遗传算法根据适者生存、优胜劣汰等自然进化规则，一代一代的 优选适应性能评价函数的参数，重组后构成新的参数组合。与许多传 统的搜索算法不同，遗传算法在搜索最佳组合时间时考虑搜索空间中 的多个点，而非仅考虑一个点该算法使用参数集的数字串作为工作模 式二不直接使用参数本身。他的缺陷是处理大规模的连续变量有困难， 因而一般需要与其它方法组合实用。本文中正是基于此算法对装箱问 题进行求解。 z 4 遗传算法在装箱问题中的应用情况 早在19 8 4 年就有学者将遗传算法应用于求解装箱问题。但是对于 装箱问题这类离散的组合最优化问题，往往无法直接采用简单遗传算 法进行求解。一般来说，遗传算法对解的编码方案大多采用二进制编 码形式，但是对于装箱这类排序问题显然是行不通的，一是物品的坐 标用二进制表示编码太长，会导致搜索空间急剧扩大，算法性能降低， 二是坐标值的调整变化描述了待布入物品本身位置的改变，可能会出 现待布入物品交叉的现象，而处理交叉问题计算量特别。并且经典的 山东大学硕士学位论文 量| 鼍曼皇量鲁l 鲁曼曼鲁量量皇量量曼皇量曼量皇曼鲁量曼曼量皇曼量量曼皇曼量薯量皇喜蔓皇曼皇曼喜皇置量量皇鲁皇璺曼曼曼舅量量量皇量量舅 交叉、变异操作常会产生无意义的解。因此，必须对简单的遗传算法 进行适当的改进以适应装箱问题的特殊情况。到目前为止，已经有多 种改进后的遗传算法，例如：小生境遗传算法、自适应遗传算法、并 行遗传算法、混合遗传算法等。其中混合遗传算法就是将g a 与其它启 发式的搜索算法相结合，从而弥补单一优化方法的某些不足之处。比 较常见的混合遗传算法有：模拟退火遗传算法、免疫遗传算法、模糊 遗传算法、混沌遗传算法、量子遗传算法等。 此外为了提高遗传算法的收敛性和性能，还可以和其他优化算法 集成使用或引入新的进化机制。 山东大学硕士学位论文 第3 章算法的理论基础 本文中对装箱问题的求解是基于遗传算法的，遗传算法( g e n e t i c a l g o r i t h m ) 是一类借鉴生物界的进化规律诸如：适者生存，优胜劣汰， 遗传机制等演化而来的随机化搜索方法。它是一种有效的解决最优化 问题的方法。它主要由美国m i c h i g a n 大学的j o h nh o l l a n d 教授提出， 并进一步研究发展，从而最终形成遗传算法理论与应用基本框架。遗 传算法作为现代有关智能计算中的关键技术之一，已被人们广泛地应 用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。 3 1 遗传算法中的概念 在遗传算法中，借用了很多生物学中的术语，理解这些术语在遗 传算法中的意义对于理解遗传算法很有帮助。这些概念如下： 一、基因1 ( g e n e ) 在生物学中，基因是基本的遗传单位。生物的基因根据物种的不 同而数量不一，一些小的病毒只含有几个基因，而高等动、植物的基 因却数以万计。在生物学与遗传算法中，基因都是染色体的基本组成 单元。 二、染色体3 1 ( c h r o m o s o m e ) 染色体一般由多个基因组成，是遗传物质的主要载体。即使组成 染色体的基因完全相同，如果其排列不同，则构成的染色体也是不同 的。在遗传算法中，染色体是待优化问题的解的一种表现形式。 三、个体3 1 ( i n d i v i d u a l ) 在生物学中，个体是带有染色体特征的实体。例如，一只鸡，一 条狗，一匹马等等。它们之所以不同，是因为它们的染色体不一样。 在遗传算法中，个体代表待优化问题的一个解。在生物界中，可能由 很多染色体共同决定一种生物个体的特征，但是，在遗传算法中，个 体的特征很可能由一条染色体决定。因此，在遗传算法中，有时候， 个体与染色体在某种程度上是等价的，即一个个体与一条染色体是相 l l j 东大学硕士学位论文 同的，都可以看成是问题的一个解。 四、适应度3 1 ( f i t n e s s ) 俗话说：“适者生存”。何谓“适? 生物学中是使用适应度这个 术语来度量某个物种对于生存环境的适应程度的。对生存环境适应度 较高的物种将获得更多的繁衍机会，而对生存环境适应度较低的物种， 其繁衍机会较少，甚至逐渐灭绝。在遗传算法中，适应度被用来度量 解( 个体、染色体) 的优劣程度。越接近最优解的解，其适应度越高， 反之，其值越低。 五、种群阳3 1 ( p o p u l a t i o n ) 生物的遗传进化不能仅通过自身进行，而需要在一个群体中进行， 这一群体即称为种群。种群中的单个成员称为个体。种群规模是遗传 算法的参数之一，种群规模的设置可能会影响到遗传算法的优化效果。 种群规模太小，则使种群缺乏多样性，从而影响到遗传算法全局搜索 的能力：种群规模太大，则遗传算法易退化成随机搜索。一般取值为 2 0 1 0 0 。 六、代阳33 ( g e n e r a t i o n ) 在生物的繁衍过程中，个体从出生到死亡即为一代，在遗传算法 中，代的意义为遗传算法的迭代次数。可以指定遗传算法运行时的最 大迭代次数，即代数可以作为遗传算法的一个结束标志。代数一般视 具体问题而定，一般取值为1 0 0 5 0 0 。 七、遗传型m 3 ( g e n o t y p e ) 基因组合的模型被称为遗传型。它是染色体的内部表现，又称为 基因型。在遗传算法中，遗传型即为染色体的编码形式。 八、表现型拈3 1 ( p h e n o t y p e ) 根据遗传型形成的个体称为表现型，在遗传算法中即为问题解空 间中的解 九、编码与解码3 1 ( c o d i n ga n dd e c o d e ) 将问题的解转换成基因型的过程称为编码，编码是由问题空间到 遗传算法空间的映射。反之，将基因型转换成问题的解的过程称为解 码。一般情况下，个体与它所代表的问题的解之间存在一一对应的关 山东大学硕士学位论文 系。在遗传算法中，首先需要将问题的解编码成基因型，在需要确定 染色体的优劣时，再将其解码到解空间进行评估。遗传算法的一个特 点是它只在编码空间对染色体执行遗传算子，而在解空间对解进行评 估和选择。 十、遗传算子钉( g e n e t i co p e r a t o r s ) 遗传算子指作用在染色体上的各种遗传操作。虽然在遗传算法的 发展过程中，产生了一些特殊的遗传算子，例如免疫算子。但是在几 乎所有遗传算法中都包含有三种基本的遗传算子：选择算子、交叉算 子和变异算子。 1 、选择算子( s e l e c t i o no p e r a t o r ) 生物界遵循“优胜劣汰、适者生存这个规律进行自然选择。在 遗传算法中，选择算子就模拟了生物界的自然选择过程。所谓选择算 子，指在适应度评估的基础上，按照某种规则或方法，从当前代的种 群中选择出一些适应度高的个体遗传到下一代种群中。 目前常用的选择方法有：轮盘赌方法，也称比例法：最佳个体保 留法；截断选择法；期望值法；竞争法；线形标准化方法等本文将在 使用时再解释所用到的选择算子。 2 、交叉算子( c r o s s o v e ro p e r a t o r ) 在遗传算法中，交叉算子指以下操作：以某一概率( 称为交叉概率) 选择种群中的个体，把两个父个体染色体的部分基因加以替换、重组 而生成新的个体。交叉的作用是为了获得新的更好的个体。交叉概率 酌选择决定了交叉操作的频率。如果频率过小，会使搜索过程缓慢， 以至停滞不前。频率越高，产生新个体的速度就越快，但太高的频率 可能导致具有高适应度的个体结构很快就会被破坏，过早的收敛，一 般取值0 4 0 9 9 。 3 、变异算子( m u t a t i o no p e r a t o r ) 生物学中的变异指：在细胞进行复制时可能以很小的概率产生某 些复制差错，从而使d n a 发生某种变化，产生出新的染色体，这些新 的染色体表现出新的性状。在遗传算法中，变异算子指以下操作：以某 概率( 称为变异概率) 选择种群中的个体，改变其染色体中某些基因 1 4 山东大学硕士学位论文 的值或对其染色体进行某种方式的重组( 例如，改变基因的排列顺序) 。 变异概率的选取一般受种群大小、染色体长度等因素影响，通常选取 很小的值，一般取0 0 0 1 0 1 。若选取高的变异率，虽然增加样本的 多样性，但也有可能破坏掉很多较好的模式。种群大小及染色体长度 越大，变异率选取越小。但变异率太小，抑制早熟现象的能力也就会 很差了。 3 2 遗传算法的基本思想 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是模拟生物在自然环境中优胜 劣汰、适者生存的遗传和进化过程而形成的一种具有自适应能力的、 全局性的概率搜索算法。遗传算法是从代表待优化问题潜在解集的一 个种群开始。而种群则由经过基因编码的一定数目的个体组成。基因 编码成染色体，每个个体由染色体构成，每个个体实际上是带有染色 体特征的实体。染色体作为遗传物质的主要载体，是多个基因的集合， 其内部表现( 即基因型) 是多个基因的某种组合，它决定了个体的形状 的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编 码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代 演化产生出适应性越来越好的个体。在每一代中，根据问题域中个体 的适应度的优劣，选择一些适应度高的个体，基于这些选出的适应度 高的个体，并借助于自然遗传学的交叉、变异算子，产生出代表新解 集的下一代种群。这个过程将导致种群像自然进化一样，使后生代种 群比前代种群具有更高的适应度，更加适应于环境。在优化过程结束 后，末代种群中的最优个体经过解码，即可以作为问题的近似最优解。 3 3 基本遗传算法描述 虽然在实际应用中遗传算法的形式出现了不少变型，但这些遗传 算法都有共同的特点，即通过对自然界进化过程中自然选择、交叉、 变异机理的模仿，来完成对最优解的搜索过程。基于这个共同的特点， g o l d b e r g 总结了一种统一的最基本的遗传算法，该算法被称为基本遗 山东大学硕士学位论文 j i 量暑量毫曼量量量曼舅曼曼量曼量舅量量曼曼量喜量量曼皇舅舅鲁量鲁量| 量皇罾量量皇曼曼曼曼量喜量量量量量皇曼曼曼量皇曼曼曼量量皇皇量量 传算法u 驯( s i m p l eg e n e t i ca l g o r i t h m s ，s g a ) ，s g a 只使用了选择算子、 交叉算子和变异算子这三种遗传算子，其结构简单，易于理解，是其 它遗传算法的雏形和基础。本文所涉及的遗传算法也基于s g a 。 s g a 的基本流程n 3 1 如下： s t e pl 初始化，产生初始种群。 s t e p 2 个体评价，即计算种群中每个个体的适应度 s t e p 3 按选择概率p s ，执行选择算子，从当前种群中选择部分个 体进入下一代种群。 s t e p 4 按交叉概率p c ，执行交叉算子。 s t e p 5 按变异概率p m ，执行变异算子。 s t e p 6 若满足设定的终止条件，则执行s t e p 7 ，否则执行s t e p 2 。 s t e p 7 输出种群中适应度最优的个体作为问题的最优解或满意 解。 遗传算法的终止条件可以设定为：( 1 ) 达到了预先设定的进化代 数；( 2 ) 种群中的最优个体在连续若干代中都没有再获得改进；( 3 ) 最 优个体达到预先设定的满意解。 3 4 遗传算法的原理 遗传算法的数学基础主要是模式定理和积木块假设，下面从这两 个方面来说明其原理： 一、模式定理n 钉 模式是指种群个体基因串中的相似样板，它用来描述基因串中某 些特征位相同的结构。在二进制编码中，模式是基于三个字符集( 0 ，1 ，l c ) 的字符串，符号木代表任意字符，即0 或者1 。例如：模式0 0 1 0 1 木， 该模式可表示四个串：0 0 1 0 0 10 、0 01 0 0 11 、0 0 11 0 1 0 、0 0 11 011 。 下面介绍两个与此密切相关的定义：阶和模式 定义1 ：模式h 中确定位置的个数称为模式h 的阶，记作0 ( n ) 。 例如0 ( 0 0 1 木0 1 木) = 5 。 定义2 ：模式h 中第一个确定位置和最后一个确定位置之间的距 离称为模式h 的定义距，记作8 ( h ) 。例如6 ( 0 0 1 木0 1 木) = 5 。 山东大学硕士学位论文 模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式 的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数 相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质 的差异。 下面介绍一个联系密切且比较重要的定理： 模式定理n 引：具有低阶、短定义距以及平均适应度高于种群平均 适应度的模式在子代中呈指数增长。 模式定理保证了较优的模式的数目呈指数增长，为解释遗传算 法机理提供了数学基础。 二、积木块假设n 3 1 积木块假设：具有短定义距、低阶以及高平均适应度的模式称之 为积木块，遗传算法通过积木块在遗传操作下相互结合，最终接近全 局最优解。 模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法 找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的 作用下，能生成全局最优解。 山东大学硕士学位论文 第4 章遗传算法在装箱环节中的应用 4