遗传算法求遍历所有点的最短路径
时间: 2023-08-15 18:08:49 浏览: 43
遗传算法是一种基于遗传学原理的优化算法,它可以应用于许多组合优化问题,包括旅行商问题(TSP)。下面是一个简单的 Python 实现,使用遗传算法求解 TSP 问题:
```python
import random
def tsp_ga(points, population_size=1000, generations=1000, mutation_rate=0.01):
"""
使用遗传算法解决旅行商问题。
"""
n = len(points)
if n == 0:
return 0
elif n == 1:
return points[0][0]
# 生成初始种群
population = []
for i in range(population_size):
population.append(random.sample(range(n), n))
# 迭代
for gen in range(generations):
# 计算适应度
fitness = []
for i in range(population_size):
dist = 0
for j in range(n - 1):
dist += ((points[population[i][j]][0] - points[population[i][j+1]][0])**2 + (points[population[i][j]][1] - points[population[i][j+1]][1])**2)**0.5
dist += ((points[population[i][-1]][0] - points[population[i][0]][0])**2 + (points[population[i][-1]][1] - points[population[i][0]][1])**2)**0.5
fitness.append(1 / dist)
# 选择
parents = []
for i in range(population_size // 2):
p1 = random.choices(population, weights=fitness)[0]
p2 = random.choices(population, weights=fitness)[0]
parents.append((p1, p2))
# 交叉
offspring = []
for p1, p2 in parents:
cut = random.randint(1, n - 1)
o1 = p1[:cut] + [x for x in p2 if x not in p1[:cut]]
o2 = p2[:cut] + [x for x in p1 if x not in p2[:cut]]
offspring.extend([o1, o2])
# 变异
for i in range(population_size):
if random.random() < mutation_rate:
idx1, idx2 = random.sample(range(n), 2)
population[i][idx1], population[i][idx2] = population[i][idx2], population[i][idx1]
# 更新种群
population = offspring
# 返回最优解
best = population[0]
best_dist = float('inf')
for i in range(population_size):
dist = 0
for j in range(n - 1):
dist += ((points[population[i][j]][0] - points[population[i][j+1]][0])**2 + (points[population[i][j]][1] - points[population[i][j+1]][1])**2)**0.5
dist += ((points[population[i][-1]][0] - points[population[i][0]][0])**2 + (points[population[i][-1]][1] - points[population[i][0]][1])**2)**0.5
if dist < best_dist:
best = population[i]
best_dist = dist
return best, best_dist
```
这个算法的时间复杂度约为 $O(n^2)$,因此可以处理较大规模的问题。如果需要更高的求解精度和更短的求解时间,可以适当调整参数和算法细节。