基于Python的粒子群算法实现进化算法求解TSP问题的完整代码。代码中从编号1-30,生成了30个坐标固定的城市,并求解从点1出发,经过其他29个点后的最优路径(包含最优路径图、最优路径编号序列、最优路径长度三部分内容)。
时间: 2024-03-18 21:38:59 浏览: 62
好的,我可以提供这样一个示例代码,其中使用了Python的pyswarms库实现粒子群算法(PSO)求解TSP问题。
```python
import numpy as np
from pyswarms.utils.functions import single_obj as fx
from pyswarms.utils.plotters import plot_cost_history, plot_contour, plot_surface
from pyswarms.utils.plotters.formatters import Mesher, Designer
from pyswarms.single import GlobalBestPSO
def distance_matrix(cities):
n_cities = cities.shape[0]
dist_mat = np.zeros((n_cities, n_cities))
for i in range(n_cities):
for j in range(i+1, n_cities):
dist_mat[i,j] = np.sqrt((cities[i,0]-cities[j,0])**2 + (cities[i,1]-cities[j,1])**2)
dist_mat[j,i] = dist_mat[i,j]
return dist_mat
def tsp_cost_function(x, dist_mat):
n_cities = dist_mat.shape[0]
cost = 0.0
for i in range(n_cities-1):
cost += dist_mat[x[i], x[i+1]]
cost += dist_mat[x[n_cities-1], x[0]]
return cost
def pso_tsp(n_particles, n_cities, n_iterations):
cities = np.random.rand(n_cities, 2)
dist_mat = distance_matrix(cities)
options = {'c1': 0.5, 'c2': 0.3, 'w': 0.9}
optimizer = GlobalBestPSO(n_particles=n_particles, dimensions=n_cities, options=options)
cost, pos = optimizer.optimize(lambda x: tsp_cost_function(x, dist_mat), n_iterations=n_iterations)
best_path = np.argsort(pos)
best_cost = tsp_cost_function(best_path, dist_mat)
print("Best path found: ", best_path)
print("Best cost found: ", best_cost)
return cities, best_path, best_cost
if __name__ == "__main__":
cities, best_path, best_cost = pso_tsp(n_particles=50, n_cities=30, n_iterations=1000)
# Plot the cities and the best path
mesher = Mesher(x=cities[:, 0], y=cities[:, 1])
designer = Designer(limits=[0, 1], label=["x-axis", "y-axis"])
plot_cost_history(cost_history=optimizer.cost_history)
plot_contour(pos_history=optimizer.pos_history, mesher=mesher, designer=designer)
plot_surface(pos_history=optimizer.pos_history, mesher=mesher, designer=designer)
fig, ax = plt.subplots()
ax.scatter(cities[:, 0], cities[:, 1])
for i in range(len(best_path)-1):
ax.plot([cities[best_path[i], 0], cities[best_path[i+1], 0]], [cities[best_path[i], 1], cities[best_path[i+1], 1]], 'r-')
ax.plot([cities[best_path[0], 0], cities[best_path[-1], 0]], [cities[best_path[0], 1], cities[best_path[-1], 1]], 'r-')
ax.set_title("Best path found (cost = {})".format(best_cost))
ax.set_xticks([])
ax.set_yticks([])
plt.show()
```
在上面的代码中:
- `distance_matrix`函数用于计算城市间的距离矩阵。
- `tsp_cost_function`函数用于计算给定路径的总成本。
- `pso_tsp`函数是主要的求解函数,它使用pyswarms库中的GlobalBestPSO类实现粒子群算法。在函数中,我们首先生成随机的城市坐标,并计算距离矩阵。然后,我们调用`optimize`方法来最小化`tsp_cost_function`函数。最后,我们使用得到的最优路径来计算最小成本,并返回城市坐标、最优路径和最小成本。
- 最后,我们使用matplotlib库来画出城市和最优路径的图形。
注意,这个代码示例只是一个基本的实现,还有很多可以改进的方面,比如使用其他的进化算法、改进目标函数等。
阅读全文