NSGA-II（Non-dominated Sorting Genetic Algorithm II） 算法求解 ZDT1 双目标优化问题

前言

提醒：
文章内容为方便作者自己后日复习与查阅而进行的书写与发布，其中引用内容都会使用链接表明出处（如有侵权问题，请及时联系）。
其中内容多为一次书写，缺少检查与订正，如有问题或其他拓展及意见建议，欢迎评论区讨论交流。

内容由AI辅助生成，仅经笔者审核整理，请甄别食用。

---

matlab代码

clc; clear; close all;
%%NSGA-II（Non-dominated Sorting Genetic Algorithm II） 优化算法
%%NSGA-II 的核心创新包括快速非支配排序、拥挤度距离计算、精英保留策略
%% 参数设置
nPop = 100;        % 种群大小
nVar = 30;         % 决策变量个数
MaxIt = 200;       % 最大迭代次数
pc = 0.9;          % 交叉概率
pm = 0.1;          % 变异概率
VarMin = 0;        % 决策变量范围
VarMax = 1;%% 初始化种群
pop = rand(nPop, nVar);
costs = arrayfun(@(i) ZDT1(pop(i,:)), 1:nPop, 'UniformOutput', false);
costs = cell2mat(costs');%% 主循环
for it = 1:MaxIt%% 非支配排序[Fronts, rank] = NonDominatedSort(costs);%% 拥挤度计算crowding = CrowdingDistance(costs, Fronts);%% 选择（基于等级和拥挤度的锦标赛）selected = TournamentSelection(pop, costs, rank, crowding, nPop);%% 生成子代offspring = zeros(size(pop));for i = 1:2:nPopp1 = selected(i,:);p2 = selected(i+1,:);if rand < pc[c1, c2] = SBX(p1, p2, VarMin, VarMax);elsec1 = p1; c2 = p2;endc1 = Mutate(c1, VarMin, VarMax, pm);c2 = Mutate(c2, VarMin, VarMax, pm);offspring(i,:) = c1;offspring(i+1,:) = c2;end%% 合并种群union = [pop; offspring];union_costs = arrayfun(@(i) ZDT1(union(i,:)), 1:size(union,1), 'UniformOutput', false);union_costs = cell2mat(union_costs');%% 非支配排序 + 拥挤度计算[Fronts, rank] = NonDominatedSort(union_costs);crowding = CrowdingDistance(union_costs, Fronts);%% 选择新一代pop = [];costs = [];i = 1;while size(pop,1) + length(Fronts{i}) <= nPoppop = [pop; union(Fronts{i},:)];costs = [costs; union_costs(Fronts{i},:)];i = i + 1;end% 拥挤度排序remaining = Fronts{i};[~, sort_idx] = sort(crowding(remaining), 'descend');n_rest = nPop - size(pop,1);pop = [pop; union(remaining(sort_idx(1:n_rest)),:)];costs = [costs; union_costs(remaining(sort_idx(1:n_rest)),:)];%% 可视化f1_theory = linspace(0,1,100);f2_theory = 1 - sqrt(f1_theory);plot(f1_theory, f2_theory, 'b-', 'LineWidth', 1.5); hold on;scatter(costs(:,1), costs(:,2), 25, 'r', 'filled');title(['NSGA-II 第 ' num2str(it) ' 代']);xlabel('f_1'); ylabel('f_2');axis([0 1.5 0 5]); grid on;legend('理论前沿', '当前解'); drawnow;hold off;
end%% 目标函数 ZDT1
function y = ZDT1(x)f1 = x(1);g = 1 + 9 * sum(x(2:end))/(length(x)-1);f2 = g * (1 - sqrt(f1/g));y = [f1, f2];
end%% 非支配排序
function [Fronts, rank] = NonDominatedSort(costs)N = size(costs,1);S = cell(N,1);     % 被支配集n = zeros(N,1);    % 被支配数rank = zeros(N,1);Fronts{1} = [];for p = 1:Nfor q = 1:Nif Dominates(costs(p,:), costs(q,:))S{p} = [S{p} q];elseif Dominates(costs(q,:), costs(p,:))n(p) = n(p)+1;endendif n(p) == 0rank(p) = 1;Fronts{1} = [Fronts{1}, p];endendi = 1;while ~isempty(Fronts{i})Q = [];for p = Fronts{i}for q = S{p}n(q) = n(q) - 1;if n(q) == 0rank(q) = i+1;Q = [Q, q];endendendi = i + 1;Fronts{i} = Q;end
end%% 拥挤度计算
function D = CrowdingDistance(costs, Fronts)N = size(costs,1);D = zeros(N,1);for f = 1:length(Fronts)F = Fronts{f};if isempty(F), continue; endfor j = 1:size(costs,2)[~, idx] = sort(costs(F,j));D(F(idx(1))) = Inf;D(F(idx(end))) = Inf;for k = 2:length(F)-1D(F(idx(k))) = D(F(idx(k))) + ...(costs(F(idx(k+1)),j) - costs(F(idx(k-1)),j)) / ...(max(costs(F,j)) - min(costs(F,j)) + eps);endendend
end%% 支配关系
function b = Dominates(p, q)b = all(p <= q) && any(p < q);
end%% 锦标赛选择
function selected = TournamentSelection(pop, costs, rank, crowding, N)selected = zeros(N, size(pop,2));for i = 1:Ni1 = randi(size(pop,1));i2 = randi(size(pop,1));if rank(i1) < rank(i2)selected(i,:) = pop(i1,:);elseif rank(i2) < rank(i1)selected(i,:) = pop(i2,:);elseif crowding(i1) > crowding(i2)selected(i,:) = pop(i1,:);elseselected(i,:) = pop(i2,:);endendend
end%% 模拟二进制交叉 SBX
function [y1, y2] = SBX(p1, p2, VarMin, VarMax)eta = 20;u = rand(size(p1));beta = (2*u).^(1/(eta+1));y1 = 0.5*((1+beta).*p1 + (1-beta).*p2);y2 = 0.5*((1-beta).*p1 + (1+beta).*p2);y1 = max(min(y1, VarMax), VarMin);y2 = max(min(y2, VarMax), VarMin);
end%% 多项式变异
function y = Mutate(x, VarMin, VarMax, pm)eta = 20;y = x;for i = 1:length(x)if rand < pmu = rand;delta = (2*u)^(1/(eta+1)) - 1;y(i) = x(i) + delta;endendy = max(min(y, VarMax), VarMin);
end

运行结果

代码分析

这段代码实现了NSGA-II（Non-dominated Sorting Genetic Algorithm II） 算法，用于求解ZDT1双目标优化问题。NSGA-II是多目标进化算法的标杆，核心创新在于快速非支配排序、拥挤度距离计算、精英保留策略。以下结合数学公式和代码实现，详细解析其核心机制：

一、目标函数：ZDT1双目标优化问题

NSGA-II求解的ZDT1函数是典型的双目标冲突问题，数学定义为：

• 目标1：$f_1(x)=x_1$
• 目标2：$f_2(x)=g(x)\cdot \left(1-\sqrt{\frac{f_1(x)}{g(x)}}\right)$
• 约束函数：$g(x)=1+\frac{9}{n-1}{\sum }_{i=2}^n{x}_i$

其中，$x_i\in [0,1]$（$n=30$为决策变量维度），理论Pareto前沿满足：$f_2=1-\sqrt{f_1}$。

代码中ZDT1函数直接实现该公式：
ZDT1 双目标优化问题简介

function y = ZDT1(x)f1 = x(1);g = 1 + 9 * sum(x(2:end))/(length(x)-1);f2 = g * (1 - sqrt(f1/g));y = [f1, f2];
end

二、核心机制1：快速非支配排序（NonDominatedSort函数）

非支配排序是NSGA-II的基础，用于将种群划分为不同“前沿（Fronts）”，量化解的优劣。

1. 支配关系定义

对于两个解$p$和$q$，若满足：

• 所有目标：$f_i(p)\le f_i(q)\forall i=1,2$
• 至少一个目标：$f_i(p)<f_i(q)\exists i$

则$p$支配$q$（记为$p\prec q$）。代码中Dominates函数实现：

function b = Dominates(p, q)b = all(p <= q) && any(p < q);
end

2. 快速非支配排序流程

排序通过计算每个个体的被支配数（$n(p)$） 和支配集合（$S(p)$） 实现：
-$n(p)$：支配$p$的个体数量；
-$S(p)$：被$p$支配的个体集合。

分层规则：

• 第1层（Fronts{1}\text{Fronts}\{1\}Fronts{1}）：$n(p)=0$（不被任何个体支配）；
• 第$k$层（Fronts{k}\text{Fronts}\{k\}Fronts{k}）：仅被第1至$k-1$层个体支配（即$n(p)$的所有支配者都在第1至$k-1$层）。

代码实现逻辑：

function [Fronts, rank] = NonDominatedSort(costs)N = size(costs,1);S = cell(N,1);  % S{p}：被p支配的个体集合n = zeros(N,1); % n(p)：支配p的个体数量Fronts{1} = [];% 计算S和nfor p = 1:Nfor q = 1:Nif Dominates(costs(p,:), costs(q,:))S{p} = [S{p} q];  % p支配q，加入S{p}elseif Dominates(costs(q,:), costs(p,:))n(p) = n(p) + 1;  % q支配p，n(p)++endendif n(p) == 0  % 第1层：不被任何个体支配rank(p) = 1;Fronts{1} = [Fronts{1}, p];endend% 生成后续层i = 1;while ~isempty(Fronts{i})Q = [];  % 下一层候选for p = Fronts{i}for q = S{p}  % 对p支配的个体q，减少其被支配数n(q) = n(q) - 1;if n(q) == 0  % 若q的被支配数为0，加入下一层rank(q) = i+1;Q = [Q, q];endendendi = i + 1;Fronts{i} = Q;end
end

• 输出Fronts为细胞数组，存储各层个体索引；
• rank(p)为个体$p$的层级（越小越优）。

三、核心机制2：拥挤度距离（CrowdingDistance函数）

拥挤度距离用于衡量同一前沿层内个体的“稀疏程度”，避免种群集中在局部区域，数学定义如下：

对第$f$层的个体集合$F$，按目标$j$排序后：

• 边界个体（最小/最大目标值）的拥挤度为$\infty$；
• 中间个体$k$的拥挤度：$D(k)={\sum }_{j=1}^m\frac{f_{k+1,j}-f_{k-1,j}}{f_{\text{max},j}-f_{\text{min},j}}$

其中，$m$为目标数，$f_{k,j}$为个体$k$在目标$j$上的值，$f_{\text{max},j}/f_{\text{min},j}$为目标$j$在$F$中的最大/最小值。
相关链接：拥挤度距离计算示例

代码实现：

function D = CrowdingDistance(costs, Fronts)N = size(costs,1);D = zeros(N,1);  % 拥挤度距离for f = 1:length(Fronts)F = Fronts{f};  % 第f层个体if isempty(F), continue; endfor j = 1:size(costs,2)  % 对每个目标j[~, idx] = sort(costs(F,j));  % 按目标j排序sorted_F = F(idx);  % 排序后的个体索引% 边界个体拥挤度为无穷大D(sorted_F(1)) = Inf;D(sorted_F(end)) = Inf;% 中间个体拥挤度计算f_max = max(costs(F,j));f_min = min(costs(F,j));for k = 2:length(F)-1% 累加各目标的距离差D(sorted_F(k)) = D(sorted_F(k)) + ...(costs(sorted_F(k+1),j) - costs(sorted_F(k-1),j)) / ...(f_max - f_min + eps);  % eps避免除零endendend
end

四、选择操作：锦标赛选择（TournamentSelection函数）

选择基于“双准则”：优先选择等级低（rank小）的个体；等级相同则选择拥挤度大（crowding大）的个体。

数学逻辑：对两个个体$a$和$b$，若$\text{rank}(a)<\text{rank}(b)$，则选$a$；若$\text{rank}(a)=\text{rank}(b)$且$\text{crowding}(a)>\text{crowding}(b)$，则选$a$。

代码实现：

function selected = TournamentSelection(pop, costs, rank, crowding, N)selected = zeros(N, size(pop,2));for i = 1:Ni1 = randi(size(pop,1));  % 随机选两个个体i2 = randi(size(pop,1));if rank(i1) < rank(i2)selected(i,:) = pop(i1,:);elseif rank(i2) < rank(i1)selected(i,:) = pop(i2,:);else  % 等级相同，比较拥挤度if crowding(i1) > crowding(i2)selected(i,:) = pop(i1,:);elseselected(i,:) = pop(i2,:);endendend
end

五、遗传操作：交叉与变异

1. 模拟二进制交叉（SBX，SBX函数）

SBX适用于连续决策变量，子代生成公式：
$$\{\begin{array}{l}{c}_1=0.5\cdot \left[(1+\beta )\cdot p_1+(1-\beta )\cdot p_2\right]\\ c_2=0.5\cdot \left[(1-\beta )\cdot p_1+(1+\beta )\cdot p_2\right]\end{array}$$

其中，交叉因子$\beta$为：
$$\beta =\{\begin{array}{ll}(2u{)}^{1/({\eta }_c+1)}& \text{if }u\le 0.5\\ (1/(2(1-u)){)}^{1/({\eta }_c+1)}& \text{if }u>0.5\end{array}$$

$u\sim \text{Uniform}(0,1)$，${\eta }_c$为交叉分布指数（代码中${\eta }_c=20$）。

代码实现：

function [y1, y2] = SBX(p1, p2, VarMin, VarMax)eta = 20;u = rand(size(p1));beta = (2*u).^(1/(eta+1));  % 交叉因子y1 = 0.5*((1+beta).*p1 + (1-beta).*p2);y2 = 0.5*((1-beta).*p1 + (1+beta).*p2);% 边界处理y1 = max(min(y1, VarMax), VarMin);y2 = max(min(y2, VarMax), VarMin);
end

2. 多项式变异（Mutate函数）

变异公式：$c=x+\delta \cdot (VarMax-VarMin)$，其中变异步长$\delta$为：
$$\delta =\{\begin{array}{ll}(2u{)}^{1/({\eta }_m+1)}-1& \text{if }u\le 0.5\\ 1-(2(1-u){)}^{1/({\eta }_m+1)}& \text{if }u>0.5\end{array}$$

$u\sim \text{Uniform}(0,1)$，${\eta }_m$为变异分布指数（代码中${\eta }_m=20$）。

代码实现：

function y = Mutate(x, VarMin, VarMax, pm)eta = 20;y = x;for i = 1:length(x)if rand < pm  % 以概率pm变异u = rand;delta = (2*u)^(1/(eta+1)) - 1;  % 变异步长y(i) = x(i) + delta;% 边界处理y(i) = max(min(y(i), VarMax), VarMin);endend
end

六、精英保留策略（核心创新）

NSGA-II通过合并父代与子代（规模$2N$），选择最优$N$个个体形成下一代，确保优秀个体不被淘汰：

1. 合并父代（pop）与子代（offspring）为union（规模$2N$）；
2. 对union重新非支配排序，得到新的Fronts；
3. 依次纳入完整的Fronts，直至剩余名额不足；
4. 对最后一个不完整的Front，按拥挤度降序选择剩余个体。

代码实现：

% 合并父代与子代
union = [pop; offspring];
union_costs = [costs; offspring_costs];
% 重新排序
[Fronts, rank] = NonDominatedSort(union_costs);
crowding = CrowdingDistance(union_costs, Fronts);% 选择下一代
pop = [];
costs = [];
i = 1;
% 纳入完整的Fronts
while size(pop,1) + length(Fronts{i}) <= nPoppop = [pop; union(Fronts{i},:)];costs = [costs; union_costs(Fronts{i},:)];i = i + 1;
end
% 最后一个不完整的Front按拥挤度选择
remaining = Fronts{i};
[~, sort_idx] = sort(crowding(remaining), 'descend');  % 拥挤度降序
n_rest = nPop - size(pop,1);
pop = [pop; union(remaining(sort_idx(1:n_rest)),:)];
costs = [costs; union_costs(remaining(sort_idx(1:n_rest)),:)];

七、算法流程总结

NSGA-II的迭代过程可概括为：
$$\text{父代}\stackrel{\text{选择+交叉+变异}}{\to }\text{子代}\stackrel{\text{合并+排序+选择}}{\to }\text{下一代父代}$$

核心优势：

• 快速非支配排序：效率远高于初代NSGA；
• 拥挤度距离：无需人工设置参数，自动维持多样性；
• 精英保留：确保优质解不丢失，收敛速度更快。

八、可视化结果

代码每代绘制当前解集与理论Pareto前沿（$f_2=1-\sqrt{f_1}$）的对比，直观展示算法收敛过程：

f1_theory = linspace(0,1,100);
f2_theory = 1 - sqrt(f1_theory);  % 理论前沿
plot(f1_theory, f2_theory, 'b-');  % 绘制理论前沿
scatter(costs(:,1), costs(:,2), 'r');  % 绘制当前解集

运行结果

最终解集将逼近理论前沿，且分布均匀，体现NSGA-II在收敛性和多样性上的优势。