csdn遗传算法tsp问题python
时间: 2023-09-03 20:12:11 浏览: 56
遗传算法是一种优化算法,可以用来解决旅行商问题(Traveling Salesman Problem,TSP)。TSP是一个经典的组合优化问题,它要求在给定的一些城市和它们之间的距离的情况下,找到一条最短的回路,使得每个城市恰好被访问一次。
下面是一个使用Python实现遗传算法解决TSP问题的示例代码:
```python
import random
import numpy as np
# 定义遗传算法的参数
POP_SIZE = 20 # 种群大小
CROSS_RATE = 0.6 # 交叉概率
MUTATE_RATE = 0.01 # 变异概率
N_GENERATIONS = 500 # 迭代次数
# 定义城市坐标
city_location = np.array([
[2, 3], [5, 6], [8, 4], [7, 2], [6, 3], [5, 6],
[8, 4], [7, 2], [3, 9], [6, 3], [5, 6], [8, 4],
[7, 2], [3, 9], [6, 3], [5, 6], [8, 4], [7, 2],
[3, 9], [6, 3], [5, 6], [8, 4], [7, 2], [3, 9]
])
# 计算城市之间的距离矩阵
def calc_distance(city_location):
n_cities = city_location.shape[0]
dist_matrix = np.zeros((n_cities, n_cities))
for i in range(n_cities):
for j in range(n_cities):
dist_matrix[i, j] = np.sqrt(
np.sum(np.square(city_location[i, :] - city_location[j, :]))
)
return dist_matrix
# 计算总路程
def calc_total_distance(routine, dist_matrix):
n_cities = dist_matrix.shape[0]
dist = np.sum([dist_matrix[routine[i % n_cities], routine[(i + 1) % n_cities]] for i in range(n_cities)])
return dist
# 生成初始种群
def init_population(n, n_cities):
pop = np.zeros((n, n_cities), dtype=int)
for i in range(n):
pop[i, :] = np.random.permutation(n_cities)
return pop
# 选择种群中的个体
def select(pop, fitness):
idx = np.random.choice(np.arange(len(pop)), size=len(pop), replace=True, p=fitness / fitness.sum())
return pop[idx]
# 对个体进行交叉操作
def crossover(parents, cross_rate):
n_kids = len(parents)
kids = np.empty((n_kids, parents.shape[1]), dtype=int)
for i in range(n_kids):
p1, p2 = np.random.choice(len(parents), size=2, replace=False)
mask = np.random.rand(len(parents[p1])) < cross_rate
keep = np.where(~mask)[0]
swap = np.argsort(parents[p1][mask])
p2_swap = np.argsort(parents[p2][mask])
child = np.zeros(len(mask), dtype=int)
child[keep] = parents[p1][keep]
child[mask] = parents[p2][mask][p2_swap][swap]
kids[i, :] = child
return kids
# 对个体进行变异操作
def mutate(kids, mutate_rate):
n_kids, n_cities = kids.shape
for i in range(n_kids):
if np.random.rand() < mutate_rate:
idx1, idx2 = np.random.choice(n_cities, size=2, replace=False)
kids[i, idx1], kids[i, idx2] = kids[i, idx2], kids[i, idx1]
return kids
# 主函数
def run():
n_cities = city_location.shape[0]
dist_matrix = calc_distance(city_location)
pop = init_population(POP_SIZE, n_cities)
for generation in range(N_GENERATIONS):
fitness = np.array([1 / calc_total_distance(routine, dist_matrix) for routine in pop])
parents = select(pop, fitness)
kids = crossover(parents, CROSS_RATE)
kids = mutate(kids, MUTATE_RATE)
pop = np.vstack([parents, kids])
fitness = np.array([1 / calc_total_distance(routine, dist_matrix) for routine in pop])
pop = pop[np.argsort(-fitness)]
pop = pop[:POP_SIZE]
print('Generation:', generation, '| Best distance:', np.round(1 / fitness[0], 2))
best_route = pop[0]
best_distance = np.round(1 / fitness[0], 2)
print('Best route:', best_route)
print('Best distance:', best_distance)
if __name__ == '__main__':
run()
```
在上面的代码中,我们首先定义了遗传算法的参数:种群大小、交叉概率、变异概率和迭代次数。然后,我们定义了城市坐标和计算城市之间距离矩阵的函数。
接着,我们定义了计算总路程、生成初始种群、选择种群中的个体、对个体进行交叉操作和对个体进行变异操作等函数。
最后,我们在主函数中实现了遗传算法的整个流程,并输出了最优解和最优解对应的路径。
你可以根据自己的需要修改代码中的参数和城市坐标,以解决你的TSP问题。
相关推荐
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)