遗传算法解决tsp问题python完整代码

遗传算法（Genetic Algorithm, GA）是一种启发式搜索算法，常用于优化问题，如旅行商问题（Traveling Salesman Problem, TSP）。TSP是一个经典的组合优化问题，目标是找到一条经过所有城市一次且仅一次的最短路径。

下面是一个简单的遗传算法解决TSP问题的Python代码示例，这里使用了DEAP库来实现：

import random
from deap import base, creator, tools

# 定义问题数据
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

def distance(city1, city2):
    # 根据实际城市坐标计算距离，这里假设是个二维坐标系
    return ((city1[0] - city2[1])**2)**0.5

def tsp_distance(individual):
    distance = 0
    for i in range(len(individual) - 1):
        distance += distance(individual[i], individual[i + 1])
    distance += distance(individual[-1], individual[0])  # 回到起点
    return distance,

toolbox = base.Toolbox()
toolbox.register("individual", tools.initCycle, creator.Individual,
                list(range(n_cities)), n_cities)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("evaluate", tsp_distance)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)

def main():
    pop = toolbox.population(n=100)
    hof = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean)
    stats.register("min", np.min)
    stats.register("max", np.max)

    pop, logbook = algorithms.eaSimple(pop, toolbox, cxpb=0.8, mutpb=0.2,
                                       ngen=1000, stats=stats, halloffame=hof,
                                       verbose=True)

    best_ind = hof[0]
    print(f"Best solution found: {best_ind}, Fitness: {best_ind.fitness.values}")

if __name__ == "__main__":
    n_cities = 10  # 你想要的城市数量，替换为你的问题规模
    main()

请注意，这只是一个简化的版本，实际应用中可能需要根据具体问题调整初始化、交叉和突变操作，以及其他参数设置。同时，由于TSP问题本身具有NP-hard特性，找到全局最优解的可能性随着城市数量的增长而降低。