您的当前位置：首页正文

随机蛙跳算法和NSGA2算法

来源：抵帆知识网

《智能算法及应用技术》

结课综述

Name: Moonlightran

Email: randolphingwp@163.com

1. 随机蛙跳（SFLA）算法 .................................................................................. 1

1.1 SFLA理论基础 ......................................................................................... 1 1.2 SFLA 的基本原理 .................................................................................... 3 1.3 SFLA 的基本概念 .................................................................................... 4 1.4 SFLA 的参数设置 .................................................................................... 4 1.5 SFLA 的运算流程 .................................................................................... 5 1.6 SFLA函数优化中实例 ........................................................................... 10 1.7 粒子群算法（PSO）函数优化 ............................................................. 14 2. 多目标优化算法(NSGA—II) ......................................................................... 19

2.1多目标优化问题描述.............................................................................. 19 2.2 基本概念................................................................................................. 19 2.3 非支配排序算法(NSGA) ....................................................................... 20 2.4 带精英策略的非支配排序遗传算法(NSGA—II) ................................ 22 2.5 NSGA-II函数优化实例 .......................................................................... 27

单目标和多目标优化算法介绍

——随机蛙跳算法和带精英策略的非支配排序算法

通常的优化问题可以分为单目标优化问题和多目标优化问题。针对这两类问题，分别介绍随机蛙跳算法（SFLA）和带精英策略的非支配排序算法（NSGA—II），并且给出这两类算法在函数优化中的应用实例。

1.随机蛙跳（SFLA）算法

随机蛙跳算法是由Kevin Lanes和Mustafa Eusuff于2003 年共同提出，该算法结合了基于遗传特性的模因算法和基于行为的粒子群算法的优点，适合解决各类组合优化问题。混合蛙跳算法具有设置参数少、简单易于理解、鲁棒性强等特点，已在语音情感识别、作业车间调度、复杂函数优化问题求解等领域得到成功应用。

1.1 SFLA理论基础

SFLA 是一种群体仿生类启发式进化计算方法，该算法将模因算法和粒子群优化算法的思想相结合，并经过适度扩展，因而兼具二者的优点。作为 SFLA的理论基础，模因算法和粒子群优化算法有必要进行简要介绍。

1.1.1模因算法

Moscato受Dawkin提出的 meme概念的启示，于1989年首次提出了模因算法。该算法源于文化进化理论中的隐喻思想，结合了全体成员参与搜索的思想和有选择性的特定个体搜索的机制，可以通过启发式搜索解决优化问题。模因算法在原理上与遗传算法很相似，不同的是该算法在原始遗传算法步骤中的交叉和变异步骤之后增加了一个小范围的局部进化过程，故模因算法也曾被叫做增加了局部搜索功能的遗传算法。给出模因算法的运算流程如图1.1所示。

开始编码产生初始种群局部搜索计算适应度满足停止准则YN选择交叉变异局部搜索产生新种群得出最优个体解码结束

图1.1模因算法流程

1.1.2粒子群算法

Kennedy和Eberhart受鸟群的群体飞行特性启发于1995年提出粒子群优化

算法，该算法是一种基于群体智能的自适应优化计算方法。假设有一群鸟，其中的所有个体均被称作一个“粒子”，这样的“粒子”被赋予速度和位置两种属性，在可行域中按照一定的规则飞行，目标是经过一定的进化次数找出待解问题的最佳参考方案。进化过程中，所有个体不断追随两个关键的极值以调整自己的位置和速度。其中一个极值是该粒子本身搜索到的最佳位置Pbest，即粒子自身的最优值；另外一个是粒子群中的所有成员中当前最优个体所在的位置Gbest，即全局最优解。

粒子群优化算法中个体的速度、位置更新公式如下：

kkVik1k1Vikc1rand()(PibestXik)c2rand()(GbestXik)（1.1）

Xik1XikVik1（1.2）

其中，Vik为第k次迭代中第i个粒子的速度。

Xik为第 k 次迭代中第i个粒子的位置。

kPibest为第 k 次迭代中第i个粒子的自身最优位置。 k为第 k 轮进化中的全局最优位置。 GbestRand()为位于范围[0,1]之间的随机数。

为粒子的惯性因子，c1为粒子的认知因子，控制Pik移动的幅度。 c2为粒子的社会因子，控制Gk移动的幅度。

粒子群优化算法的运算流程为： Step1：初始化粒子的速度和位置。 Step2：计算所有粒子的适应值。

