进化算法

有信息搜索和无信息搜索

进化算法实际是一种从较高层面上去指导优化思路的元启发式搜索算法。从这个层面出发，我们将搜索方式总体的分成无信息搜索（Uninformed Search）和有信息搜索（Informed Search）。

无信息搜索指的是算法在搜索的过程中不依赖额外的路径信息，诸如BFS和DFS，其在搜索的过程中并不关心具体的树结构是什么样的。
相对的有信息搜索算法就是会去感知总体或局部搜索地图的结构，或者递进式的基于前面计算的结果去进行最优解的搜索。

启发式搜索

启发式搜索（Heuristic Search）就是一种有信息搜索。并且启发式搜索经过发展和演变，分为以A-Star算法为例的基础启发式搜索和在指导思路上更加高度抽象的进化算法这类元启发式搜索（Meta-heuristic Search）。

进化算法

作为元启发式搜索思路的一种实现路径的进化算法指代的是一大类受生物进化启发的全局优化算法，遵循“种族、选择、变异、重组、适应度评价”的基本框架，包含有：

• 遗传算法（Genetic Algorith,GA）
• 进化策略（Evolutionary Strategies,ES）
• 进化规划（Evolutionary Programming,EP）
• 遗传编程（Genetic Programming,GP）
• 差分进化（Differential Evolution,DE）

我们将以一个简单的遗传算法为例，管中窥豹地浅探进化算法。

一个简单的遗传算法

我们先抽象的描述一个优化问题和我们的目标。现在，我们面对一个实际问题，我们的目标是尽可能找到这个问题的最优解。对此，我们首先假设拥有两个初始化的随机解x1和x2,这两个解即是进化搜索概念中的种群，以及评价解结果好坏的评价函数f(x)。

种群/编码

第一步，我们需要对种群进行编码，我们以两个长度为6的0/1数组作为例子。一般来讲，这种0/1数组是较为理想的编码结构，便于操作和理解，但是当然也有其他的编码形式。

进行编码后我们的种群有两个个体：

个体1: [0, 1, 1, 0, 1, 0]
个体2: [1, 0, 0, 1, 1, 1]

在遗传算法中，每个个体通常称为一个染色体（chromosome），而染色体上的每个位置称为一个基因（gene）。这里我们使用二进制编码，每个基因取值为0或1。

适应度函数

适应度函数（Fitness Function）用于评价每个个体的优劣。在我们的例子中，我们假设要最大化函数 f(x)，其中x是由二进制串解码得到的整数。解码方式是将二进制串转换为十进制整数。例如，对于个体1 [0,1,1,0,1,0]，其对应的整数为：

0*2^5 + 1*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 0 + 16 + 8 + 0 + 2 + 0 = 26

然后我们计算 f(26) 的值作为适应度。假设我们的目标函数是 f(x) = x^2（为了简单，这里使用一个简单的二次函数），那么个体1的适应度为 26^2 = 676。

类似地，个体2 [1,0,0,1,1,1] 对应整数：

1*2^5 + 0*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 1*2^0 = 32 + 0 + 0 + 4 + 2 + 1 = 39

适应度为 39^2 = 1521。

选择

选择（Selection）操作模拟自然选择，根据个体的适应度选择优秀的个体进入下一代。常用的选择方法有轮盘赌选择（Roulette Wheel Selection）、锦标赛选择（Tournament Selection）等。

轮盘赌选择：每个个体被选中的概率与其适应度成正比。首先计算所有个体的适应度总和，然后计算每个个体的选择概率（个体适应度/适应度总和），最后根据概率进行选择。

在我们的例子中，总适应度为 676 + 1521 = 2197。个体1的选择概率为 676/2197 ≈ 0.307，个体2的选择概率为 1521/2197 ≈ 0.693。然后我们可以通过随机数生成来选择个体，例如生成一个[0,1)之间的随机数，如果随机数小于0.307则选择个体1，否则选择个体2。通常选择操作会进行多次，直到选中足够数量的个体（与种群大小相同，这里我们假设种群大小保持为2）

交叉

交叉（Crossover）操作模拟基因重组，将两个父代个体的部分基因交换，产生新的子代个体。常用的交叉方法有单点交叉（Single-point Crossover）、多点交叉（Multi-point Crossover）和均匀交叉（Uniform Crossover）等。

我们以单点交叉为例：随机选择一个交叉点（假设为3），然后将两个父代个体在交叉点之后的部分进行交换。

假设我们选择了个体1和个体2作为父代，交叉点为3：

父代1: [0, 1, 1, 0, 1, 0]
父代2: [1, 0, 0, 1, 1, 1]

交叉后产生两个子代：

子代1: [0, 1, 1, 1, 1, 1] （父代1的前3个基因 + 父代2的后3个基因）
子代2: [1, 0, 0, 0, 1, 0] （父代2的前3个基因 + 父代1的后3个基因）

变异

变异（Mutation）操作模拟基因突变，以一定的概率（变异率）改变个体中的某个或某些基因的值。对于二进制编码，变异就是翻转基因（0变1，1变0）。

假设变异率为0.1（即每个基因有10%的概率发生变异）。我们对子代1进行变异，假设随机选择到第5个基因发生变异：

子代1变异前: [0, 1, 1, 1, 1, 1]
子代1变异后: [0, 1, 1, 1, 0, 1]（第5个基因从1变为0）

同样，子代2可能也会发生变异，假设没有基因被选中，则保持不变。

新一代种群

