论文总字数：26764字

目 录

1 引言 1

1.1 本课题的研究目的及意义 1

1.2 本课题的国内外的研究现状 1

2 遗传算法 3

2.1 遗传算法的简介 3

2.2 遗传算法的特点 4

2.3 遗传算法的应用 4

2.4 遗传算法的主要步骤 5

2.5 遗传算法基本运算流程图 6

2.6遗传算法的伪代码表示 6

2.6.1 遗传算法的形式化定义 6

2.6.2 遗传算法的伪代码 6

3 车间动态设施布局问题的遗传算法 7

3.1 问题描述 8

3.2 基本假设 8

3.3 约束条件 8

3.4 数学模型 8

3.5 改进型遗传算法描述 10

3.5.1 罚函数 10

3.5.2 适应度函数 10

3.5.3 编码方案 11

3.5.4 遗传操作 11

3.5.5 选择策略 11

3.5.6 改进的交叉操作 13

3.5.7 变异操作 15

3.5.8 迭代终止条件 16

3.5.9 自适应策略 16

3.5.10 改进的自适应策略 17

3.5.11 核心代码 19

4 算例仿真分析与结果比较 21

4.1 算例与计算结果 21

4.1.1 运行环境 21

4.1.2 算例的各项数据 21

4.1.3 交叉和变异策略不同搭配的比较结果 23

4.1.4 加入自适应策略后的比较结果 27

4.2 运行的最佳结果的截图与坐标表示 28

4.2.1 KCM策略最佳运行结果的截图（KCM策略的第5次运行结果） 28

4.2.2 KCM策略最佳运行结果的坐标显示（KCM策略的第5次运行结果） 29

5 总结与展望 31

5.1 本文所做的主要工作 31

5.2 本文的主要创新点 31

5.3 研究展望 32

参考文献 33

致谢 34

基于遗传算法的车间动态设施布局方法及实现

邵楷

ABSTRACT: Demand changes make traditional static layout plan of the enterprise more and more difficult to adapt to, and this requires enterprises to seek a continuous layout scheme based on the whole cycle, namely in different period, the enterprise will use different layout plan, so as to meet the market demand and reduce the cost of the enterprise. In short, this is the dynamic layout problem (DFLP) that this article is about to study. The purpose of this study is to make the raw material handling fee and cost facilities replacement plan period changes lead to the sum of the achieve minimum, so the research of practical has significance for the production of the enterprise. In this paper, a mathematical model of workshop layout based on multiple cycles is established, and a modified genetic algorithm is applied to solve the mathematical model. Finally, the algorithm system is implemented using the Java language. In order to verify the feasibility of this algorithm in dynamic business facilities layout, we constructed a simulation example of facility layout using the algorithm system to carry out.Compared with the algorithms in the literature, using the improved genetic algorithm to solve the problem can reduce the production cost by 7.1%. As we can see, the algorithm can help guide the production of enterprises, reduce the waste of resources in production, and improve the profit margin of enterprise products.

Key word: Dynamic equipment layout; genetic algorithm; multiple planning period; unequal area equipment; continuous layout

1 引言

市场是不断变化的，市场需求的动态性是其最大的特点之一。这要求我们必须制定能够随着生产周期不断变化的设施布局方案。为了解决这类问题，动态设施布局这个概念就被国内外专家提了出来。动态设施布局问题通过在生产周期内有计划地变动各部门之间的物流关系来扩展静态设施布局问题（SFLP）。在本文的引言部分，我们主要介绍了动态设施布局问题的背景，研究该问题的意义，现阶段国内外对该问题的研究状况以及算法的基本概述。

1.1 本课题的研究目的及意义

市场伴随着客户的需求而不断变化，车间内部的布局如果是一成不变的话，那么这个车间将很难顺应市场潮流。这要求我们必须制定能够随着生产周期不断变化的设施布局方案，即各个时期有各个时期的布局，从而组成一串连续的布局方案，这就是动态设施布局问题。

