070. 编写一个函数，实现简单的遗传算法

遗传算法（Genetic Algorithm, GA）是一种基于自然选择和遗传学原理的搜索和优化技术。它通过模拟生物进化过程来解决优化问题。以一个简单的优化问题为例：最大化一个函数 f(x) 的值。

示例

假设我们要最大化函数 f(x)=x2，其中 x 是一个整数，范围在 [−10,10] 之间。

遗传算法的基本步骤

初始化种群：随机生成一组解（个体）。
适应度评估：计算每个个体的适应度（目标函数值）。
选择：根据适应度选择个体进行繁殖。
交叉（Crossover）：将两个个体的部分基因组合生成新的个体。
变异（Mutation）：随机改变个体的某些基因。
迭代：重复上述步骤，直到满足终止条件（如达到最大迭代次数或适应度不再显著提高）。

代码

import random

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

# 初始化种群
def initialize_population(pop_size, gene_length):
    population = []
    for _ in range(pop_size):
        individual = [random.randint(-10, 10) for _ in range(gene_length)]
        population.append(individual)
    return population

# 适应度评估
def evaluate_population(population):
    fitness_scores = []
    for individual in population:
        fitness = sum(fitness_function(gene) for gene in individual)
        fitness_scores.append(fitness)
    return fitness_scores

# 选择操作（轮盘赌选择）
def selection(population, fitness_scores):
    total_fitness = sum(fitness_scores)
    probabilities = [score / total_fitness for score in fitness_scores]
    selected_indices = random.choices(range(len(population)), weights=probabilities, k=len(population))
    return [population[i] for i in selected_indices]

# 交叉操作（单点交叉）
def crossover(parent1, parent2):
    crossover_point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:crossover_point] + parent2[crossover_point:]
    child2 = parent2[:crossover_point] + parent1[crossover_point:]
    return child1, child2

# 变异操作
def mutate(individual, mutation_rate):
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            individual[i] = random.randint(-10, 10)
    return individual

# 遗传算法主函数
def genetic_algorithm(pop_size, gene_length, generations, mutation_rate):
    # 初始化种群
    population = initialize_population(pop_size, gene_length)

    for generation in range(generations):
        # 适应度评估
        fitness_scores = evaluate_population(population)

        # 选择
        selected_population = selection(population, fitness_scores)

        # 交叉
        new_population = []
        for i in range(0, len(selected_population), 2):
            parent1 = selected_population[i]
            parent2 = selected_population[i + 1]
            child1, child2 = crossover(parent1, parent2)
            new_population.extend([child1, child2])

        # 变异
        for individual in new_population:
            mutate(individual, mutation_rate)

        population = new_population

        # 打印当前代的平均适应度
        avg_fitness = sum(fitness_scores) / len(fitness_scores)
        print(f"Generation {generation + 1}: Average Fitness = {avg_fitness:.2f}")

    # 最终结果
    best_individual = population[fitness_scores.index(max(fitness_scores))]
    best_fitness = max(fitness_scores)
    return best_individual, best_fitness

# 示例用法
if __name__ == "__main__":
    pop_size = 50  # 种群大小
    gene_length = 5  # 每个个体的基因长度
    generations = 100  # 迭代次数
    mutation_rate = 0.01  # 变异率

    best_individual, best_fitness = genetic_algorithm(pop_size, gene_length, generations, mutation_rate)
    print(f"Best Individual: {best_individual}")
    print(f"Best Fitness: {best_fitness}")

代码说明

目标函数：定义了一个简单的目标函数 f(x)=x2。
初始化种群：随机生成一组解，每个解是一个长度为 gene_length 的列表，每个基因是一个整数，范围在 [−10,10] 之间。
适应度评估：计算每个个体的适应度，适应度是每个基因的目标函数值之和。
选择操作：使用轮盘赌选择法，根据适应度选择个体进行繁殖。
交叉操作：使用单点交叉法，将两个父代个体的部分基因组合生成两个子代个体。
变异操作：随机改变个体的某些基因，变异率由 mutation_rate 控制。
迭代：重复选择、交叉和变异操作，直到达到指定的迭代次数。

示例输出

Generation 1: Average Fitness = 150.20
Generation 2: Average Fitness = 160.45
...
Generation 100: Average Fitness = 245.67
Best Individual: [10, 10, 10, 10, 10]
Best Fitness: 500

注意事项

参数调整：种群大小、基因长度、迭代次数和变异率等参数对算法性能有重要影响，需要根据具体问题进行调整。
编码方式：本示例中使用了整数编码，对于不同的问题，可能需要使用其他编码方式（如二进制编码、浮点数编码等）。
终止条件：除了达到最大迭代次数外，还可以设置其他终止条件，例如适应度不再显著提高。
多样性保持：在某些情况下，种群可能会过早收敛，导致多样性丧失。可以通过引入多样性保持机制（如精英保留、模拟退火等）来解决这一问题。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)