NSGA-Ⅱ算法C++实现（测试函数为ZDT1）

pulbieup · 发表于 2020-9-24 14:02

EDA365欢迎您登录！

您需要登录才可以下载或查看，没有帐号？注册

x

本帖最后由 pulbieup 于 2020-9-24 14:04 编辑

在看C++实现之前，请先看一下NSGA-II算法概述：NSGA-II多目标遗传算法概述

NSGA-Ⅱ就是在第一代非支配排序遗传算法的基础上改进而来，其改进主要是针对如上所述的三个方面：
①提出了快速非支配排序算法，一方面降低了计算的复杂度，另一方面它将父代种群跟子代种群进行合并，使得下一代的种群从双倍的空间中进行选取，从而保留了最为优秀的所有个体；
②引进精英策略，保证某些优良的种群个体在进化过程中不会被丢弃，从而提高了优化结果的精度；
③采用拥挤度和拥挤度比较算子，不但克服了NSGA中需要人为指定共享参数的缺陷，而且将其作为种群中个体间的比较标准，使得准Pareto域中的个体能均匀地扩展到整个Pareto域，保证了种群的多样性。

头文件：

#include<stdio.h>
#include<stdlib.h>
#include<Windows.h>
#include<math.h>
#include<time.h>
#include<iostream>
#define Dimension 2//基因维数，在这里即ZDT1问题xi的i的最大值
#define popsize 100//种群大小
#define generation 500 //繁衍代数
#define URAND (rand()/(RAND_MAX+1.0))//产生随机数
int temp1[popsize];//临时数组
int mark[popsize];//标记数组
//以上两个数组用于产生新的子代
using namespace std;# M+ b R; H4 D

个体的类声明：

class individual
{
public:
double value[Dimension];//xi的值
int sp[2*popsize];
//被支配个体集合SP。该量是可行解空间中所有被个体p支配的个体组成的集合。
int np;
//支配个数np。该量是在可行解空间中可以支配个体p的所以个体的数量。
int is_dominated;//集合sp的个数
void init();//初始化个体
int rank;//优先级，Pareto级别为当前最高级
double crowding_distance;//拥挤距离
double fvalue[2];//ZDT1问题目标函数的值
void f_count();//计算fvalue的值
};9 Y) u2 v1 w9 t$ F5 N$ d

群体的类声明：

class population
{
public:
population();//类初始化
individual P[popsize];
individual Q[popsize];
individual R[2*popsize];
void set_p_q();
//随机产生一个初始父代P，在此基础上采用二元锦标赛选择、
//交叉和变异操作产生子代Q。P和Q群体规模均为popsize
//将Pt和Qt并入到Rt中（初始时t=0），对Rt进行快速非支配解排序，
//构造其所有不同等级的非支配解集F1、F2........
int Rnum;
int Pnum;
int Qnum;
//P,Q,R中元素的个数
void make_new_pop();//产生新的子代
void fast_nondominated_sort();//快速非支配排序
void calu_crowding_distance(int i);//拥挤距离计算
void f_sort(int i);//对拥挤距离降序排列
void maincal();//主要操作
int choice(int a,int b);
//两个个体属于不同等级的非支配解集，优先考虑等级序号较小的
//若两个个体属于同一等级的非支配解集，优先考虑拥挤距离较大的
int len[2*popsize];//各个变异交叉后的群体Fi的长度的集合
int len_f;//整个群体rank值
};
. N; | y; c1 ]. G V: U

全局变量及部分函数声明：

individual F[2*popsize][2*popsize];
double rand_real(double low,double high)
//产生随机实数
{
double h;
h=(high-low)*URAND+low+0.001;
if(h>=high)
h=high-0.001;
return h;
}
int rand_int(int low,int high)
//产生随机整数
{
return int((high-low+1)*URAND)+low;
}
3 K+ u8 Z" R8 Y7 k( S2 g4 x

关于排序函数qsort

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )
利用qsort对F数组按照cmp3排序

int cmp1(const void *a,const void *b)
//目标函数f1的升序排序
{
const individual *e=(const individual *)a;
const individual *f=(const individual *)b;
if(e->fvalue[0]==f->fvalue[0])
return 0;
else if(e->fvalue[0]<f->fvalue[0])
return -1;
else return 1;
}
int cmp2(const void *a,const void *b)
//目标函数f2的升序排序
{
const individual *e=(const individual *)a;
const individual *f=(const individual *)b;
if(e->fvalue[1]==f->fvalue[1])
return 0;
else if(e->fvalue[1]<f->fvalue[1])
return -1;
else return 1;
}
int cmp_c_d(const void *a,const void *b)
//对拥挤距离降序排序
{
const individual *e=(const individual *)a;
const individual *f=(const individual *)b;
if(e->crowding_distance==f->crowding_distance)
return 0;
else if(e->crowding_distance<f->crowding_distance)
return 1;
else
return -1;
}
void population::f_sort(int i)
{
int n;
n=len;
qsort(F,n,sizeof(individual),cmp_c_d);
}6 X+ J" X X2 ]# T) @# n C' I' Q

群的初始化：

population::population()
{
int i;
for(i=0;i<popsize;i++)
{
P.init();
}
for(i=0;i<popsize;i++)
{
P.f_count();
}
Pnum=popsize;
Qnum=0;
Rnum=0;
}
' J& G+ w4 Y' Q% U$ z

个体初始化：

void individual::init()
{
for(int i=0;i<Dimension;i++)
value=rand_real(0.0,1.0);
}* X* c3 R; X( e7 `

利用二进制锦标赛产生子代：

1、随机产生一个初始父代Po，在此基础上采用二元锦标赛选择、交叉和变异操作产生子代Qo， Po 和Qo群体规模均为N
2、将Pt和Qt并入到Rt中（初始时t=0），对Rt进行快速非支配解排序，构造其所有不同等级的非支配解集F1、F2……..
3、按照需要计算Fi中所有个体的拥挤距离，并根据拥挤比较运算符构造Pt+1，直至Pt+1规模为N，图中的Fi为F3