遗传算法深度指南

关键词

选择策略	交叉操作	变异操作	编码方式	适应度函数
轮盘赌选择	单点交叉	位翻转变异	二进制编码	比例选择
锦标赛选择	多点交叉	均匀变异	实数编码	排名选择
适应度尺度	均匀交叉	高斯变异	格雷码	精英保留
收敛速度	算术交叉	边界变异	符号编码	多目标优化

摘要

遗传算法（Genetic Algorithm, GA）是由John Holland于1975年在其开创性著作《Adaptation in Natural and Artificial Systems》中正式提出的自适应启发式搜索算法。该算法根植于Darwin自然选择理论与Mendel遗传学的计算模拟，通过模拟生物进化过程中的选择、交叉、变异等核心机制，在解空间中进行高效搜索，已成为解决复杂优化问题的重要工具。

---

一、进化计算的起源与历史背景

1.1 理论奠基（1960s-1970s）

进化计算的历史可追溯至20世纪60年代。Ingo Rechenberg和Hans-Paul Schwefel在德国斯图加特大学开展的进化策略实验，可以视为进化计算领域的先驱工作。与此同时，Lawrence Fogel在美国提出的进化规划（Evolutionary Programming）也为该领域奠定了重要基础。

然而，遗传算法作为独立算法体系的正式确立，以1975年John Holland的标志性著作《Adaptation in Natural and Artificial Systems》为标志。Holland首次系统性地提出了遗传算法的数学框架，证明了该算法具有隐含并行性（Implicit Parallelism）——即算法在执行过程中，实际上同时评估了$O(m^3)$个模式（schema），其中$m$为种群规模。

1.2 模式定理（Schema Theorem）

模式定理是遗传算法理论的核心基石，由Holland提出。该定理揭示了种群中”好”基因得以传递的数学机制：

在具有固定长度$L$、离散字母表$\Sigma$的串中，模式（Schema）$H$是$\Sigma \cup \{\ast \}$上长度为$L$的模板，其中$\ast$为”不关心”符号。

模式定理的数学表达为：

$$m(H,t+1)\ge m(H,t)\cdot \frac{f(H)}{\bar{f}}\cdot \left(1-p_c\cdot \frac{\delta (H)}{L-1}\right)\cdot {\left(1-p_m\right)}^{\sigma (H)}$$

其中：

• $m(H,t)$：时刻$t$种群中包含模式$H$的个体数量
• $f(H)$：包含模式$H$的个体平均适应度
• $\bar{f}$：种群平均适应度
• $\delta (H)$：模式$H$的定义长度（端点间距离）
• $\sigma (H)$：模式$H$的阶数（确定位置数）
• $p_c,p_m$：交叉概率和变异概率

核心结论：短定义长度、低阶、高适应度的模式（称为建筑块，Building Block）在进化过程中呈指数级增长。

---

二、遗传算法入门：用一个故事讲清楚什么是GA

2.1 村庄里的选种故事

想象一个古老的村庄，村民每年都要在一片广袤的土地上种植玉米。问题来了：什么时候浇水、浇多少水、施什么肥、施多少肥——这些决策直接影响秋天的收成。

最笨的办法是挨个试，把所有可能的组合都试一遍。但这不现实，因为可能的组合太多了。

村里有个老农，他想到了一个聪明的主意：

第一年，他随机撒下100颗玉米种子，秋收时记录每颗种子的产量。第二年，他用产量最高的那20颗种子继续种植。第三年，不仅选好的种子，还把两株好玉米的花粉互相授粉，希望能培育出更好的品种。偶尔，他还会故意”犯错”——比如把种子用盐水泡一泡，看能不能激发出更强的生命力。

就这样年复一年，玉米的产量越来越高。

这，就是遗传算法的核心思想。

2.2 GA的基本概念对照

生物进化	遗传算法	通俗解释
个体	解（Solution）	一个完整的解决方案
种群	解集（Population）	一组候选解的集合
基因	决策变量	解的一个组成部分
适应度	目标函数值	衡量解有多好
选择	选择优秀个体	优中选优
交叉	基因重组	两个解交换信息
变异	基因突变	随机引入新特性
进化代数	迭代次数	算法运行了多久

2.3 为什么适者生存能优化解？

你可能会问：凭什么”适者生存”就能找到好的解？这不是随机的吗？

关键在于”积累”二字。

