C++实现8皇后问题遗传算法：轮盘赌选择与交叉问题排查

一、轮盘赌选择的正确性验证要点 #

要确认你的轮盘赌选择是否正确，需对照以下核心逻辑逐一排查：

• 适应度计算合理性：8皇后问题中，适应度需与个体质量正相关——通常用非攻击对数或总攻击对数的倒数/负数表示。若直接用攻击对数作为适应度，轮盘赌会优先选择劣质个体，这是高频错误。
• 轮盘概率分布逻辑：
  1. 计算种群所有个体的适应度总和total_fitness，需处理总和为0的极端情况（如所有个体完全相同时随机选择）。
  2. 生成0到total_fitness区间内的随机数rand_val，注意随机数类型与适应度类型匹配。
  3. 遍历种群累加适应度，当累加值≥rand_val时选中当前个体。
  4. 排查是否存在整数溢出（如适应度用int且总和过大）或随机数范围错误（如生成0-1浮点数却直接与整数累加值比较）。

以下是符合核心逻辑的代码示例：

// 假设个体类型为Individual，包含getFitness()方法
Individual rouletteSelect(const vector<Individual>& population) {
    double total_fitness = 0.0;
    for (const auto& ind : population) {
        total_fitness += ind.getFitness();
    }

    // 处理所有个体适应度为0的极端场景
    if (total_fitness == 0.0) {
        int rand_idx = rand() % population.size();
        return population[rand_idx];
    }

    double rand_val = static_cast<double>(rand()) / RAND_MAX * total_fitness;
    double current_sum = 0.0;
    for (const auto& ind : population) {
        current_sum += ind.getFitness();
        if (current_sum >= rand_val) {
            return ind;
        }
    }

    // 兜底逻辑，理论上不会执行到此处
    return population.back();
}

二、轮盘赌选择的优化点 #

• 适配负适应度场景：若用负数表示适应度（如-攻击对数），需先给所有适应度加偏移量转为非负值，否则总和可能为负，导致随机数逻辑完全失效。
• 预计算累积概率数组：种群规模较大时，每次选择重复累加适应度会浪费时间。可预先计算累积概率数组，后续选择用二分查找定位个体，提升效率：

  // 预计算累积概率数组
  vector<double> cum_probs;
  double current = 0.0;
  double total_fitness = accumulate(population.begin(), population.end(), 0.0,
      [](double sum, const Individual& ind) { return sum + ind.getFitness(); });
  for (const auto& ind : population) {
      current += ind.getFitness() / total_fitness;
      cum_probs.push_back(current);
  }
  // 选择阶段用二分查找
  double rand_val = static_cast<double>(rand()) / RAND_MAX;
  auto it = lower_bound(cum_probs.begin(), cum_probs.end(), rand_val);
  int selected_idx = it - cum_probs.begin();
  

• 缓解适应度两极分化：若少数个体适应度极高，轮盘赌会导致其被过度选择，降低种群多样性。可对适应度做非线性缩放（如取平方根、对数），或结合精英保留策略——既保留优秀个体，又维持种群多样性。
• 优化随机数生成：弃用老旧的rand()，改用C++11 <random>库的mt19937等随机数生成器，其随机数分布更均匀，避免选择结果出现偏差。

三、交叉环节的常见排查点 #

虽然你核心疑问是轮盘赌，但交叉环节问题也可能导致算法失效，提供两个高频出错点：

• 交叉点范围合理性：8皇后常用单点交叉，交叉点需避开首尾（否则等同于复制父代），建议在1到6之间随机选择（编码通常为8位，索引0-7）。
• 修复无效个体：交叉后需检查是否出现重复列值（8皇后编码为每行皇后所在列，不可重复），若存在重复需随机替换重复值，否则个体无效，会导致适应度计算错误。

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