偷偷摸摸的旅行推销员 [英] Travelling Salesman in scipy
问题描述
如何解决python中的Traveling Salesman问题?我没有找到任何库，应该有一种使用scipy函数进行优化的方法或其他库.
我的hacky-extremelly-lazy-pythonic强力解决方案是:
tsp_solution = min( (sum( Dist[i] for i in izip(per, per[1:])), n, per) for n, per in enumerate(i for i in permutations(xrange(Dist.shape[0]), Dist.shape[0])) )[2]
其中Dist(numpy.array)是距离矩阵. 如果Dist太大，这将永远花费.
建议?
scipy.optimize函数的构造不能直接适应旅行商问题(TSP).对于简单的解决方案，我建议使用2-opt算法，该算法是解决TSP的公认算法，并且相对容易实现.这是我对算法的实现:
import numpy as np
# Calculate the euclidian distance in n-space of the route r traversing cities c, ending at the path start.
path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p]]-c[r[p-1]]) for p in range(len(r))])
# Reverse the order of all elements from element i to element k in array r.
two_opt_swap = lambda r,i,k: np.concatenate((r[0:i],r[k:-len(r)+i-1:-1],r[k+1:len(r)]))
def two_opt(cities,improvement_threshold): # 2-opt Algorithm adapted from https://en.wikipedia.org/wiki/2-opt
route = np.arange(cities.shape[0]) # Make an array of row numbers corresponding to cities.
improvement_factor = 1 # Initialize the improvement factor.
best_distance = path_distance(route,cities) # Calculate the distance of the initial path.
while improvement_factor > improvement_threshold: # If the route is still improving, keep going!
distance_to_beat = best_distance # Record the distance at the beginning of the loop.
for swap_first in range(1,len(route)-2): # From each city except the first and last,
for swap_last in range(swap_first+1,len(route)): # to each of the cities following,
new_route = two_opt_swap(route,swap_first,swap_last) # try reversing the order of these cities
new_distance = path_distance(new_route,cities) # and check the total distance with this modification.
if new_distance < best_distance: # If the path distance is an improvement,
route = new_route # make this the accepted best route
best_distance = new_distance # and update the distance corresponding to this route.
improvement_factor = 1 - best_distance/distance_to_beat # Calculate how much the route has improved.
return route # When the route is no longer improving substantially, stop searching and return the route.
以下是正在使用的功能的示例:
# Create a matrix of cities, with each row being a location in 2-space (function works in n-dimensions).
cities = np.random.RandomState(42).rand(70,2)
# Find a good route with 2-opt ("route" gives the order in which to travel to each city by row number.)
route = two_opt(cities,0.001)
这是图中显示的近似解路径:
import matplotlib.pyplot as plt
# Reorder the cities matrix by route order in a new matrix for plotting.
new_cities_order = np.concatenate((np.array([cities[route[i]] for i in range(len(route))]),np.array([cities[0]])))
# Plot the cities.
plt.scatter(cities[:,0],cities[:,1])
# Plot the path.
plt.plot(new_cities_order[:,0],new_cities_order[:,1])
plt.show()
# Print the route as row numbers and the total distance travelled by the path.
print("Route: " + str(route) + "\n\nDistance: " + str(path_distance(route,cities)))
如果算法的速度对您很重要，我建议预先计算距离并将其存储在矩阵中.这样可以大大减少收敛时间.
自定义起点和终点
对于非圆形路径(一条路径终止于与起点不同的位置)，请将路径距离公式编辑为
path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p+1]]-c[r[p]]) for p in range(len(r)-1)])
，然后使用
对城市进行重新排序以进行绘图new_cities_order = np.array([cities[route[i]] for i in range(len(route))])
按原样使用代码，将起始城市固定为cities中的第一个城市，而终止城市是可变的.
要使结束城市成为cities中的最后一个城市，请使用代码更改two_opt()中swap_first和swap_last的范围，以限制可互换城市的范围
for swap_first in range(1,len(route)-3):
for swap_last in range(swap_first+1,len(route)-1):
要使起点和终点城市都可变，请改为使用
import matplotlib.pyplot as plt
# Reorder the cities matrix by route order in a new matrix for plotting.
new_cities_order = np.concatenate((np.array([cities[route[i]] for i in range(len(route))]),np.array([cities[0]])))
# Plot the cities.
plt.scatter(cities[:,0],cities[:,1])
# Plot the path.
plt.plot(new_cities_order[:,0],new_cities_order[:,1])
plt.show()
# Print the route as row numbers and the total distance travelled by the path.
print("Route: " + str(route) + "\n\nDistance: " + str(path_distance(route,cities)))
扩展swap_first和swap_last的范围
for swap_first in range(0,len(route)-2):
for swap_last in range(swap_first+1,len(route)):
How do I solve a Travelling Salesman problem in python? I did not find any library, there should be a way using scipy functions for optimization or other libraries.
My hacky-extremelly-lazy-pythonic bruteforcing solution is:
tsp_solution = min( (sum( Dist[i] for i in izip(per, per[1:])), n, per) for n, per in enumerate(i for i in permutations(xrange(Dist.shape[0]), Dist.shape[0])) )[2]
where Dist (numpy.array) is the distance matrix. If Dist is too big this will take forever.
Suggestions?
The scipy.optimize functions are not constructed to allow straightforward adaptation to the traveling salesman problem (TSP). For a simple solution, I recommend the 2-opt algorithm, which is a well-accepted algorithm for solving the TSP and relatively straightforward to implement. Here is my implementation of the algorithm:
import numpy as np
# Calculate the euclidian distance in n-space of the route r traversing cities c, ending at the path start.
path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p]]-c[r[p-1]]) for p in range(len(r))])
# Reverse the order of all elements from element i to element k in array r.
two_opt_swap = lambda r,i,k: np.concatenate((r[0:i],r[k:-len(r)+i-1:-1],r[k+1:len(r)]))
def two_opt(cities,improvement_threshold): # 2-opt Algorithm adapted from https://en.wikipedia.org/wiki/2-opt
route = np.arange(cities.shape[0]) # Make an array of row numbers corresponding to cities.
improvement_factor = 1 # Initialize the improvement factor.
best_distance = path_distance(route,cities) # Calculate the distance of the initial path.
while improvement_factor > improvement_threshold: # If the route is still improving, keep going!
distance_to_beat = best_distance # Record the distance at the beginning of the loop.
for swap_first in range(1,len(route)-2): # From each city except the first and last,
for swap_last in range(swap_first+1,len(route)): # to each of the cities following,
new_route = two_opt_swap(route,swap_first,swap_last) # try reversing the order of these cities
new_distance = path_distance(new_route,cities) # and check the total distance with this modification.
if new_distance < best_distance: # If the path distance is an improvement,
route = new_route # make this the accepted best route
best_distance = new_distance # and update the distance corresponding to this route.
improvement_factor = 1 - best_distance/distance_to_beat # Calculate how much the route has improved.
return route # When the route is no longer improving substantially, stop searching and return the route.
Here is an example of the function being used:
# Create a matrix of cities, with each row being a location in 2-space (function works in n-dimensions).
cities = np.random.RandomState(42).rand(70,2)
# Find a good route with 2-opt ("route" gives the order in which to travel to each city by row number.)
route = two_opt(cities,0.001)
And here is the approximated solution path shown on a plot:
import matplotlib.pyplot as plt
# Reorder the cities matrix by route order in a new matrix for plotting.
new_cities_order = np.concatenate((np.array([cities[route[i]] for i in range(len(route))]),np.array([cities[0]])))
# Plot the cities.
plt.scatter(cities[:,0],cities[:,1])
# Plot the path.
plt.plot(new_cities_order[:,0],new_cities_order[:,1])
plt.show()
# Print the route as row numbers and the total distance travelled by the path.
print("Route: " + str(route) + "\n\nDistance: " + str(path_distance(route,cities)))
If the speed of algorithm is important to you, I recommend pre-calculating the distances and storing them in a matrix. This dramatically decreases the convergence time.
Edit: Custom Start and End Points
For a non-circular path (one which ends at a location different from where it starts), edit the path distance formula to
path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p+1]]-c[r[p]]) for p in range(len(r)-1)])
and then reorder the cities for plotting using
new_cities_order = np.array([cities[route[i]] for i in range(len(route))])
With the code as it is, the starting city is fixed as the first city in cities, and the ending city is variable.
To make the ending city the last city in cities, restrict the range of swappable cities by changing the range of swap_first and swap_last in two_opt() with the code
for swap_first in range(1,len(route)-3):
for swap_last in range(swap_first+1,len(route)-1):
To make both the starting and ending cities variable, instead expand the range of swap_first and swap_last with
for swap_first in range(0,len(route)-2):
for swap_last in range(swap_first+1,len(route)):
这篇关于偷偷摸摸的旅行推销员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
