遗传算法的原理与实现示例

  遗传算法是一种受生物进化理论启发的随机优化算法，其核心思想是模拟自然界中 “物竞天择、适者生存” 的进化过程，通过对候选解的迭代优化，找到问题的最优解。
一、核心思想

  遗传算法将优化问题的候选解视为生物群体中的“个体”，每个个体的“基因”对应解的参数。通过模拟生物进化中的选择、交叉、变异等过程，让群体中 “适应性强”（即更接近最优解）的个体保留并繁衍，“适应性弱” 的个体被淘汰，最终使群体逐渐逼近最优解。
二、算法步骤

1. 编码：将问题解转化为“基因”形式

  首先需要将实际问题的候选解编码为计算机可处理的字符串（如二进制串、实数编码等），这个字符串称为 “染色体”，其中的每个元素（如二进制位）称为 “基因”。
  例如：若优化问题是求“x 在 [0,31] 范围内使函数 f (x)=x² 最大的解”，可将 x 用 5 位二进制编码（如 x=5 对应染色体“00101”）。
2. 初始化群体

  随机生成一定数量的染色体，组成初始 “群体”（个体数量称为 “种群规模”）。
  例如：随机生成 4 个 5 位二进制串，组成初始群体：00101、11011、01001、10010。
3. 适应度评估：衡量个体的 “优劣”

  定义“适应度函数”，计算每个个体的适应度值，值越高表示该个体（解）越优。
  例如：对上述问题，适应度函数可直接用 f (x)=x²，将染色体转为十进制后计算：
      00101（x=5）→ 适应度 = 25；
      11011（x=27）→ 适应度 = 729（最优）。
4. 遗传操作：模拟进化过程

  通过选择、交叉、变异，生成下一代群体：
  选择（Selection）：从当前群体中筛选出适应度高的个体，使其有更高概率繁衍后代（类似 “适者生存”）。
  常用方法：轮盘赌选择（适应度越高的个体，被选中的概率越大）。例如：适应度为 729 的个体被选中的概率远高于25的个体。
  交叉（Crossover）：将两个选中的个体（父代染色体）按一定概率（交叉概率）交换部分基因，生成新个体（子代染色体），增加群体多样性。
  例如：对父代11011和10010，随机选择交叉点（如第 3 位后），交换后半部分：
      父代 1：110 | 11 → 子代 1：11010；
      父代 2：100 | 10 → 子代 2：10011。
  变异（Mutation）：对子代染色体的基因按一定概率（变异概率）随机改变（如二进制位 0 变 1 或 1 变 0），避免群体陷入局部最优。
  例如：对子代11010的第 4 位进行变异（1→0），得到11000。
5. 终止条件

  重复步骤 3 和 4，直到满足终止条件（如迭代次数达到上限、最优个体的适应度不再提升等），最终输出适应度最高的个体作为最优解。
三、算法特点

  鲁棒性：对问题的数学性质要求低，可处理非线性、多峰等复杂问题。
  并行性：群体中的多个个体可同时优化，适合并行计算。
  随机性：通过随机操作探索解空间，但通过适应度评估引导优化方向，兼顾 “探索” 与 “利用”。
四、应用场景

  遗传算法广泛用于函数优化、机器学习（如神经网络参数优化）、组合优化（如旅行商问题、背包问题）、工程设计（如电路布局）等领域。
五、Python实现示例

  现寻找函数\(f(x)=-x^2+10\)在区间\([-10,10]\)内的最大值。理论上，当\(x=0\)时函数取得最大值 \(f(0)=10\)。运行该程序后，可以观察算法如何逐步逼近这个最优解。

