用遗传算法解决TSP问题代码

TSP问题是指旅行商问题，即一个旅行商要在N个城市之间旅行一次，求最短路径。遗传算法可以用来解决TSP问题，以下是一份Python代码示例：

import random
import math

# 定义城市坐标
city_list = [(16.47,96.10), (16.47,94.44), (20.09,92.54), (22.39,93.37), 
             (25.23,97.24), (22.00,96.05), (20.47,97.02), (17.20,96.29),
             (16.30,97.38), (14.05,98.12), (16.53,97.38), (21.52,95.59),
             (19.41,97.13), (20.09,94.55)]

# 定义遗传算法的参数
POPULATION_SIZE = 50
GENERATIONS = 100
MUTATION_RATE = 0.01

# 随机生成初始群体
def create_population(size):
    population = []
    for i in range(size):
        population.append(random.sample(range(len(city_list)), len(city_list)))
    return population

# 计算路径长度
def get_distance(city1, city2):
    return math.sqrt((city1[0]-city2[0])**2 + (city1[1]-city2[1])**2)

def get_total_distance(order):
    total_distance = 0
    for i in range(len(order)-1):
        city1 = city_list[order[i]]
        city2 = city_list[order[i+1]]
        total_distance += get_distance(city1, city2)
    return total_distance

# 选择函数（轮盘赌选择）
def selection(population):
    fitness = []
    for order in population:
        fitness.append(1/get_total_distance(order))
    total_fitness = sum(fitness)
    probabilities = [f/total_fitness for f in fitness]
    chosen = random.choices(population, weights=probabilities, k=2)
    return chosen[0], chosen[1]

# 交叉函数
def crossover(order1, order2):
    start = random.randint(0, len(order1)-1)
    end = random.randint(start+1, len(order1))
    child = [-1]*len(order1)
    for i in range(start, end):
        child[i] = order1[i]
    for i in range(len(order2)):
        if order2[i] not in child:
            for j in range(len(child)):
                if child[j] == -1:
                    child[j] = order2[i]
                    break
    return child

# 突变函数
def mutate(order):
    for i in range(len(order)):
        if random.random() < MUTATION_RATE:
            j = random.randint(0, len(order)-1)
            order[i], order[j] = order[j], order[i]
    return order

# 演化函数
def evolve(population):
    new_population = []
    for i in range(len(population)):
        order1, order2 = selection(population)
        child = crossover(order1, order2)
        child = mutate(child)
        new_population.append(child)
    return new_population

# 主函数
def genetic_algorithm():
    population = create_population(POPULATION_SIZE)
    for i in range(GENERATIONS):
        population = evolve(population)
        best_order = population[0]
        best_distance = get_total_distance(best_order)
        print("Generation {}: Best Distance = {:.3f}".format(i+1, best_distance))
    return best_order

best_order = genetic_algorithm()
print("Best Order:", best_order)
print("Best Distance:", get_total_distance(best_order))

在代码中，首先定义了城市坐标和遗传算法的参数。然后定义了几个函数，包括创建初始群体、计算路径长度、轮盘赌选择、交叉、突变和演化函数。最后，在主函数中执行遗传算法，并输出最佳路径和最短距离。如果要使用自己的数据集，只需要修改city_list即可。