当前位置：首页 > news >正文

遗传算法（GA）

news 来源：原创 2025/8/5 7:54:26

基本原理

算法介绍

遗传算法（Genetic Algorithm，简称GA）是一种基于自然选择和遗传学原理的搜索和优化技术。它模拟了生物进化过程，通过选择、交叉（重组）和变异等操作，逐步优化问题的解。

遗传算法可以类比为选择性的枚举——更科学的说，遗传算法是一种启发式的仿生算法，其中，仿生指的是模仿自然规律或生物行为；启发式指的是基于一定经验和规则的算法，在遗传算法当中，就应用了“物竞天择”这一法则。

基因编码

在GA当中，所有的解都要理解为基因编码，因此，基因编码的方式尤为重要，常见的编码方式有：二进制编码，实数编码（用于解决连续优化问题）列编码（用于解决排序问题）

基本步骤

1.初始化

种群初始化：随机生成一组初始解，称为种群（Population）。每个解称为个体（Individual），通常用二进制编码或其他合适的编码方式表示。

适应度评估：计算每个个体的适应度（Fitness），适应度函数根据问题的目标来评估个体的优劣。适应度高的个体更有可能被选中进入下一代。

2.选择

选择操作是指选择合适的种群进入下一代，常见的选择方法如下：

轮盘赌选择（Roulette Wheel Selection）

根据个体适应度占总适应度的比例来选择个体。适应度高的个体被选中的概率更大

锦标赛选择（Tournament Selection）

随机选择若干个个体，比较它们的适应度，选择适应度最高的个体进入下一代。

排名选择（Rank Selection）

根据个体的适应度排名来选择个体，排名高的个体被选中的概率更大。

3.交叉

交叉是指将两个父代个体的部分基因片段进行交换来产生新的子代个体。

常见的交换算法如下：

单点交叉（Single-point Crossover）：

随机选择一个交叉点，将两个父代个体在该点处的基因片段进行交换。

多点交叉（Multi-point Crossover）：

选择多个交叉点，将基因片段进行交换。

均匀交叉（Uniform Crossover）：

每个基因位都有一定的概率从另一个父代个体中继承。

4.变异

变异操作是对个体的基因进行随机改变，以一定的概率改变个体的某些基因。变异操作虽然概率较低，但能够防止算法陷入局部最优解，增加种群的多样性。常见的变异方法包括：

位变异（Bit-flip Mutation）

对于二进制编码的个体，随机选择一个或多个基因位，将其值取反。

均匀变异（Uniform Mutation）

随机选择一个基因位，将其值替换为随机生成的新值。

5.适应度评估与替换

1.适应度评估

对新生成的子代个体进行适应度评估。

2.替换

根据一定的策略用子代个体替换种群中的一些个体，形成新一代种群。

常见的替换策略如下：

完全替换：用所有子代个体替换种群中的所有个体。

部分替换：用部分子代个体替换种群中适应度较低的个体。

精英保留：保留种群中适应度最高的若干个个体，直接进入下一代，以防止最优解丢失。

6.迭代

重复上述选择、交叉、变异和适应度评估的过程，直到满足终止条件（终止条件可以是达到一定的适应度，迭代次数，或者物种多样性降低到一定程度等等）。

应用

假设我们要用遗传算法解决一个简单的优化问题：最大化函数 f(x) = x^2，其中 x \in [0, 31]。
（1）初始化种群大小：10编码方式：二进制编码，5位二进制数可以表示0到31的整数。初始种群：随机生成10个5位二进制数，如 [01010, 11001, 00110, 10101, 11110, 01101, 10010, 00011, 11010, 01111] 。

# 1. 初始化种群
def initialize_population(pop_size, chrom_length):population = []for _ in range(pop_size):individual = ''.join(random.choice('01') for _ in range(chrom_length))population.append(individual)return population

（2）适应度评估计算每个个体的适应度，即 f(x) = x^2。例如，个体 01010 表示十进制的10，其适应度为 10^2 = 100。

