英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
基于单排设施布局的高效遗传算法
摘要
单排设施布局是在给定的一条直线上安排设施的NP困难问题,以便于最小化所有对设备之间的距离的加权总和.由于其计算复杂度，研究人员已经开发了几个启发式来获得高质量的解决方案。在这篇论文中，我们提出了一种被叫作GENALGO的遗传式算法来解决大型单排设备布局的实例。我们的算法使用标准的遗传算子而且定期该善所有遗传算子的适合度。
我们的计算实验表明我们的遗传算法即使产生在随机生成的种群中也会产生高质量的解决方案。我们的算法提高了以前最出名的58个基准实例的19个实例的解决方案并且对于大多数其余的实例的解决也是有竞争力的。
关键词：设施规划设计；单排设施布局；遗传算法；局部搜索算法
-
引言
单排设施布局问题（SRFLP）是一个获得一个线性设施布局的问题，以便于最小化所有设施距离的加权总和。每对设备的重量，以及每个设施的长度是已知的，每对设备间的距离被定义为其质心间的距离。特别是实例中设施的数量被称为实例的大小。这个问题第一次被证明是被作为NP困难问题，正式声明的目的是最小化单排设施布局问题成本的表达
Z= (1)
是指设备的重量是指每对设备间的距离（i，j）。由于设备之间的距离取决于设 备的线性排列，故对于单排设施布局问题的解决方案是最大限度减少上述线性排列的成本表达。
单排设施布局问题模型已被用于许多实际情况，它被用于医院中房间的安排，办公楼中部门的安排或是在柔性制造系统中超市机器的安排，计算机存储磁盘中文件的安排，仓库布局的设计
在文献中，一些精确的方法已被应用于解决单排设施布局问题的最优性，这些方法包括分支定界，混合整数规划，切割面，动态规划，分支切割，半确定规划。目前，最好的可用的精确算法是最大的单排设施布局问题实例，拥有最优的42台设备排列。
研究人员集中解决大型单排设施布局问题实例启发。这些启发式方法有2种类型，结构和改进。对于单排设施布局问题建设启发式算法已经在[14，24]中提出。然而这些都后来被改进的启发式取代，大多数的改进启发式的单排设施布局问题是启发式，例如，模拟退火蚁群优化[ 10,13,25 ]，菌落优化[ 29 ]，分散搜索算法[ 17 ]，禁忌搜索算法[ 10,26 ]，粒子群优化算法 [ 27 ]，和遗传算法[ 9,22 ]，其中在[22]的遗传算法产生了大尺寸的基准单排设施布局问题实例的最好结果
在文献中，遗传算法已被应用在[9]和[22]的单排设施布局问题中，一个被称为帝国主义的竞争算法的紧密相关的算法在[20]中被提出参考文献[ 9 ]和[ 20 ]已报告基准有多达80个设施的情况，而[ 22 ]已报告的结果在一组有限基准的情况下，多达110个设施。我们提出了一个简单而强大的遗传算法并且测试了在文献中可供使用的实例的所有大型单排设施布局问题基准的性能。
我们的论文组织如下。在第2节我们介绍我们的遗传算法求解大型HENALGO SRFL实例。然后，我们报告我们的结果在SRFLP基准在教派的计算实验。在第三节将它们和那些在已发表的文献中的数据比较。第四节是工作总结。
- 遗传算法
遗传算法（见，例如，[ 12 ]）是一种对基于适应度生存原则的自然进化的仿真的进化搜索算法。被编码为个体，族群的可行的解决问题的方案是遗传因子的迭代改进办法，例如选择，交叉和变异来创建高适应性的个体。在优化问题中个体的适应性通常是衡量目标函数所代表的解决方案的价值的依据。对单排设施布局问题来说，低成本的解决方案意味着高适应性的解。对应在遗传算法中所遇到的问题的最高适应性个体的解决方案是对有关单排设施布局问题实例的近似最优解的输出
在本文中，我们提出了一个称为genalgo的遗传算法来解决单排设施布局问题。
该算法是一种在一代所有个体中进行周期性局部搜索排异来提高适应性的通用算法。
这个算法的伪代码如下，几个步骤的细节在那之后说明。
在genalgo算法，一个个体对应一个解作为一个排列的设施来编码，一个个体的适合度对应它所对应的表达成本给出。
在genalgo算法的第一步，生成一个初始的用户指定的确定数量的设备群体。为了使该算法以足够多样性的设备群体开始，对应于个体的解是随机产生的一系列设施的排列。给定一个解代，创建下一代解得第一步是创建一个遗传算法复制的交配池。这是在genalgo 4步完成。
在genalgo算法中，交配池是用二进制竞标选择方法创建的，在竞标选择中两个从群体中随机选择的个体的合适度会进入交配池。这可能会允许在交配池有多份相同的解决方案。在交配池中产生的解随后产生交叉和变异操作来为下一代创建候选解。我们在第5步用部分交叉算子来用用户定义的交换方式Pc使个体交换以得到子池。在genalgo 第6步，在生成子池后，每个子都提交给一个变异算子。根据用户定义的变异概率Pm,对应个体的解在以下小的方式改变。在解决方案中两台设备是随即被选择的第二台设备会移动以便跟在第一台设备后面。所有剩余的设施都充分转移。这种突变在文献中被称为插入的突变。Genalgo算法第7步是精华保存操作，确保每个个体在前代中的高适合度会被带入下一代，低适合度的个体在交叉和变异后会被隐去。这保证了种群个体的平均适合度不世代降解。步骤9是一个本地搜索操作，之后进行定期提高种群个体的适合度操作，我们在这一步中局部搜索的插入邻域，因为在文学的经验表明，插入附近是为单排设施布局局部搜索最好的区域。下面提供在步骤9中使用的本地搜索的伪代码。算法在生成用户指定打最大数量的代后结束。
Genalgo在有些方面不同于现有的遗传算法[ 9,22 ]。第一个区别是选择初始种群的解决方案。在[9]中提出的遗传算法的初始种群的每个解是用四种随机选择方法产生的。这样保证了初始设备群体的解的适合度很高，但是解不能足够的多样化。Genalgo算法随机产生的解落户于初始的设备群体。这确保了多样性，但不能确保解的平均高适合度。在这方面，Genalgo算法与算法[22]是相似的。第二个区别在于交叉算子。在[9]遗传算法使用了作者所设计的交叉算子，而在[22]的算法使用了为排列问题所设计的OX交叉算子。因为在初始的实验中PMX交叉算子的表现优于OX交叉算子，所以Genalgo算法也使用了为排列问题所设计的PMX交叉算子。在遗传算法[9]中突变参数值是自适应的，而在Genalgo算法中突变参数值是不变的。最后在Genalgo算法的第9步中使用的使用的局部搜索操作与[22]中的不同。在[ 9 ]中的遗传算法不包括任何局部搜索操作。
在下一节中，我们描述了Genalgo算法在大型单排设施布局问题的计算结果。
3.计算经验
我们用C语言对遗传算法genalgo进行编码，用gcc4编译器对其进行编译。我们在一台搭载英特尔i5 2500K 主频为3.3GHZ的处理器，4GB内存，运行Ubuntu Linux version 12.04版本系统的电脑上进行试验。我们让交叉概率Pc的值在0.6，0.7，0.8，0.9，和0.95中随机选择，让变异概率Pm在0.001和0.05中随机选择。每一次genalgo算法的运行可以产生最大5000代或直到设备群聚集结束。因为genalgo算法是随机的，我们运行200次genalgo算法并选择最佳的解作为genalgo算法的输出。我们在三类基准实例方面将genalgo算法的性能与已发表文献的结果进行了比较。第一类20个实例是是在[5]中用到的安霍斯实例并且被大多数研究人员效仿。这一类包含5中实例，每个尺寸60，70，75，和80。第2类的35个例子在[7，16]中被用到。它包含基于QAP基准的实例并被称为SKO实例。有5个实例每个尺寸42，49，56，64，72，81，和100。在[19]中介绍的第三类是一组三个大小110的实例。
这使得我们的实验最全面的，因为它包含了基于单排设施布局的所有的大尺寸的实例，这些实例的实验已经在最近的研究 [4，16]中被测试过了，但是没有在目前的遗传算法研究中[9，22]中被测试过。
3.1在[5]中安霍斯等人测试的20个实例
表1将200次genalgo算法运行200次输出解的成本与文献中安霍斯的实例（[22]）的最优解的成本进行了比较
表1 基于安霍斯的尺寸在60到80之间的实例的genalgo算法输出的解的成本
表的前两列给出了实例的名字和它的尺寸，第三列呈现[22]中的最佳成本。第4列报告了genalgo算法在任何运行输出的最优解的成本。第5列和第6列报告了genalgo算法200次运行输出的解的成本的均值和标准差。第7列报告了genalgo算法输出的解的成本的中位数。表格的最后一列报告了genalgo算法运行相应实例输出的最坏成本。
从表1来看，我们观察到对于每20个安霍斯实例，genalgo算法输出的最佳成本与文献中报告的最佳成本相匹配。平均成本被发现高于所有的情况下的中位数成本，从而表明在大多数运行中，算法genalgo输出的解的成本接近最佳成本。
表2将 genalgo算法执行安霍斯实例所需要的cpu计算时间与[22]中所报告的时间进行了比较，表2的结构与表1的结构相同。前两列描述了实例，第三列呈现了[22]中报告的时间，其余5列报告了算法genalgo在200次运行相应实例的过程中所需时间的最小值，平均值，中位数，最差值，和标准差。
表2 基于安霍斯的尺寸在60到80之间的实例的genalgo算法的执行时间
从表2中，我们观察到对于安霍斯实例，算法genalgo的执行时间比[22]中算法的执行时间少，此外，我们看到，随着问题规模的增加算法genalgo变得越来越快。我们所用机器的速度大约是[22]所用机器的3.3倍（基于CPU速度的比较，使用的数据来自http://www.cpubenchmark.net)。然而两个实现的执行时间不严格可比，因为语言和编译器的使用是不同的。
3.2 sko实例的测试
表3给出了算法genalgo200次运行输出解的成本与基于sko实例的QAP的文献中的最佳成本的比较。表3的结构与表1的结构相似。因为没有一个单独的研究报告所有实例的最佳成本，在第三列，每一个成本报告有一个指示费用来源的上标
表3 基于sko的尺寸在42到100之间的实例的genalgo算法输出的解的成本
表3中粗体显示那些genalgo算法产生的成本低于文献中已知的解。从表3中，我们发现genalgo算法的表现优于已知的35个中的19个sko实例的算法。在余下的16个实例中genalgo算法的输出成本等于文献中得到的那些。有趣的是，在6的实例中genalgo算法的平均输出成本优于先前文献中已知的最优成本。就安霍斯的实例而言，在基于sko实例的大多数QAP中，genalgo算法输出的平均成本低于平均成本说明genalgo算法在多数运行下输出低成本的解
表4呈现了genalgo算法运行这些实例产生最优解所需要的时间与其他算法的执行时间的对比。表4的结构与表2的结构相似。对大小介于64和81之间的实例来说，最优成本解是在[4]中提出的，但是却没有提供得到解所需的确切时间。对于这些实例，我们在[4]中提出了限制的执行时间。
3.3带有110个设施的拉提佛和阿马拉尔[ 19 ]实例测试
表5给出了genalgo算法运行3个拉提佛和阿马拉尔[ 19 ]介绍的尺寸为110的三个实例200次得到的解的成本与[22]中介绍的解的成本的对比。文献中已知的对于这些实例的最优解已经在[22]中被报告了。第一列给出了实例的名称，第二列给出了文献中已知的最优成本，其余列给出了genalgo算法得到解的成本的细节。结果显示genalgo算法得到的最优输出对于[22]中的三个案例中的两个匹配，对另一个实例有一定误差。表6给出了genalgo算法运行这些案例所需要的执行时间的细节
从我们的计算结果来看genalgo算法在解决大型单排设施布局问题实例方面是很有竞争性的。
4.结论
在本文中，我们提出了一个包含局部搜索的解决大型单排设施布局问题(SRFLP)实例的高效的叫作genalgo的遗传算法。我们将genalgo算法在解决大型单排设施布局问题的表现与文献中其他算法的表现进行了比较。我们的测试床包括58个大小范围从42到110的实例。我们发现，在19个实例，genalgo算法产生优于已知文献中的算法的最优解。在其他的37个实例中，genalgo算法产生与已知文献中最优解匹配的解，在另两个实例中，genalgo算法产生的解有一定误差。因此我们在本文中提出的genalgo算法对于解决大型单排设施布局问题是有竞争力的
目前的研究在使用标准基础操作运行方面是有局限性的。这在使它易于实现方面是有优势的，但更先进的设备可能会产生更好的结果。所以一个进一步研究的直接方向是更先进的启发式genalgo算子的性能测试。其他的局部搜索方法，如2-opt或3-opt邻域可以驱动步骤9中的局部搜索算法。测试不同的交叉和变异算子也可以发现更好的启发式算法来解决大型单排设施布局问题实例。你也可以寻找解决大型单排设施布局
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[147901]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
