遗传算法深度指南

关键词

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

摘要

遗传算法（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）在进化过程中呈指数级增长。

---

二、遗传算法的核心组件

2.1 编码机制（Encoding）

编码是个体在解空间与基因空间之间的映射接口，直接影响算法的搜索能力和效率。

2.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$的二进制整数。

优势：

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

劣势：

• 连续变量需要离散化，存在精度损失
• 海明悬崖（Hamming Cliff）问题

2.1.2 实数编码（Real-valued Encoding）

实数编码直接使用浮点数表示决策变量，特别适用于连续优化问题。

编码示例：

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

优势：

• 无精度损失
• 适合高维连续优化
• 直观易懂

劣势：

• 理论分析困难
• 交叉变异需要专门设计

2.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$为异或运算。

Note

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

---

2.2 适应度函数（Fitness Function）

适应度函数衡量个体对环境的适应程度，是自然选择的唯一依据。

2.2.1 直接适应度与间接适应度

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

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

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

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

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

线性尺度变换：

$$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$为适应度标准差。

---

2.3 选择算子（Selection Operators）

选择算子模拟”适者生存”机制，引导种群向高适应度区域进化。

2.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 = accumulate(selection_probs)
    
    # 随机旋转轮盘
    r = random.uniform(0, 1)
    for i, cum_prob in enumerate(cumulative_probs):
        if r <= cum_prob:
            return population[i]

Warning

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

2.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]

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

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

2.3.3 排名选择（Rank Selection）

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

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

---

2.4 交叉算子（Crossover Operators）

交叉算子模拟生物有性繁殖中的基因重组，是GA的主要搜索机制。

2.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}$$

2.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

2.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

2.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]$为混合参数。

---

2.5 变异算子（Mutation Operators）

变异算子模拟基因突变，为种群引入新的遗传材料，防止早熟收敛。

2.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}$$

2.5.2 高斯变异（Gaussian Mutation）

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

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

其中$\sigma$为变异步长参数。

2.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.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.1 马尔可夫链分析

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

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

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

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

4.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])

4.3 收敛速度估计

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

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

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

---

五、参数设置指南

5.1 关键参数

参数	典型范围	影响因素
种群规模$N$	20-200	隐式并行性、解多样性
交叉概率$p_c$	0.6-0.9	探索能力
变异概率$p_m$	0.001-0.1	开发能力
最大代数	100-5000	终止条件

5.2 自适应参数调整

线性递减变异率：

$$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}$$

---

六、应用领域与实践建议

6.1 典型应用

• 旅行商问题（TSP）
• 车间调度问题
• 神经网络权重优化
• 组合优化

6.2 实践建议

Tip

1. 编码选择：连续问题优先考虑实数编码
2. 选择压力：锦标赛选择优于比例选择
3. 多样性保持：使用混合编码或混合算子
4. 局部搜索结合：在GA框架内嵌入局部搜索算子（Memetic Algorithm）

---

参考文献

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
• 神经进化详解