基于遗传算法的选址问题外文翻译资料

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

---

基于遗传算法的选址问题

摘要

本文旨在评估遗传算法作为替代程序计算选址问题最优或近似最优解的性能。考虑的具体问题有无容量限制和有容量限制的固定费用问题、最大覆盖问题和有竞争的选址模型。我们利用公开可用数据集的测试基础，将开发的基于遗传算法的启发式算法与文献中众所周知的启发法进行性能对比。

范围和目的

遗传算法是潜在的解决大规模组合优化问题的强大工具。本文探讨了使用这一类算法来解决一系列选址问题。目的不是证明这些算法优于目前应用于解决选址问题的程序，而是确定在哪些情况下这些方法能更为有效和可行地作为一种可替代或更优越的启发式解决方案。1.介绍和因素

近三十年来，获得选址问题最佳和最接近的解决方案刺激着选址分析领域的发展（参见Daskin [1], Drezner [2] , Mirchandani和 Francis [3]）。但是，这一领域的主要模型，即固定费用选址模型，非竞争定位理论的覆盖模型和竞争定位理论的中值和中心模型，均为NP（非确定性多项式）难问题，即计算困难的组合优化问题(参见Jacobsen [4], Krarup and Pruzan [5] 和Hakimi[6])。由此可见，精确的算法只在中等规模或特殊情况的问题的计算上是可行的。因此，大量的研究努力致力于设计以合理的计算时间运行并产生可接受效果的解的启发式算法程序。

遗传算法（GAs）是基于自然选择的生物进化过程的一种随机搜索优化启发法(参见Goldberg [7])。但是，选址问题对于遗传算法的应用相对较少。在Beasley和Chu [8]以及 Lorena和de Souza-Lopez [9]的两篇论文中，作者侧重于应用遗传算法解决覆盖问题。对于这种选址模型，或许最早应用遗传算法的是在Hosage和Goodchild [10]的文章中，他们提出了对p-中值模型的遗传算法改进。最近，Owen和 Daskin [11,12] 已经使用遗传算法来解决战略设施选址中的复杂模型。不过，据我们所知，对基于遗传算法的选址模型的比较性能的综合研究以前没有尝试过。鉴于遗传算法已经被证明对非凸优化问题是非常有效的，因此它比较容易评估给定可行解决方案的质量，但难以通过确定性迭代方法系统地改进解决方案这一事实，这项综合研究尤其重要。受这些考虑的推动下，本文评估了应用于选址理论中五个代表性模型的遗传算法的性能。对于非竞争的选址模型，我们选择了无容量限制和有容量限制的固定费用问题（参见[5]和[1，第7章]）和最大覆盖模型（见[1，第4章]和[3，第6章]）。对于竞争的选址模型，我们选择了中值和中心模型[6]。在选择这些模型时，我们主要考虑两个因素。首先，模型必须尽可能一般。 因此问题选择的是固定费用选址而不是p-中值选址，因为后者是前者的一个特殊情况。同样的原因，我们选择了最大覆盖模型。其次，我们希望实证研究和报告的模型基于公开可用数据集。我们选择的所有五个模型都满足了这些限制。对于每个这些选择的模型，我们开发设计遗传算法，并使用公开可用数据集的测试基础将其性能与文献中的知名启发式进行比较。

2.遗传算法：概述

遗传算法的概念首先是由Holland [13]提出，后来Goldberg [7]对其进行了详细阐述。遗传算法是基于自然选择和遗传学机制的随机搜索技术。不同于常规搜索技术，它以称为种群的一系列初始解为搜索起点。种群中的每一个个体被称为染色体，并且在我们的语境中，其代表现有问题的解决方案。染色体是一串符号; 其通常是二进制位串，但也有其他类型。染色体通过连续迭代演化，称为代。在每一代都使用适应度评估染色体。为了创造下一代，使用交叉操作融合来自当前一代的两条染色体或使用变异算子修改染色体来形成后代的新染色体。按照适应度值选择一些父母和子孙，并拒绝他人进入以保持种群数量不变，这个中间种群形成新一代。适应度更高的染色体具有更大的可能性被选择。经过若干代，最优解收敛，代表着对于所求解问题的最优或次优解决方案。令P(t)和C(t)分别代表当前第t代的父母和后代；遗传算法的一般结构如图1所示，其描述如下：

