遗传算法（Genetic Algorithm, GA）

简介

遗传算法（Genetic Algorithm, GA）是一种基于自然选择和遗传机制的优化算法，由 John Holland 于20世纪70年代提出。它是一种模拟生物进化过程的启发式搜索算法，被广泛应用于函数优化、机器学习、调度问题等领域。

代码说明

参数定义：
设置种群大小、基因长度、最大代数、交叉概率、变异概率等参数。
适应度函数：
目标函数为 f(x)=x^2 ，即计算个体的适应度值。
初始化种群：
随机生成一个种群，每个个体用 5 位二进制编码，表示范围[0,31]的整数。
选择操作（selection）：
使用轮盘赌选择方法，根据适应度值的比例概率挑选个体。
交叉操作（crossover）：
使用单点交叉，将两个父代基因部分交换生成子代。
变异操作（mutate）：
以一定概率随机翻转个体的某个位，模拟基因突变。
主循环：
每一代执行以下操作：
计算每个个体的适应度值。
记录本代中适应度最高的个体。
执行选择、交叉和变异操作生成下一代种群。
重复直到达到指定代数。
结果输出与可视化：
打印每代的最佳适应度及个体。
绘制代数与最佳适应度的变化趋势图。

代码

import random
import matplotlib.pyplot as plt# 遗传算法参数
POPULATION_SIZE = 10  # 种群大小
GENE_LENGTH = 5       # 基因长度
GENERATIONS = 20      # 最大代数
CROSSOVER_RATE = 0.8  # 交叉概率
MUTATION_RATE = 0.1   # 变异概率# 适应度函数
def fitness_function(x):return x ** 2# 初始化种群（随机生成二进制字符串）
def initialize_population():return [random.randint(0, 2**GENE_LENGTH - 1) for _ in range(POPULATION_SIZE)]# 个体解码（二进制 -> 十进制）
def decode(individual):return individual# 选择操作（轮盘赌选择）
def selection(population, fitness_values):total_fitness = sum(fitness_values)probabilities = [f / total_fitness for f in fitness_values]cumulative_probs = [sum(probabilities[:i+1]) for i in range(len(probabilities))]selected = []for _ in range(POPULATION_SIZE):r = random.random()for i, cumulative_prob in enumerate(cumulative_probs):if r <= cumulative_prob:selected.append(population[i])breakreturn selected# 交叉操作
def crossover(parent1, parent2):if random.random() < CROSSOVER_RATE:point = random.randint(1, GENE_LENGTH - 1)mask = (1 << point) - 1child1 = (parent1 & mask) | (parent2 & ~mask)child2 = (parent2 & mask) | (parent1 & ~mask)return child1, child2return parent1, parent2# 变异操作
def mutate(individual):for i in range(GENE_LENGTH):if random.random() < MUTATION_RATE:individual ^= (1 << i)  # 翻转某个位return individual# 遗传算法主程序
def genetic_algorithm():# 初始化种群population = initialize_population()best_fitness_history = []  # 每一代的最佳适应度记录for generation in range(GENERATIONS):# 计算适应度fitness_values = [fitness_function(decode(ind)) for ind in population]best_fitness = max(fitness_values)best_fitness_history.append(best_fitness)  # 记录当前代的最佳适应度# 打印每代的最佳结果best_individual = population[fitness_values.index(best_fitness)]print(f"Generation {generation + 1}: Best fitness = {best_fitness}, Best individual = {best_individual} (Decoded: {decode(best_individual)})")# 选择操作selected_population = selection(population, fitness_values)# 交叉操作next_generation = []for i in range(0, POPULATION_SIZE, 2):parent1 = selected_population[i]parent2 = selected_population[(i + 1) % POPULATION_SIZE]child1, child2 = crossover(parent1, parent2)next_generation.extend([child1, child2])# 变异操作population = [mutate(ind) for ind in next_generation]# 返回结果和适应度历史final_fitness_values = [fitness_function(decode(ind)) for ind in population]best_individual = population[final_fitness_values.index(max(final_fitness_values))]return best_individual, max(final_fitness_values), best_fitness_history# 运行遗传算法
best_individual, best_fitness, fitness_history = genetic_algorithm()# 打印最优结果
print(f"Optimal solution: {best_individual} (Decoded: {decode(best_individual)}), Fitness: {best_fitness}")# 绘制统计图
plt.figure(figsize=(10, 6))
plt.plot(range(1, GENERATIONS + 1), fitness_history, marker='o', linestyle='-', color='b', label='Best Fitness')
plt.title("Genetic Algorithm Convergence", fontsize=14)
plt.xlabel("Generation", fontsize=12)
plt.ylabel("Fitness Value", fontsize=12)
plt.grid(True)
plt.legend()
plt.show()