专栏首页图灵技术域NSGA-Ⅱ算法C++实现(测试函数为ZDT1)

NSGA-Ⅱ算法C++实现(测试函数为ZDT1)

在看C++实现之前,请先看一下NSGA-II算法概述

https://www.omegaxyz.com/2017/04/14/nsga-iiintro/

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

头文件:

C++

#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;

个体的类声明:

C++

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的值
};

群体的类声明:

C++

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值
};

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

C++

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;
}

关于排序函数qsort

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

C++

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[i];
 qsort(F[i],n,sizeof(individual),cmp_c_d);
}

群的初始化:

C++

population::population()
{
    int i;
    for(i=0;i<popsize;i++)
    {
        P[i].init();
    }
    for(i=0;i<popsize;i++)
    {
        P[i].f_count();
    }
    Pnum=popsize;
    Qnum=0;
    Rnum=0;
}

个体初始化:

C++

void individual::init()
{
    for(int i=0;i<Dimension;i++)
        value[i]=rand_real(0.0,1.0);
}

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

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

C++

void population::make_new_pop()
{
    int i,j,x,y,t1,t2,t3;
    double s,u,b;
    memset(mark,0,sizeof(mark));
    t3=0;
    while(t3<popsize/2)
    {
        while(t1=t2=rand_int(0,popsize-1),mark[t1]);
        while(t1==t2||mark[t2])
        {
            t2=rand_int(0,popsize-1);
        }
        t1=choice(t1,t2);
        temp1[t3++]=t1;
        mark[t1]=1;
    }
    for(i=0;i<popsize;i++)
    {
        s=rand_real(0.0,1.0);
        if(s<=0.9)
        {
            for(j=0;j<Dimension;j++)
            {
                u=rand_real((0.0+1e-6),(1.0-1e-6));
                if(u<=0.5)
                    b=pow(2*u,1.0/21);
                else
                    b=1.0/pow(2*(1-u),1.0/21);
                x=y=rand_int(0,popsize/2-1);
                while(x==y)
                    y=rand_int(0,popsize/2-1);
                Q[i].value[j]=1.0/2*((1-b)*P[temp1[x]].value[j]+(1+b)*P[temp1[y]].value[j]);
                if(Q[i].value[j]<0)
                    Q[i].value[j]=1e-6;
                else if(Q[i].value[j]>1)
                    Q[i].value[j]=1.0-(1e-6);
                if(i+1<popsize)
                {
                    Q[i+1].value[j]=1.0/2*((1+b)*P[temp1[x]].value[j]+(1-b)*P[temp1[y]].value[j]);
                    if(Q[i+1].value[j]<=0)
                        Q[i+1].value[j]=1e-6;
                    else if(Q[i+1].value[j]>1)
                        Q[i+1].value[j]=(1-1e-6);
                }
            }
            i++;
        }
        else
        {
            for(j=0;j<Dimension;j++)
            {
                x=rand_int(0,popsize/2-1);
                u=rand_real(0.0+(1e-6),1.0-(1e-6));
                if(u<0.5)
                    u=pow(2*u,1.0/21)-1;
                else
                    u=1-pow(2*(1-u),1.0/21);
                Q[i].value[j]=P[temp1[x]].value[j]+(1.0-0.0)*u;
                if(Q[i].value[j]<0)
                    Q[i].value[j]=1e-6;
                else if(Q[i].value[j]>1)
                    Q[i].value[j]=1-(1e-6);
            }
        }
    }
    Qnum=popsize;
    for(i=0;i<popsize;i++)
        Q[i].f_count();
}

C++

void population::set_p_q()
{
    Rnum=0;
    Qnum=popsize;
    int i;
    for(i=0;i<Pnum;i++)
        R[Rnum++]=P[i];
    for(i=0;i<Qnum;i++)
        R[Rnum++]=Q[i];
    for(i=0;i<2*popsize;i++)
        R[i].f_count();
}

ZDT1问题函数值的计算:

C++

void individual::f_count()
{
    fvalue[0]=value[0];
    int i;
    double g=1,sum=0;
    for(i=1;i<Dimension;i++)
    {
        sum+=value[i];
    }
    sum+=9*(sum/(Dimension-1));
    g+=sum;
    fvalue[1]=g*(1-sqrt(value[0]/g));
}

判断目标函数值是否被支配:

C++

bool e_is_dominated(const individual &a,const individual &b)
{
    if((a.fvalue[0]<=b.fvalue[0])&&(a.fvalue[1]<=b.fvalue[1]))
    {
        if((a.fvalue[0]==b.fvalue[0])&&a.fvalue[1]==b.fvalue[1])
            return false;
        else
            return true;
    }
    else
        return false;
}