为了在竞争越来越激烈的市场环境中生存下来，企业必须做到适应市场的动态需求，减少生成过程中不必要的损耗，同时提高自身的生产效率，增强自己的竞争力。据统计：一个企业将约20%~50%的加工费用于原材料的运输，而理论上，假定能够对车间的布局进行恰当的优化，使之更有效率，那么，可以降低企业10%~20%的生产总成本，并可提高大约2~3倍的生产效率。

因此，这个毕业设计的意义在于建立一种包含多个周期多个设施的车间布局的数学模型，并运用一种改良的遗传算法对该数学模型进行求解，使原料搬运费用和计划期内变更设施导致的产值损失费用之和达到最低，从而得到车间在整个生产周期中的最佳布局，帮助企业减少资源浪费的现象。

1.2 本课题的国内外的研究现状

动态设施布局本质上是由多个连续的静态布局构成的。简而言之，就是将车间看做一个二维平面，并在该平面上确定各个不等面积设施的坐标。当然车间的大小以及各个设施都有各种各样的限制，例如，车间和设施的长度和宽度，不同设施之间的限制距离，设施与车间边界的限制距离等。在这些限制中有两个是主要的：（1）各个设施彼此不能重合起来；（2）设施在X轴，Y轴这个二维平面上必须处于车间的范围之内。

1831年，数学大师高斯首先对布局问题进行了研究，到了21世纪的今天，历经上百年的历史，布局问题有了更长远的进展，由原先的静态设施布局，演变为如今的动态设施布局问题。现代化的快节奏，影响着布局问题的演变，静态的布局无法满足新时代的物流变化。设施物流之间的物流关系已经不像上百年前的那样一成不变了，运输工具的发展让各个设施之间的联系更加紧密，同时，变化也更加明显了，为了应对这种变化，动态布局问题也就自然而然地产生了。

这些年来，国内外专家学者对设施的动态布局问题进行了深入的研究。一部分专家使用了遗传算法，他们运用抽象的思维方式，将动态的设施布局问题抽象为一个个连续的静态的设施布局问题，通过遗传算法对这些连续的静态布局进行优化从而得到最优解，这种方法在实际运用中取得了较好的成果，为企业节约成本做出了贡献。与此同时，还有一部分专家，他们更进一步，在传统的遗传算法的基础上，作出了改良，使遗传算法更加适用于动态设施布局问题，不仅使算法运行的速度更快，而且最终的结果也更好。虽然，动态设施布局问题越来越引起专家的关注，相关的论文也越来越多，但是，大部分的论文都只停留在对物料搬运成本的数学分析，大部分论文的目的也只是求解出最小的物料搬运费用，从而忽视了车间的形状对布局产生的影响以及车间重置时所产生的损失。这些因素在布局方案中同样拥有较大的比重，所以我们在设计车间最佳布局的时候也必须考虑它们。

在国外，Mostafa Mazinani等^[1]于2013年对一种新的DFLP的结构进行了研究。由于结构的复杂性,只有小型问题在逻辑时间内可以得到解决。因此,他们提出了一种遗传算法(GA)来解决这个优化问题，并将其运用在了一些DFLP文学问题上，成功地证实了该算法的有效性。之后，Srisatja Vitayasak^[2]在2016年使用了回溯搜索算法(BSA)成功地解决一系列的设施布局问题(FLP)，创新地运用修改回溯搜索算法解决了随机DFLP与异构资源的问题，使得物流和设计成本之和达到最小值，并且该算法所需的计算时间不到GA 的70%，大大地提高了解决问题的效率。

