非支配排序遗传算法进化多目标优化算法

非支配排序遗传算法（NSGA-II）是一种经典的多目标优化算法，其Matlab实现结合了遗传算法框架与非支配排序、拥挤距离等关键技术。

一、NSGA-II算法核心原理

1. 非支配排序
   通过比较个体间的支配关系，将种群划分为多个非支配层级（Front）。第一层为Pareto前沿解，第二层为被第一层支配的解，依此类推。快速非支配排序算法的时间复杂度为O(MN2)O(MN^2)O(MN2)，显著优于传统方法。
2. 拥挤距离计算
   在相同非支配层级内，通过计算个体在目标空间中的密度（即与相邻个体的目标函数值差异之和），评估其多样性。拥挤距离越大，个体越优，避免算法早熟收敛。
3. 精英策略与环境选择
   合并父代与子代种群后，通过非支配排序和拥挤距离筛选下一代，确保优秀个体（如Front层内距离大的解）被保留，提升收敛性与多样性。

二、Matlab实现步骤

1. 初始化参数与种群

% 定义问题参数
nvars = 3;          % 决策变量维度
lb = [0,0,0];       % 下界
ub = [5,5,5];       % 上界
options = optimoptions('gamultiobj', 'PopulationSize', 100, ... 
                       'CrossoverFcn', @simulatedBinaryCrossover, ...
                       'MutationFcn', @polynomialMutation);

2. 目标函数与约束定义

% 目标函数（示例：ZDT1问题）
function f = evaluateObjectives(x)
    f1 = x(:,1);                % 第一目标
    f2 = (1 - x(:,1)).^2 + 100*(x(:,2) - x(:,1).^2).^2; % 第二目标
    f = [f1, f2];
end

% 约束函数（可选）
function [c, ceq] = constraints(x)
    c = [];       % 不等式约束
    ceq = [];     % 等式约束
end

3. 调用gamultiobj求解

[x, fval] = gamultiobj(@evaluateObjectives, nvars, [], [], [], [], lb, ub, @constraints, options);

4. 结果可视化

figure;
plot(fval(:,1), fval(:,2), 'o');
xlabel('Objective 1');
ylabel('Objective 2');
title('Pareto Front');

三、关键代码解析

1. 非支配排序实现

function fronts = fastNondominatedSort(population, objectives)
    N = size(population, 1);
    M = size(objectives, 2);
    dominatedCount = zeros(N, 1);
    dominatesList = cell(N, 1);
    
    % 比较所有个体对
    for i = 1:N
        for j = 1:N
            if i ~= j
                if all(objectives(i,:) <= objectives(j,:)') && any(objectives(i,:) < objectives(j,:)')
                    dominatesList{i} = [dominatesList{i}, j];
                elseif all(objectives(j,:) <= objectives(i,:)') && any(objectives(j,:) < objectives(i,:)')
                    dominatedCount(i) = dominatedCount(i) + 1;
                end
            end
        end
        if dominatedCount(i) == 0
            fronts{1} = [fronts{1}, i];
        end
    end
    
    % 构建层级
    frontIndex = 1;
    while ~isempty(fronts{frontIndex})
        nextFront = [];
        for i = fronts{frontIndex}
            for j = dominatesList{i}
                dominatedCount(j) = dominatedCount(j) - 1;
                if dominatedCount(j) == 0
                    nextFront = [nextFront, j];
                end
            end
        end
        frontIndex = frontIndex + 1;
        fronts{frontIndex} = nextFront;
    end
end

2. 拥挤距离计算

function distances = crowdingDistance(front, objectives)
    N = length(front);
    M = size(objectives, 2);
    distances = zeros(N, 1);
    
    for m = 1:M
        [~, sortedIdx] = sort(objectives(front, m));
        distances(sortedIdx(1)) = Inf;
        distances(sortedIdx(end)) = Inf;
        for i = 2:N-1
            distances(sortedIdx(i)) = distances(sortedIdx(i)) + ...
                (objectives(front(sortedIdx(i+1)), m) - objectives(front(sortedIdx(i-1)), m)) / ...
                (max(objectives(front, m)) - min(objectives(front, m)));
        end
    end
end

四、参考资料

• Matlab官方网页：gamultiobj函数说明 https://wenku.csdn.net/answer/1n3snvbxb1
• 非支配排序遗传算法（NSGA2-matlab）进化多目标优化算法 www.youwenfan.com/contentcse/82938.html
• 多目标优化案例库（如电力调度、工程设计）通过上述步骤，用户可快速构建适用于工程、经济等领域的多目标优化模型，并通过Matlab实现高效求解。