想象一座山，山顶是全局最优解，山脚是随便一个解。如果你的算法能不断往高处走，最终就能到达山顶。

但问题在于，山不一定是光滑的——它可能有无数个小山包（局部最优）。普通贪心算法一旦爬到一个小山包就停下来了，遗传算法不。

遗传算法的聪明之处在于，它用”种群”来同时探索山的不同区域。某些个体会探索东边，另一些探索西边。当某个区域的个体表现好，它的”基因”（解的部分）就会通过交叉传播到其他区域。

这就好像一个部落分散在世界各地寻找传说中的宝藏，每个人都在尝试不同的路线。找到金矿的那批人会把路线分享给其他人，整个种群的金矿知识就越来越丰富。

---

三、遗传算法的核心组件

3.1 编码机制（Encoding）

编码是个体在解空间与基因空间之间的映射接口，直接影响算法的搜索能力和效率。简单说，就是你打算怎么用一串代码来表示一个解。

3.1.1 二进制编码（Binary Encoding）

二进制编码是最经典也是应用最广泛的编码方式。将决策变量离散化为二进制串表示。

编码示例（变量$x\in [x_{min},x_{max}]$）：

$$x=x_{min}+\frac{\text{bin}}{2^l-1}\cdot (x_{max}-x_{min})$$

其中$\text{bin}$为长度为$l$的二进制整数。

打个比方：假设你要优化一个参数$x\in [0,100]$，用8个二进制位来表示：

• 00000000 代表 0
• 11111111 代表 100
• 01010101 代表大约 33

优势：

• 数学性质优良，便于理论分析
• 交叉、变异操作实现简单
• Schema定理适用性强

劣势：

• 连续变量需要离散化，存在精度损失
• 海明悬崖（Hamming Cliff）问题——相邻两个整数的二进制表示可能相差很大，比如7（0111）和8（1000）只有一位不同，但7和8的二进制表示却差了四位

3.1.2 实数编码（Real-valued Encoding）

实数编码直接使用浮点数表示决策变量，特别适用于连续优化问题。这就像直接用真实的数字来表示参数，而不是用0和1的编码。

编码示例：

$$\mathbf{x}=(x_1,x_2,...,x_n),x_i\in [x_i^{min},x_i^{max}]$$

比如，要优化两个参数：$x_1\in [0,10]$ 和 $x_2\in [-5,5]$，一个个体可能直接就是 (3.14159, -2.71828)。

优势：

• 无精度损失，想多精确就多精确
• 适合高维连续优化
• 直观易懂，代码里用浮点数直接操作

劣势：

• 理论分析困难，没有像Schema定理那样优美的数学工具
• 交叉变异需要专门设计，不能简单套用二进制的操作

3.1.3 格雷码编码（Gray Encoding）

格雷码通过保证相邻整数的海明距离为1，解决了二进制编码的Hamming Cliff问题。

二进制转格雷码规则：

