遗传算法求解一维数独无法达到最优解问题排查

我使用遗传算法求解以一维数组表示的数独，已完成染色体等核心结构的生成。算法基于初始规模为100的染色体种群与自定义适应度函数，运行过程中种群的适应度均值和最大值均随交叉、突变操作逐步上升，但最大适应度始终卡在159，而数独求解完成的目标适应度值为162。附上核心代码，请求排查问题所在。

主循环代码：

while(!encontrado) {
    encontrado = newPopulation(encontrado,listOfIndividuals,initialSudoku);
}

种群更新核心函数：

private static boolean newPopulation (boolean encontrado, List<int[]> listOfIndividuals, int[] initialSudoku) {
    boolean returnBoolean = false;
    List<int[]> aux = new ArrayList<>();
    int añadidos = 0;
    int cnt = 0;
    int max = 0;
    Random alea = new Random();
    while (añadidos != 100 && !returnBoolean) {
        int rnd = alea.nextInt(101);
        int f = fitness(listOfIndividuals.get(cnt),initialSudoku);
        int p = Math.round(((100 * f) - 1800) / 144);
        if (f == 162) {
            System.out.println("HE ENCONTRADO EL FITNESS LIMITE");
            returnBoolean = true;
            aux.add(0,listOfIndividuals.get(cnt));
            continue;
        } else if (p >= rnd) {
            aux.add(listOfIndividuals.get(cnt));
            añadidos++;
            max += f;

            if(añadidos % 2 == 0) {
                crossover(aux,añadidos-2,añadidos-1);

            }
        }

        if (cnt + 1 == 100) {
            cnt = 0;
        } else {
            cnt++;
        }
    }

    if (!returnBoolean) {
        mutationGroup(aux,initialSudoku);
    }
    System.out.println("The mean is  " + max/aux.size());
    System.out.println();
    System.out.println();
    listOfIndividuals.clear();

    for (int j = 0; j < aux.size(); j++) {
        listOfIndividuals.add(aux.get(j));
    }
    return returnBoolean;
}

问题排查方向 #

• 选择算子的概率计算逻辑缺陷
  当前的选择概率公式 p = Math.round(((100 * f) - 1800) / 144) 会导致高适应度个体与次优个体的选择概率差距过小：比如适应度159的个体计算后p≈98，而目标值162的个体p=100，两者概率几乎无差异。这种情况下，次优个体大量被选中并参与交叉突变，种群很难突破局部最优的瓶颈。
  建议改用基于适应度占比的轮盘赌选择，或者用适应度的平方值来放大优秀个体的选择权重，拉开不同适应度个体的选中概率差。

• 交叉操作的时机与适配性问题
  当前每添加2个个体就执行交叉，但如果交叉操作未针对数独的约束特性设计（比如随机位置交叉破坏行/列/宫的合法结构），会大量产生无效解，消耗进化资源。另外，如果交叉直接覆盖父代个体，可能丢失已有优秀基因。
  建议针对数独设计按行交叉的策略（比如交换两个个体的某几整行），同时保留父代个体到下一代（即精英保留+交叉产生子代的模式），避免优秀基因被破坏。

• 突变操作的强度不足
  当种群陷入局部最优时，低强度的突变很难修正159到162之间的3个错误点。如果mutationGroup只是低概率随机修改单个位置，突破局部最优的概率极低。
  建议：

  • 对适应度接近162的个体提高突变概率，或者定向突变那些导致适应度扣分的位置（如果能通过适应度函数定位错误行/列/宫）；
  • 突变时严格规避初始数独的固定值，避免产生无效解。

• 种群多样性缺失
  初始种群规模100较小，若进化过程中种群快速收敛到相似染色体，极易陷入局部最优。可以加入：

  • 精英保留策略：直接将当前种群Top N的高适应度个体不经过交叉突变保留到下一代；
  • 随机个体注入：每几代引入少量随机生成的合法个体，维持种群多样性。

• 适应度函数准确性验证
  务必确认适应度函数的计算逻辑：162是否确实对应完全合法的数独？比如常规数独适应度按行、列、宫的不重复数字数计算，每行/列/宫最高9分，396=162。若适应度函数计算错误（比如某类约束未被计入），则算法永远无法达到目标值。

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