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

Question

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

谢谢大家的建议

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 中找到更多详细信息和其他技术。 .