python写一个商旅问题求解

商旅问题是指在给定的一组城市中，求出一条经过每个城市恰好一次的最短路径。这是一个NP难问题，因此我们一般采用启发式算法来解决。

下面是一个Python实现的商旅问题求解程序，使用了遗传算法：

import random

# 城市坐标
city_pos = [
    (60, 200), (180, 200), (80, 180), (140, 180), (20, 160),
    (100, 160), (200, 160), (140, 140), (40, 120), (100, 120),
    (180, 100), (60, 80), (120, 80), (180, 60), (20, 40),
    (100, 40), (200, 40), (20, 20), (60, 20), (160, 20)
]

# 城市数量
city_num = len(city_pos)

# 种群数量
pop_size = 100

# 迭代次数
max_iter = 500

# 交叉概率
crossover_prob = 0.8

# 变异概率
mutation_prob = 0.1

# 个体编码长度
chromosome_length = city_num

# 计算城市之间的距离
def dist(city1, city2):
    return ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5

# 计算路径长度
def path_length(path):
    length = 0
    for i in range(city_num):
        length += dist(city_pos[path[i]], city_pos[path[(i+1)%city_num]])
    return length

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

# 选择
def selection(population):
    fitness_list = [1.0/path_length(chromosome) for chromosome in population]
    total_fitness = sum(fitness_list)
    accum_fitness = [sum(fitness_list[:i+1])/total_fitness for i in range(pop_size)]
    selection_results = []
    for i in range(pop_size):
        r = random.random()
        for j in range(pop_size):
            if accum_fitness[j] > r:
                selection_results.append(population[j])
                break
    return selection_results

# 交叉
def crossover(parent1, parent2):
    if random.random() > crossover_prob:
        return parent1
    pos1 = random.randint(0, chromosome_length-1)
    pos2 = random.randint(0, chromosome_length-1)
    if pos1 > pos2:
        pos1, pos2 = pos2, pos1
    child = [-1] * chromosome_length
    for i in range(pos1, pos2+1):
        child[i] = parent1[i]
    index = pos2 + 1
    for i in range(chromosome_length):
        if parent2[i] not in child:
            child[index] = parent2[i]
            index = (index + 1) % chromosome_length
    return child

# 变异
def mutation(chromosome):
    if random.random() > mutation_prob:
        return chromosome
    pos1 = random.randint(0, chromosome_length-1)
    pos2 = random.randint(0, chromosome_length-1)
    chromosome[pos1], chromosome[pos2] = chromosome[pos2], chromosome[pos1]
    return chromosome

# 遗传算法
def genetic_algorithm():
    population = init_population()
    for i in range(max_iter):
        population = selection(population)
        new_population = []
        for j in range(pop_size):
            parent1 = random.choice(population)
            parent2 = random.choice(population)
            child = crossover(parent1, parent2)
            child = mutation(child)
            new_population.append(child)
        population = new_population
    best_chromosome = min(population, key=path_length)
    return best_chromosome

# 测试
best_path = genetic_algorithm()
print("最短路径: ", best_path)
print("路径长度: ", path_length(best_path))

这个程序使用遗传算法来求解商旅问题，其中`city_pos`是城市坐标，`city_num`是城市数量，`pop_size`是种群数量，`max_iter`是迭代次数，`crossover_prob`是交叉概率，`mutation_prob`是变异概率，`chromosome_length`是个体编码长度。程序的输出为最短路径和路径长度。