遗传算法的原理与实现示例
遗传算法是一种受生物进化理论启发的随机优化算法，其核心思想是模拟自然界中 “物竞天择、适者生存” 的进化过程，通过对候选解的迭代优化，找到问题的最优解。一、核心思想
遗传算法将优化问题的候选解视为生物群体中的“个体”，每个个体的“基因”对应解的参数。通过模拟生物进化中的选择、交叉、变异等过程，让群体中 “适应性强”（即更接近最优解）的个体保留并繁衍，“适应性弱” 的个体被淘汰，最终使群体逐渐逼近最优解。
二、算法步骤
1. 编码：将问题解转化为“基因”形式
首先需要将实际问题的候选解编码为计算机可处理的字符串（如二进制串、实数编码等），这个字符串称为 “染色体”，其中的每个元素（如二进制位）称为 “基因”。
例如：若优化问题是求“x 在 范围内使函数 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\)。运行该程序后，可以观察算法如何逐步逼近这个最优解。
import matplotlib
matplotlib.use('TkAgg')
import numpy as np
import matplotlib.pyplot as plt
# 目标函数：寻找 -x^2 + 10 的最大值
def objective_function(x):
return -x ** 2 + 10
# 解码染色体为实际数值
def decode_chromosome(chromosome, min_val, max_val):
"""将二进制染色体解码为区间内的实数值"""
binary_str = ''.join(map(str, chromosome))
decimal = int(binary_str, 2)
max_decimal = 2 ** len(chromosome) - 1
return min_val + (max_val - min_val) * decimal / max_decimal
# 计算适应度（函数值越大适应度越高）
def calculate_fitness(population, min_val, max_val):
fitness = []
for chromosome in population:
x = decode_chromosome(chromosome, min_val, max_val)
fitness.append(objective_function(x))
return fitness
# 选择操作（锦标赛选择）
def tournament_selection(population, fitness, tournament_size=3):
selected = []
for _ in range(len(population)):
# 随机选择几个个体进行比较
tournament_indices = np.random.choice(len(population), tournament_size)
tournament_fitness = for i in tournament_indices]
# 选择适应度最高的个体
winner_index = tournament_indices
selected.append(population)
return selected
# 交叉操作（单点交叉）
def crossover(parents, crossover_rate=0.8):
children = []
for i in range(0, len(parents), 2):
parent1 = parents
parent2 = parents if i + 1 < len(parents) else parents
# 以一定概率进行交叉
if np.random.random() < crossover_rate:
crossover_point = np.random.randint(1, len(parent1))
child1 = parent1[:crossover_point] + parent2
child2 = parent2[:crossover_point] + parent1
else:
child1, child2 = parent1.copy(), parent2.copy()
children.extend()
# 确保种群大小不变
return children[:len(parents)]
# 变异操作
def mutate(population, mutation_rate=0.01):
for chromosome in population:
for i in range(len(chromosome)):
if np.random.random() < mutation_rate:
chromosome = 1 - chromosome# 翻转位
return population
# 主函数
def genetic_algorithm(pop_size=100, chromosome_length=10, generations=100,
min_val=-10, max_val=10):
# 初始化种群
population =
best_fitness_history = []
best_solution = None
best_x = None
for generation in range(generations):
# 计算适应度
fitness = calculate_fitness(population, min_val, max_val)
# 记录最佳解
best_idx = np.argmax(fitness)
best_fitness_history.append(fitness)
if best_solution is None or fitness > calculate_fitness(, min_val, max_val):
best_solution = population
best_x = decode_chromosome(best_solution, min_val, max_val)
# 选择
parents = tournament_selection(population, fitness)
# 交叉
children = crossover(parents)
# 变异
population = mutate(children)
# 打印进度
if generation % 10 == 0:
print(f"Generation {generation}: Best fitness = {best_fitness_history[-1]:.4f}, Best x = {best_x:.4f}")
# 绘制适应度进化曲线
plt.figure(figsize=(10, 6))
plt.plot(best_fitness_history)
plt.title('Best Fitness Over Generations')
plt.xlabel('Generation')
plt.ylabel('Fitness')
plt.grid(True)
plt.savefig('figure/fitness_evolution.png')
return best_solution, best_x, objective_function(best_x)
# 运行算法
best_chromosome, best_x, best_fitness = genetic_algorithm()
print("\n优化结果:")
print(f"最佳染色体: {best_chromosome}")
print(f"最优解 x = {best_x:.6f}")
print(f"最大值 f(x) = {best_fitness:.6f}")
示例通过模拟生物进化过程来寻找函数的最优解。流程包括：
初始化种群：随机生成一组二进制编码的染色体
评估适应度：计算每个染色体对应的函数值
选择操作：使用锦标赛选择法选出较优个体
交叉操作：对选中的个体进行基因重组
变异操作：引入随机变异增加多样性
迭代进化：重复上述过程直到满足终止条件
通过模拟生物进化的“优胜劣汰”机制，遗传算法能在复杂解空间中高效搜索最优解，是启发式优化算法中的经典方法之一。
End.
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
页:
[1]