csdn遗传算法tsp问题python

遗传算法是一种常用的求解TSP问题的优化算法。下面是一个使用Python实现的遗传算法解决TSP问题的示例代码：

import random

# 城市坐标
CITIES = {
    'A': (1, 2),
    'B': (3, 4),
    'C': (5, 6),
    'D': (7, 8),
    'E': (9, 10)
}

# 城市个数
CITY_COUNT = len(CITIES)

# 种群大小
POPULATION_SIZE = 100

# 迭代次数
ITERATIONS = 1000

# 交叉概率
CROSSOVER_PROBABILITY = 0.9

# 变异概率
MUTATION_PROBABILITY = 0.2


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


# 计算一条路径的总距离
def path_distance(path):
    distance_sum = 0
    for i in range(CITY_COUNT):
        distance_sum += distance(CITIES[path[i]], CITIES[path[(i + 1) % CITY_COUNT]])
    return distance_sum


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


# 选择
def selection(population):
    fitness_list = []
    for path in population:
        fitness_list.append(1 / path_distance(path))
    total_fitness = sum(fitness_list)
    probability_list = [fitness / total_fitness for fitness in fitness_list]
    selected_population = []
    for i in range(POPULATION_SIZE):
        selected_population.append(population[roulette_wheel_selection(probability_list)])
    return selected_population


# 轮盘赌选择
def roulette_wheel_selection(probability_list):
    r = random.random()
    for i in range(len(probability_list)):
        r -= probability_list[i]
        if r <= 0:
            return i


# 交叉
def crossover(population):
    offspring_population = []
    for i in range(0, POPULATION_SIZE, 2):
        if random.random() < CROSSOVER_PROBABILITY:
            # 随机选择两个父代
            parent1, parent2 = random.sample(population, 2)
            # 随机选择交叉点
            crossover_point = random.randint(1, CITY_COUNT - 1)
            # 交叉得到两个子代
            offspring1 = parent1[:crossover_point] + [city for city in parent2 if city not in parent1[:crossover_point]]
            offspring2 = parent2[:crossover_point] + [city for city in parent1 if city not in parent2[:crossover_point]]
            offspring_population.append(offspring1)
            offspring_population.append(offspring2)
        else:
            offspring_population.append(population[i])
            offspring_population.append(population[i + 1])
    return offspring_population


# 变异
def mutation(population):
    for i in range(POPULATION_SIZE):
        if random.random() < MUTATION_PROBABILITY:
            # 随机选择两个城市
            city1, city2 = random.sample(range(CITY_COUNT), 2)
            # 交换两个城市的位置
            population[i][city1], population[i][city2] = population[i][city2], population[i][city1]
    return population


# 遗传算法求解TSP问题
def tsp_ga():
    # 初始化种群
    population = init_population()
    best_path = None
    best_distance = float('inf')
    # 迭代
    for i in range(ITERATIONS):
        # 选择
        selected_population = selection(population)
        # 交叉
        offspring_population = crossover(selected_population)
        # 变异
        mutated_population = mutation(offspring_population)
        # 计算适应度
        for path in mutated_population:
            distance = path_distance(path)
            if distance < best_distance:
                best_path = path
                best_distance = distance
        print(f'Iteration {i + 1}: Best distance = {best_distance}')
        # 更新种群
        population = mutated_population
    return best_path, best_distance


if __name__ == '__main__':
    best_path, best_distance = tsp_ga()
    print(f'Best path: {best_path}')
    print(f'Best distance: {best_distance}')

在上面的代码中，我们使用字典表示城市的坐标，然后根据坐标计算城市之间的距离。种群的个体是一个城市路径，使用随机打乱城市顺序的方式初始化种群。选择方面，使用轮盘赌选择算法选择下一代个体。交叉方面，使用部分映射交叉算法。变异方面，使用随机交换两个城市的位置的方式进行变异。最后，迭代若干代后，输出最优路径和最短距离。