Exact Solutions to the Traveling Salesperson Problem by a Population-Based Evolutionary Algorithm

机译：基于人口的进化算法对旅行商问题的精确解

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

This articles introduces a (μ + 1)-EA, which is proven to be an exact TSP problem solver for a population of exponential size. We will show non-trivial upper bounds on the runtime until an optimum solution has been found. To the best of our knowledge this is the first time it has been shown that an NP-hard problem is solved exactly instead of approximated only by a black box algorithm.

机译：本文介绍了（μ+1）-EA，它已被证明是针对指数大小总体的精确TSP问题求解器。我们将在运行时显示不平凡的上限，直到找到最佳解决方案为止。据我们所知，这是首次证明精确解决NP难题，而不是仅通过黑匣子算法来解决。

著录项

来源
《Evolutionary computation in combinatorial optimization》|2009年|145-155|共11页
会议地点 Tubingen(DE);Tubingen(DE)
作者
Madeleine Theile;
展开▼
作者单位

Institut fuer Mathematik, TU Berlin, Germany;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类理论、方法;
关键词

相似文献

外文文献
中文文献
专利

1. Theoretical Analysis of Local Search and Simple Evolutionary Algorithms for the Generalized Travelling Salesperson Problem [J] . Mojgan Pourhassan, Frank Neumann Evolutionary computation . 2019,第3期

机译：广义旅行商问题的局部搜索和简单进化算法的理论分析
2. Parameterized Runtime Analyses of Evolutionary Algorithms for the Planar Euclidean Traveling Salesperson Problem [J] . Sutton A, Neumann F, Nallaperuma S Evolutionary computation . 2014,第4期

机译：平面欧式旅行商问题演化算法的参数化运行时分析
3. NONEXISTENCE OF TRAVELING WAVE SOLUTIONS, EXACT AND SEMI-EXACT TRAVELING WAVE SOLUTIONS FOR DIFFUSIVE LOTKA-VOLTERRA SYSTEMS OF THREE COMPETING SPECIES [J] . Chen Chiun-Chuan, Hung Li-Chang Communications on pure and applied analysis . 2016,第4期

机译：三种竞争种的LOTKA-VOLTERRA系统的行波解，精确和半精确行波解的不存在
4. Exact Solutions to the Traveling Salesperson Problem by a Population-Based Evolutionary Algorithm [C] . Madeleine Theile European Conference on Evolutionary Computation in Combinatorial Optimization . 2009

机译：基于人口的进化算法对旅行销售人员问题的精确解决方案
5. Design and application of genetic algorithms for the multiple traveling salesperson assignment problem. [D] . Carter, Arthur E. 2003

机译：遗传算法的多重旅行商分配问题的设计与应用。
6. PathGame: Crowdsourcing Time-Constrained Human Solutions for the Travelling Salesperson Problem [O] . Slaviša Dumnić, Đorđije Dupljanin, Vladimir Božović, 2019

机译：PathGame：针对旅行商问题的时间约束性众包解决方案
7. Parameterized runtime analyses of evolutionary algorithms for the planar Euclidean traveling salesperson problem [O] . Sutton A., Neumann F., Nallaperuma S. 2014

机译：平面欧氏旅行商问题演化算法的参数化运行时分析

Exact Solutions to the Traveling Salesperson Problem by a Population-Based Evolutionary Algorithm

摘要

著录项

相似文献

相关主题

期刊订阅