【基于遗传算法对W公司最终布局优化与评价案例5300字】

47基于遗传算法对W公司最终布局优化与评价案例综述1基于遗传算法的车间布局优化模型构建模型的基本要求和思想模型的基本要求数学模型是将实际问题与数学理论相结合的一门学科，主要就是用定性或者定量的方法通过字母、数字或者其他符号等建立数学表达式使抽象的问题具体化，在近年来发展迅速并得到广泛应用。在建立数学模型的过程中，为了方便后续模型求解以及增强模型的实用性常常需要对复杂的现实问题做一些简化和假设，通常需要满足以下几点要求：真实完整。实际问题的完整性以及数据的真实性是保证建立合理有效数学模型的前提，以便更好的体现模型的应用价值。条件充分。在建立模型时，要根据实际问题所需选取恰当的决策变量来描述问题的特征，要明确实际问题所需的约束条件，以便更好的建立模型。适应变化。随着人们对理论知识的深入研究以及实际问题情况的相关条件的变化，可以对模型中相关变量以约束做出调整，以便更好的解决实际问题。车间布局优化模型的思想车间作为制造型企业生产的基础，车间布局是否合理直接影响企业产品生产周期以及生产成本，因此成为跨学科的研究课题以及规划设计专员一直在探索研究以寻求更好的解决方案的问题。在本文中主要对W公司物流关系和非物流关系进行分析，建立双目标目标函数并根据企业实际情况设定约束条件，以得到车间布局最优得方案。车间布局和常见得几何形体布局不同，几何形体布局一般各个几何形体之间不存在相关性，是独立的个体，并且要求根据其约束条件以实现最小化体积或者面积。相较于几何形体布局，车间布局各个作业单元之间存在物流关系甚至存在非物流关系。因此建立车间布局优化模型时，要根据车间的生产区域面积以及各个作业单元所需面积情况，建立最大化物流关系目标函数，此外还需要考虑现实约束条件，如各个作业单元在车间只能出现一次、相邻作业单元之间不可以出现重叠等等，只有这样求解出的布局方案才能符合实际情况且具有一定的应用价值。模型的假设由于W公司实际的生产车间布局较复杂，而数学模型是对实际问题的简化描述。因此，为了更好的构建适合车间布局的模型，增强模型的可靠性与实用性，本文对其所设及到的相关数据和条件列出下列假设：（1）假设W公司生产车间以及车间各个工作单元的形状都为矩形，车间边长已知，忽略它们的具体形状细节；（2）假设W公司生产车间各个工作单元间物料的搬运方向与车间的长度和宽度平行，都采用直线行驶的方式；（3）假设W公司生产车间各个工作单元随机排列，且与车间的墙壁四周平行；综合上述假设，W公司的车间布局优化问题的数学问题可以描述为：在工作单元数目、搬运距离、物流量已知的情况下，求解最小化物流量距积和最大化非物流关系的双目标函数，即根据车间现状所得出得最优布局方案。具体生产车间布局坐标示意图见图5-1。图5-1生产车间布局坐标示意图Figure5-1Layoutcoordinatediagramofproductionworkshop模型的目标函数在对W公司车间布局进行优化研究的过程中不仅对其物料搬运强度进行减少，而且对其有相关关系作业单元之间的紧密程度进行加强。因此，构建出以最小化物流量距积和最大化非物流相关单元的双目标函数。首先确定物流量距积的目标函数。假设W公司车间布局有一个布局规划方案，和是其中的作业单元，则用表示作业单元和作业单元之间的距离，表示作业单元和作业单元之间的物料搬运量，其中。故作业单元间的距离矩阵和物料搬运量矩阵为：（5-1）（5-2）由距离矩阵和物料搬运量得到最小化物料搬运强度的目标函数：（5-3）在公式5-3中，表示物流量量距积。然后确定非物流关系的目标函数，通过各个作业单元之间的密切关系等级来表示其远近程度。故得到最大化非物流相关作业单元之间关系的目标函数：（5-4）在公式5-4中，表示非物流相关作业单元关系的总和，表示作业单元和作业单元之间的密切程度与距离产生的关联因子，表示作业单位在非物流关系影响下的相互之间的密切等级。和的取值分别见表5-1和表5-2[41]，其中的取值由作业单元和作业单元之间的距离所决定的，其界定值采用的定义，分成六个子区域，根据所处的子区间判断各相关作业单元间的邻接度[42]。表5-1非物流强度等级量化表Table5-1Quantitativetableofnon-logisticsintensitylevel密切关系等级意义A绝对重要4E非常重要3I重要2O一般1U不重要0X需要远离-1表5-2关联因子量化值表Table5-2Quantitativevaluesofcorrelationfactors作业单元距离关联度取值10.80.60.40.20其中，为W公司生产车间规划区域的长度和宽度的总和[41]。综上以上对物流关系和非物流关系的分析，构建出以最小化物流量距积和最大化非物流相关单元的双目标函数，且物料搬运距离的计算公式为物料在工作单元中心点的起始位置坐标与终止位置坐标的差值，即：（5-5）在公式5-5中，是物料搬运的距离，`是工作单元中心点的起始位置坐标，是工作单元中心点的终止位置坐标。各个表达式符合和具体代表的含义见表5-3。表5-3各公式符号及其含义Table5-3Formulasymbolsandtheirmeanings符号含义作业单元序号总物料搬运强度非物流相关作业单元之间关系之和作业单元和作业单元之间的物料搬运距离工作单元中心点的起始位置坐标工作单元中心点的终止位置坐标作业单元和作业单元之间的物料搬运量作业单元和作业单元之间的密切程度与距离产生的关联因子作业单位在非物流关系影响下的相互之间的密切等级为了求解方便，将双目标函数转化为单目标函数后得到下面目标函数表达式：（5-6）（5-7）（5-8）（5-9）通过查阅相关资料数据以及企业自身生产规模状况，决定将物流量距积和非物流相关强度的权重设定为1：1，即。此外，考虑到和之间存在量纲的差异，因此对二者进行标准化处理：（5-10）（5-11）故最终目标函数表达式为：（5-12）结合W公司实际情况后为了实现目标函数表达式（5-12），目标函数需满足以下约束条件：（1）每一个作业单位在车间布局中只能出现一次，而且只能布置在某一行中，即（5-13）每一个作业单元之间留有一定的间隙，确保相邻作业单元不会出现重叠的情况，即：（5-14）（5-15）每一行或者列上的作业单元在X轴或者Y轴方向上的长度或者宽度总和必须小于生产车间的总长度或总宽度，即：（5-16）（5-17）在上述约束条件中，和分别表示W公司车间的长度和宽度，和分别表示作业单元和的长度，同样和分别表示作业单元和的宽度，和分别表示作业单元和在X轴的距离和Y轴的距离。2基于遗传算法的模型求解过程2.1编码机制对于车间布局问题主要是确定各个作业单元的相对位置进而得到布局规划方案，因此在选择算法编码机制时只需要选择表示相对位置的符号即可，无需涉及到数值运算。针对车间布局问题的这一特征，本模型采用符号编码机制，即选用自然数来表示各个作业单元及其相对位置关系。2.2初始种群在使用遗传算法对研究对象进行求解时，为了在优化过程中较快找到最优解，还需要产生一组个体组成初始种群来做为遗传算法的初始解。传统遗传算法大都采用随机方式来产生初始化种群，虽然该方式简单易操作，但对于算法后续的运行速率以及种群选取的合理性进行保证。为了增强遗传算法的运行速率和准确性，专家学者在后续的研究中提出可以根据研究对象的实际情况构造或者从其他算法中选取较优的染色体作为初始种群。因此，本模型采用SLP方法初始布局方案和随机方案相结合作为初始种群。2.3适应度函数遗传算法在求解过程中根据适者生存原则选择下一代的个体，对外部信息的依赖度不高，主要通过对目标函数进行变形后得到适应度函数，进而对初始化种群中的个体好坏程度进行评判，选择出适应度较高的个体使其更多的繁殖下一代，依次循环，最终留下最好的个体。大多数情况下采用表示目标函数，表示适应度函数的表达方式，根据对适应度函数的分析以及本模型所研究的是物流量距积最小的目标函数，采用取倒数法来确定适应度函数，即：（5-18）其中，2.4遗传算子遗传算子在操作过程中，主要涉及到选择、交叉、变异和终止四个步骤。选择在运用遗传算法进行求解的过程中所涉及到的选择操作，最常用的是轮盘赌方法。本次遗传算法运用轮盘赌的方法对初始种群个体进行选择操作，首先对每一个个体的适应性值进行计算并全部进行求和，然后计算出每一个个体适应性值在总体适应性值中的所占的比例大小，最后运用轮盘赌方法对种群中的个体进行选择，个体被保留遗传给后代的概率为：（5-19）其中，为种群规模，为个体所计算出的适应性值。（2）交叉交叉操作是增加样本种群中个体数量的主要方法。遗传算法中的交叉是指按照一定的规则，对种群中的两个相互配对的个体中的单个基因、多个基因或者部分基因进行交叉运算，进而产生两个新的种群个体。在进行交叉操作之前，首先需要采用随机配对法对初始种群中的所有个体进行两两配对，然后根据研究对象的实际情况进行分析，在保证不对个体的良好基因进行过多破坏的同时有较多的个体产生。根据本次研究对象的情况的交叉操作运用部分匹配交叉的方法。（3）变异变异操作是增加样本种群中个体数量的辅助方法。遗传算法中的变异是指种群中的个体在遗传运算的过程中，通过对单条染色体基因的改变进而产生新得种群个体，其对遗传算法的局部搜索能力有较大影响。通过交叉和变异操作的结合，增强了遗传算法的搜索能力，可以使得寻找最优解的过程变得高效。常见的变异算子设计方法有基本位变异、逆转变异和交换变异三种。（4）终止遗传算法通过对种群规模最大迭代次数进行限定来终止算法的运行，并根据实际所需将编码进行解码得到最终结果。为了防止算法过早终止而得不到最优解，本次将遗传算法迭代次数设置为1500次。综合上述分析，遗传算法的整个运算求解过程见图5-2。图5-2遗传算法求解步骤Figure5-2Geneticalgorithmsolvingstep3模型应用与结果评价3.1模型应用W公司整个生产车间长为60米，宽约45米，占地面积约2700平方米，是单层生产结构，可分为18个作业单元，各个作业单元所需面积及长宽参数见表5-4。表5-4车间作业单元面积及长宽参数Table5-4Workshopareaandlengthandwidthparameters作业单元序号作业单元名称需求面积/平方米长/米宽/米1原料库1261872研发室24643来料待检区24644投料区32485烧录区136946烧录区236947组装区40858入库待检区40859测试区328410老化区7212611包装区16416412包装区2549613入库暂存区4041014半成品库143131115成品库200102016维修区12030417办公室17.553.518消防重点区45153各个作业单元之间的物流量矩阵和作业单位在非物流关系影响下相互之间的密切等级关系矩阵分别见（5-20）和（5-21)：(5-20)（5-21）作业单元和作业单元之间的密切程度与距离产生的关联因子采用Lee的定义[42]，由作业单位之间的距离与生产车间规划区域的长宽之和的比值划分为六个子区域，每一个区域有一个对应的关联因子，根据W公司实际情况可得，具体关联因子量化表见表5-5。表5-5关联因子量化表Table5-5Correlationfactorquantizationtable作业单元间距离10.80.60.40.20为了防止遗传算法在求解过程中过早收敛的情况发生，相关参数设定如下：初始种群大小,最大迭代次数，交叉概率，变异概率。运用MATLAB编写遗传算法程序，相关参数均按照上述数据设定后对模型进行求解，运算过程见图5-3。图5-3遗传算法迭代曲线Figure5-3Geneticalgorithmiterationcurve从图5-3可以看出，遗传算法迭代运行次数到1300次左右时接近收敛，可以认为此时求解出的布局方案为最优解，作业单元之间的相对位置即车间最优规划布局见图5-4。图5-4最终车间布局规划图Figure5-4Finalworkshoplayoutplan3.2结果评价为了验证最终车间布局规划方案的有效性，采用定量与定性相结合的方法进行分析评价。首先是定量分析，根据W公司实际情况车间布局现状、SLP方法初始布局方案以及遗传算法最终车间布局的相关作业单元的物料搬运距离见表5-6。表5-6优化前后车间布局物流量距积Table5-6Logisticsvolumeproductofworkshoplayoutbeforeandafteroptimization序号相关作业单元现有车间布局物流量距积（Kg·m）SLP方法车间布局物流量距积（Kg·m）遗传算法车间布局物流量距积（Kg·m）11-2749.291249.351402.8121-3504.871094.63183.3331-42057.193882.493577.9342-51015.002092.94591.5352-8600.96500.06335.7962-1697.64267.31368.5172-1739.8795.62136.1483-51961.703996.20761.9793-147135.545541.156248.39103-18384.24423.03115.23114-52156.491724.351011.47124-71918.721920.561312.75135-61094.801164.721369.13145-71097.822552.851703.89156-72223.262886.013541.08166-141042.371069.981442.79177-88638.757755.75296.82187-143003.003119.582430.34198-98030.308104.352196.28208-10439.43128.915497.93219-113411.803760.95226.87229-14657.941068.281445.04239-16160.69139.85745.902410-11284.32222.9163.252510-161625.481081.651476.732611-1