Step3：比较各个粒子的当前适应值与其历史最优位置Pbest的适应值，如果前者优，则置此粒子当前最佳位置为Pbest。

Step4：比较各个粒子的当前适应值与其全局最优位置Gbest的适应值，若前者优，则置此粒子当前全局最佳位置为Gbest。

Step5：采用式（1.1）和式（2.1）更新种群中个体的速度和位置。 Step6：判断：若满足停止准则，则算法终止，否则转Step2。

上述两种算法核心思想的有机结合，即形成了所研究的混合蛙跳算法。

1.2 SFLA 的基本原理

SFLA 是基于群体智能的仿生类优化算法，种群（解集）由一些具有相同结构的青蛙（解）组成。SFLA模仿了青蛙群体的集体觅食活动。

为了寻找当前有限的食物源，在空间受限的一块区域内，一群青蛙首先按一定规则找准各自的初始位置。位置确定后，每只青蛙开始利用各自携带的个性化信息在自己所在位置附近寻找食物更丰富的位置，并通过跳跃更新自己的位置。寻找的规则是，蛙群通过充分发挥自身的自组织性，分别由个数基本相同的青蛙组团搜索，形成局部范围内的小团体，即为子种群。子种群内部，由局部精英个体带领其它个体进行搜索。每个子群搜索结束之后，所有个体重新组织起来，混合后重新按照规则分组，再执行组内搜索。组团搜索和群体混合迭代执行，直至找到最丰富的食物源。

对于 SFLA，每只青蛙被看作一个候选解，确定初始位置即为青蛙种群的初始化过程。组团搜索对应于种群的划分并执行局部搜索，此过程是 SFLA 最核心的步骤，本质上青蛙个体的位置更新发生于此阶段。子群的混合形成算法的混合运算，即全局信息交换。全局信息交换与局部深度搜索相互作用，为SFLA跳出局部极值提供了保证。

1.3 SFLA 的基本概念

1．青蛙：承载思想与信息的个体，构成种群的元素。 2．种群：由一定数量的青蛙组成的集合。

3．子种群：种群的子集。由所有青蛙构成的群体根据相应规则被划分为多个并行、独立的子集，这些子集被称为子种群，即局部小团体。

4．适应度：用来评价青蛙个体好坏的度量标准。

5．局部搜索：子种群内部个体的更新操作。按照一定的更新机制，子群内部的青蛙个体执行跳跃操作，从而消息得以在小团体内部传播和扩散。

6．混合运算：将各个子种群合并为一个种群的操作。将各个局部小团体进行合并，形成一个统一的群体，便于个体间的信息交流，为下一轮进化提供条件。

7．控制参数：SFLA 执行需要的控制参数，主要有：所有青蛙个体总数（种群规模），最大混合迭代次数，局部小团体（子种群）的个数，子种群内部进化代数，各局部团体中青蛙的个数，青蛙个体的维数，青蛙最大跳动步长等。

8．执行终止条件：

（1）在若干连续进化代数内，全局最优解没有得到刷新；（2）算法执行到初始设定的最大混合迭代次数。满足二者之一，算法即被强制终止。

1.4 SFLA 的参数设置

SFLA 的参数设置对算法的搜索性能具有非常重要的影响。SFLA 主要包括五个关键的参数，具体为：群体中青蛙个体数量F，算法的最大混合迭代次数G，子种群数量m ，各子种群的局部进化代数N，青蛙的最大允许跳跃距离Dmax。SFLA 的参数设置具体解释如下：

（1）群体中青蛙个体数量F：又称种群规模，指所有青蛙个体总数。一般而言是算法最重要的参数。青蛙个体数量越多，算法搜索到全局最优值的可能性也相应越大，但太大的种群规模会对搜索速度造成不利影响。

（2）算法的最大混合迭代次数G：此参数需要合理设置，如果G 过大，则导致算法复杂度增加；相反，如果G太小，将造成青蛙种群之间缺乏交流，影响青蛙向最优个体靠近。该参数的选取一般与问题的规模相关，规模越大，G的取值也相应越大。

（3）子种群数量m：此参数也需要合理地选择，m如果过小，导致每个子种群内部青蛙个数过多，参与局部搜索的个体相应过少，因此信息难以在子种群间充分交换，失去局部搜索的优势；但当m太大时，会造成每个子种群规模太小，因此会削弱局部模因搜索的优势，造成算法易于早熟收敛。

（4）各子种群的局部进化代数N：此参数也需要合理设置，过小的N会造成子种群内部青蛙个体频繁跳跃，减少了局部个体信息交流的机会；反之，若N过大，将会增加局部区域内算法早熟的可能性。

