第4章：遗传算法入门——从生物进化到路径优化

各位工程师朋友，大家好。今天我们来聊聊遗传算法。

说实话，我第一次接触遗传算法是在一个激光切割项目中。当时要优化几百个孔位的切割顺序，传统算法算到天荒地老。后来一位老前辈跟我说：「你试试遗传算法，让路径自己进化。」我当时就懵了——路径还能进化？

嗯，后来我才明白，这玩意儿确实能。

4.1 遗传算法核心概念

遗传算法（GA）说白了就是模仿生物进化过程。你想想看，自然界里生物是怎么变强的？

• 种群（Population）：一群候选解，就像一群狮子
• 染色体（Chromosome）：每个解的具体编码，比如切割顺序
• 基因（Gene）：染色体上的一个点位，比如某个孔的位置
• 适应度（Fitness）：这个解好不好，路径短不短
• 选择（Selection）：好的留下，差的淘汰
• 交叉（Crossover）：两个好解结合，产生更好的
• 变异（Mutation）：随机改变一点点，防止陷入局部最优

我在项目中遇到过一个问题：一开始种群太小，结果算法很快就「近亲繁殖」了，所有解都差不多。后来我把种群规模调到100以上，效果明显改善。

4.2 适应度函数设计——这是最关键的一步

适应度函数，就是告诉算法「什么样的解是好解」。

对于TSP（旅行商问题），我们关心的是路径总长度。路径越短，适应度越高。

我常用的设计方式是这样的：

// 适应度函数伪代码
function fitness(route):
    total_distance = 0
    for i = 0 to route.length - 2:
        total_distance += distance(route[i], route[i+1])
    // 加上回到起点的距离
    total_distance += distance(route[last], route[0])
    // 适应度 = 1 / 总距离（越小越好）
    return 1.0 / total_distance

为什么会这样？你想想看，如果最好的解适应度是100，最差的只有0.01，那差的解基本没机会被选中，种群很快就单一化了。

4.3 遗传算法求解TSP的Python实现

好了，理论说完了，咱们直接上代码。这是我个人习惯的写法，简洁实用。

import random
import math

# 城市坐标（示例）
cities = [
    (0, 0), (1, 5), (3, 2), (6, 4), (7, 1),
    (8, 6), (2, 7), (5, 8), (9, 3), (4, 9)
]

# 计算两个城市间的距离
def distance(city1, city2):
    return math.sqrt((city1[0]-city2[0])**2 + (city1[1]-city2[1])**2)

# 计算路径总长度
def total_distance(route):
    dist = 0
    for i in range(len(route)-1):
        dist += distance(cities[route[i]], cities[route[i+1]])
    dist += distance(cities[route[-1]], cities[route[0]])  # 回到起点
    return dist

# 适应度函数
def fitness(route):
    return 1.0 / total_distance(route)

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

# 选择（轮盘赌）
def selection(population, fitnesses):
    total_fitness = sum(fitnesses)
    pick = random.uniform(0, total_fitness)
    current = 0
    for i, f in enumerate(fitnesses):
        current += f
        if current > pick:
            return population[i]
    return population[-1]

# 交叉（顺序交叉 OX）
def crossover(parent1, parent2):
    size = len(parent1)
    start, end = sorted(random.sample(range(size), 2))
    child = [None] * size
    child[start:end] = parent1[start:end]
    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 mutation(route, mutation_rate=0.1):
    if random.random() < mutation_rate:
        i, j = random.sample(range(len(route)), 2)
        route[i], route[j] = route[j], route[i]
    return route

# 主算法
def genetic_algorithm(pop_size=100, generations=500):
    num_cities = len(cities)
    population = init_population(pop_size, num_cities)
    best_route = None
    best_dist = float('inf')

    for gen in range(generations):
        fitnesses = [fitness(route) for route in population]
        new_population = []

        for _ in range(pop_size):
            p1 = selection(population, fitnesses)
            p2 = selection(population, fitnesses)
            child = crossover(p1, p2)
            child = mutation(child)
            new_population.append(child)

        population = new_population

        # 记录最优解
        current_best = min(population, key=total_distance)
        current_dist = total_distance(current_best)
        if current_dist < best_dist:
            best_dist = current_dist
            best_route = current_best

        if gen % 50 == 0:
            print(f"第{gen}代，最优距离：{current_dist:.2f}")

    return best_route, best_dist

# 运行
best_route, best_dist = genetic_algorithm()
print(f"最优路径：{best_route}")
print(f"最短距离：{best_dist:.2f}")

4.4 遗传算法核心流程

下面这张图是我自己画的，把整个流程串起来，一目了然。

4.5 参数调优建议

遗传算法好不好用，参数很关键。我整理了一张表，是我这些年调试的经验值。

参数	推荐范围	我的经验
种群大小	50 ~ 200	100左右最稳，太小容易早熟
交叉概率	0.7 ~ 0.9	我常用0.8，太高会破坏好解
变异概率	0.05 ~ 0.2	0.1是个好起点，太大变随机搜索
迭代次数	200 ~ 1000	看问题规模，500代基本够用

好了，这一章的内容就到这里。遗传算法入门其实不难，关键是理解「进化」这个思想。你想想看，我们做激光切割路径优化，本质上也是在寻找一条「最优的生存路径」。

代码我已经跑过了，10个城市的情况下，一般100代以内就能找到接近最优的解。你可以试试把城市数量增加到20个、50个，看看算法表现如何。

---