遗传算法早熟收敛问题排查及优化建议求助

近期实现遗传算法时遭遇早熟收敛，无法突破疑似局部最优解。尝试过以下手段均未奏效，算法始终卡在同一适应度水平：

• 算法陷入停滞时执行全局突变
• 提高突变率并降低交叉率
• 运行多种群并迁移部分个体
• 应用适应度共享技术（通过降低常见个体的适应度促进个体独特性、提升种群多样性）

简化后的单次迭代函数 #

def single_iteration(self):
    new_population = []

    for individual in self.population:
        individual.evaluate(evaluator)

    self.adjust_fitness_for_sharing()

    while len(new_population) < len(self.population):
        fst_parent_index = self.tournament_selection(2)
        snd_parent_index = self.tournament_selection(2)

        children = self.population[fst_parent_index].one_point_crossover(self.population[snd_parent_index], self.crossover_ratio)

        children[0].mutate(self.mutation_ratio, evaluator)
        children[1].mutate(self.mutation_ratio, evaluator)

        new_population.append(children[0])
        new_population.append(children[1])

    self.population = new_population

适应度共享相关函数（采用汉明距离计算个体间距离，用于锦标赛选择） #

def calculate_sharing_function(self, distance, sigma_share):
    if distance < sigma_share:
        return 1 - math.pow(distance / sigma_share, 0.8)
    else:
        return 0

def adjust_fitness_for_sharing(self):
    niche_count = [0] * len(self.population)

    for i in range(len(self.population)):
        for j in range(len(self.population)):
            if i != j:
                distance = self.population[i].calculate_hamming_distance(self.population[j])
                niche_count[i] += self.calculate_sharing_function(distance, 800)

    for i in range(len(self.population)):
        self.population[i].set_shared_fitness(self.population[i].get_fitness() / niche_count[i])

代码问题排查与改进建议 #

核心可能问题

1. 锦标赛选择未使用共享适应度：
   若tournament_selection函数仍基于原始fitness而非调整后的shared_fitness进行选择，那么适应度共享的逻辑完全不会生效——必须确保锦标赛比较的是individual.get_shared_fitness()，而非原始适应度值。

2. sigma_share参数设置不合理：
   汉明距离的取值范围由个体编码长度决定。如果你的个体编码长度远小于800，那么所有个体间的距离都会小于sigma_share=800，导致niche_count的区分度极低，所有个体的共享适应度几乎成比例缩小，无法起到筛选独特个体的作用。建议根据编码长度调整sigma_share，比如编码长度为100时，可尝试设置为20-30。

其他优化方向

3. 种群替换策略过于激进：
   当前实现采用完全替换策略（所有父代被子代替换），容易导致种群多样性快速丢失。建议加入精英保留机制：每次迭代保留少量（比如5%-10%）最优个体（基于共享适应度），再生成剩余子代补充种群。

4. 交叉与突变策略的多样性不足：

   • 单点交叉在长编码场景下多样性有限，可尝试多点交叉或均匀交叉；
   • 固定突变率难以适配种群动态变化，可改为自适应突变率：根据种群平均汉明距离判断多样性，低多样性时提高突变率，高多样性时降低。

5. 种群多样性监控：
   加入代码监控种群的平均汉明距离、独特个体占比等指标，确认适应度共享生效后多样性是否有提升。若多样性仍无改善，说明参数或逻辑仍存在问题。

6. 适应度函数验证：
   确认当前卡住的适应度水平是否真的是局部最优，而非适应度函数本身存在平台期（即某一范围内适应度无变化），导致算法无法感知更优解。

7. 尝试其他小生境技术：
   若适应度共享调参困难，可尝试拥挤选择（Crowding Selection），通过替换相似个体来维持多样性，调参逻辑相对简单。

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