tsp问题ga算法python

TSP问题是指旅行商问题，即在给定的一些城市之间，求解访问每个城市一次并回到起始城市的最短路径。GA算法是一种基于生物进化过程的优化算法，可以用来解决TSP问题。下面是一个使用GA算法求解TSP问题的Python代码示例：

import numpy as np

# 计算距离矩阵
def calc_distance_matrix(points):
    n = len(points)
    distance_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(i+1, n):
            distance_matrix[i][j] = np.sqrt((points[i][0]-points[j][0])**2 + (points[i][1]-points[j][1])**2)
            distance_matrix[j][i] = distance_matrix[i][j]
    return distance_matrix

# 计算路径长度
def calc_path_length(path, distance_matrix):
    length = 0
    for i in range(len(path)-1):
        length += distance_matrix[path[i]][path[i+1]]
    length += distance_matrix[path[-1]][path[0]]
    return length

# 初始化种群
def init_population(pop_size, n):
    population = []
    for i in range(pop_size):
        path = list(range(n))
        np.random.shuffle(path)
        population.append(path)
    return population

# 选择操作
def selection(population, fitness):
    idx1, idx2 = np.random.choice(len(population), 2, replace=False, p=fitness/np.sum(fitness))
    return population[idx1], population[idx2]

# 交叉操作
def crossover(parent1, parent2):
    n = len(parent1)
    child = [-1] * n
    start, end = sorted(np.random.choice(n, 2, replace=False))
    child[start:end+1] = parent1[start:end+1]
    idx = end + 1
    for i in range(n):
        if idx == n:
            idx = 0
        if parent2[i] not in child:
            child[idx] = parent2[i]
            idx += 1
    return child

# 变异操作
def mutation(path):
    n = len(path)
    idx1, idx2 = np.random.choice(n, 2, replace=False)
    path[idx1], path[idx2] = path[idx2], path[idx1]
    return path

# GA算法求解TSP问题
def tsp_ga(points, pop_size=50, max_iter=1000):
    n = len(points)
    distance_matrix = calc_distance_matrix(points)
    population = init_population(pop_size, n)
    best_path = None
    best_length = float('inf')
    for i in range(max_iter):
        fitness = np.array([1/calc_path_length(path, distance_matrix) for path in population])
        idx = np.argsort(-fitness)
        population = [population[i] for i in idx]
        fitness = fitness[idx]
        if fitness[0] > 1/best_length:
            best_path = population[0]
            best_length = calc_path_length(best_path, distance_matrix)
        new_population = [population[0]]
        while len(new_population) < pop_size:
            parent1, parent2 = selection(population, fitness)
            child = crossover(parent1, parent2)
            if np.random.rand() < 0.1:
                child = mutation(child)
            new_population.append(child)
        population = new_population
    return best_path, best_length

# 示例
points = [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
best_path, best_length = tsp_ga(points)
print('最短路径:', best_path)
print('路径长度:', best_length)