第一步：设置t=0；

第二步：生成初始种群P(t)；

第三步：评估P(t)并算出适应度值；

第四步：当（不终止条件）执行下一步；

第五步：按照适应度值选择并重组P(t)得到C(t)；

第六步：评估C(t)；

第七步：从P(t)和C(t)中得到P(t 1)；

第八步：设置t=t 1；

第九步：结束此次循环；

第十步：停止迭代。

我们在实现上述通用遗传算法时使用了两个终止标准。一旦算法收敛（即目标函数值的改善降低到小于10^-5的容差极限），或者已经运行达到预先指定的遗传次数时这个通用算法停止执行。读者可参考文献[7,14]和Reeves [15]更详细地了解遗传算法。

3.针对我们所研究的选址问题的基于遗传算法的启发式

基本的遗传算法方案结构允许实现基于遗传算法的启发式的各种方法，并且对这些方法的探索已经形成了大量的科学文献。在本节中，我们将简要介绍我们对基本遗传算法进行的主要修改，以及从文献中采用的准则，以获得针对我们考虑的选址问题的合适的基于遗传算法的启发式。

3.1编码方案

为特定问题设计遗传算法的第一步是设计合适的编码方案。开发的编码方案是一个n_f位的二进制符号串，作为染色体结构，其中n_f是潜在设施场所的数量。第i位的值为1意味着设施位于第i个站点。一个个体染色体（解）的二进制编码如图2所示。图2所示的网络有四个潜在的设施场所。（a）表示只选择位于潜在场地1和4的两个设施的情况，（b）表示选择所有潜在的设施场所的情况。（a）和（b）的各个二进制编码也在同一图中表示出来。

3.2适应度函数

遗传算法中的适应度函数是对目标函数的解的优劣的量度。在我们改进的遗传算法中，个体的适应度与其目标函数值直接相关。

3.2.1无容量限制的固定费用问题的适应度函数

无容量限制的固定费用选址问题的目标函数可以表达为如下：

其中

——表示由j点设施供应的客户点i的需求分量；

——表示在候选点j建址的固定费用；

——表示客户点i的需求；

——表示客户点i与候选点j之间的距离；

c——单位需求单位距离的运输费率。

个体的适应度可以通过评估目标函数的两个组成部分（和运输成本）来计算并相加。

解决方案i的固定设施成本可由以下公式计算：

其中是对应第i个个体字符串中第j位的值。为了评估运输成本，我们首先找到一套目前解决方案的开放设施。接下来，由于这些设施是无容量限制的，所以我们计算通过将每个需求节点分配给最近的开放设施来计算各自的最小运输成本。

3.2.2有容量限制的固定费用问题的适应度函数

有容量限制与无容量限制的固定费用问题目标函数相同，固定设施成本的计算方式与上述问题完全相同。为了计算运输成本，我们注意到，如果我们给出一套可行的设施，这些设施的总容量超过总需求，则将需求分配给设施的问题变成了可以用特殊的方法解决的运输问题，如运输单纯形法。设施的容量小于总需求时，目前的解决方案是不可行的，个体的适应度将分得一个惩罚值。我们分配的该惩罚值远大于当前种群个体的任何可能的目标函数值。

3.2.3最大覆盖问题的适应度函数

最大覆盖问题的每个可能的解决方案的适应度函数值是通过查找属于正在评估的解决方案的开放设施的集合并添加这些设施覆盖的需求来计算的。必须注意避免需求被多次计数，因为一个需求点可能同时被几个设施所覆盖。

3.2.4中值和中心问题的适应度函数

中值问题：通过寻找属于服务范围的开放式设施集合的市场份额来计算这一类问题的每一个可能的解决方案的适应度。市场份额是由将每个需求节点分配给最近的开放设施并仅添加落在服务范围内的一组设施中的需求来得到。

中心问题：(r| p)-中心问题本质上是决策者（领导者）面对的“最大值”最小问题。对于领导者考虑的每个候选解决方案，都有必要计算或估计服务区域的最佳反应，这需要求解(r| p)-中心问题或通过Benati和Laporte [17]描述的贪心算法估算。需求总值减去服务区域覆盖的需求值即是被评估个体的适应度。

3.3父代选择程序

