用MATLAB实现nsgaII算法求解多目标问题

一、nsgaII算法简介

NSGA-II（非支配排序遗传算法II）是一种多目标优化算法，2000年由Srinivas, N., Deb, Kalyanmoy提出，是一种效果非常好的多目标优化算法，尤其是其中的快速非支配排序，极大提高了算法的运行效率。

其基本步骤如下：

1.初始化种群：

随机生成一个包含多个个体的初始种群。每个个体都代表一个潜在的解。
2.计算适应度：

针对每个个体，计算其在目标函数空间中的适应度。适应度函数值反映了个体在多目标优化问题中的优劣程度。
3.快速非支配排序：

利用Pareto最优解的概念将种群中的个体进行分级。非支配状态越高的个体层级越靠前，从而能够挑选出个体中较为优异的，使其有较大机会进入下一迭代。具体算法如下：
首先找到种群中N(i)=0的个体，将它存入到当前集合F1。N(i)表示种群中支配个体i的解个体的数量。
然后对于当前集合F1中的每个个体j，考察它所支配的个体集S(j)，将集合S(j)中的每个个体k的n(k)减去1，即支配个体k的解个体数减1（因为支配个体k的个体j已经存入当前集F1）。n(k)表示被个体k所支配的解个体的数量。
如n(k)-1=0则将个体k存入另一个集F2。
最后，将F1作为第一级非支配个体集合，并赋予该集合内个体一个相同的非支配序i(rank)，然后继续对H作上述分级操作并赋予相应的非支配序，直到所有的个体都被分级。
4.拥挤距离计算：

为了保持Pareto前沿的多样性，NSGA-II计算拥挤距离，以度量个体在目标空间的密度。拥挤距离越大，个体之间的距离越远，从而有助于保持Pareto前沿上的均匀分布。针对每个等级，计算个体之间的拥挤距离。
5.选择操作：

NSGA-II使用二元锦标赛（binary tournament）作为选择操作。在每代中，首先使用二元锦标赛选择操作从当前种群中随机选择两个个体，然后选择其中具有更高非支配级别的个体。如果非支配级别相同，则选择拥挤距离较大的个体。
6.交叉操作：

对选定的父代个体进行交叉操作，生成新的子代个体。交叉方式有多种，如单点交叉、多点交叉等。
7.变异操作：

对子代个体进行变异操作，增加种群的多样性。变异方式有多种，如随机变异、均匀变异等。
8.重复步骤2-7，直到满足终止条件（如达到最大迭代次数或找到满意的解）。

总体流程如下图所示：

二、用MATLAB实现nsgaII算法

MATLAB主程序如下：

%% nsgaIInsgaII算法优化多目标
clc;close all;clear all;warning off;%清除变量
rand('seed', 100);
randn('seed', 100);
format long g;

global C1 C2 C3;
C1=randi([0,20],1,20);
C2=randi([10,20],1,20);
C3=randi([10,20],1,20);

%% 设置变量上下限
lbmy=0*ones(1,20);
ubmy=20*ones(1,20);

%% 设置模型参数
objnumbemyr=3;% 目标函数个数
variablenumbmyer=length(lbmy);% 变量个数


%% 设置算法参数
popsizemy=20;%种群数
maxgenmy=200;%迭代次数
PMmy=0.1;% 变异率
PCmy=0.7;% 交叉率

%% 算法主体
Chrommy=inivariables(popsizemy,objnumbemyr,variablenumbmyer,lbmy,ubmy);% 初始化算子
Chrommy=nondominationsort(Chrommy, objnumbemyr, variablenumbmyer);% 非支配快速排序算子

value_cellmy=cell(objnumbemyr,1);
for i=1:objnumbemyr
    value20imy=zeros(maxgenmy,2);
    value_cellmy{i,1}=value20imy;
end

tic;

wait_handmy=waitbar(0,'running...', 'tag', 'TMWWaitbar');
tourmy=2;
for genmy=1:maxgenmy
    %% 遗传算子
    poolmy=round(popsizemy/2);
    parent_chromosome=tournaselect(Chrommy,poolmy,tourmy);% 竞标赛算子
    off2chrommy=mutationcross(parent_chromosome,objnumbemyr,variablenumbmyer,lbmy,ubmy,PMmy,PCmy);% 变异和交叉算子
    mainpmy=size(Chrommy,1);
    offspring_popmy=size(off2chrommy,1);
    tempchrommy(1:mainpmy,:)=Chrommy;
    tempchrommy(mainpmy+1:mainpmy+offspring_popmy,1:objnumbemyr+variablenumbmyer)=off2chrommy;
    tempchrommy=nondominationsort(tempchrommy,objnumbemyr,variablenumbmyer);% 非支配快速排序算子
    Chrommy=replacechrom(tempchrommy,objnumbemyr,variablenumbmyer,popsizemy);% 选择算子
    
    %% 记录每代结果
    for i=1:objnumbemyr
        value20imy=value_cellmy{i,1};
        value20imy(genmy,1)=min(Chrommy(:,variablenumbmyer+i));
        value20imy(genmy,2)=mean(Chrommy(:,variablenumbmyer+i));
        value_cellmy{i,1}=value20imy;
    end;
    
    waitbar(genmy/maxgenmy,wait_handmy);%每循环一次更新一次进步条
