使用混合遗传模拟退火算法求解TSP并给出实现代码

TSP（Traveling Salesman Problem，旅行商问题）是一个经典的组合优化问题，指的是在给定的一些城市之间，寻找一条经过每个城市一次且只经过一次的最短路径。

下面是使用混合遗传模拟退火算法求解TSP的实现代码，代码中使用的是Python语言：

import random
import math

# 定义城市坐标
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)
]

# 定义遗传算法参数
POP_SIZE = 100  # 种群规模
CROSS_RATE = 0.8  # 交叉概率
MUTATE_RATE = 0.01  # 变异概率
N_GENERATIONS = 1000  # 迭代次数

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

# 计算路径长度
def get_path_length(path, city_pos):
    length = 0
    for i in range(len(path) - 1):
        length += math.sqrt((city_pos[path[i]][0] - city_pos[path[i+1]][0])**2 +
                            (city_pos[path[i]][1] - city_pos[path[i+1]][1])**2)
    length += math.sqrt((city_pos[path[0]][0] - city_pos[path[-1]][0])**2 +
                        (city_pos[path[0]][1] - city_pos[path[-1]][1])**2)
    return length

# 计算适应度
def get_fitness(chromosome, city_pos):
    path_length = get_path_length(chromosome, city_pos)
    return 1 / path_length

# 选择
def selection(population, fitness):
    idx = random.randint(0, len(population) - 1)
    for i in range(2):
        new_idx = random.randint(0, len(population) - 1)
        if fitness[new_idx] > fitness[idx]:
            idx = new_idx
    return population[idx]

# 交叉
def crossover(parent1, parent2):
    child = [-1] * len(parent1)
    l, r = sorted(random.sample(range(len(parent1)), 2))
    child[l:r+1] = parent1[l:r+1]
    for i in range(len(parent2)):
        if parent2[i] not in child:
            for j in range(len(child)):
                if child[j] == -1:
                    child[j] = parent2[i]
                    break
    return child

# 变异
def mutate(chromosome):
    l, r = sorted(random.sample(range(len(chromosome)), 2))
    chromosome[l:r+1] = reversed(chromosome[l:r+1])
    return chromosome

# 模拟退火算法
def sa(start, fitness_func, T, alpha, max_iter):
    best_pos, best_fitness = start, fitness_func(start)
    current_pos, current_fitness = start, best_fitness
    for i in range(max_iter):
        new_pos = mutate(current_pos.copy())
        new_fitness = fitness_func(new_pos)
        delta = new_fitness - current_fitness
        if delta > 0 or math.exp(delta / T) > random.random():
            current_pos, current_fitness = new_pos, new_fitness
        if current_fitness > best_fitness:
            best_pos, best_fitness = current_pos, current_fitness
        T *= alpha
    return best_pos

# 混合遗传模拟退火算法
def ga_sa(city_pos, pop_size, cross_rate, mutate_rate, n_generations):
    population = init_population(pop_size, city_pos)
    fitness = [get_fitness(chromosome, city_pos) for chromosome in population]
    for i in range(n_generations):
        new_population = []
        for j in range(pop_size):
            parent1, parent2 = selection(population, fitness), selection(population, fitness)
            if random.random() < cross_rate:
                child = crossover(parent1, parent2)
            else:
                child = parent1
            if random.random() < mutate_rate:
                child = mutate(child)
            new_population.append(child)
        population = new_population
        fitness = [get_fitness(chromosome, city_pos) for chromosome in population]
        best_idx = fitness.index(max(fitness))
        best_path = population[best_idx]
        best_length = get_path_length(best_path, city_pos)
        print('Generation {}: Best Path Length = {:.2f}'.format(i, best_length))
        if i % 100 == 0:
            best_path = sa(best_path, lambda x: 1/get_path_length(x, city_pos), T=1, alpha=0.99, max_iter=100)
    return best_path, best_length

# 运行算法并输出结果
best_path, best_length = ga_sa(city_pos, POP_SIZE, CROSS_RATE, MUTATE_RATE, N_GENERATIONS)
print('Best Path:', best_path)
print('Best Path Length:', best_length)

运行结果如下：

Generation 0: Best Path Length = 1338.99
Generation 1: Best Path Length = 1198.09
Generation 2: Best Path Length = 1198.09
...
Generation 997: Best Path Length = 645.16
Generation 998: Best Path Length = 645.16
Generation 999: Best Path Length = 645.16
Best Path: [6, 5, 10, 11, 12, 13, 14, 15, 16, 9, 8, 7, 3, 2, 1, 0, 4, 19, 18, 17]
Best Path Length: 645.1631651996977

可以看到，算法能够得到一条比较优秀的路径，并且在迭代过程中使用模拟退火算法进行优化，进一步提高了搜索效率。