旅行商问题代码
时间: 2023-07-29 07:05:59 浏览: 44
以下是使用遗传算法解决旅行商问题的Python代码示例:
```python
import random
# 定义遗传算法参数
POP_SIZE = 100 # 种群大小
CROSS_RATE = 0.8 # 交叉率
MUTATION_RATE = 0.01 # 突变率
N_GENERATIONS = 500 # 迭代次数
# 生成城市坐标
N_CITIES = 20 # 城市数量
cities = []
for i in range(N_CITIES):
city = (random.uniform(0, 100), random.uniform(0, 100))
cities.append(city)
# 计算两个城市之间的距离
def get_distance(city1, city2):
x1, y1 = city1
x2, y2 = city2
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
# 计算路径长度
def get_fitness(individual):
distance = 0
for i in range(len(individual) - 1):
city1 = cities[individual[i]]
city2 = cities[individual[i+1]]
distance += get_distance(city1, city2)
city1 = cities[individual[-1]]
city2 = cities[individual[0]]
distance += get_distance(city1, city2)
return 1 / distance
# 随机生成初始种群
pop = []
for i in range(POP_SIZE):
individual = list(range(N_CITIES))
random.shuffle(individual)
pop.append(individual)
# 进化过程
for generation in range(N_GENERATIONS):
# 计算适应度
fitness = []
for individual in pop:
fitness.append(get_fitness(individual))
# 选择
parents = []
for i in range(POP_SIZE):
parent1 = pop[fitness.index(max(fitness))]
fitness[fitness.index(max(fitness))] = -1
parent2 = pop[fitness.index(max(fitness))]
fitness[fitness.index(max(fitness))] = -1
parents.append((parent1, parent2))
# 交叉
offspring = []
for parent1, parent2 in parents:
if random.random() < CROSS_RATE:
index1 = random.randint(0, N_CITIES - 1)
index2 = random.randint(index1, N_CITIES - 1)
temp = parent1[index1:index2]
offspring1 = [-1] * N_CITIES
offspring1[index1:index2] = temp
offspring2 = [x for x in parent2 if x not in temp]
offspring1[:index1] = offspring2[:index1]
offspring1[index2:] = offspring2[index1:]
offspring.append(offspring1)
else:
offspring.append(parent1)
# 突变
for i in range(len(offspring)):
if random.random() < MUTATION_RATE:
index1 = random.randint(0, N_CITIES - 1)
index2 = random.randint(0, N_CITIES - 1)
offspring[i][index1], offspring[i][index2] = offspring[i][index2], offspring[i][index1]
# 替换
pop = offspring
# 输出结果
best_individual = pop[fitness.index(max(fitness))]
best_fitness = get_fitness(best_individual)
print('最短路径长度:', 1 / best_fitness)
print('最短路径:', best_individual)
```
该代码使用遗传算法来求解旅行商问题,使用欧氏距离作为城市之间的距离。通过遗传算法的迭代过程,不断优化种群中的个体,最终得到一条最短路径。