genetic-algorithm - 旅行推销员的启发法

Question

我正在研究进化优化，并且在这个项目中我需要旅行商问题的启发式方法。在此背景下，遗传算法，我们应用小的突变并希望在某个地方 future 事情会变得更好。所以，我正在寻找简单的启发式方法改变可能带来改进的解决方案。

感谢您的建议

Answer 1

我想推荐的一个引用是 R's TSP package 。 (即使您不使用 R，也请研究一下。) Their vignette on TSP非常棒，并且有很多基于动态编程的技巧，您可以尝试改进您的 GA 实现。

第 2.4 节 的小插图特别讨论了您可以合并的游览构建启发式。引述如下:

Nearest neighbor algorithm: follows a very simple greedy procedure: The algorithm starts with a tour containing a randomly chosen city and then always adds to the last city in the tour the nearest not yet visited city. The algorithm stops when all cities are on the tour.

An extension to this algorithm is to repeat it with each city as the starting point and then return the best tour found. This heuristic is called repetitive nearest neighbor.

Insertion algorithms. start with a tour consisting of an arbitrary city and then choose in each step a city not yet on the tour. This city is inserted into the existing tour between two consecutive cities i and j, such that the insertion cost (i.e., the increase in the tour's length) is minimized. The algorithms stop when all cities are on the tour.

Nearest insertion The city k is chosen in each step as the city which is nearest to a city on the tour.

Farthest insertion The city k is chosen in each step as the city which is farthest from any of the cities on the tour.

Cheapest insertion The city k is chosen in each step such that the cost of inserting the new city is minimal.

您可以在 vignette 中找到更多详细信息和其他技术。 .