现在我们将讨论选择父代的问题，即选择交叉的方案。为此，我们选择了二元竞赛选择法（参见Beasley和Chu [8]），因为它可以非常有效地实现，且在Beasley和Chu [8]中已经表明这种方法比其他方法产生的解决方案质量更佳。

3.4交叉算子

我们选择了Beasley和Chu [8]提出的基于适合度融合的交叉算子。当两个父代解决方案在结构上相似时，该算子比单点交叉算子更能够产生新的解决方案，因为它侧重于二者结构的差异。然而，得到与父代相同的后代的可能性仍然存在。鉴于这个问题，对整个交叉算子进行了以下修改：

第一步：选择父代双亲P₁和P₂；

第二步：应用融合算子得到一个后代（C₁）;

第三步：将后代C₁与其双亲对比，若其不同于双亲中任何一个执行第五步，否则执行第四步；

第四步：对父代中适应度更低的染色体进行变异；

第五步：操作停止。

3.5变异算子

变异是一种逆转染色体结构的过程，从而产生变种，即与群体中大多数染色体不同的个体。它是防止解决方案陷于局部最优中的一种策略，被认为是遗传算法运行的次要机制。在这项工作中，变异算子通过随机选择一个开放式设施并将其移动到另一个站点起作用。新站点也是随机从一组空的建设设施的可能场所中挑选出来的。

突变率（概率）通常设置在非常低的水平。 然而，不同的参考文献[8,14]指出当遗传算法已经收敛时，有必要设置更高的突变率。为了在遗传算法进行过程中改变突变率，Beasley和Chu [8]利用可变突变率而不是固定变异率，并且其变化率取决于遗传算法收敛的速率。这里应用的算法是在遗传算法进展期间使用突变，并且在后代与其父代之一相同的情况下，交换算子被变异算子代替。

3.6更新种群方法

一旦通过遗传算法各项操作得到了新的子代解决方案，子代解决方案将取代种群中适应度不太高的个体。如果子代解决方案的适应度比被替代的方案的更好，那么种群的平均适应度将会提高。这种类型的方法被称为增量替换。另一个常用的方法是整代替换，它产生新的子代种群，并取代了整个父代种群（见Beasley等[18]）。

在我们的遗传算法中，我们使用的是增量替换方法。在这种方法下，最好的解决方案总是保留在种群中，新创建的解决方案可以立即用于选择和再繁殖。请注意，在替换解决方案时，必须注意防止方案复制过多地进入群体。允许群体中存在太多重复的解决方案是不可取的，因为种群可能保持在相同的方案，从而严重限制了遗传算法产生新解决方案的能力。

3.7群体规模

与遗传算法性能相关的最明显的问题之一是群体规模对其有何影响。原则上，很明显的是，小群体面临着严重解空间局限的风险，而大群体则需要极大的计算量。Alander[19]的实验工作表明，对于所考虑的问题类型，群体规模处于n和2n之间的值是最优的，其中n是染色体的长度。我们选择了n值，并且在我们的情况下，染色体的长度与可能的设施地点的数量一致。

3.8算法

因此，我们实现的遗传算法可以用算法描述如下：

第一步：设置t=0；

第二步：随机生成初始种群P(t)；

第三步：根据处理的问题具体类型评估P(t)中的每一个染色体串；

第四步：当进化代数小于等于设置最大迭代次数或目标函数值的改善在10^-5以内时执行下一步；

第五步：设置t=t 1；

第六步：利用二院竞赛选择法在群体中选择两个解决方案P₁和P₂；

第七步：对P₁和P₂染色体应用遗传算子：

若交叉：使用融合交叉算子组合P₁和P₂得到后代O₁，若其与双亲中任何一个染色体相同，对父代中更高适应度的应用变异算子。

若变异：对父代中更高适应度的应用变异算子得到后代O₁。

第八步：重复第六、七步，直到得到和父代群体规模大小相同的新子代集合；

第九步：根据处理的问题具体类型评估这个新的子代集合；

第十步：利用增量替换方法从父代和子代群体中创建新种群P（t）。

4.计算结果

该启发式算法以FORTRAN90编码，并在PC COMPAQ Presario 4716上执行。Sun Sparc工作站和此PC之间的比较的初步测试表

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

---

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