（5）青蛙的最大允许跳跃距离Dmax：此参数可在一定程度上控制算法的全局寻优能力。若Dmax太小，青蛙将在局部小范围跳动，容易陷入局部最优，削弱算法的全局搜索能力；而如果Dmax过大，青蛙将在可行域内大步跳跃，又容易造成错过最佳寻优位置。

SFLA 的研究起步相对较晚，就算法的参数设置而言，学术界尚未形成可遵循的指导性原则，多数情况下通过仿真实验测试得到一组设置。这也给不同学者针对经典SFLA的改进效果对比造成了一定困难。

1.5SFLA 的运算流程

SFLA 首先从可行域中随机地产生一组初始解构成初始种群，每个解对应于一只青蛙；接着计算各个青蛙的适应度值，按照适应度降序排列；然后以某种规则把整个青蛙种群划分为一定数量的子种群，在每个子种群内执行局部搜索，即根据指定的策略更新子种群内的最差青蛙，促使被更新个体向局部最优位置靠近。子种群进化结束后，各子种群之间进行信息交换实现混合运算。交替执行局部搜索和混合运算直至满足停止条件。

为说明SFLA的算法机理，以函数优化问题为例进行研究，问题如下：

minf(x)（1.3） s.t.x[l,u]其中[l,u]:{xS|lkxkuk,k1,2,S}。利用混合蛙跳算法求解该问题时，分为四个步骤：

1.初始化 2.子种群划分 3.局部搜索 4.其种群混合 1.5.1初始化

从可行域中随机产生F个解{x1,x2xF}作为初始种群，问题的纬数为S，

iiixi{x1,x2xS}为S纬空间的一个解(i1,2,F)。经典的SLFA初始化过程是

随机初始化的，种群分布不均匀，不利于算法在整个可行域空间上进行均匀搜索，进而有影响了算法的全局寻优的缺点，算法的初始化过程如图2中的伪代码所示：

图1.2经典SFLA的初始化过程

1.5.2子种群划分

计算每个解的目标函数值f(xi)(i1,2,F)，将目标函数值按照降序排列，并且将目标函数的最优值记为xg作为整个种群的最优解。将整个种群划分为m个子种群Y1,Y2,Ym，每个子种群包含n个解，即满足Fm*n。其中，第一个解进入Y1，第二个解进入Y2，直到第m个解进入Ym，然后将第m1个解进入Y1，以此类推，直至所有的解分配完毕。每个子种群中，目标函数最好和最差的解分别记为xb和xw。经典混合蛙跳算法中子种群的划分如图1.3中伪代码所示：

图1.3 经典SFLA的子种群划分过程

1.5.3局部搜索

在迭代过程中，各子种群只更新目标函数值最差的解xw，其更新公式为：

Dirand()*(xbxw),xwxwDi,DmaxDiDmax,i1,2,m;（1.4） i1,2,m（1.5）

其中，rand()为0到1之间的随机数，Di为青蛙的移动步长，Dmax表示允许青蛙移动的最大距离。式(5)对目标函数值最差的青蛙xw执行更新，即修改解的位置。

如果更新后得到比xw更好的解，则用更新后的解替代最差解；否则用xg代替式(4)中的xb，重新利用公式(4)、(5)计算新解；若仍得不到比xw更优的解，则随机产生一个新解去替换最差解，子种群中最差青蛙的位置就得到了更新。在指定迭代次数内重复执行以上操作，就完成了一轮子种群的局部搜索。经典混合蛙跳算法的局部搜索过程见图1.4所示。

图1.4 经典混合蛙跳算法的局部搜索过程

1.5.4子种群混合

将各子种群Y1,Y2Ym重新合并为X，即X{Y1Y2Y3Ym}，然后将X 重新按目标函数值降序排列，并用整个种群中最好的青蛙（即目标函数值最小）及时更新xg，重新划分子种群，进行下一轮的局部搜索。

经过上述四步即种群初始化、子种群划分、局部搜索、子种群混合，完成了SFLA 的一次迭代，解的位置也得到了更新。混合蛙跳算法的算法流程如图1.5所示。

开始初始化种群:确定种群规模F，子种群数m，每个子种群中青蛙个数n,子种群内的迭代次数计算每只青蛙的适应度，并将所有青蛙按适应度降序排列子种群划分：将F只青蛙按照一定的的规则划分到m个子种群中局部搜索，利用最差解更新公式，更新最差解更新后的最差解是否比原来最差解较优？YN用整个种群的最优解代替最差解更新公式中子种群中的最优解来更新最差解此解更新后的最差解是否比原来最差解较优？YN随机产生一个新解用新解替代原有的最差解子种群混合：所有青蛙混合、排序，准备进入下一轮迭代N满足终止条件？Y输出最优解结束图1.5 混合蛙跳算法流程

