csdn遗传算法tsp问题python
时间: 2023-10-10 18:07:28 浏览: 41
遗传算法是一种常用的求解TSP问题的方法之一。下面是一份Python代码,可以实现基于遗传算法的TSP问题求解。
``` python
import numpy as np
# TSP问题的距离矩阵,需要自己定义
distance_matrix = np.array([
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
])
# 遗传算法的参数设置
population_size = 50 # 种群大小
elite_size = 10 # 精英个体数量
mutation_rate = 0.01 # 变异率
generations = 200 # 迭代次数
# 随机生成初始种群
def initial_population(population_size, num_cities):
population = []
for i in range(population_size):
individual = np.arange(num_cities)
np.random.shuffle(individual)
population.append(individual)
return population
# 计算每个个体的适应度(距离)
def fitness(individual):
distance = 0
for i in range(len(individual)-1):
distance += distance_matrix[individual[i]][individual[i+1]]
distance += distance_matrix[individual[-1]][individual[0]]
return distance
# 选择操作(轮盘赌算法)
def selection(population):
fitnesses = [fitness(individual) for individual in population]
total_fitness = np.sum(fitnesses)
probabilities = [fitness/total_fitness for fitness in fitnesses]
return np.random.choice(population, size=len(population), replace=True, p=probabilities)
# 交叉操作(顺序交叉)
def crossover(parent1, parent2):
child = np.zeros(len(parent1), dtype=int)
start_index = np.random.randint(len(parent1))
end_index = np.random.randint(len(parent1))
if start_index > end_index:
start_index, end_index = end_index, start_index
for i in range(start_index, end_index+1):
child[i] = parent1[i]
remaining_cities = [city for city in parent2 if city not in child]
index = 0
for i in range(len(child)):
if child[i] == 0:
child[i] = remaining_cities[index]
index += 1
return child
# 变异操作(交换两个城市)
def mutation(individual):
for i in range(len(individual)):
if np.random.uniform() < mutation_rate:
j = np.random.randint(len(individual))
individual[i], individual[j] = individual[j], individual[i]
return individual
# 遗传算法求解TSP问题
def genetic_algorithm(population_size, elite_size, mutation_rate, generations):
population = initial_population(population_size, len(distance_matrix))
for generation in range(generations):
offspring = []
elites = sorted(population, key=lambda x: fitness(x))[:elite_size]
offspring.extend(elites)
for i in range(population_size-elite_size):
parent1, parent2 = selection(population), selection(population)
child = crossover(parent1, parent2)
child = mutation(child)
offspring.append(child)
population = offspring
best_individual = sorted(population, key=lambda x: fitness(x))[0]
return best_individual
# 执行遗传算法
best_route = genetic_algorithm(population_size, elite_size, mutation_rate, generations)
# 输出最优路径和距离
best_distance = fitness(best_route)
print("最优路径:", best_route)
print("最优距离:", best_distance)
```
其中距离矩阵需要自己定义,这里是一个4个城市的例子。可以根据实际情况进行修改。