[Python] 遗传算法的一个示例

夜歌乘年少 / 2024-09-13 / 原文

通过精英保留策略简单解决基因退化的问题。

import random

# 遗传算法参数
POP_SIZE = 10  # 种群大小
CHROM_LENGTH = 10  # 染色体长度（表示0-1023）
CROSS_RATE = 0.7  # 交叉率
MUTATION_RATE = 0.01  # 变异率
GENERATIONS = 50  # 迭代次数
ELITE_RATE = 1  # 精英个体保留数


# 适应度函数：目标是最大化 f(x) = x^2
def fitness(x):
    return x ** 2


# 将二进制编码的染色体解码为整数
def decode(chrom):
    return int(chrom, 2)


# 初始化种群
def init_population():
    population = []
    for _ in range(POP_SIZE):
        chrom = ''.join(random.choice('01') for _ in range(CHROM_LENGTH))
        population.append(chrom)
    return population


# 选择操作：轮盘赌选择
def select(population):
    weights = [fitness(decode(chrom)) for chrom in population]
    total_fitness = sum(weights)
    selection_probs = [w / total_fitness for w in weights]
    return random.choices(population, weights=selection_probs, k=POP_SIZE)


# 交叉操作
def crossover(parent1, parent2):
    if random.random() < CROSS_RATE:
        point = random.randint(1, CHROM_LENGTH - 1)
        return parent1[:point] + parent2[point:], parent2[:point] + parent1[point:]
    else:
        return parent1, parent2


# 变异操作
def mutate(chrom):
    chrom_list = list(chrom)
    for i in range(CHROM_LENGTH):
        if random.random() < MUTATION_RATE:
            chrom_list[i] = '1' if chrom_list[i] == '0' else '0'
    return ''.join(chrom_list)


# 遗传算法主循环
def genetic_algorithm():
    population = init_population()

    for generation in range(GENERATIONS):
        # 精英保留：找到当前最优个体
        best_chrom = max(population, key=lambda chrom: fitness(decode(chrom)))
        elite = [best_chrom]  # 将最优个体保留

        # 选择操作
        population = select(population)
        next_generation = []

        # 生成下一代
        for i in range(0, POP_SIZE - ELITE_RATE, 2):  # 留出精英位置
            parent1, parent2 = population[i], population[i + 1]
            child1, child2 = crossover(parent1, parent2)  # 交叉
            child1, child2 = mutate(child1), mutate(child2)  # 变异
            next_generation.extend([child1, child2])

        # 添加精英个体到下一代
        next_generation.extend(elite)

        population = next_generation

        # 记录当前种群中最优解
        best_chrom = max(population, key=lambda chrom: fitness(decode(chrom)))
        print(
            f"Generation {generation + 1}: Best solution = {decode(best_chrom)}, f(x) = {fitness(decode(best_chrom))}")


# 执行遗传算法
genetic_algorithm()