遗传算法课程报告

NSGA-II遗传算法一背景NSGA是由Srinivas和Deb于20世纪90年代初期提出的，它的高效性在于运用一个 非支配分类程序，使多目标简化至一个适应度函数的方式。该方法能解决任意数目的目标问 题，并且能够求最大和最小的问题。Deb于2002年对NSGA进行了改进，提出了 NSGA-II, 一种快速的非劣性排序方法：定义了拥挤距离估计某个点周围的解密度取代适应值共享。NSGA-II有效克服了 NSGA的三大缺陷：计算复杂性从O ( mN3)降至O ( mN2)，具 备最优保留机制及无需确定一个共享参数。进一步提高了计算效率和算法的鲁棒性。该算法 得到的非劣解再目标空间分布均匀，收敛性和鲁棒性好，已成为进化多目标优化里关于的基 准算法之一。二. NSGA-II 简介在NSGA-II算法中，种群的初始化和普通的遗传算法一样，在决策变量的定义域区间 随机产生。初始化之后，对群体进行非支配性排序，使个体进入各自的前沿集合。非支配性 个体属于第一前沿集合P，只受第一前沿集合个体直接支配个体属于第二前沿P，依次类推。1 2并且处于同一前沿集合的个体具有相同的秩(rank)。秩的大小等于个体所处的第几前沿数。 第一前沿P的个体的秩为1,第二前沿P的个体的秩为2,依次类推。1 2此外，每个个体除有秩这个参数之外，还有一个参数聚集距离(crowding distance )。用来衡量个体与其相邻的个体间的聚集度。较大的聚集距离意味着在种群中具有较好的分布 性。种群中父个体的选择采用基于秩和聚集距离的二进制锦标赛选择方式。具有较小秩的个 体优先选择。若两个体秩相同，具有较大聚集距离的个体优先选择。所选择父个体种群经变 异和杂交之后产生子种群，在与原来产生父个体的种群进行合并，经非支配性排序之后产生 下一代群体。三. NSGA-II详细介绍3.1构造非支配集该算法有两部分组成，第一部分用于计算n和S。其中n表示支配个体i的个体总数, iiiS表示个体i所支配的个体集合。第二部分用于求P,P,P,.。P表示第i个前沿集合。i123ifast-nondominated-sort( Pop) for each p e Pop for each q e Pop thenif ( p dominated q ) then / p 支配己 qS = S uqp pelse if ( q dominated p ) then / q 支配 pn = n + 1p pend for qif ( n = 0 ) then P1 = P1 u pi = 1;while(Pi != 0 ) H = 0 for each p e Pi for each q e Spn = n -1 ;q qif (nq = 0) then H = H U q end for pi = i + 1;P. = H;iend for while end for fast-nondominated-sort3.2聚集距离计算在产生新群体时，通常将优秀的同时聚集距离较大的个体保留下来参与下一代进化。聚 集密度小的个体其聚集距离反而大，一个个体的聚集距离可以通过计算与其相邻的两个个体 在每个子目标的差距之和来求取。因此需要对个体p的每个个体按目标函数进行排序，这里 选择快排。如下图所示，设有两个子目标f和f ,个体i的聚集距离是图中虚线四边形的1 2长与宽之和。贝I目标空间的i 的聚集距离 Pi.=distance(Pi+1.f Pil.f ) + (Pi+l.f -Pi-1.f )11 2 2Cuboidi-h图i聚集距离计算计算个体间的聚集距离如下： crowding-distance-assignment(P) N = IPI/ N为种群的大小distancemP = sort(P,m);P0= PN-1=distancedistancefor each i = 1 to (N-2)Pi=卩用 +(Pi+1.m - Pi-1.m);distancedistancefor each i, Pil= 0 ;for each objective3.4选择操作一旦种群中的个体按照非支配性原则和聚集距离进行排序。个体的选择操作就可以进 行。排序中的比较操作定义如下：设个体i和个体j为进化群体中的任意个体，个体间的大 小关系定义为if ( irankrank或者irank且 Pidistance Pjdistance定义表明，当两个体属于不同的前沿集合时，较小秩(rank)的个体优于较大秩的个体;当两个体的秩相同时，聚集距离较大的个体优先得到选择。在群体进行二进制锦标赛选择时，父个体的选择也是基于如上的大小比较定义进行的。3.5遗传操作遗传操作采用模拟二进制杂交。其杂交方式如下：Ci,k = 5 * (1-0 k)*pi,k +(1+0 k)*P2,k)C2,k =* d+0 k)*Pi,k + d-0 k)*P2,k)其中，Cik，表示第i个孩子第k维的值，Pik表示第i个父个体第k维的值。0 k是满 足一定概率密度分布的随机数。具体产生方式如下：0 k = (2*U)l/(e +1)u 0.50 k = 1 / 2*(1-u)1/(e +1)u 三 0.5其中u是(0, 1)直接的随机数，e是个常量参数。变异方式采用多项式变异。变异计算方式如下：C = P + (Pu - Pl)* 5kkkkk其中的ck是孩子个体，Pk是父个体，Pku和Pkl，是第k维决策变量的定义域的上下限。 kkkk8k是随机变量，满足多项式分布，其分布函数如下：和=(2rk)1/(n+i) - 1rk = 0.5公式中rk是满足(0, 1)均匀分布的随机数，n是变异分布参数。k3.6重组和选择操作后代种群和当代种群混合，从中选择优秀的个体作为下一代种群。由于之前优秀的个体 被加入混合种群中，因此，精英种群得到保护和继承。混合种群之后居于非支配性原则进行 排序。下一代个体产生通过选择每个前沿集合中的个体，直到下一代种群的大小达到原来当 代种群的大小。如果添加当前前沿集合P中的个体超过种群大小N,则从P中选择聚集距ii离大的个体。并不断重复上述的迭代操作，直到到终止条件。算法流程如下：NSGA-II初始产生P和Q t = 00 0Rt 二 Pt U QtF = fast-nondominated-sort(Rt)Pt+1 = 0 and i = 1Until ( |Pt+1| + |Fi| using namespace std;int main()NSGA_II();return 0;/* NSGA_II.h*/#include #include #define D 10#define M 2#define N 100#define Pi 3.1415926535898#define INF 0x1fffffff#define NEAR_ZEOR 1e-7typedef struct Individouble varD;double fitnessM;int rank;double crowdDistance;void init();/ Initialization the individualvoid evaluate (); / evaluate the individual Individual;typedef struct Popint popSize;Individual entiy2*N;Pop(int size); void setPopSize(int size);Population;struct cmpStrint id; double var; cmpStr(int a, double v);voidNSGA_H();/* NSGA_II.cpp*/#include NSGA_II.h#include#include#includevcstdlib#include#includeusing namespace std;vectorv vectorv int Front;void Individual:init () / Individual Initializationfor (int i = 0 ; i D ; i+)vari = rand()/double(RAND_MAX);void Individual:evaluate ()double x1 = var0;fitness0 = 1 - exp(-4*x1) * pow(sin(6*Pi*xl),6);double sum = 0 ;for(int i = 1 ; i D ; i+)sum += vari;sum /= (D-l);double gx = 1 + 9 * pow(sum,0.25);double temp = fitnessO/gx; fitness1 = gx * (1 - temp*temp);Population:Pop(int size)popSize = size;void Population:setPopSize (int size)popSize = size;void InitPop(Population &Pop)for(int i = 0 ; i Pop.popSize ; i+)Pop.entiyi.init();Pop.entiyi.evaluate();cmpStr:cmpStKint a ,double v)id = a;var = v;bool cmp1(const cmpStr &a , const cmpStr &b)return a.var b.var ;bool cmp2(const Individual &a , const Individual &b)if(a.rank b.crowdDistance ) return true;return false ;bool cmp3(const cmpStr &a , const cmpStr &b)return a.var b.var ;void merge (Population & Pl,Population & P2,Population & P3) int i = 0 ;while(i P2.popSize)P1.entiyi = P2.entiyi;i+;while(i (P2.popSize + P3.popSize)P1.entiyi = P3.entiyi-P2.popSize;i+;P1.setPopSize(P2.popSize + P3.popSize);void merge (Population &P1,Population &P2,vector &v)for (int i = 0 ; i (int)v.size() ; i+)if(P1.popSize N)P1.entiyP1.popSize+ = P2.entiyv.at(i);int dominated(Individual a,Individual b)bool less = false;bool big = false;for(int i = 0 ; i M ; i+)if(a.fitnessi b.fitnessi)big = true;if( less = true & big = false)return 1;if( less = false & big = true)return -1;return 0;void fast_nondominated_sort(Population & Pop)Front.clear();int num2*N = 0;vectorv vectorv int S;vectorv int *P = new vector();for(int i = 0 ; i *t = new vectorv int();for(int j = 0 ;j v Pop.popSize ; j+)if(i = j) continue;int k = dominated(Pop.entiyi,Pop.entiyj); if(k = 1)(*t).push_back(j);else if(k = -1)np+;S.push_back(*t);Pop.entiyi.rank = numi = np;if(np = 0)(*P).push_back(i);while(!(*P).empty()Front.push_back(*P);vectorv int *H = new vectorv int();for(int i = 0 ; i v (int)(*P).size() ; i+)int p = (*P).at(i);for(int j =0 ; j &v)for (int i = 0 ; i &v)int fmax,fmin;vectorvcmpStr tempV;for(int j = 0 ; j (int)v.size() ; j+)Pop.entiyv.at(j).crowdDistance = 0;for(int i = 0 ; i M ; i+)tempVclear();for(int j = 0 ; j (int)v.size() ; j+)tempVpush_back(cmpStr(v.at(j), Pop.entiyv.at(j).fitnessi);sort(tempV.begin(),tempVend(),cmpl);fmax = tempV.at(v.size()-1).var;fmin = tempVat(0).var;Pop.entiytempVat(0).id.crowdDistance = INF;Pop.entiytempVat(v.size()-l).id.crowdDistance = INF; for(int j = 1 ; j (int)v.size()-1 ; j+)double pre = tempV.at(j-1).var;double next = tempV.at(j+1).var;if(fabs(fmax - fmin) NEAR_ZEOR)Pop.entiyv.at(j).crowdDistance = INF;Pop.entiyv.at(j).crowdDistance += (next - pre) / (fmax - fmin); tempVclear();void sort_by_distance (Population & Pop,vector &v)vectorvcmpStr tempV;for(int j = 0 ; j (int)v.size() ; j+) tempVpush_back(cmpStr(v.at(j),Pop.entiyv.at(j).crowdDistance);sort(tempV.begin(),tempVend(),cmp3);/sort by crowd distance in descendingv.clear();for(int i = 0 ; i (int)tempVsize() ; i+)v.push_back(tempVat(i).id);tempVclear();void randInTwo(int &a, int&b,int size)a = rand()%size;b = rand()%size;while(a = b)b = rand()%size;void tournament_selection(const Population &Pop,Population &cPop, int size)int array2*N;for(int i = 0 ; i Pop.popSize ; i+) arrayi = i;int index ,a,b;int popSize = Pop.popSize;for(int j = 0 ; j size ; j+ ) randInTwo(a,b,popSize);if(cmp2(Pop.entiyarraya,Pop.entiyarrayb) index = a;elseindex = b;cPop.entiyj = Pop.entiyarrayindex; arrayindex = array-popSize;cPop.setPopSize(size);double dealBorder(double x)if (x 1) x = 1 ;return x;bool checkNaN(double x)return isnan(x);void crossover (const Population & fPop,Population & cPop) Individual childl,child2;int a,b;randInTwo(a,b,fPop.popSize);double u = 20.0;double r,beta;for(int i = 0 ; i D ; i+ )dor = rand()/(double)RAND_MAX; while(fabs(l-r)vNEAR_ZEOR); if( r = 0.5)beta = pow(2*r,1/(u+1);elsebeta =1.0 / pow(2*(1-r),1/(u+1);child1.vari = 0.5 *(1-beta)*fPop.entiya.vari; child1.vari += 0.5 *(1+beta)*fPop.entiyb.vari;child2.vari = 0.5 *(1+beta)*fPop.entiya.vari;child2.vari += 0.5 *(1-beta)*fPop.entiyb.vari;child1.vari = dealBorder(child1.vari);child2.vari = dealBorder(child2.vari);child1.evaluate();child2.evaluate();cPop.entiycPop.popSize+ = child1; cPop.entiycPop.popSize+ = child2;void mutation(const Population & Pop,Population & childPop) Individual child;int p = rand()%Pop.popSize;double u = 20.0;for(int i = 0 ; i D ; i+)double r = rand()/(double)RAND_MAX;double delt = 0;if(r 0.5)delt = pow(2*r,1/(u+1) - 1;elsedelt = 1- pow(2*(1-r),1/(u+1);child.vari = Pop.entiyp.vari + delt;child.vari = dealBorder(child.vari);child.evaluate(); childPop.entiychildPop.popSize+ = child;void make_new_Pop(const Population & Pop,Population & childPop) Population fatherPop(N); toumament_selection(Pop,fatherPop,Pop.popSize/2);int size = 0 ;childPop.setPopSize(O);while(size Pop.popSize)double r = rand()/(double)RAND_MAX;if(r 0.9)crossover(fatherPop,childPop);size +=2;elsemutation(fatherPop,childPop);size+;childPop.setPopSize(Pop.popSize);void outputl (const Population & Pop)for(int i = 0 ; i Pop.popSize ; i+)for(int j = 0 ; j M ; j+)coutPop.entiyi.fitnessj;coutendl;void output2(const Population & Pop)for(int i = 0 ; i Pop.popSize ; i+)coutthe i=;for(int j = 0 ; j D ; j+)coutvvPop.entiyi.varjvv;coutvvendl;coutvvvvendl;void NSGA_H()int gen = 2000;Population parentPop(N);Population mergePop(2*N);Population childPop(N);srand(unsigned) time(NULL);InitPop(parentPop); / initialization end evaluate InitPop(childPop);while(gen_) merge(mergePop,parentPop,childPop); fast_nondominated_sort(mergePop);parentPop.setPopSize(0);int i = 0;while(parentPop.popSize + Front.at(i).size() = N) crowding_distance_assianment(mergePop,Front.at(i); merge(parentPop,mergePop,Front.at(i);i+;if(parentPop.popSize N)sort_by_distance(mergePop,Front.at(i); merge(parentPop,mergePop,Front.at(i); make_new_Pop(parentPop,childPop);outputl(parentPop);output2(parentPop);