一、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]
f =
179.674882486581 903.730955686099 1052.75541840183
>>
参考文献:
[1]Srinivas, N., Deb, Kalyanmoy, Multiobjective Function Optimization Using Nondominated Sorting Genetic Algorithms,2000/06/25
标签:variablenumbmyer,16.8384405583322,个体,15.6347508056251,算法,MATLAB,9.66324284191394 From: https://blog.csdn.net/corn1949/article/details/136987236