遗传算法 Python 3.11 实战：5步实现函数优化，对比梯度下降收敛速度-平芜编程栈

遗传算法Python 3.11实战：5步实现函数优化与梯度下降对比

当我们需要在复杂搜索空间中找到最优解时，传统优化方法往往力不从心。遗传算法作为一种模拟自然进化过程的智能优化技术，正成为解决这类问题的利器。本文将带您用Python 3.11从零实现遗传算法，并对比其与梯度下降在函数优化中的表现差异。

1. 遗传算法核心原理与Python实现

遗传算法的魅力在于它将生物进化原理转化为数学优化工具。想象一群在解空间中探索的"数字生物"，它们通过选择、交叉和变异不断进化，最终逼近最优解。

1.1 算法框架搭建

我们先构建遗传算法的核心骨架：

import numpy as np from typing import List, Callable, Tuple class GeneticAlgorithm: def __init__(self, population_size: int, chromosome_length: int, fitness_func: Callable, crossover_rate: float = 0.8, mutation_rate: float = 0.01, elitism: bool = True): self.pop_size = population_size self.chrom_len = chromosome_length self.fitness_func = fitness_func self.crossover_rate = crossover_rate self.mutation_rate = mutation_rate self.elitism = elitism def initialize_population(self) -> np.ndarray: """生成随机初始种群""" return np.random.uniform(-5.12, 5.12, (self.pop_size, self.chrom_len)) def selection(self, population: np.ndarray, fitness: np.ndarray) -> np.ndarray: """轮盘赌选择""" normalized_fitness = fitness / fitness.sum() selected_indices = np.random.choice( len(population), size=len(population), p=normalized_fitness, replace=True) return population[selected_indices] def crossover(self, parent1: np.ndarray, parent2: np.ndarray) -> Tuple[np.ndarray, np.ndarray]: """单点交叉""" if np.random.rand() > self.crossover_rate: return parent1.copy(), parent2.copy() crossover_point = np.random.randint(1, self.chrom_len-1) child1 = np.concatenate([parent1[:crossover_point], parent2[crossover_point:]]) child2 = np.concatenate([parent2[:crossover_point], parent1[crossover_point:]]) return child1, child2 def mutation(self, individual: np.ndarray) -> np.ndarray: """高斯变异""" mask = np.random.rand(self.chrom_len) < self.mutation_rate noise = np.random.normal(0, 0.5, self.chrom_len) return np.where(mask, individual + noise, individual) def evolve(self, population: np.ndarray) -> np.ndarray: """执行一代进化""" fitness = np.array([self.fitness_func(ind) for ind in population]) new_population = np.empty_like(population) # 精英保留 if self.elitism: elite_idx = np.argmax(fitness) new_population[0] = population[elite_idx] start_idx = 1 else: start_idx = 0 # 选择 selected = self.selection(population, fitness) # 交叉和变异 for i in range(start_idx, self.pop_size, 2): parent1, parent2 = selected[i], selected[i+1] child1, child2 = self.crossover(parent1, parent2) new_population[i] = self.mutation(child1) if i+1 < self.pop_size: new_population[i+1] = self.mutation(child2) return new_population

1.2 适应度函数设计

以Rastrigin函数为例，这是一个典型的多模态优化问题：

def rastrigin(x: np.ndarray) -> float: """Rastrigin函数，全局最小值在原点处为0""" A = 10 return A * len(x) + np.sum(x**2 - A * np.cos(2 * np.pi * x)) def fitness_function(individual: np.ndarray) -> float: """适应度函数，将最小化问题转化为最大化问题""" return -rastrigin(individual)

Rastrigin函数在优化领域具有代表性，其特点是具有大量局部极值点，非常适合测试算法的全局搜索能力。

2. 完整优化流程实现

2.1 参数配置与算法执行

def run_optimization(dimensions=2, generations=100, pop_size=50, verbose=True): """执行完整优化流程""" ga = GeneticAlgorithm( population_size=pop_size, chromosome_length=dimensions, fitness_func=fitness_function, crossover_rate=0.85, mutation_rate=0.02 ) population = ga.initialize_population() best_fitness_history = [] avg_fitness_history = [] for gen in range(generations): population = ga.evolve(population) fitness_values = np.array([fitness_function(ind) for ind in population]) best_fitness = np.max(fitness_values) avg_fitness = np.mean(fitness_values) best_fitness_history.append(best_fitness) avg_fitness_history.append(avg_fitness) if verbose and gen % 10 == 0: print(f"Generation {gen}: Best={-best_fitness:.4f}, " f"Avg={-avg_fitness:.4f}") best_idx = np.argmax([fitness_function(ind) for ind in population]) best_solution = population[best_idx] return best_solution, best_fitness_history, avg_fitness_history

2.2 可视化收敛过程

import matplotlib.pyplot as plt def plot_convergence(best_history, avg_history): """绘制适应度收敛曲线""" plt.figure(figsize=(10, 6)) plt.plot(-np.array(best_history), 'r-', label='Best Fitness') plt.plot(-np.array(avg_history), 'b--', label='Average Fitness') plt.xlabel('Generation') plt.ylabel('Function Value') plt.title('Convergence History') plt.legend() plt.grid(True) plt.show() # 执行优化并可视化 best_solution, best_hist, avg_hist = run_optimization(dimensions=5) plot_convergence(best_hist, avg_hist) print(f"Optimized solution: {best_solution}") print(f"Final value: {-best_hist[-1]:.6f}")

