MATLAB中遗传算法求解n皇后问题陷入停滞的技术咨询

你的MATLAB遗传算法实现频繁陷入局部最优（冲突数接近0但无法达到0），核心原因在于种群多样性不足、选择策略单一、变异率过高以及初始种群未遵循N皇后的基本约束（每行每列仅一个皇后）。以下是针对性的优化措施及修改后的代码：

关键优化点 #

• 扩大种群规模：将种群数量从5提升至20，避免过早收敛到局部最优。
• 初始种群生成排列：确保每个个体的y坐标是0到n-1的排列，消除列冲突的可能性，大幅减少初始冲突数。
• 调整变异率：将变异率从80%降至5%，避免过度随机化破坏优良基因。
• 锦标赛选择策略：替代单纯选择最优2个个体，保留更多种群多样性。
• 优化冲突计算：简化冲突统计逻辑，仅计算对角线上的冲突对（列冲突已通过排列避免）。
• 精英保留机制：确保每代最优个体直接进入下一代，加快收敛速度。

修改后的完整代码 #

% N皇后问题遗传算法优化版
clc, clear
% 参数设置
N = 1000; % 最大迭代次数
n = 8; % 皇后数量
l = 8; % 棋盘边长
pob = 20; % 种群规模
mutation_rate = 0.05; % 变异率

% 适应度函数：冲突数越少，适应度越高
f = @(x) n*(n-1)/2 - x; % 总可能无冲突对数减去实际冲突对数

% 初始化种群（每个个体是0~n-1的排列，代表每行皇后的列位置）
posiciones = cell(1, pob);
for i = 1:pob
    posiciones{i} = [0:n-1; randperm(n)-1]'; % 第一列是行号，第二列是列号（排列）
end
posiciones_iniciales = posiciones; % 保存初始种群用于绘图

% 计算初始种群冲突数和适应度
cont_jaques = zeros(1, pob);
puntuacion = zeros(1, pob);
for i = 1:pob
    cont_jaques(i) = calcular_conflictos(posiciones{i}(:,2));
    puntuacion(i) = f(cont_jaques(i));
end

cont = 1;
encontrado = false;
mejor_indice = find(cont_jaques == 0, 1);
encontrado = ~isempty(mejor_indice);

while cont <= N && ~encontrado
    % 锦标赛选择父代
    padres = seleccion_torneo(puntuacion, pob, 2);
    
    % 交叉操作：单点交叉
    hijos = cell(1, 2);
    pc = randi([1, n-1]);
    hijos{1} = [posiciones{padres(1)}(1:pc, :); posiciones{padres(2)}(pc+1:n, :)];
    hijos{2} = [posiciones{padres(2)}(1:pc, :); posiciones{padres(1)}(pc+1:n, :)];
    
    % 修复交叉后的个体（确保列位置是排列，无重复）
    hijos{1} = reparar_individuo(hijos{1});
    hijos{2} = reparar_individuo(hijos{2});
    
    % 变异操作：随机交换两个列位置
    if rand < mutation_rate
        idx = randperm(n, 2);
        temp = hijos{1}(idx(1), 2);
        hijos{1}(idx(1), 2) = hijos{1}(idx(2), 2);
        hijos{1}(idx(2), 2) = temp;
    end
    if rand < mutation_rate
        idx = randperm(n, 2);
        temp = hijos{2}(idx(1), 2);
        hijos{2}(idx(1), 2) = hijos{2}(idx(2), 2);
        hijos{2}(idx(2), 2) = temp;
    end
    
    % 将子代加入种群
    posiciones{pob+1} = hijos{1};
    posiciones{pob+2} = hijos{2};
    
    % 计算所有个体的冲突数和适应度
    for i = 1:pob+2
        cont_jaques(i) = calcular_conflictos(posiciones{i}(:,2));
        puntuacion(i) = f(cont_jaques(i));
    end
    
    % 精英保留+淘汰最差个体：保留前pob个最优个体
    [~, orden] = sort(puntuacion, 'descend');
    posiciones = posiciones(orden(1:pob));
    cont_jaques = cont_jaques(orden(1:pob));
    puntuacion = puntuacion(orden(1:pob));
    
    % 检查是否找到解
    mejor_indice = find(cont_jaques == 0, 1);
    encontrado = ~isempty(mejor_indice);
    
    cont = cont + 1;
