英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
用遗传算法解决TSP问题 - 科索沃案例
AVNI REXHEPI AGNI DIKA ADNAN MAXHUNI
普里什蒂纳大学 电脑与计算机工程系 卡德拉戴理特大学 电脑系
摘要：在本文中，我们描述了使用遗传算法解决科索沃城市/城市的TSP问题，其中必须尽量减少城市（地点）之间的旅行距离。由于TSP问题是一个NP问题，动态规划，回溯，分支和界限等方法对于解决这个问题并不是很有用。对于传统上认为计算不可行的问题，如TSP，遗传算法证明是获得解决方案的最佳途径。约翰荷兰的着作“自然和人工系统的自适应”（1975,1992）展示了如何利用被称为“遗传算法”（GA）的高度并行技术来解决各种问题的演化过程。遗传算法使用达尔文式的适应性和适应性和自然发生的遗传操作类似物的生存和存活原理，将具有相关适应值的个体对象的种群（集合）转换成新一代种群，如交叉（性交重组）和突变。人口中的每个人都可以解决某个问题。遗传算法试图通过一系列世代遗传育种个体的人群来找到一个非常好的（或最好的）解决方案。科索沃是一个相对较小的国家，面积为10887平方公里。除首都普里什蒂纳以外，还有其他六个大城市和大约23个小城市，其余的地区都是村庄。基本上，共有30个市，共有1467个地方，约有两千万居民。最近有七个地方被提出认定为直辖市，正在进行转型。为了解决这个问题，我们在C＃中设计了一个应用程序，它将使用遗传算法为TSP科索沃问题找到最佳解决方案。本文的第一部分是简要介绍科索沃和科索沃市。
关键词：遗传算法、旅行商问题、C#、科索沃
一、导入
科索沃是欧洲最新的国家，按照这个领土的规模，属于小国（169个世界级的领土）。 它有10887平方米。 科索沃位于欧洲东南部的巴尔干半岛，地理坐标为42.35 N和21 E，位于阿尔巴尼亚，黑山，塞尔维亚和马其顿之间。 边境线总长702公里，边界国家为：阿尔巴尼亚112公里，马其顿159公里，黑山79公里，塞尔维亚352公里。 科索沃有7个大城市，首都普里什蒂纳和30个城市。 大部分道路铺设。 有大约2000公里的道路和94％的铺设。 只有2％是国际公路，而66％是国家公路，32％是区域性公路。
在本文中，我们使用遗传算法描述科索沃城市的旅行推销员问题（TSP）。
二、旅行商问题
TSP，是旅行推销员想从一个家乡出发返回家乡，只想访问一个城市的每一个城市的问题。他的聚焦点在于找到这样一次旅行的最短路线。 TSP在数学，计算机科学，运筹学等许多分支中具有模型特征。线性编程，启发式算法和分支界限是硬组合优化问题的最成功方法的主要组成部分，首先为TSP制定并使用在1954年由Dantzig，Fulkerson和Johnson解决实际问题的例子。当NP完全性理论发展起来时，TSP是1972年Karp首先要证明的NP hard问题之一。新的算法技术首先被开发出来，或者至少已经应用于TSP以显示它们的有效性。这样的例子是分支和束缚的，拉格朗日松弛，Lin-Karneghan聚类型算法，模拟退火算法等。表示模型为：令Kn =（Vn，En）为n = | Vn |的完全无向图节点，并且m = | En | =
条边。具有端点i和j的边e也可以由ij表示，或由（i,j）表示。我们用表示组成部分由En元素索引的实向量空间。由边e = ij索引的任何向量zisin;的分量用,或z（i,j）表示。给定一个目标函数cisin;，将“长度”与的每个边e相关联，对称旅行商问题包括找到一个哈密尔顿周期，使得它的c长度（其边的长度之和）是尽可能小。特别感兴趣的是旅行推销员问题的欧几里德实例。在这些情况下，定义问题的节点对应于二维平面中的点，并且两个节点之间的距离是它们对应点之间的欧几里德距离。更一般地说，满足三角不等式的实例。
对于所有三个不同的i,j和k, gt;=是特别令我们感兴趣的。就我们的情况而言，我们将科索沃城市/城市的地点视为该图的节点。为了做到这一点，我们采取他们的地理坐标，并基于此，我们计算他们在我们的地图中缩放到较小尺寸的位置，以便通过使用实际位置和距离计算实际位置和距离，城市。
三、遗传算法通识
遗传算法（GA）是计算机算法，在大量可能的解决方案中寻找问题的良好解决方案。他们是在20世纪60年代John Holland和他的学生以及密歇根大学的同事们提出和发展起来的。这些计算范式受到自然进化机制的启发，包括适者生存，繁殖和变异。这些机制非常适合解决许多领域中的各种实际问题，包括计算问题。遗传算法的一些应用是优化，自动编程，机器学习，经济学，免疫系统，群体遗传学和社会系统。 GA已经成功应用于许多商业，工程和科学问题。由于其操作简单和适用性广，GA在计算优化和操作研究中发挥着重要作用。遗传算法使用达尔文式的适应性和适应性和自然发生的遗传操作类似物的生存和存活原理，将具有相关适应值的个体对象的种群（集合）转换成新一代种群，如交叉（性交重组）和突变。人口中的每个人都可以解决某个问题。遗传算法试图通过一系列世代遗传育种个体的人群来找到一个非常好的（或最好的）解决方案。
四、遗传算法的基本参数
大多数GA类方法基于以下元素：染色体种群，根据适应度选择，交叉产生新的后代，以及随机变异的新后代。 GA中的染色体代表候选解决方案的空间。 可能的染色体编码是二进制，置换，值和树编码。 遗传算法需要一个适应函数，为当前人群中的每个染色体分配一个分数。 因此，它可以计算出解决方案的编码程度以及它们如何很好地解决问题。 选择过程基于健身。 用较高值（fitter）评估的染色体很可能被选择重现，而具有较低值的染色体将被丢弃。
最适合的染色体可以选择多次，但是，选择繁殖的染色体数量与群体大小相等，因此，每一代都保持大小不变。这个阶段具有随机性，就像自然界有机体的生存一样。最常用的选择方法是轮盘，等级选择，稳态选择等等。此外，为了提高GA的表现，选择方法通过精英主义选择法来增强。精英主义是一种方法，首先将一些最高得分的染色体拷贝到新的人群中，然后继续产生其余的人群。因此，它可以防止失去几个最好的解决方案。交叉是将一个染色体的位与另一个染色体的位相结合以便为继承父母双方特征的下一代创建后代的过程。例如，考虑以下父母和位置3的交叉点：
父类1 1 0 0 | 0 1 1 1 父类2 1 1 1 | 1 0 0 0
后代1 1 0 0 | 1 0 0 0 后代2 1 1 1 | 0 1 1 1
在本例中，后代1继承了父节点1交叉点左侧位置1,2和3的位，其余从父母2的交叉点的右侧开始。类似地，子代2从父母2继承位置1,2和3中的位，其余从父母1继承。交叉后进行突变以防止所有解决方案落入人口转化为解决问题的局部最优解。突变通过将位从1变为0或从0变为1来改变新的后代。突变可能发生在字符串中的每个位位置，具有一些概率，通常非常小（例如0.001）。例如，考虑以下具有位置3上的突变点的染色体：未突变的染色体：1 0 0 0 1 1 1突变的染色体：1 0 1 0 1 1 1位置3处的0在突变后翻转为1。
因此，基本遗传算法的总体概述：
1.开始：随机生成一个N染色体群体。
2.适应度：计算所有染色体的适应度。
3.创建新的群体：
a选择：根据选择方法从群体中选择2条染色体。
b交叉：在选择的2条染色体上进行交叉。
c突变：对获得的染色体进行突变。
4.替换：用新的人口替换当前的人口。
5测试
测试结束条件是否满足。如果是这样，停下来。如果不是，则返回当前总体中的最佳解，并转到第2步。此过程的每次迭代都称为生成。遗传算法对象确定哪些个体应该存活，哪些个体应该重现，哪些应该死亡。它还记录统计数据并决定进化应该持续多久。一个典型的遗传算法将永远运行，所以我们必须构建函数来指定算法何时终止。这些包括终止生成，其中指定算法应该运行的特定数量的世代，并且在收敛时终止，其中您指定了最佳世代分数应该收敛的值。可以定制终止函数来使用自己的停止标准，并且必须告诉算法何时停止。通常情况下，代数被用作停止措施，但是如果您愿意的话，您可以使用最佳解决方案，人口聚合或任何问题特定标准。有一些遗传算法的风味。例如，第一个是Goldberg在他的书中描述的标准“简单遗传算法”。该算法使用不重叠的人群和可选的精英主义。每一代算法都会创建一个全新的人群。第二种是使用重叠种群的“稳态遗传算法”。在这种变化中，您可以指定在每一代中应该替换多少人口。第三种变化是“增量遗传算法”，其中每代只由一个或两个孩子组成。增量遗传算法允许定制替换方法来定义新一代应该如何整合到人群中。因此，例如，新生儿可以替换其父母，替换人群中的随机个体，或者替换最相似的个体。第四种类型是基础样本遗传算法。该算法使用稳态算法并行演变多个群体。每一代算法都会将每个人群中的一些人迁移到其他人群中。基础遗传算法类包含大多数遗传算法通用的算子和数据。遗传算法包含运行算法的统计信息，替换策略和参数。人口对象，基因组容器，还包含一些统计数据以及选择和缩放操作符。
功能评估的数量是将不同遗传算法与其他各种搜索方法进行比较的好方法。 基本算法如下：
五、科索沃背景下的TSP
为了计算从最初的城市到最短的旅行距离，通过只访问一次并返回到最初的一个，我们将这些位置视为图的模型中的节点。同时，城市之间的距离是图的边缘。对于边的长度，我们采用以公里为单位的城际间距离。我们创建了所有城市之间的距离矩阵，矩阵元素是平方对称矩阵的元素，因为距离ij等于另一边ji的距离。矩阵的对角线将包含零值，因为矩阵的对角线元素（其中i = j）将表示城市与自身的距离，所以实际上它将是零公里的行进距离，因此这些元素将等于 = 0。通过在TSP的定义中使用完全图，保证了可行解的存在性，而对于一般图，判定哈密尔顿周期的存在性是一个NP完全问题。中的哈密尔顿循环的数量，即TSP的可行解集合为（n-1) !/ 2。 TSP的算法处理确保了不能保证找到最佳值的近似算法，但是唯一可用的技术来找到大问题实例的良好解决方案。为了评估解决方案的质量，人们必须能够计算最短哈密顿周期值的下限。我们从“交通和电信部”官方网站，市政网页以及我们使用谷歌 - 地球路径计算地图中的路线计算的一些网页收集了城市间距离的数据。
六、应用
我们已经在C＃中构建了一个应用程序，其中包含科索夫地图的小尺寸图像，并显示了城市的边界和位置。 可以通过点击地图选择一个特定的城市，我们还添加了按钮，可以为所有三十个城市的七个最大城市和地点创建地点。
我们用一张有城市地理坐标的表格来计算它们的位置。通过运行应用程序，我们可以通过使用遗传算法找到TSP的解决方案来计算所选城市之间的最短行程距离。 我们还使用两个名单，第一个将显示选定的城市，第二个将显示找到的解决方案中城市的序列。 应用程序将计算并显示以千米为单位的总行驶距离。 用户可以设置初始人口数，最大生成数，组大小，突变百分比和近距离城市/地点的数量（算法使用，同时查找最近的位置）。
七、结论
通过使用标准的数学方法不可能找到NP难题的最佳解决方案。遗传算法是计算机算法，可以在大量可能的解决方案中搜索问题的良好解决方案。旅行推销员问题是一个NP难题。使用遗传算法，我们可以找到一个可行的解决方案，它不能保证是最好的解决方案，而是在合理的时间内找到的最好解决方案。
bull;为了找到科索沃城市/城市之间最短的旅行距离，我们使用遗传算法，在C＃构建的应用程序中。
bull;我们使用地理坐标来计算图形/图像中节点/城市的位置。
bull;我们使用城际距离矩阵来计算行驶距离的长度。
bull;应用程序将查找所选城市之间的最短行程距离。
参考文献：
[1] J. H. Holland，天然和人造系统的适应。 Ann Arbor，MI：密歇根大学出版社，1975。
[2]D. E. Goldberg，遗传算法在搜索，优化和机器学习中的应用。 Reading，MA：Addison-Wesley，1989。
[3] Michael Junger，Gerhard Reinelt，Giofanni Rinaldi，旅行推销员问题，M.O. Ball et all，Eds。 OR＆Ms，Vol。 7，Elsevier Science，B.V.1997
[4] T.-L. Yu，D. E. Goldberg和Y.-P. Chen，“一种受组织理论启发的遗传算法设计：依赖结构矩阵驱动的遗传算法的先导研究”，伊利诺伊大学厄巴纳 - 香槟分校伊利诺伊大学遗传算法实验室，伊利诺伊州Urbana市，2003年。
[5] K. Sastry，DE Goldberg和G. Kendall，“Genetic algorithms：A tutorial，”in Introductory Tutorials in Optimization，Search and Decision Support Methodologies，ch。 4，pp.97-125，Springer，2005。
[6] Martin Pelikan，遗传算法，MEDAL报告号2010007,2010
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[21671]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
