如何改进面向骰子个体的进化算法？当前最优适应度仅为42

问题背景 #

我正在实现一个进化算法，目标是让由100个骰子组成的个体所有骰子数值均为6。目前已实现骰子类、个体类，以及变异、重组和选择方法，但尝试多种超参数后，最优适应度仅能达到42，希望得到具体的算法改进建议。

当前实现代码 #

import numpy as np
import random

class Die():
    def __init__(self):
        self.number = np.random.randint(1, 7)
    
    def roll(self):
        self.number = np.random.randint(1, 7)


class Individual():
    def __init__(self, dices=None):
        self.dices = dices if dices != None else [Die() for _ in range(100)] 
        self.fitness = self.fitness_function()
        
    def fitness_function(self):
        return sum(1 for die in self.dices if die.number == 6)

    def mutate(self, mutation_rate):
        for die in self.dices:
            if np.random.random() < mutation_rate:
                die.roll()
        self.fitness = self.fitness_function()

def elite_selection(individuals, selection_size):
    sorted_individuals = sorted(individuals, key=lambda individual: individual.fitness, reverse=True)
    selected_individuals = sorted_individuals[:selection_size]
    return selected_individuals


def rank_based_selection(population, selection_size):
    sorted_population = sorted(population, key=lambda individual: individual.fitness, reverse=True)
    selection_probs = [1.0 / (i+1) for i in range(len(sorted_population))]
    total_prob = sum(selection_probs)
    normalized_probs = [p / total_prob for p in selection_probs]
    selected_individuals = list(np.random.choice(sorted_population, size=selection_size, p=normalized_probs))
    return selected_individuals


def one_point_crossover(parent_1, parent_2):
    crossover_point = np.random.randint(0, len(parent_1.dices))
    child_1_genes = parent_1.dices[:crossover_point] + parent_2.dices[crossover_point:]
    child_2_genes = parent_2.dices[:crossover_point] + parent_1.dices[crossover_point:]
    child_1 = Individual(child_1_genes)
    child_2 = Individual(child_2_genes)
    return child_1, child_2


def uniform_crossover(parent_1, parent_2):
    child_1_genes = []
    child_2_genes = []
    for i in range(len(parent_1.dices)):
        if np.random.uniform() < 0.5:
            child_1_genes.append(parent_1.dices[i])
            child_2_genes.append(parent_2.dices[i])
        else:
            child_1_genes.append(parent_2.dices[i])
            child_2_genes.append(parent_1.dices[i])        
    child_1 = Individual(child_1_genes)
    child_2 = Individual(child_2_genes)
    return child_1, child_2


def evolutionary_algorithm(population_size, selection_size, mutation_rate, max_iterations, target_fitness=80):
    population = [Individual() for _ in range(population_size)]

    for _ in range(max_iterations):
        selected_population = elite_selection(population, selection_size)
        new_population = selected_population

        while len(new_population) < population_size:
            parent_1, parent_2 = random.sample(selected_population, 2)
            child_1, child_2 = uniform_crossover(parent_1, parent_2)
            child_1.mutate(mutation_rate)
            child_2.mutate(mutation_rate)
            new_population += [child_1, child_2]

        population = new_population
        
        if np.mean([individual.fitness for individual in population]) >= target_fitness:
            break
        
    return population

population_size = 500
selection_size = 100
mutation_rate = 0.01
max_iterations = 300

indiv = evolutionary_algorithm(population_size, selection_size, mutation_rate, max_iterations)
print(max((i.fitness for i in indiv)), end=" ")

核心问题分析 #

当前算法的瓶颈在于：纯精英选择易陷入局部最优，交叉操作无针对性（会破坏已有的6点骰子），变异机制会随机重置已有的最优基因，且终止条件设置不合理。

具体改进建议 #

• 优化选择策略：
  混合精英选择与锦标赛选择：保留Top 20%的精英个体，剩余选择名额用锦标赛选择（每次随机抽取3-5个个体，选其中最优者），既保留优质基因，又维持种群多样性。
• 改进交叉操作：
  替换随机交叉为定向交叉：仅在双方骰子都非6的位置进行交换；若某一方对应位置是6，则直接将该骰子遗传给子代，避免优质基因被随机交换。
• 调整变异机制：
  改成针对性变异：仅对非6的骰子执行变异操作，变异率可提高至0.05-0.1；完全跳过已为6的骰子，避免破坏已有的最优基因。
• 修正终止条件：
  放弃种群平均适应度的终止逻辑，改为追踪种群最优个体的适应度：当最优个体适应度达到100时立即终止，或当连续10-20代最优适应度无提升时停止迭代，避免提前终止进化。
• 超参数调优：
  • 种群规模：增大至800-1000，提升基因多样性；
  • 选择比例：将selection_size设为种群规模的30%-40%（如500种群选150-200），避免选择压力过大；
  • 变异率：针对非6骰子的变异率调整为0.05-0.1，加速非最优骰子的优化。
• 提升计算效率：
  优化适应度计算逻辑，改为增量更新：变异时记录被修改的骰子位置，仅更新这些位置对适应度的贡献，减少重复计算。

改进后的关键代码片段 #

# 改进的针对性变异方法
def mutate(self, mutation_rate):
    for die in self.dices:
        # 仅变异非6的骰子
        if die.number != 6 and np.random.random() < mutation_rate:
            die.roll()
    self.fitness = self.fitness_function()

# 改进的定向交叉方法
def targeted_crossover(parent_1, parent_2):
    child_1_genes = []
    child_2_genes = []
    for d1, d2 in zip(parent_1.dices, parent_2.dices):
        # 优先保留6点骰子
        if d1.number == 6:
            child_1_genes.append(d1)
            child_2_genes.append(d2 if d2.number == 6 else random.choice([d1, d2]))
        elif d2.number == 6:
            child_2_genes.append(d2)
            child_1_genes.append(d1 if d1.number == 6 else random.choice([d1, d2]))
        else:
            # 非6位置随机交换
            if np.random.uniform() < 0.5:
                child_1_genes.append(d1)
                child_2_genes.append(d2)
            else:
                child_1_genes.append(d2)
                child_2_genes.append(d1)
    child_1 = Individual(child_1_genes)
    child_2 = Individual(child_2_genes)
    return child_1, child_2

内容的提问来源于stack exchange，提问作者Felix