3. 梯度下降实现与对比

3.1 梯度下降基础实现

def gradient_descent(func: Callable, grad_func: Callable, initial_point: np.ndarray, learning_rate: float = 0.01, max_iter: int = 1000, tol: float = 1e-6) -> Tuple[np.ndarray, List[float]]: """标准梯度下降实现""" x = initial_point.copy() history = [func(x)] for _ in range(max_iter): grad = grad_func(x) x_new = x - learning_rate * grad if np.linalg.norm(x_new - x) < tol: break x = x_new history.append(func(x)) return x, history def rastrigin_gradient(x: np.ndarray) -> np.ndarray: """Rastrigin函数的梯度""" A = 10 return 2 * x + 2 * np.pi * A * np.sin(2 * np.pi * x)

3.2 多起点梯度下降

为公平比较，我们实现多起点梯度下降：

def multi_start_gradient_descent(func: Callable, grad_func: Callable, dimensions: int, num_starts: int = 20, max_iter: int = 500) -> Tuple[np.ndarray, float]: """多起点梯度下降""" best_x = None best_value = float('inf') history = [] for _ in range(num_starts): x0 = np.random.uniform(-5.12, 5.12, dimensions) x, hist = gradient_descent(func, grad_func, x0, learning_rate=0.01, max_iter=max_iter) history.extend(hist) current_value = func(x) if current_value < best_value: best_value = current_value best_x = x return best_x, best_value, history

4. 性能对比分析

4.1 定量对比实验

我们设计实验对比两种算法的表现：

def run_comparison(dimensions=2, trials=10): """运行对比实验""" ga_results = [] gd_results = [] for _ in range(trials): # 遗传算法 ga_solution, ga_history, _ = run_optimization( dimensions=dimensions, verbose=False) ga_results.append(rastrigin(ga_solution)) # 梯度下降 gd_solution, gd_value, _ = multi_start_gradient_descent( rastrigin, rastrigin_gradient, dimensions) gd_results.append(gd_value) return ga_results, gd_results # 运行对比实验 ga_vals, gd_vals = run_comparison(dimensions=5, trials=20) # 结果统计 print("Genetic Algorithm Results:") print(f" Best: {np.min(ga_vals):.4f}") print(f" Worst: {np.max(ga_vals):.4f}") print(f" Average: {np.mean(ga_vals):.4f}") print(f" Std Dev: {np.std(ga_vals):.4f}") print("\nGradient Descent Results:") print(f" Best: {np.min(gd_vals):.4f}") print(f" Worst: {np.max(gd_vals):.4f}") print(f" Average: {np.mean(gd_vals):.4f}") print(f" Std Dev: {np.std(gd_vals):.4f}")

4.2 结果可视化

def plot_comparison(ga_values, gd_values): """绘制对比箱线图""" plt.figure(figsize=(10, 6)) plt.boxplot([ga_values, gd_values], labels=['Genetic Algorithm', 'Gradient Descent']) plt.ylabel('Final Objective Value') plt.title('Performance Comparison (20 trials)') plt.grid(True) plt.show() plot_comparison(ga_vals, gd_vals)

典型实验结果可能显示：

指标	遗传算法	梯度下降
最优值	0.0012	3.4521
最差值	0.8563	18.724
平均值	0.1425	9.8732
标准差	0.2314	4.5621

5. 高级技巧与参数调优

5.1 关键参数影响分析

遗传算法性能受多个参数影响：

种群大小：
- 太小：多样性不足，易早熟
- 太大：计算成本高
- 推荐：20-100，复杂问题可更大
交叉率：
- 典型值：0.7-0.95
- 高值促进信息交换
- 低值减慢收敛
变异率：
- 典型值：0.001-0.05
- 高值增加多样性但破坏优良解
- 低值导致早熟收敛

5.2 自适应参数调整

实现自适应变异率：

def adaptive_mutation(self, individual: np.ndarray, generation: int, max_generations: int) -> np.ndarray: """自适应变异率""" base_rate = self.mutation_rate # 随着代数增加逐渐降低变异率 adaptive_rate = base_rate * (1 - generation/max_generations) mask = np.random.rand(self.chrom_len) < adaptive_rate noise = np.random.normal(0, 0.5, self.chrom_len) return np.where(mask, individual + noise, individual)

5.3 混合策略

结合两种算法优势：

def hybrid_optimization(dimensions, ga_generations=50, gd_iterations=100): """混合优化策略""" # 先用GA进行全局搜索 ga = GeneticAlgorithm(population_size=50, chromosome_length=dimensions, fitness_func=fitness_function) population = ga.initialize_population() for _ in range(ga_generations): population = ga.evolve(population) # 选择最佳个体进行梯度优化 best_idx = np.argmax([fitness_function(ind) for ind in population]) best_solution = population[best_idx] # 梯度下降局部优化 refined_solution, _ = gradient_descent( rastrigin, rastrigin_gradient, best_solution, max_iter=gd_iterations) return refined_solution

在实际项目中，遗传算法特别适合以下场景：