end
delete(wait_handmy);%执行完后删除该进度条

disp('算法运行时间');
runtime201=toc

%% 输出结果
% 迭代图
for i=1:objnumbemyr
    value20imy=value_cellmy{i,1};
    figure;
    plot(value20imy(:,1),'r-','linewidth',1.5);
    xlabel('迭代次数','fontname','宋体');
    ylabel(['f',num2str(i)],'fontname','宋体');
    title(['nsgaII算法的f',num2str(i),'的迭代曲线'],'fontname','宋体');
end

%
dominatedmatmy=determinedomination(Chrommy(:,variablenumbmyer+1:variablenumbmyer+objnumbemyr));% 找出非支配解
h_dominate= dominatedmatmy==0;
[mat2,indexa1]=matuniquefun(Chrommy(h_dominate,variablenumbmyer+1:variablenumbmyer+objnumbemyr));% 找出不重复的前沿集
index99= find(h_dominate);
indexselect=index99(indexa1);
paretomatmy=Chrommy(indexselect,1:variablenumbmyer);
NDvaluemy=Chrommy(indexselect,variablenumbmyer+1:variablenumbmyer+objnumbemyr);%


% 绘制帕累托前沿图
figure;
plot3(NDvaluemy(:,1),NDvaluemy(:,2),NDvaluemy(:,3),'r.','markersize',35);
xlabel('f1','fontname','宋体');
ylabel('f2','fontname','宋体');
zlabel('f3','fontname','宋体');
grid on;
title('NSGAII算法优化目标函数的帕累托前沿','fontname','宋体');

outcell201=cell(1,variablenumbmyer+1);
outcell201{1,1}='非支配解编号';
for i=1:variablenumbmyer
    outcell201{1,i+1}=['自变量',num2str(i)];
end

outcell202my=cell(1,objnumbemyr);
for i=1:objnumbemyr
    outcell202my{1,i}=['目标',num2str(i)];
end


