英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
应用遗传算法和Electre方法的多目标设施布局问题
G. Aiello, M. Enea, G. Galante
摘要
传统的解决布局设计问题的方法倾向于最大化布局的效率，一般靠计算设备间的流通量和各设备之间的距离决定。然而，实际的问题涉及多个相互冲突的目标，因此需要指定一个多目标的方法。最近提出，在大多数情况下，可以通过计算目标函数的加权和。这种方法的实用性差是量化这些功能权重的难度。在本文中，这个困难是由两个后续步骤逼近问题解决的：在第一步中，pereto最优解是通过使用一个多目标约束遗传算法和随后的选择决定最优解,这步是由多标准决策过程的Electre手段进行的。此过程允许决策者在候选解集的知识的基础上表现他的喜好。定量（物料搬运费用）和目标定性（设备之间的邻接和距离请求）被认为指的是基于结构布局的模式，即考虑实际限制，例如设备的纵横比。实验结果证实了此实行程序作为布局设计切实可行的辅助工具的有效性。
- 介绍：
一个设计精妙的设施布局包含了一系列在布局车间内部、确定形状和位置的设备。车间形状一般不强加，只需要是长方形。解决这个问题的传统方法是以某一个特定功能为标准最大化布局效率，如根据物流频率、设备间距离和设备纵横比满足的要求来确定搬运费用。首先第一个目标是以物料搬运费用为准来衡量的：Tompkins估计大约20%~50%的加工费用于物料运输和设备布局。第二个目标考虑到不同物体间的性质上的判断。实际上，对于两个设备间相邻要求的评价，是决策者考虑到不同物体，以主观意识为基础，根据设备的临近比例为基础做出的决断。因此，分析者的观点和基本范围将造成一个缺乏确定的评价过程带来的结果。对于布局问题的不同传统方法的分析可查看meller、Gau。
在这篇文章中，对于问题的评价考虑的不止一个目标的最优解。事实上，众所周知，布局问题包括一些方面将导致复杂的多目标问题。
从1979年开始，人们提出许多关于栽培上的布局多目标问题。Rsenblatt认为有两个方面的因素：数量（流动数据）和质量（代表“关联性”的最近比率）。因此形成了考虑到这些因素的特定的功能目标。这种方法涉及到实用理论，并运用了传统的求和比例方法。Harmonosky和Tothero拓展考虑到因素数量的影响。一些质量和数量的因素合并为单目标。首先，评价所有质量上的因素，使其可以用数学的方法处理。合法化所有因素，对每一个因素赋予一定比率，从而使其反应出与其他因素的关联。最后，所有的因素都复合成为一个因素。一个布局的构造过程是一个改进算法，这个算法最终实现了布局结构。由于划分比例不是一个一目了然的过程，Meller和Gau探究了不完善的比例对问题的影响。考虑到数量和质量的因素，Deb和Bhattacharyya提出了一个多目标的不确定体系。他们将自己的方法与传统的选择途径相比较，比较的方面包括物流费用、已占用空间和设备需要的最小空间。Lin和Sharp 比较其与方法相对于传统的选择例程流动的成本、占用空间和布局的所需的最小面积的标准布局评价。作者开发出由标准构成的三级分层结构，标准的水平和规范程度。三层标准组从此成立，包括：成本标准组，流量标准组和环境标准组。Utilising对应定性和定量指标，在这些标准中，作者开发的方法从中获得针对每个布局配置的比例，包括集成的标准和指标。并且，这种标准更加关注详细的布局方面的设计，而不是在布局中投入的调查。以杨和郭的提出的AHP和数据包络分析（DEA）为基础，在这个公式中，定性措施加上数值即AHP方法。由Spiral Algorithm产生第一解决方案，并随后通过三个手段方式成对交换算法，产生大量方式和以流量 - 距离功能排序的方法，即流量的乘积之和和depart-的中心之间的直线距离。DEA方法产生了最好的一个子集，目的在于提取前沿，即同样可行的候选人也放入最终布局。由Dweiri和迈耶使用并发现的层次分析法，将三个目标的权重（物料流信息流，
和设备流量）考虑在内。模糊的方法建议产生效关系的图表，构成CORELAP的修改版本的输入，用于产生新一代的布局解决方案。最后，该距离与部门之间的关系，是用来分配一个模糊的分数在每个解决方案中的比例。多因素模糊推理系统已经提出了通过Deb和Batta-charryya 用于定位机器块，使用在部门内部固定的提取/摆放位置。输入变量开始定义为模糊数，模型趋向于减少流动成本、固定空间和面积。基于所述成对比较法的方法，最近陈和沙在新的启发式方法为首选的一代目标的权重的前提下提出了解决多目标设施布局问题。特别是，一种迭代方法，可以解决决策者的不一致判断带来的影响。
在本文中，最佳布局由两个后续的步骤确定，使用的是不同的方法。在第一步中，Pareto最优解是通过采用多目标约束确定的遗传算法和最好的后续选择（第二步）进行，采用已知的多准则决策程序Electre。
- 问题分析：
布局的代表模型由Tate和Smith提出，名为“灵活隔间结构”。布局是一个确定长宽的矩形区域。这个区域被垂直分割为几部分，每一部分包含一个或几个矩形隔间。每部分的宽度就是这部分内所有设备的宽度，依赖于这部分设备的总面积。因此，每一个设备的高度取决于它的面积和宽度。因此，普通布局就是几个简单的条形结构，从左上角到右下角的隔间数量和顺序就可以描述布局。例如下面的三个条形结构：
这种方式的优点是包含在块内部的布局是容易变动的，在之后的布局设计过程中，是一个可以细化的部分。而且，这个条状结构也可以假设一个处理系统，操纵边缘的输入/输出设备可以放置在哪里。这个系统的主要缺点在于形状的约束是严格的，灵活可行的布局结构减少了许多。
关于布局结构的四个相关问题如下：物流费用、相邻要求、距离要求和设备的纵横比。下面的目标是要求考虑到的：
- 最小物料搬运费用；
- 满足最大相邻比例；
- 最大距离要求；
- 最大设备纵横比要求；
要求上面的这些目标是它们在艺术、质量、数量等方面经常被用来作为参数约束问题。
2.1物料搬运成本
第一目标函数表示的是最小化总材料搬运成本：
（1）
fij表示部门之间的物质流，cij表示单位成本（从一个部门向另一个部门移动成本）和dij表示部门中心之间的距离。
2.2最近邻接目标
第二个目标是邻接的最大化：
（2）
其中，rij是亲近参数，lij是接触部门i和j之间周长。
2.3距离要求
考虑的第三个方面是一些部门之间的距离要求。在布局中，对一些部门的相互分离。对于这样的要求，理由可能是，例如，环境问题，如噪音，振动，污染或相关工作人员的安全或火灾风险方面或爆炸。目标函数，也可以最大化，以表示这种情况下，由下面的等式：
（3）
其中，sij表示部门的距离参数值，dij是使用一个部门的中心之间的距离。
2.4纵横比要求
每一个设备都需要一个纵横比，一般使该设备能充分利用布局空间。用h和w两个参数表示矩阵；设备j的纵横比定义为：
Rj = max{hj,wj} / min{hj,wj} ; (4)
形状比例一般是可变的，在一定的间隔内，随着满意度的下降，比例偏离了最优解。当纵横比不合适时，目标函数急速降至0，因为制造的资源不能再放入设备内了。最简单的关于形状的目标函数如图Fig.2，arsj代表了设备纵横比满意度函数，rj.opt代表最优设备纵横比。
如果一个简单的设备有不可行的形状，那么整个布局就是不可行的，因此可行性用下面的式子表示：
纵横比（aspect ratio）= min(arsi);
或 纵横比（aspect ratio）= sum（arsi）;
一个空比例表示不可行的方案。
多目标遗传算法，如Section 3.1描述的，需要一个违反约束的评价去评判不可行的方案；因此，下面的参数定义：
V = Vr V1;
使用这个上面的式子计算不合法的方案。纵横比和合法函数如下图所示：
纵横比=
- 解决问题步骤：
前面介绍的问题的四个目标相互间存在冲突，并且其中一个目标（纵横比）也是一个约束，因此这个问题是一个多目标约束求最优解的问题。问题的解决需要两个步骤：第一步，在考虑到约束的情况下，这些解决不同目标的方法是确定的。每一种解都不能起主导作用，即每种解决方式都不一定比其他解决方式更优化；第二步，问题的其他信息用做衡量这些解决办法。多目标问题的传统解决方法是以某一个偏好向量构造一个特别的复合方法，以这种方式将多目标问题转换为单目标问题。如果一个与之相关的偏好矢量是合理的，那么这种方式就可以应用；否则，输入的信息与可能结果没有任何关系。因此，上面提到的两步法更合理，决策者在第二步中从一系列非支配的解中选择一个解。在这篇文章中，多目标约束的遗传算法用来找出最接近Pareto前端的最优解。因此，为了在众多解决方法中找到最优解，使用到了Electre多目标方法。
3.1多目标约束的遗传算法
本文引入一种基于多目标问题的遗传算法的精英解决策略，即NSGA-II。算法的步骤如下:
Step 1:随机产生个数为N的Po的初始种群；
Step 2:对每一代j，所有的个体随机选择两个形成N/2对。每一对形成的两个孩子是通过融合操作形成的，然后就形成了一个个数为N的种群。
Step 3:两个种群合并形成一个特别的数量为2N的种群Tj;
Step 4:克隆到下一代的数目在发生变异的比例控制内；
Step 5:通过Tj，最优的N个个体被挑选出来，通过选择过程（described apart）。这些个体形成了新的种群P(j 1)。
Step 6:变异操作以一定比例应用到个体中。
3.1.1基因编码
使用两个整数向量（染色体）：第一个是从上到下、从左到右的设施排列，第二个是在每一列中设备数目。
3.1.2交叉操作
对第一个染色体的交叉操作基于普通的制服的方案。二进制的序列是随机生成的。二进制串是随机生成的。复制父G1的基因中的子F1构成子代F1、F2，用1在二进制的对应串中表示。要完成F1，避免重复基因（即错误编码），引入它们在G2序列缺失的基因。生成的第二个子代是相反的。F1的染色体选择随机的断点在染色体之间G1和G2;类似的生成其他子代F2。
3.1.3变异操作
变异操作以固定概率执行每一个步骤。突变交替操作在第一或第二染色体具有已分配的概率。 在第一染色体中，变异是交换基因的一个固定的数，而在第二染色体中，它是随机选择变化的基因的歌数，保持它们的值的总和不变。这保证了可行性染色体的断点。3.1.4选拔程序
该过程将人口的个数从2N降到N。为了排列这些个体，下面的参数，考虑到重要性下降排序如下：
-
违反约束（可行域的距离，可行的个体拥有最高级别），
2.非支配的水平，
3.拥挤距离。
第一个参数是由式（7）表示，用于排名不可行的解决方案。
第二个参数是用来排名可行个体。目前人口的子集S j通过可行的个体被认为是构成;首先非支配解的水平是由非构成在Sj的主导解决方案。这样的非支配解被暂时从人口忽略。非其余人口consti-的支配解土特2级等的非支配解。该
组具有主导地位的同级别的解决方案构成了前面。一旦非排序程序主导因素已经过去，新的人口PJ 1是填充有不同程度的解决方法，一种由其他开始的最好的非支配前面。当。。。的时候趴在当前的前解决方案的数量成果其余位置，完成人口多，切刻策略是用于选择的解决方案，直到N个到达元素。选择的解决方案是那些居住在在前面的最不拥挤的区域。这个方法是通过以下方面的考虑有道理的。如代的数目增加时，在大多数解决方案种群将处于最好的非主导前，那收敛于帕累托最优前部和切口战略确保这些解决方案之间的更好传播。该具有拥挤距离的高价值解决方案是优选的。
3.2选择Electre法
-
算例
所提出的方法已被应用到的布局20个部门，必须放在一个方形区域内，等于表1中的部门的面积的总和。考虑的目标是那些在第2节，相关参数的报告在4.1节。
4.1目标
4.1.1物料搬运成本
在已经生成了部门之间的流动随机和表2中示出。fijin式流动。 等于斐济和斐济的总和在表2中的单位成本报告（成本移动一个从一个部门单位距离单位负载我要depart-换货j）的固定等于1每对部门，而部门之间的距离是曼哈顿它们的中心之间的距离。
4.1.2贴近请求
各部门RIJ款之间的接近程度要求米式（2），已经由二进制表示和示于表3。为了强调如何最终溶液方面这一目标，这些请求已仅限于部门的几对情侣。
4.1.3距离要求
两个部门之间的距离的要求可能是由于技术或安全问题。距离请求sijare
通过一个二进制再次表达和表4中报告。另外，在这种情况下，该链路已被限制为少数的夫妇部门，避免与前面的不一致目的。欧几里得距离已在此被使用
的情况，因为它更符合时的物理现象，如噪声，振动，热，都参与。
4.1.4宽高比
为了简化输入数据，以独特的满意功能已被作者假定到每个部门。特别是，线性函数被建立，在限定间隔1：0和2:5并到达的对应于1最大值1:5。该每个部门的长宽比满意功能为图5。
4.2 ELECTRE参数
通过的
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[29187]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
