tsp旅行商问题遗传算法

TSP问题是一个经典的组合优化问题，遗传算法是其中一种求解TSP问题的启发式算法。下面是遗传算法求解TSP问题的步骤：

1. 初始化种群：随机生成一定数量的路径作为初始种群。

2. 适应度函数：计算每个个体的适应度，即路径的总长度。

3. 选择操作：根据适应度函数选择优秀的个体，用于产生下一代种群。

4. 交叉操作：从父代中选择两个个体，通过交叉操作产生两个子代。

5. 变异操作：对子代进行变异操作，增加种群的多样性。

6. 更新种群：用新的个体替换旧的个体，产生下一代种群。

7. 终止条件：达到预设的迭代次数或者找到最优解时终止算法。

下面是一个Python实现的遗传算法求解TSP问题的例子：

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)]

# 计算两个城市之间的距离
def distance(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(len(path) - 1):
        length += distance(city_pos[path[i]], city_pos[path[i+1]])
    length += distance(city_pos[path[-1]], city_pos[path[0]])
    return length

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

# 选择操作
def selection(population, fitness):
    fitness_sum = sum(fitness)
    probability = [f/fitness_sum for f in fitness]
    cum_probability = [sum(probability[:i+1]) for i in range(len(probability))]
    new_population = []
    for i in range(len(population)):
        r = random.random()
        for j in range(len(cum_probability)):
            if r < cum_probability[j]:
                new_population.append(population[j])
                break
    return new_population

# 交叉操作
def crossover(parent1, parent2):
    child1, child2 = parent1.copy(), parent2.copy()
    start, end = sorted([random.randint(0, len(parent1)-1) for _ in range(2)])
    for i in range(start, end+1):
        child1[i], child2[i] = child2[i], child1[i]
    return child1, child2

# 变异操作
def mutation(path):
    i, j = sorted([random.randint(0, len(path)-1) for _ in range(2)])
    path[i:j+1] = reversed(path[i:j+1])
    return path

# 遗传算法求解TSP问题
def tsp_ga(city_pos, pop_size=100, max_iter=1000):
    city_num = len(city_pos)
    population = init_population(pop_size, city_num)
    best_path, best_length = None, float('inf')
    for i in range(max_iter):
        fitness = [1/path_length(path) for path in population]
        best_index = fitness.index(max(fitness))
        if path_length(population[best_index]) < best_length:
            best_path = population[best_index]
            best_length = path_length(best_path)
        new_population = [population[best_index]]
        while len(new_population) < pop_size:
            parent1, parent2 = random.choices(population, weights=fitness, k=2)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutation(child1) if random.random() < 0.1 else child1
            child2 = mutation(child2) if random.random() < 0.1 else child2
            new_population.extend([child1, child2])
        population = selection(new_population, fitness)
    return best_path, best_length

# 测试
best_path, best_length = tsp_ga(city_pos)
print('最短路径：', best_path)
print('路径长度：', best_length)