outcell203=[outcell201,outcell202my;
    num2cell([(1:size(NDvaluemy,1))',paretomatmy,NDvaluemy])]

[vmin,indexmin]=min(NDvaluemy(:,1));

x=paretomatmy(indexmin,:);
f=myfun(x,objnumbemyr,variablenumbmyer)




xlswrite('输出_非支配解.xlsx',outcell203);

由于子函数较多，就不一一放上来了。

程序结果如下：

算法运行时间

runtime201 =

2.0492504

outcell203 =

1 至 8 列

'非支配解编号' '自变量1' '自变量2' '自变量3' '自变量4' '自变量5' '自变量6' '自变量7'
[ 1] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [8.05348188060032] [12.4611740803631] [12.8089197784704]
[ 2] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [8.05348188060032] [12.4611740803631] [12.8089197784704]
[ 3] [9.17894392701748] [6.34999871549662] [1.38464754511819] [13.2378207581294] [7.23657722921883] [18.5588485182071] [12.8089197784704]
[ 4] [9.17894392701748] [6.34999871549662] [1.38464754511819] [13.2378207581294] [8.05348188060032] [ 17.166124292261] [12.8089197784704]
[ 5] [9.17894392701748] [6.34999871549662] [1.38464754511819] [13.2378207581294] [7.23657722921883] [18.5588485182071] [12.8089197784704]
[ 6] [9.17894392701748] [6.34999871549662] [1.38464754511819] [13.2378207581294] [8.05348188060032] [18.5588485182071] [12.8089197784704]
[ 7] [9.17894392701748] [6.34999871549662] [1.38464754511819] [13.2378207581294] [7.23657722921883] [18.5588485182071] [12.8089197784704]
[ 8] [9.17894392701748] [6.34999871549662] [5.36612482991355] [13.2378207581294] [8.05348188060032] [18.5588485182071] [12.8089197784704]
[ 9] [9.17894392701748] [6.34999871549662] [5.36612482991355] [13.2378207581294] [8.05348188060032] [18.5588485182071] [12.8089197784704]
[ 10] [9.17894392701748] [10.5105813827881] [5.36612482991355] [13.2378207581294] [8.05348188060032] [18.5588485182071] [12.8089197784704]
[ 11] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [7.23657722921883] [ 17.166124292261] [12.8089197784704]
[ 12] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [8.05348188060032] [12.4611740803631] [12.8089197784704]
[ 13] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [8.05348188060032] [12.4611740803631] [12.8089197784704]
[ 14] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [8.05348188060032] [12.4611740803631] [12.8089197784704]
[ 15] [9.17894392701748] [10.5105813827881] [5.36612482991355] [13.2378207581294] [8.05348188060032] [18.5588485182071] [12.8089197784704]
[ 16] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [7.23657722921883] [18.5588485182071] [12.8089197784704]
[ 17] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [8.05348188060032] [12.4611740803631] [12.8089197784704]
[ 18] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [8.05348188060032] [12.4611740803631] [12.8089197784704]
[ 19] [9.17894392701748] [10.5105813827881] [11.3413005188765] [13.2378207581294] [7.23657722921883] [ 17.166124292261] [12.8089197784704]

9 至 15 列

'自变量8' '自变量9' '自变量10' '自变量11' '自变量12' '自变量13' '自变量14'
[ 14.328538688984] [16.8384405583322] [13.9768943441924] [9.66324284191394] [13.7790538248508] [18.3260797701432] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [13.9768943441924] [9.66324284191394] [13.7790538248508] [18.3260797701432] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [9.93878627658765] [9.66324284191394] [2.29010590458759] [9.80993840368927] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [9.93878627658765] [9.66324284191394] [2.29010590458759] [9.80993840368927] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [9.93878627658765] [9.66324284191394] [2.29010590458759] [9.80993840368927] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [9.93878627658765] [9.66324284191394] [2.29010590458759] [ 16.912497094326] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [9.93878627658765] [9.66324284191394] [10.1317149541023] [9.80993840368927] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [9.93878627658765] [9.66324284191394] [2.29010590458759] [ 16.912497094326] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [13.9768943441924] [9.66324284191394] [10.1317149541023] [9.80993840368927] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [9.93878627658765] [9.66324284191394] [2.29010590458759] [18.3260797701432] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [9.93878627658765] [9.66324284191394] [10.1224440476496] [9.80993840368927] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [13.9768943441924] [9.66324284191394] [10.1317149541023] [9.80993840368927] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [13.9768943441924] [9.66324284191394] [2.29010590458759] [ 16.912497094326] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [13.9768943441924] [9.66324284191394] [13.7790538248508] [18.3260797701432] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [9.93878627658765] [9.66324284191394] [13.7790538248508] [18.3260797701432] [15.6347508056251]
[19.9824183154769] [16.8384405583322] [9.93878627658765] [9.66324284191394] [10.1224440476496] [18.3260797701432] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [13.9768943441924] [9.66324284191394] [13.7790538248508] [18.3260797701432] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [13.9768943441924] [9.66324284191394] [10.1224440476496] [18.3260797701432] [15.6347508056251]
[ 14.328538688984] [16.8384405583322] [13.9768943441924] [9.66324284191394] [13.7790538248508] [18.3260797701432] [15.6347508056251]

16 至 22 列

'自变量15' '自变量16' '自变量17' '自变量18' '自变量19' '自变量20' '目标1'
[ 13.256790141229] [17.4296211811852] [ 11.149273957661] [16.9203746583873] [15.04038293615] [16.3437077199778] [ 1002.6634005046]
[ 13.256790141229] [17.4296211811852] [11.0478903870321] [16.9203746583873] [15.04038293615] [16.3437077199778] [1002.84617842059]
[10.7819523619404] [1.82563634674327] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [179.674882486581]
[10.7819523619404] [1.82563634674327] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [183.897223255497]
[10.7819523619404] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [193.287390255497]
[10.7819523619404] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [242.087738211538]
[10.7819523619404] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [259.328016914391]
[10.7819523619404] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [268.965785077551]
[10.7819523619404] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [327.300508978337]
[10.7819523619404] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [352.335445320093]
[10.7819523619404] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [450.882332226453]
[10.7819523619404] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [531.520612507838]
[10.7819523619404] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [16.3437077199778] [604.595173560818]
[ 13.256790141229] [6.87190363503615] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [718.072375787898]
[ 13.256790141229] [17.4296211811852] [ 11.149273957661] [16.9203746583873] [15.04038293615] [9.95266926938326] [728.862684004153]
[ 13.256790141229] [17.4296211811852] [ 11.149273957661] [16.9203746583873] [15.04038293615] [16.3437077199778] [859.301186552929]
[2.68816179721065] [17.4296211811852] [11.0478903870321] [16.9203746583873] [15.04038293615] [16.3437077199778] [897.741677484101]
[ 13.256790141229] [17.4296211811852] [ 11.149273957661] [16.9203746583873] [15.04038293615] [16.3437077199778] [929.891388803066]
[ 13.256790141229] [17.4296211811852] [ 11.149273957661] [16.9203746583873] [15.04038293615] [16.3437077199778] [962.216400921353]

23 至 24 列

'目标2' '目标3'
[170.106808592635] [263.335379848433]
[ 170.08681936737] [263.720924905683]
[903.730955686099] [1052.75541840183]
[884.223198378976] [1030.94438279645]
[755.862910229643] [935.164976675134]
[652.809228556372] [906.404500513756]
[696.437792096302] [734.590895650529]
[576.168866017706] [837.727092544681]
[570.326857586895] [611.634318181029]
[498.128227390577] [782.143446010307]
[482.201576981102] [543.185131229793]
[425.077003471592] [462.265283026859]
[366.527443393372] [628.672349647459]
[338.401437463402] [355.501626541117]
[308.438257846463] [409.401314709731]
[270.715390382254] [413.731195896791]
[255.217628623206] [517.949787665813]
[ 155.84055332632] [314.888100571741]
[186.512166944944] [295.292920442807]