$$g_i=\{\begin{array}{ll}{b}_i& \text{if }i=1\\ b_i\oplus b_{i-1}& \text{if }i>1\end{array}$$

其中$b_i$为二进制位，$g_i$为格雷码位，$\oplus$为异或运算。

举个例子感受一下：

• 二进制：7 → 0111，8 → 1000，海明距离 = 4
• 格雷码：7 → 0100，8 → 1100，海明距离 = 1

这意味着在数值上相邻的两个解，在基因层面也是”相邻”的。进化过程中，算法能更平滑地探索数值空间。

Note

格雷码在需要细粒度局部搜索的场景中表现优异，特别适合与局部搜索算子结合使用。

3.1.4 排列编码（Permutation Encoding）

这是为组合优化问题设计的编码方式。比如旅行商问题中，你需要按特定顺序访问所有城市，排列编码就直接用一个城市编号的序列来表示解。

编码示例：假设有5个城市，用 [3, 1, 5, 2, 4] 表示先访问3号城市，然后1号，再5号，以此类推。

这种编码的特殊性在于，交叉和变异操作需要专门设计，不能随便打乱顺序——否则可能产生无效解。

---

3.2 适应度函数（Fitness Function）

适应度函数衡量个体对环境的适应程度，是自然选择的唯一依据。这个函数定义了你到底在优化什么，所以设计好坏直接影响算法效果。

3.2.1 直接适应度与间接适应度

直接适应度：直接将目标函数值作为适应度。

$$f_{\text{fitness}}(\mathbf{x})=\text{objective}(\mathbf{x})$$

这是最简单的情况，函数值本身就是适应度。比如要最大化利润，利润值直接就是适应度。

间接适应度：通过转换函数将目标函数映射为适应度。

$$f_{\text{fitness}}(\mathbf{x})=T(\text{objective}(\mathbf{x}))$$

有些问题比较棘手：

• 如果你要最小化成本，成本越低越好，但GA天生擅长”最大化”。这时可以做个转换：适应度 = -成本，或者适应度 = 最大成本 - 当前成本。
• 如果约束条件很复杂，需要用惩罚函数，把违反约束的解的适应度大幅降低。

3.2.2 适应度尺度变换（Fitness Scaling）

想象一个场景：种群中有一个”超级个体”，它的适应度是其他个体的100倍。在轮盘赌选择中，这个超级个体会被选中几乎100次，而其他个体几乎没机会。这导致种群快速失去多样性，算法容易陷入局部最优。

适应度尺度变换就是为了解决这个问题。

线性尺度变换：

$$f_i^{\prime }=a\cdot f_i+b$$

参数$a,b$由以下约束确定：

$$\{\begin{array}{l}\sum f^{\prime }=\sum f\\ \overline{f^{\prime }}=\bar{f}\end{array}$$

说人话：线性变换把适应度值重新”拉伸”，让个体之间的差距不要那么夸张。

Sigma截断：

$$f_i^{\prime }=\max (0,f_i-(\bar{f}-c\cdot \sigma ))$$

其中$c$通常取值为2，$\sigma$为适应度标准差。这个方法把低于平均值太多（超过两个标准差）的个体适应度直接设为0，不让它们占用太多选择概率。

---

3.3 选择算子（Selection Operators）

选择算子模拟”适者生存”机制，引导种群向高适应度区域进化。选择策略决定了算法的选择压力——压力太大容易早熟，压力太小收敛太慢。

3.3.1 比例选择（Roulette Wheel Selection）

基于适应度比例的选择方法，个体被选中的概率正比于其适应度。这就像一个不公平的轮盘，好个体的”扇形区域”更大。

$$P(x_i)=\frac{f(x_i)}{{\sum }_{j=1}^{N}f(x_j)}$$

算法实现：

def roulette_wheel_selection(population, fitnesses):
    total_fitness = sum(fitnesses)
    selection_probs = [f / total_fitness for f in fitnesses]
    cumulative_probs = list(accumulate(selection_probs))
    
    # 随机旋转轮盘
    r = random.uniform(0, 1)
    for i, cum_prob in enumerate(cumulative_probs):
        if r <= cum_prob:
            return population[i]

想象转轮盘的过程：随机扔一个飞镖，落在哪个扇形就选哪个个体。因为大扇形概率更高，所以优秀个体更可能被选中，但差个体也有机会——毕竟不是零概率。

Warning

比例选择存在”早熟收敛”风险：当个体适应度差异极大时，高适应度个体会快速占据整个种群，导致多样性丧失。

3.3.2 锦标赛选择（Tournament Selection）

通过随机锦标赛确定最优个体，具有更好的多样性保持能力。这个方法简单粗暴但很有效。

$(k,\tau )$-锦标赛选择：

• 从种群中随机抽取$k$个个体
• 重复$\tau$次，选择适应度最高的个体

def tournament_selection(population, fitnesses, k=3):
    tournament = random.sample(list(zip(population, fitnesses)), k)
    winner = max(tournament, key=lambda x: x[1])
    return winner[0]

锦标赛选择的巧妙之处在于：选择压力可以通过$k$值灵活控制。

• $k=2$：压力很小，几乎随机
• $k$越大：压力越大，最优个体越容易被选中

理论分析：锦标赛选择的.selection pressure可调节参数$k$控制：

$$\text{selection pressure}\propto \frac{k}{N}$$

实践中，$k=3$或$k=5$是最常用的值。

3.3.3 排名选择（Rank Selection）

根据个体在种群中的排名而非绝对适应度进行选择，有效缓解”超级个体”问题。

$$P(x_i)=\frac{\text{rank}(x_i)}{{\sum }_{j=1}^N\text{rank}(x_j)}$$

排名选择的思路是：不管适应度数值差多少，只看排名。比如种群有100个个体，排名第1的选中概率是100/5050，排名第100的是1/5050。这样就彻底避免了适应度值差异过大带来的问题。

3.3.4 精英保留（Elitism）

精英保留策略直接把当前种群中最优秀的几个个体原封不动地复制到下一代。这是一种”保险”策略，确保最好的解不会丢失。

def elitism(population, fitnesses, elite_size=2):
    # 按适应度排序
    sorted_indices = np.argsort(fitnesses)[::-1]
    elite_indices = sorted_indices[:elite_size]
    return population[elite_indices], fitnesses[elite_indices]

精英保留是把双刃剑：

• 好处：不会丢失最优解，加速收敛
• 坏处：可能降低种群多样性

通常建议 elite_size 设为种群大小的1-5%。

---

3.4 交叉算子（Crossover Operators）

交叉算子模拟生物有性繁殖中的基因重组，是GA的主要搜索机制。两个好的解”交配”，可能产生更好的解——这就是交叉的魅力所在。

3.4.1 单点交叉（Single-point Crossover）

最基础的交叉算子，在父代个体串上随机选择一个切点进行交换。就像把两条绳子各切一刀，然后交换尾部。

数学表达：

$$\begin{array}{rl}{\text{Parent}}_1& :\underset{{\text{segment}}_1}{\underbrace{a_1{a}_2\cdots a_k}}\underset{{\text{segment}}_2}{\underbrace{a_{k+1}\cdots a_L}}\\ {\text{Parent}}_2& :\underset{{\text{segment}}_1}{\underbrace{b_1{b}_2\cdots b_k}}\underset{{\text{segment}}_2}{\underbrace{b_{k+1}\cdots b_L}}\\ \downarrow & \\ {\text{Offspring}}_1& :a_1{a}_2\cdots a_k{b}_{k+1}\cdots b_L\\ {\text{Offspring}}_2& :b_1{b}_2\cdots b_k{a}_{k+1}\cdots a_L\end{array}$$

3.4.2 多点交叉（Multi-point Crossover）

选择多个切点进行交叉，增强搜索能力。两点交叉比单点交叉更常用，因为它能产生更多样化的后代。

两点交叉：

def two_point_crossover(parent1, parent2):
    points = sorted(random.sample(range(1, len(parent1)), 2))
    child1 = parent1[:points[0]] + parent2[points[0]:points[1]] + parent1[points[1]:]
    child2 = parent2[:points[0]] + parent1[points[0]:points[1]] + parent2[points[1]:]
    return child1, child2

3.4.3 均匀交叉（Uniform Crossover）

每个基因位独立地以概率$p$从父代选择。这种方式最激进，能产生最多样化的后代。

def uniform_crossover(parent1, parent2, p=0.5):
    child1 = [p1 if random.random() < p else p2 
              for p1, p2 in zip(parent1, parent2)]
    child2 = [p2 if random.random() < p else p1 
              for p1, p2 in zip(parent1, parent2)]
    return child1, child2

3.4.4 算术交叉（Arithmetic Crossover）（实数编码）

实数编码特有的交叉方式，两个父代的加权和作为后代：

$$\begin{array}{rl}{\text{Offspring}}_1& =\lambda \cdot {\text{Parent}}_1+(1-\lambda )\cdot {\text{Parent}}_2\\ {\text{Offspring}}_2& =(1-\lambda )\cdot {\text{Parent}}_1+\lambda \cdot {\text{Parent}}_2\end{array}$$

其中$\lambda \in [0,1]$为混合参数。当$\lambda =0.5$时，两个后代恰好是父代的中点。

3.4.5 模拟二进制交叉SBX（Simulated Binary Crossover）

SBX是处理实数编码问题的标准交叉算子，模仿二进制交叉的特性。

$$\begin{array}{rl}chil{d}_1& =0.5\cdot [(1+\beta )\cdot paren{t}_1+(1-\beta )\cdot paren{t}_2]\\ chil{d}_2& =0.5\cdot [(1-\beta )\cdot paren{t}_1+(1+\beta )\cdot paren{t}_2]\end{array}$$

其中$\beta$是一个随机数，分布使得短定义长度的模式更可能被保留。

---

3.5 变异算子（Mutation Operators）

变异算子模拟基因突变，为种群引入新的遗传材料，防止早熟收敛。没有变异，进化就成了无源之水。

3.5.1 二进制变异（Bit Flip Mutation）

$$x_i^{\prime }=\{\begin{array}{ll}1-x_i& \text{if }r<p_m\\ x_i& \text{otherwise}\end{array}$$

这是最简单的变异：对每个基因位，以小概率翻转（0变1，1变0）。$p_m$通常设为0.001-0.01。

3.5.2 高斯变异（Gaussian Mutation）

实数编码中常用的变异方式，在原值基础上添加服从正态分布的扰动：

$$x_i^{\prime }=x_i+N(0,{\sigma }^2)$$

其中$\sigma$为变异步长参数。简单说就是：在原值上加一个随机噪声，噪声大小服从正态分布。

3.5.3 边界变异（Boundary Mutation）

$$x_i^{\prime }=\{\begin{array}{ll}{x}_i^{min}& \text{with probability }0.5\\ x_i^{max}& \text{with probability }0.5\end{array}$$

边界变异把基因值替换为定义区间的边界值。这种变异比较激进，适合需要探索边界的场景。

3.5.4 变异率到底该怎么设？

变异率是GA中最敏感的参数之一。设得太高，算法就变成了随机搜索；设得太低，种群容易陷入局部最优。

经验法则：

• 二进制编码：$p_m\in [0.001,0.01]$
• 实数编码：$p_m\in [1/n,1/n]$，其中$n$是变量个数

更聪明的做法是让变异率自适应调整——前期高（探索），后期低（开发）。

---

四、遗传算法的完整流程

4.1 标准GA算法框架

class GeneticAlgorithm:
    def __init__(self, objective_func, n_vars, bounds, 
                 pop_size=100, n_generations=1000,
                 crossover_rate=0.8, mutation_rate=0.01):
        self.objective = objective_func
        self.n_vars = n_vars
        self.bounds = bounds
        self.pop_size = pop_size
        self.n_generations = n_generations
        self.p_c = crossover_rate
        self.p_m = mutation_rate
    
    def initialize_population(self):
        return np.random.uniform(
            self.bounds[0], self.bounds[1], 
            (self.pop_size, self.n_vars)
        )
    
    def evaluate(self, population):
        return np.array([self.objective(ind) for ind in population])
    
    def select_parents(self, population, fitnesses):
        # 锦标赛选择
        parents = []
        for _ in range(self.pop_size):
            tournament_idx = random.sample(range(self.pop_size), k=3)
            winner_idx = max(tournament_idx, key=lambda i: fitnesses[i])
            parents.append(population[winner_idx])
        return np.array(parents)
    
    def crossover(self, parent1, parent2):
        if random.random() < self.p_c:
            point = random.randint(1, self.n_vars - 1)
            child1 = np.concatenate([parent1[:point], parent2[point:]])
            child2 = np.concatenate([parent2[:point], parent1[point:]])
            return child1, child2
        return parent1.copy(), parent2.copy()
    
    def mutate(self, individual):
        for i in range(self.n_vars):
            if random.random() < self.p_m:
                individual[i] += np.random.normal(0, 0.1)
                individual[i] = np.clip(individual[i], 
                                        self.bounds[0], self.bounds[1])
        return individual
    
    def run(self):
        population = self.initialize_population()
        best_solution = None
        best_fitness = float('-inf')
        
        for gen in range(self.n_generations):
            fitnesses = self.evaluate(population)
            
            # 记录最优解
            gen_best_idx = np.argmax(fitnesses)
            if fitnesses[gen_best_idx] > best_fitness:
                best_fitness = fitnesses[gen_best_idx]
                best_solution = population[gen_best_idx].copy()
            
            # 选择
            parents = self.select_parents(population, fitnesses)
            
            # 交叉与变异
            offspring = []
            for i in range(0, self.pop_size, 2):
                child1, child2 = self.crossover(parents[i], parents[i+1])
                offspring.extend([self.mutate(child1), self.mutate(child2)])
            
            population = np.array(offspring)
            
            if gen % 100 == 0:
                print(f"Generation {gen}: Best Fitness = {best_fitness:.6f}")
        
        return best_solution, best_fitness

4.2 算法流程图解

┌─────────────────────────────────────────────┐
│              初始化种群                       │
│         （随机生成N个个体）                     │
└────────────────────┬────────────────────────┘
                     ▼
┌─────────────────────────────────────────────┐
│              评估适应度                       │
│         （计算每个个体的得分）                  │
└────────────────────┬────────────────────────┘
                     ▼
┌─────────────────────────────────────────────┐
│    ┌─────────┐    选择    ┌─────────┐       │
│    │ 父代1   │ ────────→ │ 子代1   │       │
│    │ 父代2   │  交叉+变异 │ 子代2   │       │
│    └─────────┘           └─────────┘       │
│       ...                 ...              │
│         ↑                   │              │
│         └────── 重复N次 ─────┘              │
└────────────────────┬────────────────────────┘
                     ▼
┌─────────────────────────────────────────────┐
│           是否满足终止条件？                   │
│      （最大代数 / 达到精度 / 时间限制）         │
│         Yes ──────→ 输出最优解               │
│         No ───────→ 返回"评估适应度"         │
└─────────────────────────────────────────────┘

---

五、遗传算法调参实战

5.1 关键参数的经验值

GA有四个核心参数，每个都直接影响算法表现：

参数	典型范围	影响因素	调参建议
种群规模$N$	20-200	隐式并行性、解多样性	复杂问题用大种群，简单问题用小种群
交叉概率$p_c$	0.6-0.9	探索能力	通常设0.8-0.95
变异概率$p_m$	0.001-0.1	开发能力	设低一些，通常0.01-0.05
最大代数	100-5000	终止条件	取决于问题难度

5.2 调参经验总结

1. 种群大小：不是越大越好。太小会早熟，太大会浪费计算资源。通常从50开始，根据问题难度调整。

2. 交叉vs变异：交叉主要负责探索，变异主要负责开发。大多数情况下，交叉率设高（0.8-0.95），变异率设低（0.01-0.05）。

3. 自适应参数：更高级的做法是让参数随进化动态调整。前期交叉率高变异率低（探索），后期交叉率低变异率高（开发）。

5.3 自适应参数调整

线性递减变异率：

$$p_m(t)=p_m^{max}-\frac{p_m^{max}-p_m^{min}}{T}\cdot t$$

Sigmoid自适应交叉：

$$p_c=\{\begin{array}{ll}{k}_1\cdot \frac{f_{max}-f^{\prime }}{f_{max}-\bar{f}}& f^{\prime }\ge \bar{f}\\ k_2& f^{\prime }<\bar{f}\end{array}$$

---

六、旅行商问题TSP实战

6.1 问题描述

旅行商问题（Traveling Salesman Problem）是组合优化领域最经典的问题之一。假设有个推销员要访问N个城市，要求每个城市恰好访问一次，最后回到出发点，问最短路线是什么？

这问题看起来简单，但随着城市数量增加，解空间呈指数级爆炸：

• 10个城市：181,440种可能
• 20个城市：1.2×10^18种可能
• 50个城市：3×10^62种可能

穷举？算到宇宙毁灭也算不完。

6.2 TSP的GA实现

import random
import numpy as np
 
class TSPGA:
    def __init__(self, cities, pop_size=100, n_generations=500,
                 crossover_rate=0.9, mutation_rate=0.1):
        self.cities = np.array(cities)  # N×2矩阵，存储城市坐标
        self.n_cities = len(cities)
        self.pop_size = pop_size
        self.n_generations = n_generations
        self.p_c = crossover_rate
        self.p_m = mutation_rate
    
    def create_route(self):
        """创建一条随机路线"""
        return list(range(self.n_cities))
    
    def initialize_population(self):
        """初始化种群"""
        return [self.create_route() for _ in range(self.pop_size)]
    
    def route_distance(self, route):
        """计算路线总距离"""
        total = 0
        for i in range(len(route)):
            city1 = self.cities[route[i]]
            city2 = self.cities[route[(i+1) % len(route)]]
            total += np.sqrt(np.sum((city1 - city2)**2))
        return total
    
    def evaluate(self, population):
        """评估种群中每条路线的距离（距离越短越好）"""
        return np.array([self.route_distance(ind) for ind in population])
    
    def tournament_selection(self, population, fitnesses, k=3):
        """锦标赛选择（最小化问题，所以选距离最短的）"""
        tournament_idx = random.sample(range(len(population)), k)
        best_idx = min(tournament_idx, key=lambda i: fitnesses[i])
        return population[best_idx].copy()
    
    def order_crossover(self, parent1, parent2):
        """顺序交叉（OX），专为排列编码设计"""
        if random.random() > self.p_c:
            return parent1.copy(), parent2.copy()
        
        size = len(parent1)
        start, end = sorted(random.sample(range(size), 2))
        
        # 子代1：保留父代1的中间段
        child1 = [None] * size
        child1[start:end] = parent1[start:end]
        
        # 从父代2按顺序填入剩余位置
        remaining = [city for city in parent2 if city not in child1]
        idx = 0
        for i in list(range(end, size)) + list(range(0, start)):
            if idx < len(remaining):
                child1[i] = remaining[idx]
                idx += 1
        
        # 子代2：保留父代2的中间段
        child2 = [None] * size
        child2[start:end] = parent2[start:end]
        remaining = [city for city in parent1 if city not in child2]
        idx = 0
        for i in list(range(end, size)) + list(range(0, start)):
            if idx < len(remaining):
                child2[i] = remaining[idx]
                idx += 1
        
        return child1, child2
    
    def mutate(self, route):
        """交换变异：随机交换两个城市的位置"""
        if random.random() > self.p_m:
            return route
        
        route = route.copy()
        i, j = random.sample(range(len(route)), 2)
        route[i], route[j] = route[j], route[i]
        return route
    
    def run(self):
        """运行遗传算法"""
        population = self.initialize_population()
        best_route = None
        best_distance = float('inf')
        
        for gen in range(self.n_generations):
            fitnesses = self.evaluate(population)
            
            # 更新最优解
            gen_best_idx = np.argmin(fitnesses)
            if fitnesses[gen_best_idx] < best_distance:
                best_distance = fitnesses[gen_best_idx]
                best_route = population[gen_best_idx].copy()
            
            # 选择
            parents = [self.tournament_selection(population, fitnesses) 
                      for _ in range(self.pop_size)]
            
            # 交叉与变异
            offspring = []
            for i in range(0, self.pop_size, 2):
                child1, child2 = self.order_crossover(parents[i], parents[i+1])
                offspring.extend([self.mutate(child1), self.mutate(child2)])
            
            population = offspring
            
            if gen % 50 == 0:
                print(f"Generation {gen}: Best Distance = {best_distance:.2f}")
        
        return best_route, best_distance
 
# 测试：用GA求解10城市TSP
if __name__ == "__main__":
    np.random.seed(42)
    random.seed(42)
    
    # 随机生成10个城市的坐标
    cities = [(random.randint(0, 100), random.randint(0, 100)) 
              for _ in range(10)]
    
    print("城市坐标：")
    for i, city in enumerate(cities):
        print(f"  城市{i}: {city}")
    
    print("\n开始优化...")
    ga = TSPGA(cities, pop_size=100, n_generations=500)
    best_route, best_distance = ga.run()
    
    print(f"\n最优路线：{best_route}")
    print(f"最短距离：{best_distance:.2f}")

6.3 顺序交叉（OX）为什么有效？

TSP的交叉比较特殊，因为简单的单点交叉会产生重复访问的城市（无效解）。

OX交叉的巧妙之处在于：先从父代1继承一段”基因块”，然后按父代2的顺序填入剩余城市。这样保证：

1. 子代是有效路线（不重复、不遗漏）
2. 保留了父代1的局部顺序结构
3. 通过父代2的顺序填充保持了多样性

---

七、遗传算法 vs 梯度下降：什么时候用GA？

7.1 两种方法的本质区别

梯度下降像是”沿着山坡往下走”——它需要目标函数的梯度信息，然后一步步往低处走。优点是收敛快，缺点是只能找到”脚下”最近的低谷，容易被困在局部最优。

遗传算法像是”撒一批种子等它们自己进化”——不需要梯度，只需要知道哪个解更好。优点是全局搜索能力强，缺点是收敛相对慢。

7.2 决策指南

场景	推荐方法	原因
连续可导的优化问题	梯度下降/L-BFGS	梯度信息精确，收敛快
有大量局部最优的问题	遗传算法	全局搜索能力强
离散/组合优化问题	遗传算法/模拟退火	梯度不适用
需要快速得到”够用”的解	遗传算法	并行性好
需要精确最优解	混合方法	GA+局部搜索

7.3 混合方法：兼两家之长

实践中，单纯用GA或单纯用梯度下降都不够好。最常用的是混合方法：先用GA做全局探索，找到有潜力的区域，然后用局部搜索（如梯度下降）精细调优。

这就是著名的”文化算法”或”Memetic Algorithm”（模因算法）的核心思想。

---

八、高级变体与常见问题

8.1 自适应遗传算法（Adaptive GA）

标准GA的参数是固定的，自适应GA让参数根据进化状态动态调整：

def adaptive_mutation_rate(self, gen, initial_rate, min_rate=0.001):
    """线性递减变异率"""
    progress = gen / self.n_generations
    return initial_rate - (initial_rate - min_rate) * progress
 
def adaptive_crossover_rate(self, fitness, avg_fitness, max_fitness):
    """自适应交叉率：优秀个体用较低交叉率保护"""
    if fitness > avg_fitness:
        return 0.5 * (max_fitness - fitness) / (max_fitness - avg_fitness + 1e-6)
    return 1.0

8.2 早熟收敛：问题与解决方案

早熟收敛是GA最常见的问题：种群迅速失去多样性，所有个体都聚集在某个局部最优附近，算法再也跳不出来。

诊断信号：

• 适应度快速提升然后停滞
• 种群中个体高度相似
• 交叉产生的新个体与父代几乎一样

解决方案：

1. 增加变异率：暂时提高$p_m$，引入新基因
2. 重新初始化：用新随机个体替换部分最差个体
3. 增大种群：更多样性意味着更低的早熟风险
4. 使用锦标赛选择：选择压力可调，比轮盘赌更稳健
5. 引入隔离机制：地理隔离可以天然保持多样性

8.3 混合GA与局部搜索

def hybrid_ga_with_local_search(self, individual):
    """混合算法：GA + 局部搜索"""
    # GA阶段
    improved = self.genetic_operations(individual)
    
    # 局部搜索阶段：2-opt算法（TSP经典局部搜索）
    improved = self.two_opt(improved)
    
    return improved
 
def two_opt(self, route):
    """2-opt：每次移除两条边，看是否能得到更短的路线"""
    improved = True
    while improved:
        improved = False
        for i in range(1, len(route) - 1):
            for j in range(i + 1, len(route)):
                if self.two_opt_swap_improves(route, i, j):
                    route = self.two_opt_swap(route, i, j)
                    improved = True
    return route

---

九、收敛性分析

9.1 马尔可夫链分析

遗传算法的收敛性可通过有限状态马尔可夫链进行严格分析。将种群视为状态空间$\mathcal{P}$中的元素，转移概率由选择、交叉、变异算子决定。

定义：遗传算法以概率1收敛到全局最优解，当且仅当：

$$\underset{t\to \infty }{\lim }P(X_t\in {\mathcal{P}}^{\ast }|X_0)=1$$

其中${\mathcal{P}}^{\ast }$为包含最优解的种群集合。

9.2 精英保留策略（Elitism）

标准GA的收敛性取决于变异算子的性质。采用精英保留策略可保证算法收敛：

def evolve_with_elitism(self, population, fitnesses, elite_size=2):
    # 保留精英个体
    elite_indices = np.argsort(fitnesses)[-elite_size:]
    elite = population[elite_indices]
    
    # 其余个体进行选择、交叉、变异
    remaining_pop = self.evolve_regular(population, fitnesses)
    
    return np.vstack([elite, remaining_pop])

9.3 收敛速度估计

模式定理可推导收敛速度的下界：

$$m(H,t)\ge m(H,0)\cdot (1+c{)}^t$$

其中$c=\frac{f(H)-\bar{f}}{\bar{f}}$为超指数增长率。

---

十、应用领域与实践建议

10.1 典型应用

遗传算法的应用范围极其广泛：

• 旅行商问题（TSP）：路线规划、物流配送
• 车间调度问题：工厂排产、生产计划
• 神经网络权重优化：深度学习超参数调优
• 组合优化：资源分配、装箱问题
• 工程设计优化：飞机翼型设计、电路设计
• 投资组合优化：在收益和风险之间找平衡

10.2 实践建议

Tip

1. 编码选择：连续问题优先考虑实数编码，组合问题用排列编码
2. 选择压力：锦标赛选择优于比例选择，压力可控
3. 多样性保持：监控种群多样性，必要时重启或提高变异率
4. 局部搜索结合：在GA框架内嵌入局部搜索算子（Memetic Algorithm）
5. 多次运行：GA有随机性，建议独立运行10-30次取最优

---

参考文献

1. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
2. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.
3. Holland, J. H. (1992). Genetic Algorithms. Scientific American, 267(1), 66-72.
4. Sivanandam, S. N., & Deepa, S. N. (2008). Introduction to Genetic Algorithms. Springer.

---

相关文档

• 遗传编程详解
• 进化策略深度指南
• 差分进化算法
• 粒子群优化PSO
• 神经进化详解