快速非支配排序法:重点!!!

C++

void population::fast_nondominated_sort()
{  
    int i,j,k;
    individual H[2*popsize];
    int h_len=0;
    for(i=0;i<2*popsize;i++)
    {
        R[i].np=0;
        R[i].is_dominated=0;
        len[i]=0;
    }
    for(i=0;i<2*popsize;i++)
    {
        for(j=0;j<2*popsize;j++)
        {
            if(i!=j)
            {
                if(e_is_dominated(R[i],R[j]))
                    R[i].sp[R[i].is_dominated++]=j;
                else if(e_is_dominated(R[j],R[i]))
                    R[i].np+=1;
            }
        }
        if(R[i].np==0)
        {
            len_f=1;
            F[0][len[0]++]=R[i];
        }
 
    }
    i=0;
    while(len[i]!=0)
    {
        h_len=0;
        for(j=0;j<len[i];j++)
        {
            for(k=0;k<F[i][j].is_dominated;k++)
            {
                R[F[i][j].sp[k]].np--;
                if(R[F[i][j].sp[k]].np==0)
                {
                    H[h_len++]=R[F[i][j].sp[k]];
                    R[F[i][j].sp[k]].rank=i+2;
                }
            }
        }
        i++;
        len[i]=h_len;
        if(h_len!=0)
        {
            len_f++;
            for(j=0;j<len[i];j++)
                F[i][j]=H[j];
        }
    }
}

计算拥挤距离:重点!!!具体解释见其他文章!!!

C++

void population::calu_crowding_distance(int i)
{
    int n=len[i];
    double m_max,m_min;
    int j;
    for(j=0;j<n;j++)
        F[i][j].crowding_distance=0;
    F[i][0].crowding_distance=F[i][n-1].crowding_distance=0xffffff;
    qsort(F[i],n,sizeof(individual),cmp1);
    m_max=-0xfffff;
    m_min=0xfffff;
    for(j=0;j<n;j++)
    {
        if(m_max<F[i][j].fvalue[0])
            m_max=F[i][j].fvalue[0];
        if(m_min>F[i][j].fvalue[0])
            m_min=F[i][j].fvalue[0];
    }
    for(j=1;j<n-1;j++)
        F[i][j].crowding_distance+=(F[i][j+1].fvalue[0]-F[i][j-1].fvalue[0])/(m_max-m_min);
    F[i][0].crowding_distance=F[i][n-1].crowding_distance=0xffffff;
    qsort(F[i],n,sizeof(individual),cmp2);
    m_max=-0xfffff;
    m_min=0xfffff;
    for(j=0;j<n;j++)
    {
        if(m_max<F[i][j].fvalue[1])
            m_max=F[i][j].fvalue[1];
        if(m_min>F[i][j].fvalue[1])
            m_min=F[i][j].fvalue[1];
    }
    for(j=1;j<n-1;j++)
        F[i][j].crowding_distance+=(F[i][j+1].fvalue[1]-F[i][j-1].fvalue[1])/(m_max-m_min);
}

采集多样性的选择:

C++

int population::choice(int a,int b)
{
    if(P[a].rank<P[b].rank)
        return a;
    else if(P[a].rank==P[b].rank)
    {
        if(P[a].crowding_distance>P[b].crowding_distance)
            return a;
        else
            return b;
    }
    else
        return b;
}

主要操作函数:

C++

void population::maincal()
{
    int s,i,j;
    s=generation;
    make_new_pop();
    while(s--)
    {
        printf("The %d generation\n",s);
        set_p_q();
        fast_nondominated_sort();
        Pnum=0;
        i=0;
        while(Pnum+len[i]<=popsize)
        {
            calu_crowding_distance(i);
            for(j=0;j<len[i];j++)
                P[Pnum++]=F[i][j];
            i++;
            if(i>=len_f)break;
        }
        if(i<len_f)
        {
            calu_crowding_distance(i);
            f_sort(i);
        }
        for(j=0;j<popsize-Pnum;j++)
            P[Pnum++]=F[i][j];
        make_new_pop();
    }
}

主函数:

C++

int main()
{
    FILE *p;
    p=fopen("d:\\My_NSGA2.txt","w+");
    srand((unsigned int)(time(0)));
    population pop;
    pop.maincal();
    int i,j;
    fprintf(p,"XuYi All Rights Reserved.\nWelcome to OmegaXYZ: www.omegaxyz.com\n");
    fprintf(p,"Problem ZDT1\n");
    fprintf(p,"\n");
    for(i=0;i<popsize;i++)
    {
        fprintf(p,"The %d generation situation:\n",i);
        for(j=1;j<=Dimension;j++)
        {
            fprintf(p,"x%d=%e  ",j,pop.P[i].value[j]);
        }
        fprintf(p,"\n");
        fprintf(p,"f1(x)=%f   f2(x)=%f\n",pop.P[i].fvalue[0],pop.P[i].fvalue[1]);
    }
    fclose(p);
    return 1;
}