1. import matplotlib
2. matplotlib.use('TkAgg')
4. import numpy as np
5. import matplotlib.pyplot as plt
8. # 目标函数：寻找 -x^2 + 10 的最大值
9. def objective_function(x):
10.     return -x ** 2 + 10
13. # 解码染色体为实际数值
14. def decode_chromosome(chromosome, min_val, max_val):
15.     """将二进制染色体解码为区间内的实数值"""
16.     binary_str = ''.join(map(str, chromosome))
17.     decimal = int(binary_str, 2)
18.     max_decimal = 2 ** len(chromosome) - 1
19.     return min_val + (max_val - min_val) * decimal / max_decimal
22. # 计算适应度（函数值越大适应度越高）
23. def calculate_fitness(population, min_val, max_val):
24.     fitness = []
25.     for chromosome in population:
26.         x = decode_chromosome(chromosome, min_val, max_val)
27.         fitness.append(objective_function(x))
28.     return fitness
31. # 选择操作（锦标赛选择）
32. def tournament_selection(population, fitness, tournament_size=3):
33.     selected = []
34.     for _ in range(len(population)):
35.         # 随机选择几个个体进行比较
36.         tournament_indices = np.random.choice(len(population), tournament_size)
37.         tournament_fitness = [fitness[i] for i in tournament_indices]
38.         # 选择适应度最高的个体
39.         winner_index = tournament_indices[np.argmax(tournament_fitness)]
40.         selected.append(population[winner_index])
41.     return selected
44. # 交叉操作（单点交叉）
45. def crossover(parents, crossover_rate=0.8):
46.     children = []
47.     for i in range(0, len(parents), 2):
48.         parent1 = parents[i]
49.         parent2 = parents[i + 1] if i + 1 < len(parents) else parents[0]
51.         # 以一定概率进行交叉
52.         if np.random.random() < crossover_rate:
53.             crossover_point = np.random.randint(1, len(parent1))
54.             child1 = parent1[:crossover_point] + parent2[crossover_point:]
55.             child2 = parent2[:crossover_point] + parent1[crossover_point:]
56.         else:
57.             child1, child2 = parent1.copy(), parent2.copy()
59.         children.extend([child1, child2])
61.     # 确保种群大小不变
62.     return children[:len(parents)]
65. # 变异操作
66. def mutate(population, mutation_rate=0.01):
67.     for chromosome in population:
68.         for i in range(len(chromosome)):
69.             if np.random.random() < mutation_rate:
70.                 chromosome[i] = 1 - chromosome[i]  # 翻转位
71.     return population
74. # 主函数
75. def genetic_algorithm(pop_size=100, chromosome_length=10, generations=100,
76.                       min_val=-10, max_val=10):
77.     # 初始化种群
78.     population = [np.random.randint(0, 2, chromosome_length).tolist() for _ in range(pop_size)]
80.     best_fitness_history = []
81.     best_solution = None
82.     best_x = None
84.     for generation in range(generations):
85.         # 计算适应度
86.         fitness = calculate_fitness(population, min_val, max_val)
88.         # 记录最佳解
89.         best_idx = np.argmax(fitness)
90.         best_fitness_history.append(fitness[best_idx])
92.         if best_solution is None or fitness[best_idx] > calculate_fitness([best_solution], min_val, max_val)[0]:
93.             best_solution = population[best_idx]
94.             best_x = decode_chromosome(best_solution, min_val, max_val)
96.         # 选择
97.         parents = tournament_selection(population, fitness)
99.         # 交叉
100.         children = crossover(parents)
102.         # 变异
103.         population = mutate(children)
105.         # 打印进度
106.         if generation % 10 == 0:
107.             print(f"Generation {generation}: Best fitness = {best_fitness_history[-1]:.4f}, Best x = {best_x:.4f}")
109.     # 绘制适应度进化曲线
110.     plt.figure(figsize=(10, 6))
111.     plt.plot(best_fitness_history)
112.     plt.title('Best Fitness Over Generations')
113.     plt.xlabel('Generation')
114.     plt.ylabel('Fitness')
115.     plt.grid(True)
116.     plt.savefig('figure/fitness_evolution.png')
118.     return best_solution, best_x, objective_function(best_x)
121. # 运行算法
122. best_chromosome, best_x, best_fitness = genetic_algorithm()
124. print("\n优化结果:")
125. print(f"最佳染色体: {best_chromosome}")
126. print(f"最优解 x = {best_x:.6f}")
127. print(f"最大值 f(x) = {best_fitness:.6f}")

复制代码

  示例通过模拟生物进化过程来寻找函数的最优解。流程包括：
    初始化种群：随机生成一组二进制编码的染色体
    评估适应度：计算每个染色体对应的函数值
    选择操作：使用锦标赛选择法选出较优个体
    交叉操作：对选中的个体进行基因重组
    变异操作：引入随机变异增加多样性
    迭代进化：重复上述过程直到满足终止条件

  通过模拟生物进化的“优胜劣汰”机制，遗传算法能在复杂解空间中高效搜索最优解，是启发式优化算法中的经典方法之一。


End.

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除