英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

基于排列遗传算法的单排设施布局问题

（迪利普·达塔^a，安德烈R.S·阿马拉尔^b，何塞·瑞菲盖拉^c）

关键词：单排设施布局问题、遗传算法、优化组合

摘要：在本文中，以最小的成本安排一定数量设施到单排流水线上的NP-hard问题，称为单排设施布局问题（SRFLP），运用了基于排列的遗传算法（GA）。对GA个体通过使用一些基于一定规则和随机排序得到设施的排列，这些设施的排列再由专门设计的交叉算子和变异算子的计算，使其朝向优化的方向改善。这样的计划使GA处理SRFLP就如处理一个无约束优化问题。在计算实验中进行的以前文献中出现的工序数从60到80的大问题中，所提出的GA改善了几个先前已经得知的最好的方案。

1.简介

在单排设施布局问题（SRFLP）上，我们希望安排n台设施到一条生产线上，以便减少设施之间的运输费用。更精确地说，给定设施i与设施j之间的物料流量为（i，j = 1，. . . ，n其中），且设施长度为 (i = 1，. . . ，n)；其目标是最小化一个被定义为每对安排过了的设施对之间的物料流量和设施对中心间的距离的乘积之和的函数值。通过 表示N={1，2，...，N}的所有排列pi;的集合,SRFLP的数学表述如下（阿马拉尔，2006年）：

其中表示根据排列pi;计算的设施i与设施j中心间的距离，它的计算公式如下：

这里与分别指设施i与设施j的长度，在排列pi;中，是从i到j的所有设施的排列（第一个是i，最后一个是j），是第k台设施的长度，是第k－1台设施与第k台设施间的间隙。

SRFLP的应用之一是在办公楼、超市或医院中将部门安排到通道的一侧（西蒙斯，1969年）。皮卡德和凯拉纳（1981）讨论这个问题的一些其他的实际应用，Heragu和Kusiak（1988）描述了一种运用，在生产制造系统中，运用自动搬运车（AGV小车）在放置成一条直线的机器间运输物料。

SRFLP是一个NP-hard问题（Beghin-Picavet和Hansen，1982年）。他们提出了这个问题的精确解决办法，包括分支定界法（西蒙斯，1969年），动态规划法（皮卡尔和凯拉纳，1981年 ），半正定规划（Anjos和Vannelli，2008年），和（混合）整数线性规划（Amaral，2006，2008年，2009年；Heragu和Kusiak，1991年；Love和Wong，1976年）。阿马拉尔和Letchford先生（2008年），基于大规模实例的线性规划问题（LEM），提出了一个强下界。通过半正定规划也获得了与强下界大型SRFLP实例同样的结果（安若斯等人，2005年）。

由于SRFLP的内在困难，考虑启发式方法来处理它的大问题是合理的。许多这样的启发式方法已经得到了发展。例如，混合模拟退火（Heragu和Alfa，1992年），建设性的启发式贪婪（Kumar等，1995年），基于元启发式算法的技术（德阿尔瓦伦加等人，2000）和蚁群算法（Solimanpur等人，2005）。很多最近的SRFLP启发式工作，包括分散搜索（Kumar等人，2008年），粒子群算法（Samarghandi等，2010），和禁忌搜索（Samarghandi和Eshghi，2010）。

在本文中，研究遗传算法（GA）是为了解决SRFLP问题的。一个遗传算法的个体代表着一种设施排列方案。遗传算法种群由随机排列，或者基于规则的排列来初始化。通过使用专门设计的基于排列的交叉算子和变异算子，然后遗传算法种群向优化的方向改善，这就产生了新的设施排列。由于每个设施的排列都是SRFLP的一个有效的解决方案，且上述GA方案只能产生这样的排列，所提出的GA可以对SRFLP问题以无约束优化的方式求解，正如定义成方程（1）和（2）那样的。计算实验表明，GA在变量个数不一样的不同实例中，是非常高效的，在文献中已经讨论过这样的实验。特别是，对于最难的实例，变量的规模在60和80之间，其最佳的解决方案是未知的，GA改善了许多解决方案，这些方案在之前被认为是最佳解决方案。

所提出的GA在第2部分中阐述，计算实验在第3部分呈现，接着第4部分得到文章的结论。

2.针对SRFLP的遗传算法

