通过用户输入城市用遗传算法解决TSP问题代码

以下是一个Python实现的遗传算法解决TSP问题的示例代码，可以通过用户输入城市来求解：

import numpy as np
import random

# 定义城市坐标
cities = {
    '北京': (116.3975, 39.9085),
    '上海': (121.4737, 31.2304),
    '广州': (113.5107, 23.2196),
    '深圳': (114.0579, 22.5431),
    '杭州': (120.1551, 30.2741),
    '南京': (118.7969, 32.0603),
    '成都': (104.0657, 30.6595),
    '重庆': (106.5507, 29.5647),
    '武汉': (114.3054, 30.5931),
    '西安': (108.9402, 34.3416)
}

# 计算城市之间的距离
def distance(city1, city2):
    x1, y1 = city1
    x2, y2 = city2
    return np.sqrt((x1-x2)**2 + (y1-y2)**2)

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

# 遗传算法
def genetic_algorithm(population, fitness_fn, ngen=100, mutation_prob=0.1):
    for i in range(ngen):
        new_population = []
        for j in range(len(population)):
            # 选择两个个体进行交叉
            parent1 = selection(population, fitness_fn)
            parent2 = selection(population, fitness_fn)
            child = crossover(parent1, parent2)
            # 对个体进行变异
            if random.random() < mutation_prob:
                child = mutation(child)
            new_population.append(child)
        population = new_population
    return max(population, key=fitness_fn)

# 选择
def selection(population, fitness_fn):
    fitnesses = [fitness_fn(p) for p in population]
    return population[fitnesses.index(max(fitnesses))]

# 交叉
def crossover(parent1, parent2):
    index1 = random.randint(0, len(parent1)-1)
    index2 = random.randint(index1, len(parent1)-1)
    child = parent1[index1:index2]
    for gene in parent2:
        if gene not in child:
            if len(child) < index1:
                child.insert(0, gene)
            else:
                child.append(gene)
    return child

# 变异
def mutation(individual):
    index1 = random.randint(0, len(individual)-1)
    index2 = random.randint(0, len(individual)-1)
    individual[index1], individual[index2] = individual[index2], individual[index1]
    return individual

# 运行遗传算法
def solve_tsp():
    cities_list = list(cities.keys())
    population = [random.sample(cities_list, len(cities_list)) for i in range(100)]
    path = genetic_algorithm(population, fitness_fn=path_length)
    return path

# 测试
if __name__ == '__main__':
    path = solve_tsp()
    print('最短路径：', path)
    print('路径长度：', path_length(path))

用户可以在`cities`字典中添加或修改城市坐标信息，然后输入城市名称来求解TSP问题。运行结果为最短路径和路径长度。