ZDT1问题图像及前沿面。

测试结果:

快速支配排序具体解释见多目标算法NSGA-II:https://www.omegaxyz.com/2017/04/19/nsga2fastsort/

多目标问题解释:https://www.omegaxyz.com/2017/04/16/theexpofpareto/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NSGA-Ⅱ算法Matlab实现(测试函数为ZDT1)

    NSGA-Ⅱ就是在第一代非支配排序遗传算法的基础上改进而来,其改进主要是针对如上所述的三个方面: ①提出了快速非支配排序算法,一方面降低了计算的复杂度,另一方...

    里克贝斯
  • matlab多目标优化算法之NSGA-Ⅱ【含源代码】

    当优化问题的目标函数为两个或两个以上时,该优化问题就是多目标优化。不同于单目标优化问题,多目标问题没有单独的解能够同时优化所有目标,也就是目标函数之间存在着冲...

    matlab爱好者
  • Jmetal 4+ 使用指南四使用Jmetal进行试验-NSGAIIStudy(一)

    演化计算与人工智能
  • NSGA-II多目标遗传算法概述

    Non dominated sorting genetic algorithm -II NSGA-Ⅱ是目前最流行的多目标遗传算法之一,它降低了非劣排序遗传算法...

    里克贝斯
  • Jmetal 4+ 使用指南三使用Jmetal进行试验

    演化计算与人工智能
  • 多目标进化算法应用于提高医药数据领域学习器的性能(CS AI)

    原文标题完整翻译:多目标进化算法应用于提高在医药数据领域使用整体特征选择和离散化模型的学习器的性能

    Donuts_choco
  • 基于稀疏化鲁棒LS-SVR与多目标优化的铁水硅含量软测量建模

    今天跟大家分享一篇之前发表的文章,《基于稀疏化鲁棒LS-SVR与多目标优化的铁水硅含量软测量建模 》。 摘要: 针对高炉炼铁过程的关键工艺指标——铁水硅含量[...

    昱良
  • Jmetal 4+ 使用指南一以NSGA-II为例

    演化计算与人工智能
  • Jmetal 4+ 使用指南六 Experimentation example: StandardStudy

    演化计算与人工智能
  • 遗传算法系列之五:多目标遗传算法和遗传编程

    在遗传算法深入研究的阶段,人们提出将各种将遗传算法应用到更广泛领域,从而产生了一些有趣的后续工作。这些后续工作中,多目标遗传算法和遗传编程由于它们重要...

    AlgorithmDog
  • NSGA2算法MATLAB实现(能够自定义优化函数)

    以前写了一个简单的NSGA2的算法能够用在ZDT1函数上:https://www.omegaxyz.com/2017/05/04/nsga2matlabzdt1...

    里克贝斯
  • 论文研读-多目标自适应memetic算法

    演化计算与人工智能
  • 动态多目标优化研究综述

    转载自http://cjc.ict.ac.cn/online/onlinepaper/lrc-20207694828.pdf

    演化计算与人工智能
  • Jmetal 4+ 使用指南二

    并且生成四个文件,分别是目标函数值,决策变量值,log日志文件 这种方式指定的问题是写在main方法中的problem = new ZDT3("ArrayRea...

    演化计算与人工智能
  • NSGA-II入门

    在遗传算法在解决多目标优化遇到瓶颈时,许多学者花费了不少时间和精力在多目标优化的遗传算法上,Goldberg首先将Pareto最优解的概念与适应度值概念相关联,...

    演化计算与人工智能
  • 多目标演化算法 | 从参考点出发,求解高维多目标优化问题!

    从社会生活的角度出发,最优化问题普遍存在于我们的日常生活中。例如,人们往往追求利润的最大化、投资风险的最小化等。随着科学技术和生产生活的日益发展,人们面临的优化...

    智能算法
  • 大数据平台测试

    大数据平台的基本功能和数据的导入导出对SQL任务、NoSQL任务、机器学习、批处理任务的支持

    小老鼠
  • 机器学习学习笔记(1) -- 简析入门

    机器学习是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科;机器学习是一种偏向于技术的方法,研究目的包括模式识别、神经网络和深...

    挽风
  • Jmetal 4+ 使用指南七-并行算法

    演化计算与人工智能

扫码关注云+社区

领取腾讯云代金券