# 2. 适应度评估
def evaluate_fitness(population):fitness = []for individual in population:x = int(individual, 2)fitness.append(x ** 2)return fitness

（3）选择使用轮盘赌选择法，根据适应度比例选择个体进入下一代。

# 3. 轮盘赌选择
def roulette_wheel_selection(population, fitnesses):total_fitness = sum(fitnesses)pick = random.uniform(0, total_fitness)current = 0for i in range(len(population)):current += fitnesses[i]if current > pick:return population[i]return population[-1]  # 防止浮点误差

（4）交叉随机选择两个父代个体进行单点交叉。例如，选择 01010 和 11001 ，交叉点为第3位，交叉后生成子代 01001 和 11010 。

# 4. 交叉操作
def crossover(parent1, parent2, crossover_rate):if random.random() < crossover_rate:crossover_point = random.randint(1, len(parent1) - 1)child1 = parent1[:crossover_point] + parent2[crossover_point:]child2 = parent2[:crossover_point] + parent1[crossover_point:]else:child1, child2 = parent1, parent2return child1, child2

（5）变异对子代个体进行变异操作。例如，选择 01001 ，随机变异第2位，变为 00001 。

# 5. 变异操作
def mutate(child, mutation_rate):mutated = list(child)for i in range(len(mutated)):if random.random() < mutation_rate:mutated[i] = '1' if mutated[i] == '0' else '0'return ''.join(mutated)

（6）替换用新生成的子代个体替换种群中的一些个体，形成新一代种群。
（7）迭代重复上述过程，直到满足终止条件（如达到最大迭代次数100）。通过上述步骤，遗传算法能够逐步优化解，最终找到接近最优解的个体。

# 主函数流程
def genetic_algorithm():pop_size = 10    #种群规模chrom_length = 5  #染色体长度max_generations = 100 #迭代次数crossover_rate = 0.8  # 交叉概率mutation_rate = 0.1   # 变异概率# 初始化种群population = initialize_population(pop_size, chrom_length)print("初始种群:", population)for gen in range(max_generations):# 计算适应度fitnesses = evaluate_fitness(population)# 生成新一代new_population = []while len(new_population) < pop_size:# 选择父代parent1 = roulette_wheel_selection(population, fitnesses)parent2 = roulette_wheel_selection(population, fitnesses)# 交叉生成子代child1, child2 = crossover(parent1, parent2, crossover_rate)# 变异操作child1 = mutate(child1, mutation_rate)child2 = mutate(child2, mutation_rate)new_population.extend([child1, child2])# 确保种群大小不变（截断多余个体）population = new_population[:pop_size]# 打印当前最优解current_fitness = evaluate_fitness(population)best_fitness = max(current_fitness)best_index = current_fitness.index(best_fitness)print(f"Generation {gen+1}: Best = {population[best_index]} (x={int(population[best_index], 2)}, f(x)={best_fitness})")# 最终结果final_fitness = evaluate_fitness(population)best_idx = final_fitness.index(max(final_fitness))best_individual = population[best_idx]print("\n最优解:")print(f"个体: {best_individual}, x = {int(best_individual, 2)}, f(x) = {int(best_individual, 2)**2}")# 运行算法
genetic_algorithm()

评价

GA算法有较强的全局搜索能力和并行能力，能较好的找到优秀解，但也存在着局部最优解，参数选择困难，计算量大等问题

例如在上例中，我们将种群数量设置为10，而得出的结果有很大的可能性是30，因为30和31的适应度相差不多，因此在发生配对时，末尾的1很有可能因为局部最优解的问题而被0取代

假如我们把种群规模更改为100的确很好的扩充的基因库，也让我们的结果更加准确了，但毫无疑问，在复杂的现实应用当中，这对于算力是一个极大的挑战，有时候，尽可能优秀的结果会比完美的结果更加适用