MOGA（多目标遗传算法）求解 ZDT1 双目标优化问题

前言

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

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

---

matlab代码

clc; clear; close all;
%%MOGA（Multi-Objective Genetic Algorithm，多目标遗传算法）
%%“非支配排序 + 共享机制” 的经典 MOGA 框架
%% 参数设置
nPop = 100;           % 种群规模
nVar = 30;            % 决策变量个数
VarMin = 0;           % 决策变量最小值
VarMax = 1;           % 决策变量最大值
MaxIt = 300;          % 最大迭代次数%% 初始化种群
pop = rand(nPop, nVar);             % 决策变量
pop_cost = zeros(nPop, 2);          % 目标函数值
for i = 1:nPoppop_cost(i,:) = ZDT1(pop(i,:));
end%% 主循环
for it = 1:MaxIt%% 非支配排序ranks = NonDominatedSorting_array(pop_cost);%% 共享密度计算sigma_share = 0.5;niche_count = Sharing_array(pop_cost, sigma_share);%% 适应度计算fitness = 1 ./ (1 + ranks') ./ (1 + niche_count');%% 锦标赛选择mating_pool = zeros(nPop, nVar);for i = 1:nPopidx1 = randi(nPop);idx2 = randi(nPop);if fitness(idx1) > fitness(idx2)mating_pool(i,:) = pop(idx1,:);elsemating_pool(i,:) = pop(idx2,:);endend%% 交叉 + 变异 生成子代offspring = zeros(nPop, nVar);for i = 1:2:nPopp1 = mating_pool(i,:);p2 = mating_pool(i+1,:);[c1, c2] = SBX(p1, p2, VarMin, VarMax);offspring(i,:) = Mutate(c1, VarMin, VarMax);offspring(i+1,:) = Mutate(c2, VarMin, VarMax);end%% 子代目标函数offspring_cost = zeros(nPop, 2);for i = 1:nPopoffspring_cost(i,:) = ZDT1(offspring(i,:));end%% 合并并选择下一代combined = [pop; offspring];combined_cost = [pop_cost; offspring_cost];new_ranks = NonDominatedSorting_array(combined_cost);[~, sorted_idx] = sort(new_ranks);pop = combined(sorted_idx(1:nPop), :);pop_cost = combined_cost(sorted_idx(1:nPop), :);%% 绘图f1_theory = linspace(0, 1, 100);f2_theory = 1 - sqrt(f1_theory);figure(1); clf;plot(f1_theory, f2_theory, 'b-', 'LineWidth', 1.2); hold on;if all(~isnan(pop_cost(:,1))) && all(~isnan(pop_cost(:,2)))scatter(pop_cost(:,1), pop_cost(:,2), 25, 'r', 'filled');elsewarning('pop_cost 中存在 NaN，无法绘图');endtitle(['MOGA - 第 ' num2str(it) ' 代']);xlabel('f_1'); ylabel('f_2'); axis([0 1.5 0 5]); grid on;legend('理论前沿', '当前解');drawnow;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 rank = NonDominatedSorting_array(costs)n = size(costs, 1);rank = zeros(n, 1);for i = 1:ndominated_count = 0;for j = 1:nif Dominates(costs(j,:), costs(i,:))dominated_count = dominated_count + 1;endendrank(i) = dominated_count;end
end%% 支配判断
function b = Dominates(x, y)b = all(x <= y) && any(x < y);
end%% 共享密度计算 (纯数组)
function nc = Sharing_array(costs, sigma)n = size(costs, 1);nc = zeros(n, 1);for i = 1:nfor j = 1:nd = norm(costs(i,:) - costs(j,:));if d < sigmanc(i) = nc(i) + 1 - (d / sigma);endendend
end%% SBX交叉
function [y1, y2] = SBX(x1, x2, VarMin, VarMax)eta = 15;u = rand(size(x1));beta = (2*u).^(1/(eta+1));y1 = 0.5*((1+beta).*x1 + (1-beta).*x2);y2 = 0.5*((1-beta).*x1 + (1+beta).*x2);y1 = min(max(y1, VarMin), VarMax);y2 = min(max(y2, VarMin), VarMax);
end%% 多项式变异
function y = Mutate(x, VarMin, VarMax)eta = 20;pm = 1 / numel(x);y = x;for i = 1:numel(x)if rand < pmu = rand;delta = (2*u)^(1/(eta+1)) - 1;y(i) = x(i) + delta;endendy = min(max(y, VarMin), VarMax);
end

运行结果

代码分析

代码实现了一个基于非支配排序和共享机制的多目标遗传算法（MOGA），用于求解ZDT1双目标优化问题。以下结合数学公式和算法原理，详细解析代码的核心部分：

1. 多目标优化基础

相关引用：ZDT1 双目标优化问题简介

（1）ZDT1测试函数

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]$，最优Pareto前沿满足：$f_2=1-\sqrt{f_1}$。

（2）Pareto支配关系

相关引用：Pareto 最优解（Pareto Optimal Solution）简介

对于两个解$x$和$y$，若满足：

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

则称$x$支配$y$，记为$x\prec y$。代码中通过Dominates函数实现：