遗传算法（GA）是一种基于优胜劣汰理念机制，模仿达尔文进化论的随机搜索技术（德布，2001年；戈德堡，1989年）。一个遗传算法的最基本、最关键的部分是解决方案的表现，俗称染色体或个体，它代表了问题的一个完整的解决方案。一个遗传算法是以随机个体的集合而开始的，称为种群，这是通过对一个从自然进化而来的个体反复应用某些遗传算子，如选择、交叉和变异进化了几代而来的。选择算子强调良好的个体和消除弱势个体而形成一个临时种群，这个种群称为交配池，这是从原始的种群中对良好的个体进行多次复制而形成的。交叉算子生成子个体，是通过按照一些预定义的交叉概率使用交配池中的父个体而生成的。变异算子探讨了邻居子个体，这种变异是由交叉算子所产生的，运用了另一个预定义的概率，称为突变概率。以这种方式，这个种群的给定目标函数的最优值逐渐得到改善，这个函数被称为适应度函数，这是一种衡量一个个体质量的方法。种群的进化过程一直持续到一些终止条件的出现，通常直到一个预定义的最大数量的后代的产生或达到了目标值的理想改善量。

2.1个体表现和初始化

一个GA个体(解决方案)是一个由一些元素组成的数组，数组的域名或单个元素，描述了一个问题的设计变量。在一个个体中，有四种基本的编码技巧来编码设计变量，被称为二进制编码、实数编码、整数编码和排序编码。在二进制编码表示中，其中一个元数可以具有1或0的值，一个变量由数组的域名表示。在所有其他三个编码表示中，一个单一的元素代表一个变量，这个变量分别允许有一个实数值、整数值，和不重复的/独特的整数值，这是与他们唯一的区别。就手边的SRFLP问题而言，很自然的选择是排列表示，这里的个体是将需要安排的设施进行排序的一个排列。

一旦个体表示的类型被选择，接下来的问题是如何初始化这个个体。不像许多实数或整数值的问题，随机的值可能不能分配给所描述的SRFLP问题中的个体元素。这样的初始化可能会产生一个不可行的个体。众所周知的是，在任意组合的问题上重新获得个体的可行性是一个大挑战（Datta等人，2008年）。因此，一个随机的技术和三个基于规则的技术运用到这里，以便得到一个对SRFLP问题有效的设施排列。为创造良好的排列，尽管采用三个固定的基于规则的技术，随机技术也被认为仅仅是获得一个多元化种群的方法。除此以外，遗传算法搜索可能会卡在某个局部最优。这些初始化个体的技术在接下来的四个分节中描述。

2.1.1 随机初始化（RND）

在这个方案中，在临时设施排列的帮助下，个体被安排到一个有效的随机排列中，其中，所述设施是串联布置的。然后，每个个体元素，按升序一个一个，被分配到一个随机的设施的临时排列中。每一次，一个临时排列的设施被分配给一个个体元素，临时排列通过消除设施来更新。这个过程可以确保分配给一个个体的排列是有效的。

2.1.2最糟糕的配在一起（WPT）

如果的值是所有设施对中最高的，则设施i和j被认为是一对最坏的设施对。基本原理是，如果最糟糕的设施对尽可能多的被放在一起，则会形成一个好的排列。在这个方案的实施中，设施对首先会按照他们的上述乘积的非增序来分类。然后，一个子排列是通过把最初始的设施对放在一起而形成。对于接下来的设施对（i，j），执行下述三个步骤中的一个：

1.如果设施i和j已经被包括在一个或多个子排列中，就考虑队列中的下一对。

2.如果设施i和j都没有被包括在任何子排列中，把它们放在一起形成一个新的子排列。

3.如果设施i已经被包括在一个子排列的设施中，将设施j放在这个子排列的一边（左边或右边），这将会为加强的子排列形成一个更小的目标值。

当所有的设施对已完成操作，把第一个子排列和后续的子排列加合到一起，一个完整的排列就形成了。在这里，一个子排列按照步骤3（包括单个的设施），以相似的方式加合到一起。

尽管非常符合逻辑，就像上面所提到的，如果超过一对具有相同值的设施对，这个方法可能无法给出一个很好的排列。这是因为，对于具有这种相同值的设施对，不同的排序是可能的，这将会导致随后的不同排列。然而，它可能无法检查所有这样的排列，特别是当具有相同值的设施对的数目很大的时候。

2.1.3基于流的排列（FBP）

这种方法是基于这样的假设，即如果将在他们之间具有最小数量的流量的设施，放在排列的两端，且让其中间的设施具有最大数量的流量，则会产生一个良好的排列。在这个方法的实施过程中，首先将设施排序，但是按照，的值的非降序排列。然后，通过把设施按顺序排放在队列两端来形成一个排列。更奇妙的是，如果按上述方法的排序是（1），（2），...，（n），则排列为（1）（3）...（n）...（4）（2）。

正如在2.1.2章节讲的WPT技术的情况一样，如果超过一对设施，就像上面所提到的，具有相同的值，这个方法可能无法给出一个非常好的排列。这是因为，对于具有这种相等值的设施对，不同的排序对是可能的，这将会导致随后的不同排列。

2.1.4基于长度的排

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[152403]，资料为PDF文档或Word文档，PDF文档可免费转换为Word