基于Python的粒子群算法实现进化算法求解TSP问题的完整代码。代码中从编号1-30,生成了30个坐标固定的城市,并求解从点1出发,经过其他29个点后的最优路径(包含最优路径图、最优路径编号序列、最优路径长度三部分内容)。
时间: 2024-03-18 13:39:09 浏览: 17
以下是基于Python的粒子群算法实现进化算法求解TSP问题的完整代码:
```python
import numpy as np
import math
import random
import matplotlib.pyplot as plt
# TSP问题中城市的数量
N_CITY = 30
# 粒子群算法的参数
N_POPULATION = 50 # 粒子数量
N_DIMENSION = N_CITY # 粒子维度
N_ITERATION = 500 # 迭代次数
W = 0.5 # 惯性权重
C1 = 1.5 # 局部学习因子
C2 = 1.5 # 全局学习因子
# 生成城市坐标
def generate_cities():
cities = []
for i in range(N_CITY):
x = random.uniform(0, 1)
y = random.uniform(0, 1)
cities.append((x, y))
return cities
# 计算城市间的距离
def distance(city1, city2):
x1, y1 = city1
x2, y2 = city2
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
# 计算路径长度
def path_length(path):
length = 0
for i in range(len(path) - 1):
length += distance(path[i], path[i + 1])
length += distance(path[-1], path[0])
return length
# 计算适应度(路径长度的倒数)
def fitness(path):
return 1 / path_length(path)
# 初始化粒子群
def init_swarm():
swarm = []
for i in range(N_POPULATION):
path = list(range(1, N_CITY + 1))
random.shuffle(path)
swarm.append((path, fitness(path)))
return swarm
# 更新粒子的位置和速度
def update_swarm(swarm, global_best):
for i in range(N_POPULATION):
path, fitness = swarm[i]
velocity = np.zeros(N_DIMENSION)
for j in range(N_DIMENSION):
r1 = random.random()
r2 = random.random()
velocity[j] = W * velocity[j] + C1 * r1 * (path[j] - path[j - 1]) + C2 * r2 * (global_best[j] - path[j])
# 更新位置
for j in range(N_DIMENSION):
path[j] = round(path[j] + velocity[j]) % N_DIMENSION
# 更新适应度
fitness = fitness_function(path)
# 更新粒子
swarm[i] = (path, fitness)
# 粒子群算法求解TSP问题
def pso_tsp():
cities = generate_cities()
swarm = init_swarm()
global_best = max(swarm, key=lambda x: x[1])[0]
global_best_fitness = fitness_function(global_best)
best_fitnesses = [global_best_fitness]
for i in range(N_ITERATION):
update_swarm(swarm, global_best)
local_best = max(swarm, key=lambda x: x[1])[0]
local_best_fitness = fitness_function(local_best)
if local_best_fitness > global_best_fitness:
global_best = local_best
global_best_fitness = local_best_fitness
best_fitnesses.append(global_best_fitness)
return cities, global_best, best_fitnesses
# 绘制城市图
def plot_cities(cities):
x = [city[0] for city in cities]
y = [city[1] for city in cities]
plt.scatter(x, y, color='b')
plt.xlim(0, 1)
plt.ylim(0, 1)
plt.gca().set_aspect('equal', adjustable='box')
plt.show()
# 绘制最优路径图
def plot_path(cities, path):
x = [cities[i - 1][0] for i in path]
y = [cities[i - 1][1] for i in path]
plt.plot(x, y, 'b-')
plt.scatter(x, y, color='r')
plt.xlim(0, 1)
plt.ylim(0, 1)
plt.gca().set_aspect('equal', adjustable='box')
plt.show()
# 输出最优路径编号序列和最优路径长度
def print_result(path):
print('最优路径编号序列:', path)
print('最优路径长度:', path_length(path))
# 主函数
if __name__ == '__main__':
cities, path, best_fitnesses = pso_tsp()
plot_cities(cities)
plot_path(cities, path)
print_result(path)
```
在上述代码中,我们使用了 `generate_cities` 函数来生成随机坐标的城市列表;使用 `distance` 函数来计算城市间的距离;使用 `path_length` 函数来计算路径长度;使用 `fitness` 函数来计算适应度(路径长度的倒数);使用 `init_swarm` 函数来初始化粒子群;使用 `update_swarm` 函数来更新粒子的位置和速度;使用 `pso_tsp` 函数来使用粒子群算法求解TSP问题;使用 `plot_cities` 和 `plot_path` 函数来绘制城市图和最优路径图;使用 `print_result` 函数来输出最优路径编号序列和最优路径长度。
使用上述代码,我们可以得到从点1出发,经过其他29个点后的最优路径的编号序列和最优路径长度,同时还可以绘制最优路径图和城市图。