function b = Dominates(x, y)b = all(x <= y) && any(x < y);
end

2. 非支配排序机制

（1）支配数计算

代码采用简化的非支配排序，直接计算每个解的支配数（被支配的次数）：
$$\text{rank}(i)=\sum _{j=1}^N\mathbb{I}(j\prec i)$$
其中，$\mathbb{I}(\cdot )$为指示函数，若条件成立则为1，否则为0。

代码实现：

function rank = NonDominatedSorting_array(costs)n = size(costs, 1);rank = zeros(n, 1);for i = 1:ndominated_count = 0;for j = 1:nif Dominates(costs(j,:), costs(i,:))dominated_count = dominated_count + 1;endendrank(i) = dominated_count;end
end

支配数越小，解的质量越高。

3. 共享机制（Sharing Mechanism）

（1）小生境计数（Niche Count）

相关引用：“小生境计数”简介

共享机制通过计算目标空间中解的密度，实现多样性保持。对于解$i$，其小生境计数为：
$$\text{nc}(i)=\sum _{j=1}^N\text{sh}(d_{ij})$$
其中，$d_{ij}$是解$i$和$j$在目标空间的欧氏距离，$\text{sh}(\cdot )$是共享函数：
$$\text{sh}(d)=\{\begin{array}{ll}1-\left(\frac{d}{{\sigma }_{\text{share}}}\right)& \text{if }d<{\sigma }_{\text{share}}\\ 0& \text{otherwise}\end{array}$$

代码实现：

function nc = Sharing_array(costs, sigma)n = size(costs, 1);nc = zeros(n, 1);for i = 1:nfor j = 1:nd = norm(costs(i,:) - costs(j,:));if d < sigmanc(i) = nc(i) + 1 - (d / sigma);endendend
end

（2）适应度计算

相关引用：“适应度”简介

结合非支配排序和共享机制，解的适应度为：
$$\text{fitness}(i)=\frac{1}{(1+\text{rank}(i))\cdot (1+\text{nc}(i))}$$

代码实现：

fitness = 1 ./ (1 + ranks') ./ (1 + niche_count');

• 低支配数和低密度区域的解获得更高适应度，促进种群在Pareto前沿均匀分布。

4. 遗传操作

（1）模拟二进制交叉（SBX）

SBX是连续优化问题的有效交叉算子，生成的子代在父代附近：
$$\{\begin{array}{l}{c}_1=0.5\cdot \left[(1+\beta )x_1+(1-\beta )x_2\right]\\ c_2=0.5\cdot \left[(1-\beta )x_1+(1+\beta )x_2\right]\end{array}$$
其中，$\beta =(2u{)}^{1/(\eta +1)}$，$u\sim \text{Uniform}(0,1)$，$\eta$是分布指数（代码中为15）。

代码实现：

function [y1, y2] = SBX(x1, x2, VarMin, VarMax)eta = 15;u = rand(size(x1));beta = (2*u).^(1/(eta+1));y1 = 0.5*((1+beta).*x1 + (1-beta).*x2);y2 = 0.5*((1-beta).*x1 + (1+beta).*x2);% 边界处理
end

（2）多项式变异

多项式变异在解的邻域内引入小扰动：
$$y_i=x_i+\Delta$$
其中，$\Delta =(2u{)}^{1/(\eta +1)}-1$，$u\sim \text{Uniform}(0,1)$，$\eta$是变异指数（代码中为20）。

代码实现：

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

5. 算法流程与环境选择

（1）主循环

1. 非支配排序：计算每个解的支配数ranks；
2. 共享密度计算：计算小生境计数niche_count；
3. 适应度分配：结合支配数和密度调整适应度；
4. 锦标赛选择：基于适应度选择父代；
5. 交叉变异：生成子代；
6. 合并与选择：合并父代和子代，按支配数排序，保留最优的N个解。

（2）环境选择

代码采用简单的精英保留策略：

combined = [pop; offspring];  % 合并父代和子代
combined_cost = [pop_cost; offspring_cost];
new_ranks = NonDominatedSorting_array(combined_cost);  % 重新排序
[~, sorted_idx] = sort(new_ranks);  % 按支配数升序排列
pop = combined(sorted_idx(1:nPop), :);  % 保留最优的nPop个解

6. 可视化与性能分析

（1）Pareto前沿可视化

每代迭代绘制当前解集与理论Pareto前沿的对比：

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

（2）算法性能指标

• 收敛性：解集向理论Pareto前沿逼近的程度；
• 分布性：解集在Pareto前沿上的均匀程度（由共享机制保证）；
• 多样性：种群在目标空间的分散程度。

总结

该代码实现了一个经典的MOGA框架：

1. 非支配排序：通过支配数快速评估解的优劣；
2. 共享机制：通过目标空间密度调整适应度，实现均匀分布；
3. 高效遗传操作：SBX交叉和多项式变异适合连续优化问题。

这种方法在早期多目标优化中广泛应用，但计算复杂度较高（O(N²)），且共享参数（sigma_share）需人工调整。现代算法（如NSGA-II、MOEA/D）通过改进排序和多样性保持机制，在性能上更为优越。