遗传算法详解：以旅行商问题为例

遗传算法详解：以旅行商问题为例

引用

CSDN

1.

https://m.blog.csdn.net/Dawn__f/article/details/141071041

遗传算法是一种受到自然选择和遗传学理论启发的优化算法，通过模拟自然进化过程来搜索最优解。它在解决复杂的组合优化问题时，通常能够较快地获得较好的优化结果。本文将以旅行商问题（TSP）为例，详细介绍遗传算法的基本原理、步骤，并给出具体的Python实现代码。

算法介绍

遗传算法是一种受到自然选择和遗传学理论启发的一种优化算法，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式，利用计算机仿真计算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时，相对一些常规的优化算法，通常能够较快地获得较好的优化结果。

算法步骤

1. 编码（初始化种群）：遗传算法不能直接处理问题空间的参数，因此必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。随机生成一组个体，构成初始种群。

• TSP：每组个体为一组城市路径顺序。

2. 适应度评估：对每个个体计算其适应度，即评估解决方案的优劣程度。适应度函数通常与问题的目标函数相关，目标是使适应度较高的个体在进化过程中更有可能被选择。

• TSP：总距离越短，适应度越高，越容易被保留。

3. 选择（复制）：按照适应度大小对个体进行选择，适应度较高的个体被选中的概率较大，而适应度较低的个体被选中的概率较小。这里使用的选择方法常用的是轮盘赌、锦标赛、线性排名选择等。

• 轮盘赌选择：
• 锦标赛选择：
  A. 确定每次选择的个体数量N。
  B. 从种群中随机选择N个个体（每个个体被选择的概率相同），根据每个个体的适应度值，选择其中适应度值最好的个体进入下一代种群。
  C. 重复步骤B多次（重复次数为种群的大小），直到新的种群规模达到原来的种个种群规 模。
• 线性排名选择：基于个体的适应性（或称为适应度）对种群中个体进行排序，并根据其排名来分配选择概率。该选择方法的主要目的是在进化过程中优先选择适应度更高的个体，但仍然为较差的个 体保留一定的选择机会，以维持种群的多样性。

4. 交叉：分为单点交叉、多点交叉、部分映射交叉等。从选择的个体中选取一对（或多对），进行交叉操作，生成新的个体，交叉模拟了生物学中的基因交换过程，通过交叉可以将两个个体的优良特征结合在一起。

• 部分映射交叉：

5. 变异：分为单点变异、多点变异、均匀变异、翻转变异等。在一定的概率下，对新个体进行变异操作，即对其中的某些基因进行随机修改。 变异模拟了自然界中基因发生突变的过程，有助于保持种群的多样性。

• 多点变异：
  

6. 生成下一代种群：通过选择、交叉和变异操作，生成下一代种群，取代当前种群。

7. 收敛检验：检查是否满足停止条件，如达到预定的迭代次数或找到足够优秀的解。如果满足条件，则停止进化过程，返回找到的最优解；否则返回第三步继续进行进化。

• 终止条件：
  1. 设置最大进化次数
  2. 设置最优解的精度
  3. 种群中的最优个体在连续若干代没有改进

常见问题

1. 为什么每次运行结果都不一样？
   遗传算法本身具有随机性，无论是选择、交叉还是变异，都是不确定的。

2. 如何选择编码的方式?
   根据实际问题来设计编码方式。TSP问题采用十进制编码比较容易理解，但采用二进制编码会简化交叉和变异的操作，也适合设计更复杂的交叉和变异的方式。

3. 遗传算法有什么缺点吗？
   不能保证所得解为全局最优解（参数足够大的情况下是可以求出全局最优解，但失去了算法本身的意义）。

算法实现

import numpy as np
import random
import matplotlib.pyplot as plt

# 城市坐标(30个)
coordinates = np.array([
    [1, 5], [3, 4], [2, 6], [7, 4], [11, 2], [5, 7], [6, 16], [4, 15], [7, 5], [10, 15], [14, 11], [3, 18], [5, 10], [4, 9], [2, 9],
    [15, 21], [2, 17], [3, 11], [14, 2], [13, 9], [27, 10], [4, 23], [19, 25], [7, 27], [16, 27], [9, 25], [4, 20], [20, 6], [20, 20], [24, 19]
])

# 计算两个城市之间的距离
def calculate_distance(city1, city2):
    return np.linalg.norm(city1 - city2)

# 计算路径总距离
def calculate_total_distance(path):
    total_distance = 0
    for i in range(len(path) - 1):
        total_distance += calculate_distance(coordinates[path[i]], coordinates[path[i + 1]])
    total_distance += calculate_distance(coordinates[path[-1]], coordinates[path[0]])  # 回到起点
    return total_distance

# 生成初始种群
def generate_initial_population(population_size, city_count):
    population = []
    for _ in range(population_size):
        individual = list(np.random.permutation(city_count))  # 随机生成个体（一个路径）
        population.append(individual)
    return population

# 选择父代（根据适应度选择）
def selection(population, fitness):
    selected = random.choices(population, weights=fitness, k=len(population))
    return selected

# 交叉操作（部分映射交叉，PMX）
def crossover(parent1, parent2):
    size = len(parent1)
    start, end = sorted(random.sample(range(size), 2))
    child = [None] * size
    child[start:end + 1] = parent1[start:end + 1]
    pointer = 0
    for city in parent2:
        if city not in child:
            while child[pointer] is not None:
                pointer += 1
            child[pointer] = city
    return child

# 变异操作（随机交换两个城市的位置）
def mutate(individual, mutation_rate):
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            j = random.randint(0, len(individual) - 1)
            individual[i], individual[j] = individual[j], individual[i]
    return individual

# 遗传算法主函数
def genetic_algorithm(coordinates, population_size=100, generations=500, mutation_rate=0.02):
    city_count = len(coordinates)
    population = generate_initial_population(population_size, city_count)
    
    best_individual = None
    best_distance = float('inf')
    for generation in range(generations):
        fitness = [1 / calculate_total_distance(individual) for individual in population]  # 计算适应度
        best_gen = population[np.argmax(fitness)]
        best_gen_distance = calculate_total_distance(best_gen)
        if best_gen_distance < best_distance:
            best_individual = best_gen
            best_distance = best_gen_distance
        print(f"Generation {generation}: Best Distance = {best_distance}")
        selected = selection(population, fitness)
        new_population = []
        for i in range(0, population_size, 2):
            parent1, parent2 = selected[i], selected[i + 1]
            child1, child2 = crossover(parent1, parent2), crossover(parent2, parent1)
            new_population.extend([mutate(child1, mutation_rate), mutate(child2, mutation_rate)])
        population = new_population
    return best_individual, best_distance

best_path, best_distance = genetic_algorithm(coordinates)
print("Best Path:", best_path)
print("Best Distance:", best_distance)

# 可视化结果
def plot_path(coordinates, path):
    plt.figure(figsize=(10, 5))
    for i in range(len(path)):
        plt.plot([coordinates[path[i-1]][0], coordinates[path[i]][0]], [coordinates[path[i-1]][1], coordinates[path[i]][1]], 'bo-')
    plt.plot([coordinates[path[-1]][0], coordinates[path[0]][0]], [coordinates[path[-1]][1], coordinates[path[0]][1]], 'ro-')
    plt.xlabel('X Coordinate')
    plt.ylabel('Y Coordinate')
    plt.title('Best Path Found by Genetic Algorithm')
    plt.show()

plot_path(coordinates, best_path)