遗传算法 - 旅行商
Genetic Algorithms - Travelling salesman
我正在查看过去的试卷，我试图理解以下问题：
Assume you have N cities. It's possible to go from each city to any of the other cities. Assume that you have full information about the distances between cities in a tabulated form. The distance between the city number k and the city number l is given by d(k,l); so for example, the distance from the
third city to the ninth city is given by d(3,9). Note that d(k,l)=d(l,k).
A travelling salesman needs to visit all N cities and wants to find the shortest route that connects all of the cities. Use a genetic algorithm to solve this problem.
Question: Define an appropriate fitness function for this problem
and say whether high or low fitness is better.
有人知道我需要为这个问题做些什么吗？我真的很纠结从哪里开始，需要一些指导。
您希望通过 TSP 最大限度地缩短行进距离。 n 城市的旅行方式有很多种； N! / 2 确切地说。
因此，如果您有 N = 4，您需要一个整数数组 1-4，每个整数只出现一次。所以一些可能的选择是：
[1,4,2,3]
[4,1,2,3]
[3,1,4,2]
然后您通过从列表中的城市 i 到 i+1 计算距离来评估分数。对列表中的每个城市 i（但最后一个）执行此操作，您就得到了总距离；这是你的分数！
因此对于上面的示例，分数将是：
// Please note that the integers 1-4 represent cities
score([1,4,2,3]) = d(1,4) + d(4,2) + d(2,3)
score([4,1,2,3]) = d(4,1) + d(1,2) + d(2,3)
score([3,1,4,2]) = d(3,1) + d(1,4) + d(4,2)
您想最小化距离，从而最小化分数。
您可以通过创建交换列表中两个城市的变异函数来做到这一点，例如：
[1,4,2,3] -> [4,1,2,3]
[1,2,3,4] -> [1,3,2,4]
This video 显示了 Javascript 通过遗传算法优化距离的实现的一个很好的例子。
我正在查看过去的试卷，我试图理解以下问题：
Assume you have N cities. It's possible to go from each city to any of the other cities. Assume that you have full information about the distances between cities in a tabulated form. The distance between the city number k and the city number l is given by d(k,l); so for example, the distance from the third city to the ninth city is given by d(3,9). Note that d(k,l)=d(l,k).
A travelling salesman needs to visit all N cities and wants to find the shortest route that connects all of the cities. Use a genetic algorithm to solve this problem.
Question: Define an appropriate fitness function for this problem and say whether high or low fitness is better.
有人知道我需要为这个问题做些什么吗？我真的很纠结从哪里开始，需要一些指导。
您希望通过 TSP 最大限度地缩短行进距离。 n 城市的旅行方式有很多种； N! / 2 确切地说。
因此，如果您有 N = 4，您需要一个整数数组 1-4，每个整数只出现一次。所以一些可能的选择是：
[1,4,2,3]
[4,1,2,3]
[3,1,4,2]
然后您通过从列表中的城市 i 到 i+1 计算距离来评估分数。对列表中的每个城市 i（但最后一个）执行此操作，您就得到了总距离；这是你的分数！
因此对于上面的示例，分数将是：
// Please note that the integers 1-4 represent cities
score([1,4,2,3]) = d(1,4) + d(4,2) + d(2,3)
score([4,1,2,3]) = d(4,1) + d(1,2) + d(2,3)
score([3,1,4,2]) = d(3,1) + d(1,4) + d(4,2)
您想最小化距离，从而最小化分数。
您可以通过创建交换列表中两个城市的变异函数来做到这一点，例如：
[1,4,2,3] -> [4,1,2,3]
[1,2,3,4] -> [1,3,2,4]
This video 显示了 Javascript 通过遗传算法优化距离的实现的一个很好的例子。