1.6 SFLA函数优化中实例

利用SFLA算法寻优实例函数如下：

f(x)sinx2y2xy22cos2xcos2y2e2.71289（1.6）

用matlab绘制出函数图像如图1.6所示，绘制图形代码如图1.7中所示。

图1.6 SFLA寻优函数图形

close all;clear;clc; x1=[-2:0.05:2] x2=[-1.5:0.05:1.5] [x1,x2]=meshgrid(x1,x2); y=sin( sqrt(x1.^2+x2.^2) )./sqrt(x1.^2+x2.^2)+exp((cos(2*pi*x1)+cos(2*pi*x2))/2)-2.71289; h=mesh(x1,x2,y); set(h,'EdgeColor','r','FaceColor','y'); 图1.7绘制函数图形matlab代码

从图中可以看出，该函数有很多的极大值点和极小值点，在(0,0)附近，极值估计在1左右。如果用普通的方法，很难准确的求到函数极值点。

接下来使用SFLA算法的来求解这个函数的极大值。为了和SFLA算法有一个对比。同时也用粒子群算法（PSO）来求这个函数的极大值。

一个完整的SFLA程序分为：参数设置、种群初始化、迭代寻优和结果显示几个部分，以下代码按照这几部分安排。

1.6.1 SFLA算法参数设置

SFLA参数设置程序如下所示： close all;clc;clear all; %清空运行环境 m=4; %种群分组数

n=50; %t每组青蛙包含的个数 Ne=50; %组内迭代数 smax = 50; %最大步长

MAXGEN=300; %种群总进化代数 d=2; %优化问题维数 pmax = 2; %d维最大值 pmin = -2;%d维最小值 1.6.2SFLA种群初始化 SFLA初始化程序如下所示： %%产生初始青娃 F=m*n; tic; for i1=1:F p(i1,:)=pmax*rands(1,d); end 适应度函数代码如下所示： function y = fun(x) %该函数用来计算适应度; % input 输入参数 % output 计算适应度值 y=sin( sqrt(x(1).^2+x(2).^2) )./sqrt(x(1).^2+x(2).^2)+exp((cos(2*pi*x(1))+cos(2*pi*x(2)))/2)-2.71289; end 1.6.3 SFLA迭代寻优 %%全局迭代寻优 yy=zeros(1,MAXGEN); for ii=1:MAXGEN for i2=1:F fitness(i2)=fun(p(i2,:)); 11

end

%排序，找最好的，并分组 [fitsort,index]=sort(fitness); fitsort=fitsort(end:-1:1); index=index(end:-1:1); for i3=1:F x(i3,:)=p(index(i3),:); end

gx=x(1,:);%种群内最好的青娃 yy(ii)=fitsort(1); % yy(ii)=fun(x(1,:)); % local=zeros(n,d); for i4=1:m local = p(i4:m:end,:);

for j=1:Ne %每组青蛙迭代次数 pb=local(1,:);%组内最优

pw=local(n,:);%组内最差

s1=rand.*(pb-pw);%采用组内最优更新 s1(find(s1>smax))=smax; temp= pw+s1;

