34座城市最短路径遗传算法python
时间: 2023-11-03 20:01:11 浏览: 39
下面是一个基于遗传算法求解34座城市最短路径的Python代码:
```python
import numpy as np
import random
import math
# 确定城市坐标
city_location = np.array([[1304, 2312], [3639, 1315], [4177, 2244], [3712, 1399], [3488, 1535], [3326, 1556], [3238, 1229], [4196, 1004], [4312, 790], [4386, 570], [3007, 1970], [2562, 1756], [2788, 1491], [2381, 1676], [1332, 695], [3715, 1678], [3918, 2179], [4061, 2370], [3780, 2212], [3676, 2578], [4029, 2838], [4263, 2931], [3429, 1908], [3507, 2376], [3394, 2643], [3439, 3201], [2935, 3240], [3140, 3550], [2545, 2357], [2778, 2826], [2370, 2975], [2785, 2942], [2937, 2621], [2256, 2676], [2331, 2809]])
# 确定城市数目
city_num = 34
# 确定种群大小
pop_size = 100
# 确定染色体长度(即城市的排列顺序)
chromo_len = city_num
# 确定交叉率和变异率
crossover_rate = 0.9
mutation_rate = 0.1
# 计算城市间距离
def cal_dis(point1, point2):
return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)
dis_mat = np.zeros((city_num, city_num))
for i in range(city_num):
for j in range(city_num):
dis_mat[i][j] = cal_dis(city_location[i], city_location[j])
# 初始化种群
pop = []
for i in range(pop_size):
chromosome = list(range(city_num))
random.shuffle(chromosome)
pop.append(chromosome)
# 计算染色体适应度
def cal_fitness(chromosome):
fitness = 0
for i in range(city_num - 1):
fitness += dis_mat[chromosome[i]][chromosome[i + 1]]
fitness += dis_mat[chromosome[city_num - 1]][chromosome[0]]
return fitness
# 轮盘赌选择
def roulette_wheel_selection(fitness_values):
total_fitness = sum(fitness_values)
probability = [fitness / total_fitness for fitness in fitness_values]
cum_probability = np.cumsum(probability)
random_num = random.random()
for i in range(len(cum_probability)):
if cum_probability[i] > random_num:
return i
# 交叉操作
def crossover(parent1, parent2):
child1 = [-1] * chromo_len
child2 = [-1] * chromo_len
begin = random.randint(0, chromo_len - 1)
end = random.randint(0, chromo_len - 1)
if begin > end:
begin, end = end, begin
for i in range(begin, end + 1):
child1[i] = parent1[i]
child2[i] = parent2[i]
index1 = 0
index2 = 0
for i in range(chromo_len):
if child1[i] == -1:
while parent2[index1] in child1:
index1 += 1
child1[i] = parent2[index1]
index1 += 1
if child2[i] == -1:
while parent1[index2] in child2:
index2 += 1
child2[i] = parent1[index2]
index2 += 1
return child1, child2
# 变异操作
def mutation(chromosome):
if random.random() < mutation_rate:
index1 = random.randint(0, chromo_len - 1)
index2 = random.randint(0, chromo_len - 1)
chromosome[index1], chromosome[index2] = chromosome[index2], chromosome[index1]
# 遗传算法主程序
def genetic_algorithm():
for i in range(100):
# 计算适应度值
fitness_values = [cal_fitness(chromosome) for chromosome in pop]
# 选择新的种群
new_pop = []
for j in range(pop_size):
parent1_index = roulette_wheel_selection(fitness_values)
parent2_index = roulette_wheel_selection(fitness_values)
while parent1_index == parent2_index:
parent2_index = roulette_wheel_selection(fitness_values)
parent1 = pop[parent1_index]
parent2 = pop[parent2_index]
if random.random() < crossover_rate:
child1, child2 = crossover(parent1, parent2)
new_pop.append(child1)
new_pop.append(child2)
else:
new_pop.append(parent1)
new_pop.append(parent2)
# 变异操作
for j in range(pop_size):
mutation(new_pop[j])
# 更新种群
pop = new_pop
# 返回最优解
best_chromosome = min(pop, key=cal_fitness)
return best_chromosome
best_chromosome = genetic_algorithm()
best_fitness = cal_fitness(best_chromosome)
print("最短路径为:", best_chromosome)
print("路径长度为:", best_fitness)
```
这段代码中,首先确定了34座城市的坐标,然后计算了每两座城市之间的距离,接着初始化了种群,并通过遗传算法求解最短路径。最后输出了最短路径和路径长度。需要注意的是,本代码中的遗传算法是一种基本的实现方式,可能存在优化的空间。