当前位置：首页 > news >正文

NSGA-III（非支配排序遗传算法 III）求解 7 目标的 DTLZ2 测试函数

news 2025/7/31 5:28:18

前言

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

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

文章目录

前言
matlab代码
代码分析
- - 1. 参数设置
  - 2. 生成均匀分布的参考点
  - 3. 初始化种群
  - 4. 主进化循环
  - 5. DTLZ2 测试函数
  - 6. 非支配排序
  - 7. 环境选择
  - 8. 选择最后一个前沿中的个体
  - 9. 归一化目标函数
  - 10. 遗传操作
  - 总结

matlab代码

% NSGA-III算法求解7目标DTLZ2测试函数
function nsga3_dtlz2()% 参数设置params.Nvar = 12;          % 决策变量数量params.Nobj = 7;           % 目标函数数量params.Npop = 120;         % 种群大小params.max_gen = 200;      % 最大迭代次数params.pc = 0.9;           % 交叉概率params.pm = 1/params.Nvar; % 变异概率params.eta_c = 30;         % 交叉分布指数params.eta_m = 20;         % 变异分布指数params.H = 5;              % 参考点划分参数% 生成均匀分布的参考点[Z, ~] = generate_reference_points(params.Nobj, params.H);params.Z = Z;params.Nref = size(Z, 1);  % 参考点数量% 初始化种群pop = initialize_population(params);% 主进化循环for gen = 1:params.max_gen% 显示当前迭代进度if mod(gen, 10) == 0fprintf('迭代次数: %d/%d\n', gen, params.max_gen);end% 遗传操作: 交叉和变异offspring = genetic_operators(pop, params);% 合并父代和子代种群combined_pop = [pop; offspring];% 非支配排序[fronts, ~] = non_dominated_sort(combined_pop);% 环境选择pop = environmental_selection(combined_pop, fronts, params);end% 绘制3D散点图figure;% 提取所有个体的目标函数值objs_cell = {pop.objs};objs_matrix = cell2mat(objs_cell');% 第一个3D散点图 - 目标函数1, 2, 3subplot(1, 3, 1);scatter3(objs_matrix(:, 1), objs_matrix(:, 2), objs_matrix(:, 3), 'filled');xlabel('目标函数 1');ylabel('目标函数 2');zlabel('目标函数 3');title('目标函数 1, 2, 3 的3D散点图');grid on;% 第二个3D散点图 - 目标函数4, 5, 6subplot(1, 3, 2);scatter3(objs_matrix(:, 4), objs_matrix(:, 5), objs_matrix(:, 6), 'filled');xlabel('目标函数 4');ylabel('目标函数 5');zlabel('目标函数 6');title('目标函数 4, 5, 6 的3D散点图');grid on;% 第三个3D散点图 - 目标函数1, 3, 5subplot(1, 3, 3);scatter3(objs_matrix(:, 1), objs_matrix(:, 3), objs_matrix(:, 5), 'filled');xlabel('目标函数 1');ylabel('目标函数 3');zlabel('目标函数 5');title('目标函数 1, 3, 5 的3D散点图');grid on;end% 初始化种群
function pop = initialize_population(params)% 创建结构体数组，每个元素代表一个个体pop = repmat(struct('decs', [], 'objs', []), params.Npop, 1);for i = 1:params.Npoppop(i).decs = rand(1, params.Nvar);  % 决策变量范围[0,1]pop(i).objs = dtlz2(pop(i).decs, params.Nobj);  % 计算目标函数值end
end% DTLZ2测试函数 (7目标)
function objs = dtlz2(decs, Nobj)k = Nobj - 1;  % 前k个变量用于构造目标，剩余用于g(x)n = length(decs);x = decs;f = zeros(1, Nobj);% 计算g(x)if k < ng = sum((x(k+1:end) - 0.5).^2);elseg = 0;end% 计算各目标函数for i = 1:Nobjproduct = 1;for j = 1:i-1product = product * cos(x(j) * pi / 2);endif i > 1product = product * sin(x(i-1) * pi / 2);endf(i) = (1 + g) * product;endobjs = f;
end% 生成参考点 (Das and Dennis方法)
function [Z, H] = generate_reference_points(Nobj, H)if nargin < 2H = 10;  % 默认划分参数endZ = [];if Nobj == 2Z = [(0:H)/H; H:-1:0]/H;Z = Z';elsea = ones(1, Nobj);Z = generate_recursive(a, H, Nobj, 1, 0, Z);end% 归一化参考点if ~isempty(Z)sums = sum(Z, 2);Z = Z ./ repmat(sums, 1, Nobj);end
end% 递归生成参考点的辅助函数
function Z = generate_recursive(a, H, Nobj, idx, current_sum, Z)if idx < Nobjfor i = 0:H - current_suma(idx) = i;Z = generate_recursive(a, H, Nobj, idx + 1, current_sum + i, Z);endelsea(idx) = H - current_sum;if sum(a) == HZ = [Z; a];endend
end% 非支配排序
function [fronts, ranks] = non_dominated_sort(pop)N = length(pop);S = cell(N, 1);n = zeros(N, 1);ranks = zeros(N, 1);fronts = cell(N, 1);current_rank = 1;% 计算支配关系for i = 1:Nfor j = 1:Nif i ~= jif dominates(pop(i).objs, pop(j).objs)S{i} = [S{i}, j];elseif dominates(pop(j).objs, pop(i).objs)n(i) = n(i) + 1;endendendif n(i) == 0ranks(i) = current_rank;fronts{current_rank} = [fronts{current_rank}, i];endend% 计算其他前沿while ~isempty(fronts{current_rank})next_rank = [];for i = fronts{current_rank}for j = S{i}n(j) = n(j) - 1;if n(j) == 0ranks(j) = current_rank + 1;next_rank = [next_rank, j];endendendcurrent_rank = current_rank + 1;fronts{current_rank} = next_rank;end% 移除空前沿idx = find(cellfun(@isempty, fronts));fronts(idx) = [];
end% 判断是否支配
function dom = dominates(f1, f2)dom = all(f1 <= f2) && any(f1 < f2);
end% 环境选择（修复结构体类型转换错误）
function pop = environmental_selection(combined_pop, fronts, params)% 初始化空结构体数组（关键修复：明确结构体类型）pop = repmat(struct('decs', [], 'objs', []), 0, 1);  % 空结构体数组current_size = 0;front_idx = 1;N = params.Npop;% 选择完整前沿while front_idx <= length(fronts) && current_size + length(fronts{front_idx}) <= N% 获取当前前沿的个体（结构体数组）current_front = combined_pop(fronts{front_idx});% 计算新的索引范围new_size = current_size + length(current_front);% 赋值（确保两边都是结构体数组）pop(current_size+1:new_size) = current_front;current_size = new_size;front_idx = front_idx + 1;end% 部分选择最后一个前沿if current_size < N && front_idx <= length(fronts)last_front = fronts{front_idx};need = N - current_size;% 选择最后一个前沿的个体selected = select_last_front(combined_pop(last_front), need, params);% 赋值剩余需要的个体pop(current_size+1:current_size+need) = combined_pop(last_front(selected));end
end% 选择最后一个前沿中的个体
function selected = select_last_front(front_pop, need, params)Nobj = params.Nobj;N = length(front_pop);selected = false(N, 1);count = 0;% 归一化目标函数objs_cell = {front_pop.objs};objs_matrix = cell2mat(objs_cell');[normalized_objs, ~] = normalize_objectives(objs_matrix);% 关联到参考点[associations, ~] = associate(normalized_objs, params.Z);% 计算niche countniche_counts = histcounts(associations, 1:params.Nref+1);% 选择过程while count < need[min_count, rp] = min(niche_counts);candidates = find(associations == rp & ~selected);if ~isempty(candidates)idx = candidates(randi(length(candidates)));selected(idx) = true;niche_counts(rp) = niche_counts(rp) + 1;count = count + 1;elseniche_counts(rp) = Inf;end% 处理所有参考点都满的情况if all(niche_counts == Inf) && count < needremaining = find(~selected);selected(remaining(1:need-count)) = true;count = need;endend
end% 归一化目标函数
function [normalized_objs, ideal_point] = normalize_objectives(objs)[n, m] = size(objs);ideal_point = min(objs);normalized_objs = objs - repmat(ideal_point, n, 1);max_vals = max(normalized_objs);for i = 1:mif max_vals(i) > 0normalized_objs(:,i) = normalized_objs(:,i) / max_vals(i);endend
end% 关联到参考点
function [associations, distances] = associate(normalized_objs, Z)N = size(normalized_objs, 1);Nref = size(Z, 1);associations = zeros(N, 1);distances = zeros(N, 1);for i = 1:Ndists = pdist2(normalized_objs(i,:), Z, 'cosine');[min_dist, idx] = min(dists);associations(i) = idx;distances(i) = min_dist;end
end% 遗传操作
function offspring = genetic_operators(pop, params)N = length(pop);offspring = repmat(struct('decs', [], 'objs', []), N, 1);perm = randperm(N);for i = 1:2:Nif i+1 > Noffspring(i) = pop(perm(i));continue;endp1 = pop(perm(i));p2 = pop(perm(i+1));% 交叉if rand < params.pc[c1, c2] = sbx_crossover(p1.decs, p2.decs, params.eta_c);elsec1 = p1.decs;c2 = p2.decs;end% 变异c1 = polynomial_mutation(c1, params.pm, params.eta_m);c2 = polynomial_mutation(c2, params.pm, params.eta_m);% 评估offspring(i).decs = c1;offspring(i).objs = dtlz2(c1, params.Nobj);offspring(i+1).decs = c2;offspring(i+1).objs = dtlz2(c2, params.Nobj);end
end% 模拟二进制交叉
function [child1, child2] = sbx_crossover(parent1, parent2, eta_c)nvar = length(parent1);child1 = parent1;child2 = parent2;for i = 1:nvarif rand <= 0.5u = rand;if u <= 0.5beta = (2*u)^(1/(eta_c + 1));elsebeta = (1/(2*(1 - u)))^(1/(eta_c + 1));endchild1(i) = 0.5*((1 + beta)*parent1(i) + (1 - beta)*parent2(i));child2(i) = 0.5*((1 - beta)*parent1(i) + (1 + beta)*parent2(i));child1(i) = max(0, min(1, child1(i)));child2(i) = max(0, min(1, child2(i)));endend
end% 多项式变异
function mutated = polynomial_mutation(individual, pm, eta_m)nvar = length(individual);mutated = individual;for i = 1:nvarif rand <= pmu = rand;if u < 0.5delta = (2*u)^(1/(eta_m + 1)) - 1;elsedelta = 1 - (2*(1 - u))^(1/(eta_m + 1));endmutated(i) = individual(i) + delta;mutated(i) = max(0, min(1, mutated(i)));endend
end

运行结果

代码分析

相关引用：NSGA-III（Non-dominated Sorting Genetic Algorithm III）简介

这段代码实现了 NSGA-III（非支配排序遗传算法 III），用于求解 7 目标的 DTLZ2 测试函数。NSGA-III 是一种多目标优化算法，旨在通过引入参考点来指导搜索过程，以实现良好的目标分布。下面将详细分析代码中的核心部分，包括相关的数学公式。

1. 参数设置

params.Nvar = 12;          % 决策变量数量
params.Nobj = 7;           % 目标函数数量
params.Npop = 120;         % 种群大小
params.max_gen = 200;      % 最大迭代次数
params.pc = 0.9;           % 交叉概率
params.pm = 1/params.Nvar; % 变异概率
params.eta_c = 30;         % 交叉分布指数
params.eta_m = 20;         % 变异分布指数
params.H = 5;              % 参考点划分参数

参数解释：
- Nvar：决策变量的数量。
- Nobj：目标函数的数量，这里是 7。
- Npop：种群的大小，即每一代的个体数量。
- max_gen：算法的最大迭代次数。
- pc：交叉操作的概率，表示有多大概率两个父代会进行交叉。
- pm：变异概率，表示每个基因发生变异的概率。
- eta_c 与 eta_m：分别是交叉和变异的分布指数，控制交叉和变异的强度。
- H：参考点的划分参数，用于生成参考点。

2. 生成均匀分布的参考点

[Z, ~] = generate_reference_points(params.Nobj, params.H);
params.Z = Z;
params.Nref = size(Z, 1);  % 参考点数量

参考点：
- NSGA-III 使用参考点来引导优化过程，确保目标在整个目标空间中的均匀分布。
- 生成的参考点将在后续选择中用于匹配个体的目标值。

3. 初始化种群

pop = initialize_population(params);

种群初始化：
- initialize_population 函数创建一个包含随机生成的决策变量和相应目标值的种群。

4. 主进化循环

for gen = 1:params.max_gen% 遗传操作: 交叉和变异offspring = genetic_operators(pop, params);% 合并父代和子代种群combined_pop = [pop; offspring];% 非支配排序[fronts, ~] = non_dominated_sort(combined_pop);% 环境选择pop = environmental_selection(combined_pop, fronts, params);
end

进化过程：
- 在每一代中，进行交叉和变异生成子代。
- 合并父代和子代种群，进行非支配排序，识别不同的 Pareto 前沿。
- 通过环境选择从合并的种群中选择个体生成新的种群。

5. DTLZ2 测试函数

function objs = dtlz2(decs, Nobj)k = Nobj - 1;  % 计算 g(x) 使用的变量数量n = length(decs);x = decs;f = zeros(1, Nobj);% 计算 g(x)if k < ng = sum((x(k+1:end) - 0.5).^2);elseg = 0;end% 计算各目标函数for i = 1:Nobjproduct = 1;for j = 1:i-1product = product * cos(x(j) * pi / 2);endif i > 1product = product * sin(x(i-1) * pi / 2);endf(i) = (1 + g) * product;endobjs = f;
end

数学公式：
- DTLZ2 函数的目标值计算为：
  $\sum_{j=k+1}^{n} (x_j - 0.5)^2$
  $fm(x)=(1+g(x))∏j=1m−1cos⁡(xjπ2)⋅sin⁡(xm−1π2),m=1,2,…,Mf_m(x) = (1 + g(x)) \prod_{j=1}^{m-1} \cos\left(x_j \frac{\pi}{2}\right) \cdot \sin\left(x_{m-1} \frac{\pi}{2}\right), \quad m = 1, 2, \ldots, M$

6. 非支配排序

function [fronts, ranks] = non_dominated_sort(pop)% Initialize variablesN = length(pop);S = cell(N, 1); % Domination setn = zeros(N, 1); % Number of individuals dominatedranks = zeros(N, 1); % Rank of each individualfronts = cell(N, 1); % Store the frontscurrent_rank = 1;% Calculate dominance relationsfor i = 1:Nfor j = 1:Nif i ~= jif dominates(pop(i).objs, pop(j).objs)S{i} = [S{i}, j]; % i dominates jelseif dominates(pop(j).objs, pop(i).objs)n(i) = n(i) + 1; % j dominates iendendendif n(i) == 0ranks(i) = current_rank;fronts{current_rank} = [fronts{current_rank}, i];endend% Calculate other frontswhile ~isempty(fronts{current_rank})next_rank = [];for i = fronts{current_rank}for j = S{i}n(j) = n(j) - 1;if n(j) == 0ranks(j) = current_rank + 1;next_rank = [next_rank, j];endendendcurrent_rank = current_rank + 1;fronts{current_rank} = next_rank;endidx = find(cellfun(@isempty, fronts));fronts(idx) = []; % Remove empty fronts
end

支配关系：
- 通过比较目标值确定个体间的支配关系。个体 A 支配个体 B 当且仅当：
  $\text{ dominates } B \iff (A_i \leq B_i \ \forall i) \land (A_j < B_j \ \exists j)$

7. 环境选择

function pop = environmental_selection(combined_pop, fronts, params)pop = repmat(struct('decs', [], 'objs', []), 0, 1);  % Empty struct arraycurrent_size = 0;front_idx = 1;N = params.Npop;% Select complete frontswhile front_idx <= length(fronts) && current_size + length(fronts{front_idx}) <= Ncurrent_front = combined_pop(fronts{front_idx});new_size = current_size + length(current_front);pop(current_size+1:new_size) = current_front;current_size = new_size;front_idx = front_idx + 1;end% Partial selection from the last frontif current_size < N && front_idx <= length(fronts)last_front = fronts{front_idx};need = N - current_size;selected = select_last_front(combined_pop(last_front), need, params);pop(current_size+1:current_size+need) = combined_pop(last_front(selected));end
end

环境选择：
- 通过选择完整的 Pareto 前沿和从最后一前沿中选择个体来维持种群的多样性和适应性。

8. 选择最后一个前沿中的个体

function selected = select_last_front(front_pop, need, params)selected = false(N, 1);count = 0;% Normalize objectivesobjs_cell = {front_pop.objs};objs_matrix = cell2mat(objs_cell');[normalized_objs, ~] = normalize_objectives(objs_matrix);% Associate with reference points[associations, ~] = associate(normalized_objs, params.Z);% Calculate niche countniche_counts = histcounts(associations, 1:params.Nref+1);% Selection processwhile count < need[min_count, rp] = min(niche_counts);candidates = find(associations == rp & ~selected);if ~isempty(candidates)idx = candidates(randi(length(candidates)));selected(idx) = true;niche_counts(rp) = niche_counts(rp) + 1;count = count + 1;elseniche_counts(rp) = Inf;end% Handle case where all reference points are fullif all(niche_counts == Inf) && count < needremaining = find(~selected);selected(remaining(1:need-count)) = true;count = need;endend
end

选择机制：
- 在最后一前沿中，通过关联参考点和计算小众计数来选择个体，以保持目标分布的均匀性。

9. 归一化目标函数

function [normalized_objs, ideal_point] = normalize_objectives(objs)ideal_point = min(objs);normalized_objs = objs - repmat(ideal_point, n, 1);max_vals = max(normalized_objs);for i = 1:mif max_vals(i) > 0normalized_objs(:,i) = normalized_objs(:,i) / max_vals(i);endend
end

归一化：
- 通过减去理想点并将目标值缩放到[0, 1]范围内来归一化，确保优化中的比较是公平的。

10. 遗传操作

function offspring = genetic_operators(pop, params)offspring = repmat(struct('decs', [], 'objs', []), N, 1);perm = randperm(N);for i = 1:2:Nif i+1 > Noffspring(i) = pop(perm(i));continue;endp1 = pop(perm(i));p2 = pop(perm(i+1));% Crossoverif rand < params.pc[c1, c2] = sbx_crossover(p1.decs, p2.decs, params.eta_c);elsec1 = p1.decs;c2 = p2.decs;end% Mutationc1 = polynomial_mutation(c1, params.pm, params.eta_m);c2 = polynomial_mutation(c2, params.pm, params.eta_m);% Evaluationoffspring(i).decs = c1;offspring(i).objs = dtlz2(c1, params.Nobj);offspring(i+1).decs = c2;offspring(i+1).objs = dtlz2(c2, params.Nobj);end
end