（系统分析与集成专业论文）混合智能算法在整车生产车身存储区排序问题中的研究与应用.pdf

摘要 随着计算机技术的高速发展，企业信息化已成为基本趋势。汽车公司现有的整车生 产跟踪系统，越来越不能满足当前实际业务发展的需要，因此急需建立起一套更加完整 的网络平台的整车跟踪指导系统，同时改善企业对生产过程的跟踪及指导的管理以及提 高整体的工作效率和整体技术水平就变得来越重要了。 车身存储区管理模块是整车生产跟踪系统中的一部分，它指导各车间车身的入库和 出库。合理的车身出库顺序能使车间工人的劳动负荷处于均衡状态，从而大大提高生产 效率。因此，对车身存储区的管理问题进行研究具有很重要的现实意义。研究工作主要 涉及以下方面： 1 、具体描述和分析了车身存储区捧序问题，介绍了该问题考虑的因素及其度量， 用枚举的思想提出了其理论模型，并用贪婪法具体解决了该问题。虽然此法可以得到可 行解，算法简单而且效率比较高，但是由于它将入库和出库操作分开来考虑，当入库车 比较多时并不能得到一个较好的出库清单。 2 、针对贪婪法解决这一问题的不足之处，将综合遗传算法与模拟退火算法优点的 遗传模拟退火算法用于车身存储区排序问题中，详细分析与设计了遗传算子、适应度函 数等。此法综合考虑入库和出库操作，每次可计算出批量车中每辆车的入存储区道号和 该批车的出库清单，得到的解优于贪婪法所得的结果。 3 、阐述了基于混合算法的车身存储区管理系统的设计与实现，介绍了各个模块的 功能与操作。系统的运行结果满足了调度要求，进一步证明了混合智能算法的有效性和 实用性。 最后，对全文进行了系统总结，并对本文研究内容今后需要进一步完善的地方进行 了探讨。 关键词：整车生产；车身存储区排序；遗传算法：模拟退火算法 w i t ht h eh i # - s p e e dd e v e l o p m e a to f c o m p u t e rt e d m o l o g y , a m 叩f i 越蛐咖衄捌o nh a s t u r n e di n t oa ne s s e n t i a lt r e n d t h ee x i s t i n gv e h i c l et r a c k i n gs y s t e mo fa u t o m o b i l ec o m p a n y c a nn o ts a t i s f yt h ed e m a n do fc u r r e n to p e r a t i o nd e v e l o p m e n t a c c o r d i n g l y , am o r ee x c e l l e n t v e h i c l et r a c k i n gs y s t e mm u s tb ee s t a b l i s h e d i tb e c o m e sm o r ea n dm o r ei m p o r t a n tt oi m p r o v e t h em a n a g e m e n to f p r o d u c t i o nt r a c l d n ga n dt h ew h o l ew o r k i n ge f f i c i e n c y s t o r a g ez o n em a n a g e m e n tm o d u l e i si , mo fv e h i c l ep r o d u c t i o nt r a c k i n gs y s t m , w h i c h d i r e c t si na n do u to fs t o r a g ef o re v e r yv e h i c l e ar e a s o n a b l eo u ts e q u e n c ec a nm a k et h e l a b o r s b u r t h e nab a l a n c e ds t a t es o 鹤t oi m w o v ep r o d u c t i o ne f f i c i e n c y t h e r e f o g e , i th a s p r a c t i c a ls i g n i f i c a t i o nt os t u d y t h i sp r o b l e m t h er e s e a r c h e si n v o l v et h ef o l l o w i n ga s p e c t s ： 1 、s t o r a g ez o n es c h e d u l i n gp r o b l e mi sd e s c r i b e dc o n c r e t e l ya n dt h ef a c t o r s t h i sp r o b l e m i n v o l v e sa sw e l la st h e i rm 洲e n t sa 阳i n t r o d u c e d i na d d i t i o n , o nt h eb a s e o f e n u m e r a t i n gt h o u g h t ，t h et h e o r ym o d e li sb r o u g h tf o r w a r d t h e ng r e e d ya l g o r i t h m i su s e dt o s o l v et h ep r o b l e m a l t h o u g ht h i sa l g o r i t h mm a yb eaf e a s i b l es o l u t i o n ，w h i c hi ss i m p l ea n d e f f i c i e n t , s i n c ei ts e p a r a t e so u t - o p e r a t i o nf t mi n - o p e r a t i o n , w h e nt h e r e a r et o om a n y v e h i c l e si tc o u l dn o tg e tab e t t e ro u ts e q u e n c e 2 、a i m i n ga tt h es h o r t a g eo fg r e e d ya l g o r i t h m0 1 1s o l v i n gt h i sp r o b l e m ，ag e n e t i c s i m u l a t e da n n e a l i n ga l g o r i t h m ( g s a ) ，w h i c hc o m b i n e st h ea d v a n t a g e so fg e n e t i ca l g o r i t h m a n ds i m u l a t e da n n e a l i n ga l g o r i t h m ，i se m p l o y e dt os t o r a g ez o n es c h e d u l i n gp r o b l e m t h e g e n e t i co p e r a t i o n s ，f i t n e s sf u n c t i o n a r ea n a l y z e di nd e t a i la n dd e s i g n e dc a r e f u l l y t h i s a l g o r i t h mc o n s i d e r sb o t hi na n d o u to p e r a t i o n s ar u n n i n gc a l lg e tt h es t o r a g el i n k - n u m b e ro f e v e r yv e h i c l ei nab a t c h , a n dt h eo u ts e q u e n c eo ft h i sb a t c h t h er e s u l to f t h i sa l g o r i t h mi s b e t t e rt h a nt h a to f g r e e d ya l g o r i t h m 3 、t h ed e s i g na n dr e a l i z a t i o no fs t o r a g ez o n es c h e d u l i n gs y s t e mb a s e do ng s a 矾 e x p o u n d e d t h ef u n c t i o n sa n do p e r a t i o n so ft h es y s t e mm o d u l e sa r ei n t r o d u c e dd e t a i l e d l y t h es c h e d u l i n gr e * t i l ts a t i s f i e st h er e q u i r e r a e n t s ，w h i c hs h o w st h ea v a i l a b i l i t i e so fg s a f u r t h e r t h ef i n a lc h a p t e rc o n c l u d e st h i st h e s i sa n de x p l o r e * i m p r o v e m e n t sf o rt h ep o s s i b l e a p p l i c a t i o n k e yw o r d s ：v e h i c l ep r o d u c t i o n ；s t o r a g ez o n es c h e d u l i n g ；g e n e t i ca l g o r i t h m ；s i m u l a t e d a n n e a l i n ga l g o r i t h m 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 论文作者签名： 日期：研年 捡妖 z 月7 e t 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷 本和电子版，并提供目录检索与阅览服务；学校可以允许采用影印、缩印、数字化或其 它复制手段保存学位论文；在不以赢利为目的的前提下，学校可以公开学位论文的部分 或全部内容。( 保密论文在解密后遵守此规定) 日期：碍占7 日期：岬7 第一章绪论 1 1 排序问题 1 1 1 排序问题的定义 第一章绪论 排序( ( s c h e d u l i n g ) f 可题产生的背景主要是机器制造，后来被广泛用于计算机系统、 运输调度、生产管理等颁域。从普通的生产部门的计划安捧、人员调度、学校课程表的 制定，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法【l 】。 接序( ( s c h e d u l i n g ) 问题是一类重要的组合最优化问题，它是利用一些处理机 ( p r o c e s s o r ) 机器( m a c h i n e ) 或资源( r e s o u r c e ) ，最优地完成一批给定的任务( t a s k ) 或作业 ( j o b ) 。在执行这些任务或作业时需要满足某些限制条件，如任务的到达时问、完工的限 定时问、任务的加工顺序、资源对加工时间的影响等。最优的完成指的是使目标函数达 到最小，而目标函数通常是对加工时间的长短、处理机利用率的描述。 一 捧序理论可归结为下面两类问题，一、给定了任务或工程，如何合理地安排各项具 体工作的顺序，使得花费尽量少的人力、物力、财力等资源，以完成这项任务或工程： 二、现有的入力、物力等资源已经确定，如何安捧具体工作的顺序，使这些资源能发挥 尽量大的收获。 1 1r 2 排序问题的分类和求解 在排序问题中，如果所有的数据在进行决策之前都是已知的，捧序问题称为确定性 排序( d e t e r m i n i s t i cs c h e d u l i n g ) 问题。如果有的数据，例如加工时间、准备时间和工期 等，在做决策时是未知的，它们是一些随机变量，但它们的分布是己知的，这样的排序 问题称为随机捧序( s t o c h a s t i cs c h e d u l i n g ) 问题。处理机、任务或作业、目标函数三要 素组成了排序问题。处理机的数量、类型和环境有近十种情况，任务或作业和资源的约 束条件更是错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的排序类型。 由于排序问题中的处理机、任务或作业都是有限的，绝大部分排序问题是从有限个 可行解中找出一个最优解，使目标函数达到极小。在捧序问题中，把可行解称为可行捧 序( f e a s i b l es c h e d u l e ) ，最优解称为最优摔序( o p t i m a ls c h e d u l e ) 。 湖北大学硕士学位论文 捧序问题是一类组合最优化问题，求解捧序问题的基本思路是：应用或借鉴求解其 他组合最优化问题的方法，充分利用排序问题本身的特殊性质，以确定满足约束条件的 最优捧序。有些捧序问题可直接转化为其他的组合最优化问题求解。对具有多项式算法 的捧序问题，要尽可能地找出空问复杂性和时间复杂性好的算法。所谓空间复杂性是指 算法所占存储的多少，时间复杂性指的是计算时间的长短，它们都是输入规模的函数。 由于绝大多数排序问题是n p 难题，其最优解往往很“难”找到，而且在实际应用 中往往也没有必要去找到最优解，只需找到满足一定要求的启发式解或近似解。因此， 研究排序问题主要有两个方向：一是对p 问题，即可解( s o l v a b l e ) 问题，寻找多项式 时间算法( 又称为有效算法) 来得到问题的最优解，或者对n i 难题在特殊情况下( 如 工件加工允许中断，工件的加工时间都是单位长度，工件之间有某种约束等等) 寻找有 效算法，也就是研究n i 难题的可解情况二是设计性能优良的启发式算法和近似算法。 当然，无论是启发式算法还是近似算法都应该是多项式算法。实际上，n p 难题可解情 况的多项式时自j 算法往往是可以作为n p 难题本身的启发式算法和近似算法1 2 】。 1 2 车身存储区排序问题( s z m 问题) 简介及研究现状 车身存储区排序问题( s z ms t o r a g ez o n em a n a g e m e n t 问题) 简单来说就是要解决 车身进入存储区的哪个链道及如何生成最优的出库清单。出库清单要尽可能地接近目标 生产顺序，同时又要满足下游车间的生产限制条件。它也可以看成是排序问题的一种。 存储区即是处理机，车身即是作业，根据进出存储区的各种约束条件就可以确定目标函 数。那么，车身存储区捧序问题可以简单理解成：在存储区中如何根据目标函数来确定 车身的存储链道号和出库顺序。 公司现有的车身存储区排序是工人根据经验来进行的，即车身在入存储区时，工人 根据计算机上显示的车身上的条码信息，结合存储区中现有的车身信息，主要考虑生产 限制条件的因素来决定该车入哪条存储链道；出存储区时也是如此。那么在整个过程中， 工人没有考虑到目标顺序号( 车身依据这个顺序进行总装上线是最好的) 的因素，而且 也考虑不到多方面的生产限制条件，这样的结果不够客观，而且不是最优的。所以我们 要开发存储区排序系统来综合考虑多个因素，从而期望得出最优的入库链道号和捧产清 单。 现在国外已实现了关于存储区排序的算法，比如法国的a r i 算法，但是并没有公开 相关技术，而且也不一定能适合于国内的存储区 2 第一章绪论 对于s z m 问题最简单直观的方法是直接采用枚举法，按照问题本身的性质，通过 多重循环，列出问题所有可能的解，然后检验每个可能的解是否是问题的真正解，若是， 采纳( 输出) 这个解，否则放弃它。即在车辆进入库区的时候考虑填满和排空库存的各 种方式生成可能出库清单的各种组合，也就是将所有的出库清单都枚举出来，然后将每 个清单与目标顺序比较计算出顺序权重，另外判断出库各车之问是否满足生产限制条件 计算出生产限制权重，两者综合得到一个综合权重，最后选择综合权重最小的清单即是 最优的出库清单。 这种方法将所有的解都列出来，能够保证从中找出最优解，但是得出来的解很多， 所以该算法的复杂度比较大，这样会影响生产效率 为了提高效率，将入库和出库的操作分开，在入库时主要根据车身的目标顺序进入 各存储道，出库时采用贪婪法得到出库清单( 具体方法见第二章) 。该方法效率高，但 是只能得到可行解。 1 3 智能优化算法的研究及发展动态 采用贪婪法可以得到s z m 问题的一个可行解，但优化结果往往不够理想。在人工 智能领域中，有很多问题需要在复杂而庞大的搜索空间中寻找最优解或准最优解。在求 解此类问题时，若不能利用问题的固有知识来缩小搜索空问，就很容易产生搜索的组合 爆炸【3 】。因此在搜索过程中，对自动获取和积累有关搜索空间知识并自适应地完成搜索 过程，从而得到最优解或准最优解的通用搜索算法一直是令人瞩目的研究课题。所以考 虑使用智能算法求解s z m 问题。 但是随着科技的发展和工程问题范围的拓宽，问题的规模和复杂度越来越大，传统 智能优化算法的优化结果往往也不够理想，同时算法理论研究的落后也导致了单一算法 性能改进程度的局限性，而基于自然机理来提出新的优化思想是一件很困难的事。指导 性搜索方法具有较强的通用性，无需利用问题的特殊信息，这也造成了对已知问题信息 的浪费。尽管启发式算法对问题的依赖性较强，但对特殊问题却能利用问题信息较快地 构造解，其时间性能较为理想。所以，如何合理结合两者优点来构造新算法，对于实时 性和优化性同样重要的工程领域，具有较强的吸引力。基于这种现状，算法混合的思想 已发展成为提高算法优化性能的一个重要且有效的途径，其出发点就是使各种单一算法 相互取长补短，产生更好的优化效率 3 湖北人学硕士学位论文 近年来，混合优化策略得到了较广泛的应用，并取得了理想的效果，其设计与分析 已成为算法研究的一个热点 4 1 模拟退火算法通过赋予搜索过程一种时变且最终趋于零 的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优；遗传算法则通过概 率意义下的基于“优胜劣汰”思想的群体遗传操作来实现优化。对选择优化机制上如此 差异的两种算法进行混合，有利于丰富优化过程中的搜索行为，增强全局和局部意义下 的搜索能力和效率。 1 4 本文的主要工作 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) 本文将从以下五个方面进行具体分析和研究： 描述车身存储区捧序问题( s z m 问题) 。 阐述如何用贪婪法解决s z m 问题及其不足之处。 对智能算法进行研究，并介绍将遗传算法和模拟退火算法结合起来的优势。 针对贪婪法求解该问题的不足之处，运用混合智能算法来求解s z m 问题。 介绍车身存储区排序系统的设计方案。 4 第二章s z m 问题描述及分析 第二章s z m 问题描述及分析 车身存储区捧序问题( s z mf 司题) 也是一种捧序问题。存储区即是处理机，车身 即是作业，根据进出存储区的各种约束条件就可以确定目标函数。该问题即可理解为： 如 可剩用存储区来调整出合理的车身顺序，以便进入下游车闻时能最大地提高车问生产 效率。 2 1s z m 问题描述 在整车生产过程中，车身分别经过焊装、涂装、总装这三个车问( 见图2 - 1 ) 。简单 示意图如下。而这里要讨论的主要问题是在三个车间的车身存储区管理情况。 图2 1 整车生产流程 学 当白车身佩带标签离开焊接车间，进入存储区1 后，自车身在此根据车身颜色及车 辆交货日期重新排序，最理想的捧序结果是：交货日期紧的、相同颜色的车体被成组送 往油漆车间，已喷漆的车体离开油漆车间后，即进入存储区2 。车体在此根据车型、内 饰选项、交货日期、总装车间的生产负荷及尽可能接近l u o ( 目标顺序，2 2 中将具体 介绍) 的顺序再次重新排序，捧序后的车体被送往总装车间完成内饰、仪表盘及发动机 的安装。这两个存储区的控制效果也影响了油漆车问的原料消耗和总装车间的生产效 率。 那么，车身存储区管理系统可以管理焊装车间、油漆车间和总装车间。对于该系统， 将依据一个重新捧产算法实现对整车流库存的管理，实现将整车安排在存储区并把它们 发往下游生产车间，需要考虑如下两个因素： 重置l u o 顺序以纠正来自上游流的干扰( 重新排序功能) 。 下游车间的生产限制条件( 节奏功能) 。 氐奄 e 。 存储区 l 图2 - 2 存储区结构 湖北大学硕士学位论文 由此可见，对于整车生产，存在数个链道式存储车身的库区，由若干个入口、一个 出口、链道、返回线、储存区组成，如图2 - 2 所示 2 2s z m 问题考虑的因素及度量 ( 1 ) u j o 车身在生产线上有一个l u o ，l u o 是根据总装上线预先捧好的一个目标顺序清单， 对于每个车身分配一个代表先后顺序的数值。但实际上的车身可能没有遵守这个清单的 先后顺序，比如车身在经过焊装、涂装这些车间时由于要考虑生产限制条件等，会将车 身顺序打乱。所以通过存储区撵序系统，以实现尽可能在总装上线时遵守l u o 的顾序， ( 2 ) 生产限制条件 主要限制条件如下： 间隔：l x 或n ，p 在p 辆车中指定了带有限制条件车的最大量。 例如：5 辆中最多3 辆可以有开天窗的限制条件。a 表示带天窗的车。 a a a b b a a a b b a a a b b a a a b b 遵守了限制条件 平滑间隔：n p 例如：平衡限制n 1 ) - - 1 1 2 0 = = 0 5 5 即在p 辆车中n 辆a 类型车的箨产方式如下： a b a b a b a b a b a b a b a b a b a a 连续限制 连续限制条件的特点是禁止带a 限制条件的某车与带b 限制条件的另一辆车连续 捧产。 例如：一辆双门车和一辆旅行车在一个生产线上不能连续生产，因为这是两种在总 装车间都很耗时的车。 连续限制不是对称的。例如：若想禁止一辆旅行车后跟一辆双门车，而一辆双门车 后面是一辆旅行车，需要两个限制条件。 批量集中限制 批次限制可以对具有相同特点的车设计一个序列。需要按其最小容量和最大容量确 定一个批次 第二章s z m 问题描述及分析 比如，由存储区l 取车送往油漆车间的操作应符合如下限制条件：必须将至少三辆 以上的相同颜色的车体摔成一组，送往油漆车间；必须将交货日期还剩一周的车体送往 油漆车问；在此存储区的车体捧序不考虑车型、内饰选项等车身数据。 由存储区2 取车送往总装车间的操作应符合如下限制条件：确保送往总装车间的车 体所需安装的部件不能处于缺料状态；根据不同的车型所需的劳动强度，将不同车型的 车体交叉捧序送往总装车间，使得总装车间工人的劳动负荷处于均衡状态；在此存储区 的车体排序不考虑车身颜色。 2 3 用枚举法求解s z m 问题 2 3 1 算法思想 s z m 问题简单说来就是解决每进一车，决定进哪条链道，及生成所有在库车的最 优出库清单，如果此时要出车那么就按照这个出库清单进行。 l c 6 hi1 p t l2 1 d h 2 3i p t l4 l c n 65 图2 3 存储区分布情况 以焊装存储区为例，出库清单要满足尽量恢复l u o 顺序，又尽量满足车型集中 假如存储区容量为5 1 3 ，其中已有l 、2 、3 、4 四辆车，作为初始条件。现在考虑第5 辆车进入的情况，车型为l c 6 n 。车身5 在进入时，可以进入这5 个道中的任意一个， 这里假设5 进入s 2 道。如图2 3 在出车时，每次只能出链首车，3 只能在l 后，4 只能在2 后，5 只能在4 后。此 时有如下的出库清单： 7 湖北火学硕士学位论文 e 工 卫 图2 4 出库清单 那么需要在这些清单中确定出最优的，记为l 2 。该车还可以进入s 1 、s 3 、s 4 、s 5 道，分别也有一个最优的清单，记为l l 、l 3 、l 4 、l 5 。然后比较这5 个清单选出最好 的。如果l 3 最好，那么5 就要进s 3 道，而且这5 辆车的最优出库清单为l 3 。 同样，按照以上方法进入6 、7 、8 其他车。 具体计算最优清单，即如何缛到l l 、l 2 、l 3 、l 4 、”的方法如下： 主要是根据l u o 顺序号和生产限制条件给每个清单赋一个权值，选择权值最小的 清单。计算顺序权重时会有一个函数计算清单中每辆车的权重，累加起来就是清单的顺 序权重；根据清单中的车是否满足生产限制条件，从而计算出生产限制条件权重。两者 综合起来就是该清单的权重。 2 3 2s z m 问题的数学描述 设在库车为 h ，吃，v 3 一) ，待入库车为+ 1 表示链道i 的库存车 数。假设k 。分别进入未满链道i ( i = 1 ，2 ，3 ，4 ，5 ) ，该链道的库存车数；加1 ，则匕+ 在链道 i 的位置记为，表示第i 条链道的第川辆车 设置表示再捧序的权重，尼表示拌产限制条件的权重；气表示再排序所占比率，f c 表示捧产限制条件所占比率。 表示第i 条链道的第k 辆车，s ( ) 表示在出库清单中的位置 由此建立如下数学模型： 目标函数： + ih + t r a i n p = t l 尼+ t o 岛( 2 - 1 ) l i lf i g 募 第二章s z m 问题描述及分析 约束条件： s ( 屹) s ( - - )1 如m o 。 o ，l - - - - m m ；若m o ，l m m ； 、 设定进入返回链的权值上限( 经验值) ，判断l 是否超过上限，是则进入返回链 每一轮次进入返回链的车身数量可以由用户设定 湖北人学硕士学位论文 2 4 3 实验结果及分析 为了方便考察该算法的效率和效果问题，在e x c e l 中做了一个宏来简单模拟s z m 计算。计算界面如图2 - 6 。 图2 - 6 模拟计算界面 存储区有5 个链道，每条链道的最大存储容量为1 3 。这里考虑2 0 辆车的入库和出 库问题。首先新建一个名为l i s t 的s h e e t 来记录这2 0 辆车的信息。表2 1 将几个主要的 信息，包括l u o ，车型，颜色和整车版本号列出来。 整车版本号共2 4 位，其中，前4 位表示车型，如1 c 6 n 、i p t l 、l p t 5 等；第1 0 位表示变速箱，有l 和5 两个值，l 表示自动档，5 表示手操纵5 档机械式；1 7 2 0 这 4 位表示车身颜色，如m o z r 表示水晶银，m o b 6 表示香槟金，p o w p 表示白色等。 这2 0 辆车在进入存储区时，根据本车l u o 的大小和存储区中车的l u o 选择进入 的存储区道号，具体方法见2 4 2 中的入库算法。2 0 辆车都进入后存储区的分布情况如 图2 7 所示。 出库时考虑的限制条件是自动档间隔，自动档的车前后间隔l 台( 1 2 ) 。用户可以 输入其权重值。具体方法见2 4 2 中的出库算法。2 0 辆车的入库和出库顺序如图2 8 。 第二章s z m 问题描述及分祈 表2 - 1 车身信息 i t e m订单号 l u o条码号车身颜色整车版本号 l7 e 珥x 0 2 3 54 7 1 7 6 40 2 8 1 0 8 e中国蓝l c 6 n a 5 c 6 s l 5 0 a 6 1 0 m o g e n 9 f d 27 8 4 y 0 4 0 74 7 1 7 9 00 2 8 3 3 l m中国蓝 i p t l a 5 f s 2 5 5 0 a 0 6 0 m o g e y q f x 37 8 4 x 1 4 8 84 7 1 8 0 00 3 3 2 9 7 k白 1 d n 2 a s e 6 q 5 5 0 a 0 5 0 p o w p n 3 f c 47 8 4 y 1 4 8 i 4 7 1 7 5 2 0 2 8 8 9 7 b 波尔多红 1 p t l a 5 f s 2 5 5 0 a 0 6 0 m 0 1 b y q f x 57 8 2 x 1 1 2 64 7 1 7 6 86 5 7 6 8 7 r月光灰l c 6 n a f w 6 v l 5 0 a 0 7 0 m o t s c 9 f d 67 e 1 4 x 1 9 8 8 4 7 1 8 1 00 3 3 6 4 4 w环保绿 i d n 2 a 4 a 6 q 5 5 0 a 0 5 0 m 0 7 9 m 2 f z 77 8 2 x l l 2 5 4 7 1 7 5 9 6 5 7 6 8 8 s 月光反l c 6 n a f w 6 v 5 5 0 a 0 7 0 m o t s c 9 f d s7 8 2 x 】1 2 l4 7 1 8 2 l 6 5 7 6 8 9 t 月光灰1 c 6 n a f w 6 v l 5 0 a 0 7 0 m 0 1 s c 9 f d 97 8 4 ) ( 2 7 7 0 4 7 1 7 7 8 0 3 3 7 4 9 f 水晶银1 d n 2 a 4 j 6 s l 5 0 a 0 5 0 m o z r p 4 d l 1 07 8 4 x 2 6 6 64 7 1 8 1 30 3 3 7 6 4 w水晶银1 d n 2 a 5 h 6 s 5 5 0 a 8 5 0 m o z l t n 3 f c l l7 8 4 y 1 5 0 0 4 7 1 7 8 00 2 9 1 1 4 c波尔多红l p t l a 5 f s 2 5 5 0 a d 6 0 m o l b e o f a 1 27 c i y l 4 5 44 7 1 8 1 90 3 0 0 l l m中国蓝 1 c t 2 a s s 6 s l 5 0 a 0 6 0 m o g e q l f a 1 37 c l y l 4 5 54 7 1 7 7 60 3 0 0 1 2 n爱琴海蓝 1 p t l a s f s 2 5 5 0 a 0 6 0 m 0 3 f y q f x 1 47 8 4 x 2 4 2 8 4 7 1 7 8 70 2 9 1 9 9 r香槟金i d n 2 a 5 c $ 2 5 5 0 a 6 1 0 m o b 6 n 9 f d 1 57 8 4 x 2 4 2 9 4 7 1 8 4 30 2 9 2 0 0 s香槟金l p t i a 5 c s 2 5 5 0 a 6 1 0 m o b 6 n 9 f d 1 67 8 4 x 2 8 7 04 7 1 s 2 70 2 9 2 0 2 u 巾国蓝i c t 2 a 5 c s 2 5 5 0 a 6 1 0 m o g e n 9 f d 1 77 8 4 勉6 3 8 4 7 1 7 6 90 3 3 8 8 3 v自 i d n 2 a 5 e 6 q 5 5 0 a 0 5 0 p o w p n 3 f c 1 87 8 4 x 2 6 3 94 7 1 7 9 90 3 3 8 8 4 wn i d n 2 a s e 6 q 5 5 0 a 0 5 0 p o w p n 3 f c 1 97 8 4 x 2 7 0 5 4 7 1 8 3 40 3 4 3 0 3 h成都绿i d r 2 a 4 d 2 n 5 5 0 a 0 5 0 p 0 7 6 m 2 f z 2 07 8 4 x 2 5 9 7 4 7 1 7 7 70 3 3 8 8 9 b水晶银i d n 2 a s e 6 q 5 5 0 a 0 5 0 m o z r n 3 f c i c 6 nil p t i4l c 6 h11 p t l1 3l d 胃21 7 i p t l2 l c 6 n5 i p t l1 11 d n 22 0 1 h 231 d h 29i d n 2l q l d 耳26i d h 21 01 d h 21 8 1 c 6 h8i c t 21 2 i p t l1 5i c t 21 6 1 d r 21 9 tt t t t s 1鸵 翳1 孰 s 5 图2 7 存储区分布情况 湖北大学硕士学位论文 1 c t 2 & 5 $ 6 s l 5 0 i 6 ( m o e f , q i f a 中田互1 24 7 i y 9 91 d i e 2 k s e 6 0 5 5 0 a 0 5 呼0 1 1 p n 3 f c 自 i p t i a 5 f s z 5 5 0 a 0 6 0 1 0 3 f w f x 量琴海蓝1 34 7 1 8 0 0i d l i 2 a s e 6 q 5 5 0 a 0 5 0 p o p n 3 f c 白 l d i 2 3 s c s 2 5 5 0 a 6 1 蚴6 鳓番豢金 1 44 7 1 8 1 0i 朋2 矗娃两呦卯酌7 9 t 2 f z 环像绿 l 九l , e 6 c s 2 5 5 0 & 6 1 咖0 b e l g r ) 圣板盒 1 54 1 1 8 1 31 d 1 1 2 & s h 6 s 5 5 0 a 8 5 0 w o z r n 3 f c 水翟 l c t 2 , k s c $ 2 5 5 0 & 6 1 e o g 聃中田蓝1 64 7 1 8 1 9i c t 2 a 5 $ 6 乳5 0 a 0 6 0 1 阴i f a 中田蓝 i d i l 2 a s e 5 5 0 a 0 5 0 p 0 肿t 1 3 f c 白1 7q t l 8 2 7i c t 2 i u 5 c s 2 5 5 0 a 6 1 0 i o g e i g f d 中国蓝 i d l i 2 5 e 5 5 0 0 5 叩哪3 f c 自1 54 7 1 8 2 11 c 6 n a f w 6 v l 5 0 a 0 7 0 m o t s c 9 f d 月光荻 1 d r 2 a 4 d 2 1 5 5 0 a 0 5 0 p 0 6 i 邙z 白成帮 1 9 4 1 1 8 ，4t d r 2 2 4 d 2 1 5 5 0 a o s o p 0 7 6 1 2 f z 白成都曩 i d w 2 j k s e 5 5 0 a 0 5 ( h o z 1 3 f c 水麒 2 0 l4 y 1 8 4 3i p t l a s c s 2 5 i 6 0 a 6 1 0 i i o b 砸i g f d 雪橇盒 图2 8 入库和出库顺序 点击。出库完后比较”，将输入和输出的情况进行比较，得出l u o 的调整情况如图 2 - 9 ( 对清单中所有车身的l u o 进行整体判断，是否按照由小到大顺序排列) 。 图2 - 9 入出库顺序比较图 可以看到，在进入车身比较少的情况下，使用贪婪算法能较好地调整l u o 顺序和 满足生产限制条件，而且效率比较高。但是一旦车身数量比较多的情况下对于l u o 的 调整并不能让人满意( 见第四章) 。 2 5 本章小结 本章具体描述和分析了s z m 问题，介绍了该问题考虑的因素及其度量，并用枚举 法描述了它的解决方法，最后用贪婪法具体解决了该问题。使用贪婪法解决s z m 问题， 可以得到可行解，而且效率比较高。但是由于它将入库和出库操作分开来考虑，当入库 车比较多时并不能得到一个较好的出库清单。 啪刑研m掰m御叭m盯盯盯盯盯盯盯盯盯 坦一”：h。垢，吲一峨班酬 第三章遗传算法和模拟退火算法简介 第三章遗传算法和模拟退火算法简介 随着高性能计算机的飞速发展，一系列新的优化方法，如遗传算法、模拟退火算法、 进化规划、进化策略等获得了极其迅速的发展和广泛的应用。它们对解决大型复杂系统 中出现的许多困难优化问题表现出很好的适应性。这些方法往往不仅具有简单、通用、 自组织、自适应、自学习、适于并行处理等优点，而且有望成为将数值计算与语义表达、 形象恩维等高级智能行为联系的桥梁。因此被一些学者称为智能优化方法。 3 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是美国密歇根大学教授h o l l a n d 在1 9 7 6 年 首次提出的，它是一种宏观意义上模仿生物群体进化过程的仿生算法【7 ，引。g a 在生物 学上的理论依据就是由经典的达尔文进化理论、魏思曼选择和孟德尔摩根基因学说 发展而成的现代进化理论新达尔文进化理论【9 埘。 遗传算法是模拟自然界生物进化过程的随机化搜索算法。其主要特点是采取群体搜 索策略和在群体中的个体之间进行信息交换，利用简单的编码技术和繁殖机制来描述自 然科学中各种复杂的现象，它可以不受搜索空间的各种限制与约束。遗传算法目前已经 在最优化、机器学习、作业车甸调度问题、设备布局设计问题等领域得到非常广泛的应 用【l l 】 3 1 1 遗传算法的原理和基本操作 由于遗传算法是由进化论和遗传学机理产生的直接搜索优化方法，所以在该算法 中要用到各种进化和遗传学的概念。这些概念如下【1 2 1 3 1 ： ( 1 ) 串( s u i n g ) ：它是个f - 酞( 1 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 ) ：基因是串中的元素，基因用于表示个体的特征。例如有一个串 5 = 1 0 1 1 ，则其中的1 0 1 1 这4 个元素分别称为基因。 ( 5 ) 基因位置( g e n ep o s i t i o n ) ：一个基因在串中的位置称为基因位置，有时也简称基 因位基因位置在串中由左向右计算，例如在串s = 1 1 0 1 中，0 的基因位置是3 1 5 湖北大学硕十学位论文 回适应度( f i t n e s s ) ：表示某一个体对于环境的适应程度 由上可知，遗传算法把问题的解表示成“染色体”，在算法中也就是二进制编码的 串。在执行遗传算法之前，给出一群。染色体”，也就是假设解。然后，把这些假设解 置于问题的“环境”中，按照适者生存的原则，从中选择出较为适应环境的“染色体” 进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代 代的进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。 遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体 的评价和对染色体中基因的作用，有效地利用已有的信息来指导搜索有希望改善质量的 状态。主要有如下几个相关问题： ( 1 ) 编码 利用遗传算法求解优化问题时，先要将实际问题转换成由基因( g e n e ) 按一定结构组 成的染色体( ( c h r o m o s o m e ) 或个体，这一转换操作我们称之为编码 c o d i n g ) 。编码的方 式比较灵活，可以采用二进制、十进制等整型编码，也可以采用浮点数编码。 ( 2 ) 初始群体的产生 为了满足遗传算法的群体型操作的需要，必须为遗传操作准备一个由若干初始解组 成的初始群体。一般来说，初始群体的产生( i n i t i a l i z e ) - j 采取如下的策略：根据问题的 固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范 围内设定初始群体。先随机生成一定数目的个体，然后从中挑选出最好的个体加到初始 群体中。这过程不断迭代，直到初始群体中的个体数达到了预先确定的规模。 ( 3 ) 适应度函数 遗传算法使用目标函数即适应度函数( f i t n v s sf u n c t i o n ) 来评估个体或解的优劣，并 作为以后遗传操作的依据。遗传算法的适应度函数不受连续可微的约束且定义域可以是 任意集合。对适应度函数的唯一要求是，针对输入可计算出能加以比较的非负结果。 ( 4 ) 遗传操作 遗传操作是用一定的算子( o p e r a t o r ) 对原来的种群进行变化以产生新的个体。优胜 劣汰是设计g a 的基本思想，它应在选择、交叉、变异和种群替换等遗传操作中得以体 现，并考虑对算法效率与性能的影响。 选择操作 选择操作有时也称为复制操作( ( r e p r o d u c t i o no p e r a t o r ) ，其目的是把当前群体中的 优化个体按与适应值成比例的概率直接遗传到下一代，或通过配对交叉产生新的个体再 1 6 第三章遗传算法和模拟退火算法简介 遗传到下一代这样可以避免有效基因的损失使高性能的个体得以更大的概率生存， 从而提高全局收敛性和计算效率。常用的选择方法有适应度比例方法、期望值方法、最 优个体保存方法、捧序选择方法和联赛选择方法。 交叉操作 交叉操作( c r o s s o v e ro p e r a t o r ) 是根据交叉率将两个父代个体的部分结构加以替换重 组而生成新个体的操作。交叉操作是遗传算法中起核心作用的基因操作，其目的是为了 能够在下一代产生新的个体，使群体信息进行充分组合，扩大搜索范围，同时降低对有 效模式的破坏。常用的交叉操作有：一点交叉、二点交叉、多点交叉和一致交叉。 变异操作 当交叉操作产生的后代适应度值不再进化且没有达到最优时，就意味着算法的早熟 收敛。这种现象的根源在于有效基因的缺损，变异操作在一定程度上克服了这种情况， 有利于增加种群的多样性