遗传算法（Genetic Algorithm, GA）是一种用于优化问题的搜索算法，灵感来源于自然选择和遗传学。它通过模拟生物进化过程中的遗传、变异、交叉和选择来优化问题，特别适合解决复杂的全局优化问题。
遗传算法的基本步骤：
1、初始化种群：
生成若干随机的解作为初始种群。
2、评估适应度：
计算每个个体的适应度（fitness），适应度反映了个体解问题的好坏。
3、选择（Selection）：
根据适应度值选择个体，适应度高的个体更有机会被选中。
4、交叉（Crossover）：
对选择的个体进行基因交换，生成新的个体（子代）。
5、变异（Mutation）：
以一定的概率对个体的基因进行随机变异，增加种群的多样性。
6、更新种群：
选择适应度更高的个体替换掉适应度低的个体，形成新的种群。
7、停止条件：
重复上述步骤，直到达到停止条件（如达到最大迭代次数或找到满意的解）。
公式：
1、适应度函数：
适应度函数用于衡量个体解的优劣。
2、选择概率：
常用的选择方法是轮盘赌选择法，其公式为：
其中 ( P_i ) 表示个体 ( i ) 被选中的概率，( F(x_i) ) 是个体 ( i ) 的适应度值，( n ) 是种群的大小。
3、交叉操作：
假设两个父代个体
和
，在交叉点 ( k ) 处进行交叉，则生成的子代为：
假设个体
在位置 ( k ) 处进行变异，生成新的个体：
1、编码（Encoding）：
编码是将解表示成遗传算法能够处理的形式，常见的编码方式有二进制编码、实数编码和排列编码。
二进制编码：
最常见的一种编码方式，适用于离散问题。每个个体由一个固定长度的二进制串表示。
实数编码：
个体由实数向量表示，适用于连续优化问题。
排列编码：
用于组合优化问题，如旅行商问题，个体为一系列有序排列。
2、选择策略：
轮盘赌选择：
根据适应度分配选择概率，适应度高的个体被选中的概率较大。
锦标赛选择：
随机选择若干个体进行竞争，选择最好的个体进入下一代。
精英保留策略：
将当前种群中最优个体直接保留到下一代，保证优秀基因不丢失。
3、交叉操作：
单点交叉：
在个体之间随机选择一个交叉点，进行基因交换。
多点交叉：
在多个位置进行基因交换，增加多样性。
均匀交叉：
随机选择父母个体的各个基因位置进行交叉，不局限于某几个点。
4、变异操作：
位变异：
对个体的某个位进行翻转（0变1，1变0）。
交换变异：
随机选择两个基因位置进行交换。
反转变异：
将个体基因的一段进行反转操作。
5、适应度缩放：
当种群中个体的适应度差异过大时，可能导致劣质个体几乎没有机会被选中。可以对适应度进行缩放（如平方根、对数等），以平滑适应度分布。
1、多目标遗传算法（MOGA）：
对于多目标优化问题，可以通过引入Pareto最优解集来处理多个目标函数。例如NSGA-II算法通过排序和拥挤距离来解决多目标优化问题。
2、差分进化（DE）：
差分进化是一种基于遗传算法的改进算法，尤其适合连续空间的全局优化问题。通过向个体添加差分向量来引导个体进化。
3、粒子群优化（PSO）与遗传算法结合：
粒子群优化算法模拟鸟群觅食的行为，通过速度和位置更新个体。PSO与GA结合可以提升全局搜索能力
我们通过一个简单的例子来演示如何使用遗传算法来求解一个优化问题，例如求解一个最大化函数 ( f(x) = x^2 )，其中 ( x \in [0, 31] )。
import random
# 定义适应度函数def fitness(individual): return individual ** 2
# 初始化种群def initialize_population(pop_size, gene_length): return [random.randint(0, 2 ** gene_length - 1) for _ in range(pop_size)]
# 选择操作 (轮盘赌)def selection(population, fitness_values): total_fitness = sum(fitness_values) selection_probs = [f / total_fitness for f in fitness_values] return random.choices(population, weights=selection_probs, k=len(population))
# 交叉操作def crossover(parent1, parent2, crossover_rate=0.7): if random.random() < crossover_rate: point = random.randint(1, len(bin(parent1)) - 2) # 随机选择交叉点 mask = (1 << point) - 1 return (parent1 & mask) | (parent2 & ~mask), (parent2 & mask) | (parent1 & ~mask) return parent1, parent2
# 变异操作def mutate(individual, mutation_rate=0.01, gene_length=5): if random.random() < mutation_rate: mutation_point = random.randint(0, gene_length - 1) individual ^= (1 << mutation_point) # 进行位变异 return individual
# 遗传算法def genetic_algorithm(pop_size, gene_length, generations): population = initialize_population(pop_size, gene_length) for generation in range(generations): fitness_values = [fitness(individual) for individual in population] # 选择下一代种群 population = selection(population, fitness_values) # 交叉操作 next_population = []