在国内，由于市场经济的繁荣，市场所具有的动态性让现在的许多静态的设施布局模型失去了原先作用，所以越来越多的专家开始对动态的设施布局问题进行研究。在2011年，郭爽^[3] 等采用了一种改进型的遗传算法对DFLP问题进行求解，希望能够得到在车间的多个计划期不等面积设施布局的最优解集。他们将目标函数确定为计划期内物料的运输费用和设施的重置费用之和，同时将设施重置的费用抽象成设施搬动的费用与期间产生的损失费用之和，构建了一个包含多个设施多个周期的车间动态布局问题的数学模型，同时改良了遗传算法，并使用这个算法对该数学模型进行了运算。在该算法中，他们作出的改进主要表现为他们引进了自适应策略，使交叉算子和变异算子与种群整体的进化程度关联起来了，借此能够产生新的基因组合，他们希望通过这种方法能够提高搜索效率以及准确程度。最终他们又构造了一个的仿真算例，并使用该算法对这个算例进行了验证，事实上运算结果最终证实了这个方法是有效的。之后，为了提高生产系统的效率，即对设施的布局进行优化，同时也是对原先使用二次分配方法缺点的改进，在2014年，黄君政等^[4]将运用抽象的思维，从另一个角度出发，他们认为动态设施布局问题可以由设施的重新布局问题和多个时期的静态设施布局问题两个问题构成，所以他们设计了一个多目标的多时期的动态设施布局问题的数学模型，该模型主要对面积的利用效率，设施之间的非物流关系和重新布局的费用这三个方向进行了改良。他们运用了另一种新型的遗传算法，主要表现在，他们在原先的遗传算法中加入了精英策略，同时遵循了非支配的原则，从而得到了一个Pateto解的集合。该集合在实际的应用中有着很显著的优点，它能够让企业的最高层不拘泥于一个解，而是在考虑实际的市场需求后，依据企业自身的条件从而选择合适的方案，体现了计算结果的优越与人性化的选择两个特点。最后，他们通过了对柴油发动机厂的 的车间布局问题的实例验证，证明了该模型能够同时对车间布局的多个目标进行求解以及优化，同时最终的解集也表明了该模型有能力为企业的决策层提供有效的且合适的车间布局方案。

本课题基于市场的动态性特点，以车间动态设施布局问题为基础，将车间和设施简化成长宽不同的矩形，而后结合静态设施布局与动态设施布局两种不同的布局方式来进行研究，重新构造了一种基于不等面积设施布局的数学模型；最后改良了遗传算法，并用它对一个经典的仿真算例进行了运算，证明了这个改良方法的有效性。

2 遗传算法

生存，繁衍，进化是生物在自然界中谱写的主旋律。在地球上，有着不同的地区，不同的气候，不同的地形，在这些不同的条件下，生物演化着自己独特的生存方式，谱写着自然界最美的乐章，在亿万年以来，始终繁衍不息。这样伟大的自然现象展现出生物强大的适应能力。这启迪着人们对算法的研究与改进，在这个过程中，遗传算法诞生了。它借鉴了生物的遗传和进化的特点，代表着人类对自然界的一种模仿以及升华，是计算机模拟自然这一研究领域上的重要成果之一。

2.1 遗传算法的简介

遗传算法是一种模拟自然界适者生存的法则而创建的全局寻优算法。在1975年，美国密执安大学(University of Michigan，Michigan)的Holland教授最先提出了遗传算法。60年代初，自适应系统研究的蓬勃发展促进了遗传算法的产生；70年代，De Jong在计算机系统上开展了一系列数学模型的寻优实验，在这次搜寻最优解的工作中，他使用到了遗传算法（GA）；从此遗传算法的研究以及实验开始逐渐兴起；80年代，Goldberg阅读了大量有关遗传算法的文献和资料，并且进行了大量的研究，从而对遗传算法有了更加深入的了解，同时为了方便后来的人们对遗传算法进行探讨和创新，他系统地归纳和总结了遗传算法的常规步骤，为遗传算法的推广和体系的构建作出了巨大的贡献。

剩余内容已隐藏，请支付后下载全文，论文总字数：26764字

相关图片展示：