遗传算法入门：从原理到实践的完整指南

遗传算法（Genetic Algorithm, GA）作为一类模拟自然选择与遗传机制的启发式搜索算法，自20世纪70年代提出以来，已成为解决复杂优化问题的核心工具。其通过模拟生物进化中的选择、交叉、变异等操作，在函数优化、组合优化、机器学习等领域展现出独特优势。本文将从算法原理、实现步骤、优化策略三个维度展开，为开发者提供可落地的技术指南。

一、算法核心原理：生物进化的数学抽象

遗传算法的核心思想是将问题解编码为“染色体”（个体），通过模拟自然选择中的优胜劣汰机制，逐步迭代出最优解。其数学基础可概括为三个关键环节：

编码与解码
问题解需转换为算法可处理的编码形式。常见编码方式包括：
- 二进制编码：将连续变量离散化为二进制串（如0101表示数值5），适用于离散优化问题。
- 实数编码：直接使用实数向量表示解（如[1.2, 3.4]），避免二进制转换的精度损失，常用于连续优化。
- 排列编码：针对组合优化问题（如TSP路径），用排列序列表示解（如[3,1,2,4]表示访问顺序）。
适应度函数设计
适应度函数是评价个体优劣的唯一标准，需根据问题目标定制。例如：
- 最小化问题：fitness = 1 / (1 + objective_value)（避免除零）。
- 最大化问题：直接使用目标函数值作为适应度。
- 多目标优化：可采用加权求和或帕累托前沿分析。
进化操作
- 选择（Selection）：从当前种群中挑选优质个体作为父代。常用方法包括：
  - 轮盘赌选择：按适应度比例分配选择概率。
  - 锦标赛选择：随机选取k个个体，选择其中最优者。
- 交叉（Crossover）：模拟基因重组，生成子代。例如：
  - 单点交叉：随机选择一个交叉点，交换父代部分基因。
```
# 单点交叉示例
def crossover(parent1, parent2, point):
  child1 = parent1[:point] + parent2[point:]
  child2 = parent2[:point] + parent1[point:]
  return child1, child2
```
- 变异（Mutation）：以小概率随机修改基因，增加种群多样性。例如：
  - 位翻转变异：二进制编码中随机翻转某位。
  - 高斯变异：实数编码中添加高斯噪声。

二、算法实现步骤：从问题到解的全流程

1. 问题建模与参数初始化

定义问题空间：明确变量范围、约束条件及目标函数。
设置算法参数：
- 种群大小（Population Size）：通常取50-200，影响收敛速度与解质量。
- 最大迭代次数（Max Generations）：控制算法运行时间。
- 交叉概率（Crossover Rate）：通常取0.6-0.9。
- 变异概率（Mutation Rate）：通常取0.001-0.1。

2. 初始化种群

随机生成初始种群，确保覆盖问题空间。例如，在求解函数f(x)=x²的最小值时，可生成100个[0,10]范围内的随机实数作为初始解。

3. 迭代进化

计算适应度：对每个个体评估目标函数值。
选择操作：根据适应度选择父代（如轮盘赌选择）。
交叉与变异：生成子代种群。
精英保留：将当前最优个体直接保留到下一代，避免丢失优质解。

4. 终止条件判断

当满足以下条件之一时终止算法：

达到最大迭代次数。
适应度连续N代未显著提升。
找到满足精度要求的解。

三、优化策略：提升算法性能的关键

1. 自适应参数调整

动态交叉/变异概率：根据种群多样性调整参数。例如，当种群适应度差异较小时，提高变异概率以增强探索能力。

# 自适应变异概率示例
def adaptive_mutation_rate(generation, max_gen):
    return 0.1 * (1 - generation / max_gen)  # 随迭代次数递减

2. 混合算法设计

结合其他优化算法（如局部搜索、模拟退火）提升性能。例如：

遗传-局部搜索混合算法：在遗传算法生成子代后，对优质个体应用梯度下降等局部搜索方法。

3. 并行化实现

利用多线程或分布式计算加速适应度评估。例如，将种群划分为多个子群，并行计算适应度后合并结果。

四、应用场景与代码实践

1. 函数优化示例

求解f(x)=x²在[0,10]上的最小值：

import numpy as np
def fitness_function(x):
    return -x**2  # 负号因GA默认求最大值
def genetic_algorithm():
    population_size = 100
    max_generations = 50
    crossover_rate = 0.8
    mutation_rate = 0.01
    # 初始化种群
    population = np.random.uniform(0, 10, population_size)
    for generation in range(max_generations):
        # 计算适应度
        fitness = np.array([fitness_function(x) for x in population])
        # 选择（轮盘赌）
        prob = fitness - np.min(fitness) + 1e-6  # 避免负值
        prob /= prob.sum()
        selected_indices = np.random.choice(population_size, size=population_size, p=prob)
        selected = population[selected_indices]
        # 交叉与变异
        new_population = []
        for i in range(0, population_size, 2):
            if i+1 < population_size and np.random.rand() < crossover_rate:
                point = np.random.randint(1, len(population)-1)
                child1 = np.concatenate([selected[i][:point], selected[i+1][point:]])
                child2 = np.concatenate([selected[i+1][:point], selected[i][point:]])
            else:
                child1, child2 = selected[i], selected[i+1]
            # 变异
            if np.random.rand() < mutation_rate:
                child1 += np.random.normal(0, 0.1)
            if np.random.rand() < mutation_rate:
                child2 += np.random.normal(0, 0.1)
            new_population.extend([child1, child2])
        population = np.array(new_population[:population_size])
        # 输出最优解
        best_idx = np.argmax(fitness)
        print(f"Generation {generation}: Best x={population[best_idx]}, f(x)={-fitness[best_idx]}")
genetic_algorithm()

2. 组合优化示例（TSP问题）

针对旅行商问题，可采用排列编码表示路径，并设计专门的交叉算子（如部分匹配交叉，PMX）以保持路径合法性。

五、注意事项与最佳实践

编码方式选择：根据问题特性选择编码方式。连续优化问题优先实数编码，组合优化问题采用排列编码。
适应度函数设计：避免适应度值差异过大导致早熟收敛，可通过归一化或对数变换调整尺度。
参数调优：通过实验确定最优参数组合，或采用自适应参数调整策略。
收敛性分析：记录每代最优适应度，绘制收敛曲线以判断算法性能。

遗传算法通过模拟自然进化机制，为复杂优化问题提供了一种高效、鲁棒的解决方案。开发者可通过合理设计编码方式、适应度函数及进化操作，结合自适应优化与并行化技术，进一步提升算法性能。在实际应用中，建议从简单问题入手，逐步验证算法有效性，再扩展至复杂场景。