temp(find(temp>pmax))=pmax; temp(find(temp fun(pw)

s1=rand.*(gx-pw);%采用全局最优更新 s1(find(s1>smax))=smax; temp=pw+s1;

temp(find(temp>pmax))=pmax; temp(find(tempif fun(temp)>fun(pw)

s1=pmax*rands(1,d);%随机更新 s1(find(s1>smax))=smax; temp=pw+s1;

temp(find(temp>pmax))=pmax;

temp(find(templocal(n,:) = temp; for loc=1:n fitlocal(loc)=fun(local(loc,:)); end

[localsort,indexlocal]=sort(fitlocal); localsort=localsort(end:-1:1); indexlocal=indexlocal(end:-1:1); for loc=1:n

localnew(loc,:) = local(indexlocal(loc),:); end local=localnew; end %结束Ne p(i4:m:end,:) =local; end %结束m %最好的青娃适配值 end %结束MAXGEN toc

1.6.4 结果分析

SFLA算法反复迭代300次，画出每一代最优个体适应度值变化图形，代码如下：

%结果分析 plot(yy) title('混合跬跳算法优化'); xlabel('总进化代数');ylabel('函数最优解'); fprintf(„%f\\n‟,gx); fprintf(„%f\\n‟,fun(gx)); 最优个体适应度值变化如图1.8所示，图1.9中给出所求极值的位置、还有程序运行所消耗的时间。

图1.8 最优个体适应度值曲线

图1.9 SFLA算法所求极值位置和消耗时间

从图1.8和1.9中可以看出，蛙跳算法运行300代，消耗14.7S时间。最终求得的最优个体适应度值为1.004737，对应的位置为（0.003306，0.003652），SFLA寻优值接近函数实际值，证明了SFLA算法具有较强的寻优能力。为了和SFLA算法对比，接下来我们使用粒子群算法对上述相同问题求解。

1.7 粒子群算法（PSO）函数优化

基于PSO算法函数优化的流程如下图1.10所示。

图1.10 PSO算法函数优化流程

其中，随机初始化粒子的速度和粒子的位置，速度和位置按照1.1和1.2中的公式更新。选择粒子种群大小为20，迭代次数为300次。适度函数和SFLA

算法中适度函数相同，程序代码如下：

%% 清空环境 close all; clc clear tic;

%% 参数初始化

%粒子群算法中的两个参数 c1 = 1.49445; c2 = 1.49445;

maxgen=300; % 进化次数 sizepop=20; %种群规模

Vmax=0.5; Vmin=-0.5; popmax=2; popmin=-2;

%% 产生初始粒子和速度 for i=1:sizepop

%随机产生一个种群

pop(i,:)=2*rands(1,2); %初始种群 V(i,:)=0.5*rands(1,2); %初始化速度 %计算适应度

fitness(i)=fun1(pop(i,:)); %染色体的适应度 end

%% 个体极值和群体极值

[bestfitnessbestindex]=max(fitness); zbest=pop(bestindex,:); %全局最佳 gbest=pop; %个体最佳

fitnessgbest=fitness; %个体最佳适应度值 fitnesszbest=bestfitness; %全局最佳适应度值

%% 迭代寻优 for i=1:maxgen

for j=1:sizepop

%速度更新

V(j,:) = V(j,:) + c1*rand*(gbest(j,:) - pop(j,:)) + c2*rand*(zbest -

pop(j,:));

V(j,find(V(j,:)>Vmax))=Vmax; V(j,find(V(j,:)%种群更新 pop(j,:)=pop(j,:)+V(j,:);

pop(j,find(pop(j,:)>popmax))=popmax; pop(j,find(pop(j,:)%适应度值 fitness(j)=fun1(pop(j,:));

end

for j=1:sizepop

%个体最优更新

if fitness(j) >fitnessgbest(j) gbest(j,:) = pop(j,:);

fitnessgbest(j) = fitness(j); end

%群体最优更新

if fitness(j) >fitnesszbest zbest = pop(j,:);

fitnesszbest = fitness(j); end end

yy(i)=fitnesszbest; end toc

%% 结果分析 figure(1); plot(yy);

title('最优个体适应度','fontsize',12); xlabel('进化代数','fontsize',12); ylabel('适应度','fontsize',12); fprintf('%f\\n',zbest);

适应度函数如下所示：

function y = fun1(x) %函数用于计算粒子适应度值 %x input 输入粒子 16

%y output 粒子适应度值 y=sin( sqrt(x(1).^2+x(2).^2) )./sqrt(x(1).^2+x(2).^2)+exp((cos(2*pi*x(1))+cos(2*pi*x(2)))/2)-2.71289; end 使用PSO算法最优个体适应度值变化如图1.11所示，图1.12中给出所求极值的位置、还有程序运行所消耗的时间。

图1.11 PSO算法最优个体适应度值

图1.12 PSO算法所求极值位置和消耗时间

从图1.11和1.12中可以看出，蛙跳算法运行300代，消耗0.096644S时间。最终求得的最优个体适应度值为1.005375，对应的位置为（0.000792，0.00044），单从结果上看，PSO比SFLA效率高很多。

接下来，我们简单使SFLA算法和PSO算法分别对上述问题求解10次，结果如图1.13所示。

从结果中可以看到，PSO算法运行效率高，SFLA算法消耗时间大，从结果精度来看，PSO算法有些高于SFLA算法，有些低于SFLA算法结果。可见PSO求解问题非常不稳定。在实际问题的求解过程中，不仅仅要追求算法的精度，而且算法的稳定性也是至关重要的，在这方面，SFLA算法明显要优于PSO算法。

(a) SFLA算法求解结果(b) PSO算法求解结果

图1.13SFLA算法和PSO算法对比18

2. 多目标优化算法(NSGA—II)

2.1多目标优化问题描述

工程中经常会遇到多准则或多设计目标下的设计和决策问题,这些目标往往是相悖的,要找到满足这些目标的最佳设计方案,就要解决多目标和多约束的优化问题,即多目标优化(Multi—objective Optimization)问题。

通常考虑的多目标优化问题，可以定义为在一组约束条件下,极大化(或极小化)多个不同的目标函数,其一般形式：

min/max{f1(X),f2(X),fn(X)}s.t. (2.1) g(X)0j1,2,JJhk(X)0,k1,2,K其中X{x1,x2xp}是一个p纬向量，fi(X)是目标函数，i1,2,n，gJ(X)0和hk(X)0是系统约束，j1,2,J,k1,2,K。

2.2 基本概念

2.2.1Pareto支配关系

对于最小化多目标问题,n个目标分量fi(i1,2,n)组成的向量

f(X)(f1(X),f2(X),fn(X))，任意给定两个决策变量Xu,XvU：

当且仅当，对于i{1,2n}，都有fi(Xu)fi(Xv)，则Xu支配Xv。当且仅当，对于i{1,2n}，有fi(Xu)fi(Xv)，且至少存在一个j{1,2n}，使fi(Xu)fi(Xv)，则Xu弱支配Xv。

当且仅当，存在i{1,2n}，使fi(Xu)fi(Xv)，同时，j{1,2n}，使

fj(Xu)fj(Xv)，则Xu和Xv不互相支配。

2.2.2 Pareto最优解定义

多目标优化问题与单目标优化问题有很大差异。当只有一个目标函数时,人们寻找最好的解，这个解优于其他所有解,通常是全局最大或最小，即全局最优解。而当存在多个目标时，由于目标之间存在冲突无法比较,所以很难找到一个解使得所有的目标函数同时最优,也就是说，一个解可能对于某个目标函数是最好的，但对于其他的目标函数却不是最好的，甚至是最差的。因此,对于多目标优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是：无法在改进任何目标函数的同时不削弱至少一个其他目标函数。

这种解称作非支配解(non-dominatedsolutions)或Pareto最优解(Pareto Optimal Solutions)，其定义如下：

对于最小化多目标问题，n个目标分量fi(i1,2,n)组成的向量

f(X)(f1(X),f2(X),fn(X))，XuU为决策变量，若Xu为Pareto最有解，则需要满足：

当且仅当，不存在决策变量XvU，vf(Xv)(v1,v2vn)支配

uf(Xu)(u1,u2un)，即不存在XvU使的下式成立：

i{1,2n},viui,i{1,2,n}|viui

Pareto最优概念由法国经济学家Pareto于1896年提出的。他是建立在集合论基础上的对多目标解的一种向量评估方式。传统的数学规划法与模拟退火算法是以单点搜索为特征的串行算法，无法利用Pareto最优概念对解进行评估。因此，Pareto最优概念提出百余年仍无传统算法意义上的相关算法。基于种群操作的演化算法可以隐并行地搜索解空间的多个解，并能利用不同解之间的相似性提高其并行求解问题效率，与Pareto最优概念相结合，则有可能产生真正基于Pareto最优概念的多目标优化的演化算法,实现对非劣最优解集的搜索。

2.3 非支配排序算法(NSGA)

1995年，Srinivas和Dee提出了非支配排序遗传算法(Non-dominated sorting Genetic Algorithms, NSGA)。这是一种基于Pareto最优概念的遗传算法，是众多的多目标优化遗传算法中体现Goldberg思想最直接的方法。

2.3.1 基本原理

NSGA与简单的遗传算法的主要区别在于：该算法在选择算子执行之前根据个体之间的支配关系进行了分层。其选择算子、交叉算子和变异算子与简单遗传算法没有区别。

在选择操作执行之前,种群根据个体之间的支配与非支配关系进行排序。首先，找出该种群中的所有非支配个体,并赋予他们一个共享的虚拟适应度值，得到第一个非支配最优层;然后,忽略这组己分层的个体，对种群中的其它个体继续按照支配与非支配关系进行分层，并赋予它们一个新的虚拟适应度值,该值要小于上一层的值，对剩下的个体继续上述操作，直到种群中的所有个体都被分层。

算法根据适应度共享对虚拟适应值重新指定，比如指定第一层个体的虚拟适应值为1，第二层个体的虚拟适应值应该相应减少，可取为0.9，依此类推。这样，可使虚拟适应值规范化，保持优良个体适应度的优势，以获得更多的复制机会，同时也维持了种群的多样性。

由于采用了适度共享，对于在共享半径share内的个体适应度相应减少为

f(x)。公式中，x,y为个体；f(x)为个体x共享后的适应度值；f(x)yps(d(x,y))f(x)为个体x共享前的适应度值；s为共享函数，d为距离函数，P为种群，为常数。

共享函数s表示个体x和小生境群体中其他个体的关系。

d(x,y))1(s(d(x,y))share0若d(x,y)share其它 (2.2)

其中share为共享半径。更具距离函数d(x,y)定义的不同，共享方式可以分为：编码

空间中的适应度共享，决策变量空间中的适应度共享，以及目标函数空间中的适应度共享。

2.3.2 一般流程

NSGA采用的非支配分层方法，可以使好的个体有更大的机会遗传到下一代。适应度共享策略则使得准Pareto面上的个体均匀分布，保持了群体的多样性，克服了超级个体的过度繁殖，防止了早熟收敛。算法流程如下图所示：

开始进化代数gen=0初始化种群Front=1种群全部分级N识别非支配个体Y根据虚拟适应度进行复制指定虚拟适应度应用于适应度共享小生境gen=gen+1交叉Front=Front+1变异N进化代数gen大于最大代数Y结束

图2.1 NSGA工作原理流程

2.4 带精英策略的非支配排序遗传算法(NSGA—II)

非支配排序遗传算法(NSGA)在许多问题上得到了应用，但是仍然存在一些问题：

a) 计算复杂度高，为O(mN3)（m为目标函数，N为种群大小），所以当种群较大时，计算相当耗时。

b) 没有精英策略，精英策略可以加速算法的执行速度，而且能在一定程度上确保已经找到的满意解不丢失。

c) 需要指定共享半径share。

因此，在2000年，Deb又提出NSGA的改进算法—带精英策略的非支配排序遗传算法(NSGA—II)。NSGA-II针对以上的缺陷进行了以下三个方面的改进：

a) 提出了快速非支配排序算法，降低了算法的复杂度。由原来的O(mN3)变

为O(mN2)（m为目标函数，N为种群大小）。

b) 提出拥挤度和拥挤度比较算子，代替了需要指定共享半径的适应度共享策略，并在快速排序后的同级比较中作为胜出标准，使准Pareto域中的个体能扩展到整个Pareto域，并且均匀分布，保持了种群的多样性。

c) 引入精英策略，扩大采样空间。将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，并且通过对种群中所有个体的分层存放，使得最佳个体不会丢失，迅速提高种群水平。

2.4.1 快速非支配排序算法

NSGA-II对第一代算法中非支配排序方法进行了改进：对于每个个体i都设有以下两个参数ni和Si为在种群中支配个体i的解个体的数量，Si为被个体i所支配的解个体的集合。首先，找到种群中所有ni0的个体，将它们存入当前集合F1，然后对于当前集合F1中的每个个体j，考察它所支配的个体集Sj，将集合Sj中的每个个体k的nk减去1，即支配个体k的解个体数减1（因为支配个体k的个体j已经存放在当前集合F1），如果nk10则将个体k存入另一个集合H。最后，将F1作为第一级非支配个体集合，并赋予该集合内个体一个相同的非支配序irank，然后继续对H作上述分级操作并赋予相应的非支配序，直到所有的个体都被分级。其计算复杂度为O(mN2)，m为目标函数，N为种群大小。

上述非支配排序的伪代码如下：函数sort(P) 对每一个iP Si；ni0 对每一个jP 若i支配j，则SiS1{j} 否则nini1 若ni0，则irank1；F1F1{i} 23

p1 \\\\ p为非支配层数，初始值为1；当Fp时 H 对每个iFp 对每个jSi njnj1 若nj0，则jrankp1；HH{j} pp1 FpH 2.4.2确定拥挤度

在原来的NSGA中，我们采用共享函数以确保种群的多样性，但这需要由决策者指定共享半径share的值。为了解决这个问题，我们提出了拥挤度概念：在种群中

的给定点的周围个体的密度，用id表示，它指出了在个体i周围包含个体i本身但不包含其他个体的最小长方形，如下图所示：

图2.2个体i的拥挤度

拥挤度计算伪代码如下所示，其中I为种群的为支配集：函数Crowding-Distance(I) 24

lI\\\\集合I中解个体的个数对每一个i，I[i]d0\\\\每个个体i的拥挤度初始值为0 对每个目标函数m Isort(I,m) I[1]dI[l]d 从i2到l1循环 maxminI[i]dI[i]d(I[i1]mI[i1]m)/(fmfm) 这里，I[i]m表示集合I中的第i个个体对于第m个目标函数的值。sort(l,m)指在目标函数m下对个体进行非支配排序。算法的复杂性取决于排序的复杂性，最极端情况下，当所有的个体都在一个非支配集里时，计算复杂度为O(mNlgN)。

2.4.3拥挤度比较算子

从上图中可以看出，id值比较小的时候表示该个体周围比较拥挤。为了维持种群的

多样性，我们需要一个比较拥挤度的算子以确保算法能够收敛到一个均匀分布的Pareto面上。

由于经过了排序和拥挤度的计算，群体中每个个体i都得到两个属性：非支配

序irank和拥挤度id，则定义偏序关系n：当满足条件irankjrank，或满足irankjrank且

idjd时，定义inj。也就是说：如果两个个体的非支配排序不同，取排序号较小的个

体（分层排序时,先被分离出来的个体）；如果两个个体在同一级，取周围较不拥挤的个体。

2.4.4 NSGA-II算法主流程

首先，随机初始化一个父代种群P0，并将所有个体按非支配关系排序且指定一个适应度值，如：可以指定适应度值等于其非支配序irank，则1是最佳适应度值。然后，采用选择、交叉、变异算子产生下一代种群Q0，大小为N

NSGA-II算法的主要流程如下：

RtPtQt Fsort(Rt) Pt1 从i1开始计算Fi中个体的拥挤度 Pt1Pt1Fi ii1 直到Pt1FiN sort(Fi,n) Pt1Pt1Fi[1:(NPt1) Qt1new(Pt1) tt1 如下图所示，首先将第t代产生的新种群Qt与父代Pt合并组成Rt，种群大小为2N。

然后Rt进行非支配排序，产生一系列非支配集Fi并且计算拥挤度。由于子代和父代个体都包含在Rt中，则经过非支配排序以后的非支配集F1中包含的个体是Rt中最好的，所以先将

F1放入新的父代种群Pt1中。如果F1的大小小于N，则继续向Pt1中填充下一级非支配集

直到添加F3时，种群的大小超出N，对F3中的个体进行拥挤度排序（sort(F3,n)），F2，

取前NPt1个体数量达到N。然后通过遗传算子（选择、交叉和变异）t1个个体，使P产生新的子代种群Qt1。

图2.3NSGA-II流程

算法的整体复杂性为O(mN2)，由算法的非支配排序部分决定。当排序产生的非支

配集的个体数目足够填充Pt1时，就不必再继续对剩下的部分排序了。非支配解的多样性由拥挤度比较算子保证，不需要额外的共享参数\"通过对当前解和种群中所有个体的分级存放，使得最佳个体不会丢失。

2.5NSGA-II函数优化实例

在多目标优化问题中，所求的解通常是矛盾的。如图2.4中所示的多目标优化问题，目标函数f1和f2是互相矛盾的。某一个目标函数性能的提高需要以另一个目标

函数性能的降低为代价，称这样的解A和B是非劣解，或者说是Pareto最优解。多目标优化算法就是要找这些Pareto最优解。

图2.4多目标优化问题

我们待优化的目标函数为：

f1(x)1e4x1sin6(6x1)f(x)g(x)(1(f1(x))2)(2.3) 2g(x)27

其中g(x)19(xi0.25)，0xi1,i1,2,6 i146我们的目的就是寻找式2.3的Pareto最优解。

NSGA-II算法求解上述问题的程序可在http://pan.baidu.com/s/1gdKqMJ5下载。程序中参数的设置如下表： Population 200 Generations Pool Size 1000 100 Tour Size 2 C 20 m 20 2.3中目标函数的Pareto最优解集如下图2.5中所示。

图2.5 Pareto最优解集

接下来我们用NSGA-II去求三个目标函数的的Pareto最优解。目标函数如2.4

中所示。

f1(x)(1g(x))cos(0.5x1)cos(0.5x2)f2(x)(1g(x))cos(0.5x1)sin(0.5x2) (2.4) f3(x)(1g(x))sin(0.5x1)其中g(x)(xi112i0.5)2，0xi1,i1,2,12

程序和求解2.3中程序相同，其中参数的设置如下表： Population 200 Generations Pool Size 1000 100 Tour Size 2 C 20 m 20 所求解多目标函数的Pareto最优解集如下图2.6中所示。

图2.6 Pareto最优解集

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文