经过选择、交叉、变异后，我们得到了新的个体。通常，我们会用新个体替换原来的种群，或者保留一部分优秀个体（精英保留策略）。这里我们简单地将新个体作为新一代种群：

新一代种群：
个体1: [0, 1, 1, 1, 0, 1] （变异后的子代1）
个体2: [1, 0, 0, 0, 1, 0] （未变异的子代2）

迭代

重复上述过程（适应度评价、选择、交叉、变异）多代，直到满足终止条件（如达到最大迭代次数、适应度达到阈值或适应度不再明显改善）。

示例代码

然后我们给出一个简单的遗传算法代码，求解函数 f(x) = x^2 在区间 [0, 63] 上的最大值（x为整数）。我们使用6位二进制编码，种群大小为4，迭代50代，使用轮盘赌选择、单点交叉和基本位变异。

import random

# 目标函数
def fitness_function(x):
    return x ** 2

# 生成初始种群
def generate_population(pop_size, chromosome_length):
    population = []
    for _ in range(pop_size):
        chromosome = [random.randint(0, 1) for _ in range(chromosome_length)]
        population.append(chromosome)
    return population

# 解码染色体为整数
def decode_chromosome(chromosome):
    value = 0
    for i, gene in enumerate(chromosome):
        value += gene * (2 ** (len(chromosome) - 1 - i))
    return value

# 计算适应度
def calculate_fitness(population):
    fitness_values = []
    for chromosome in population:
        x = decode_chromosome(chromosome)
        fitness_values.append(fitness_function(x))
    return fitness_values

# 轮盘赌选择
def roulette_wheel_selection(population, fitness_values):
    total_fitness = sum(fitness_values)
    pick = random.uniform(0, total_fitness)
    current = 0
    for i, chromosome in enumerate(population):
        current += fitness_values[i]
        if current > pick:
            return chromosome
    # 如果由于浮点数误差没有选中，返回最后一个
    return population[-1]

# 单点交叉
def single_point_crossover(parent1, parent2, crossover_rate):
    if random.random() < crossover_rate:
        point = random.randint(1, len(parent1) - 1)
        child1 = parent1[:point] + parent2[point:]
        child2 = parent2[:point] + parent1[point:]
        return child1, child2
    else:
        return parent1, parent2

# 基本位变异
def bit_flip_mutation(chromosome, mutation_rate):
    mutated_chromosome = []
    for gene in chromosome:
        if random.random() < mutation_rate:
            mutated_chromosome.append(1 - gene)  # 翻转
        else:
            mutated_chromosome.append(gene)
    return mutated_chromosome

# 主函数
def genetic_algorithm(pop_size, chromosome_length, max_generation, crossover_rate, mutation_rate):
    # 初始化种群
    population = generate_population(pop_size, chromosome_length)
    
    for generation in range(max_generation):
        # 计算适应度
        fitness_values = calculate_fitness(population)
        
        # 找到当前最优个体
        best_index = fitness_values.index(max(fitness_values))
        best_chromosome = population[best_index]
        best_x = decode_chromosome(best_chromosome)
        best_fitness = fitness_values[best_index]
        
        print(f"Generation {generation}: Best x = {best_x}, Best fitness = {best_fitness}")
        
        # 如果找到理论最大值（63^2=3969），提前结束
        if best_fitness == 3969:
            print("Found optimal solution!")
            break
        
        # 选择、交叉、变异产生新一代种群
        new_population = []
        for _ in range(pop_size // 2):
            # 选择两个父代
            parent1 = roulette_wheel_selection(population, fitness_values)
            parent2 = roulette_wheel_selection(population, fitness_values)
            
            # 交叉
            child1, child2 = single_point_crossover(parent1, parent2, crossover_rate)
            
            # 变异
            child1 = bit_flip_mutation(child1, mutation_rate)
            child2 = bit_flip_mutation(child2, mutation_rate)
            
            new_population.append(child1)
            new_population.append(child2)
        
        # 如果种群大小是奇数，确保新种群大小与原种群相同
        if len(new_population) < pop_size:
            new_population.append(roulette_wheel_selection(population, fitness_values))
        
        population = new_population
    
    # 最终结果
    final_fitness = calculate_fitness(population)
    best_index = final_fitness.index(max(final_fitness))
    best_chromosome = population[best_index]
    best_x = decode_chromosome(best_chromosome)
    best_fitness = final_fitness[best_index]
    
    return best_x, best_fitness

# 参数设置
pop_size = 4
chromosome_length = 6  # 2^6 = 64，可以表示0-63
max_generation = 50
crossover_rate = 0.8
mutation_rate = 0.1

# 运行遗传算法
best_x, best_fitness = genetic_algorithm(pop_size, chromosome_length, max_generation, crossover_rate, mutation_rate)
print(f"\nFinal result: x = {best_x}, f(x) = {best_fitness}")

总结

通过这个简单的遗传算法示例，我们可以看到进化算法的基本流程：编码、初始化、适应度评价、选择、交叉、变异和迭代。遗传算法作为一种典型的进化算法，具有很强的全局搜索能力，适用于各种优化问题，特别是那些解空间大、非线性、多峰的问题。

需要注意的是，遗传算法的性能受到许多参数的影响，如种群大小、交叉率、变异率等。在实际应用中，需要根据具体问题进行调整。此外，遗传算法还有其他变种，如精英保留、自适应参数调整等，以进一步提高性能。

• 本文作者： Kylin
• 本文链接： https://kylinnnnn.github.io/2026/02/15/进化算法/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！