end

% 输出结果
if encontrado
    fprintf('在%d次迭代后找到解！\n', cont-1);
    % 绘制初始和最终棋盘
    subplot(1,2,1);
    tablero(l);
    title('初始随机棋盘');
    reinas(posiciones_iniciales{1}(:,1), posiciones_iniciales{1}(:,2), n, 'red');
    subplot(1,2,2);
    tablero(l);
    title('最终解棋盘');
    reinas(posiciones{mejor_indice}(:,1), posiciones{mejor_indice}(:,2), n, 'green');
else
    fprintf('在%d次迭代内未找到解。\n', N);
end

%% 计算冲突数函数
function conflictos = calcular_conflictos(cols)
    n = length(cols);
    conflictos = 0;
    % 检查对角线冲突
    for i = 1:n-1
        for j = i+1:n
            if abs(cols(i) - cols(j)) == abs(i-1 - (j-1)) % 行号是0-based
                conflictos = conflictos + 1;
            end
        end
    end
end

%% 锦标赛选择函数
function seleccionados = seleccion_torneo(puntuacion, tam_pob, num_seleccionar)
    seleccionados = zeros(1, num_seleccionar);
    for i = 1:num_seleccionar
        candidatos = randperm(tam_pob, 3); % 3个候选者
        [~, idx] = max(puntuacion(candidatos));
        seleccionados(i) = candidatos(idx);
    end
end

%% 修复交叉后的个体（确保列位置是排列）
function individuo = reparar_individuo(individuo)
    cols = individuo(:,2);
    [valores, idx] = unique(cols);
    faltantes = setdiff(0:length(cols)-1, valores);
    % 替换重复的位置
    for i = 1:length(cols)
        if ~ismember(i-1, idx) % 找到重复的索引（idx是唯一值的位置）
            individuo(i,2) = faltantes(1);
            faltantes = faltantes(2:end);
        end
    end
end

%% 绘制棋盘函数
function tablero(l)
    x1=0; x2=l;
    y1=0; y2=l;
    x = [x1, x2, x2, x1, x1];
    y = [y1, y1, y2, y2, y1];
    plot(x, y, 'k-', 'LineWidth', 1.5);
    hold on
    xlim([-1, l+1]);
    ylim([-1, l+1]);
    % 绘制棋盘格
    for i = 1:l-1
        plot([0,l],[i,i], 'k-', 'LineWidth', 1);
        plot([i,i],[0,l],'k-', 'LineWidth', 1);
    end
    % 填充棋盘格颜色
    for i = 0:l-1
        for j = 0:l-1
            if mod(i+j,2) == 0
                fill([i,i+1,i+1,i],[j,j,j+1,j+1], 'w');
            else
                fill([i,i+1,i+1,i],[j,j,j+1,j+1], 'gray');
            end
        end
    end
    hold on
end

%% 绘制皇后函数
function reinas(rx,ry,n,color)
    for i = 1:n
        g_reinas = plot(rx(i)+0.5, ry(i)+0.5, 'or');
        g_reinas.MarkerFaceColor = color;
        g_reinas.MarkerSize = 10;
        g_reinas.MarkerEdgeColor = 'k';
    end
    hold off
end

优化说明 #

1. 排列约束：初始种群和修复后的个体确保列位置是0到n-1的排列，彻底消除列冲突，将问题简化为仅解决对角线冲突。
2. 锦标赛选择：每次从3个随机个体中选最优，平衡了选择压力和多样性。
3. 低变异率：5%的变异率仅在必要时引入小变化，避免破坏已有的优良基因组合。
4. 精英保留：每代保留最优的pob个个体，确保好的基因不会丢失。
5. 简化冲突计算：由于列冲突已被排除，仅需计算对角线冲突，提升运行效率。

内容的提问来源于stack exchange，提问作者Francisco García