提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Javascript

当前栏目

NSGA-II看这篇够了

2023-04-18 16:07:13 时间

原文: A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II

github地址
概要流程代码

public NSGAII(){
        int gen = 0;
        dim = 30;
        //DrawPointUtil drawPointUtil = new DrawPointUtil();
        List<Individual> pop = init(populationSize);
        HashMap<Integer,List<Individual>>hashMap = noDominateSort(pop);//this function will set the rank and distance;
        setDistance(hashMap);
        //drawPointUtil.draw(pop);
        while(gen<maxGen){
            List<Individual> fatherPool = battleSection(pop);//the good Father Pool
            List<Individual> sons = getSons(fatherPool);
            pop.addAll(sons);
            HashMap<Integer,List<Individual>> rankMap = noDominateSort(pop);
            setDistance(rankMap);
            pop = tournamentSection(rankMap,populationSize);//这里的rankMap以及被污染了
            if (gen%1000==0){
                System.out.println(gen);
            }
            //drawPointUtil.repaint(pop);
            gen++;
        }
    }

一，快速非支配排序

1.所需知识：帕累托前沿，非支配排序

(1)帕累托前沿

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EnzGwiXU-1667311749179)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/0b257dfe-0ead-4b10-85de-dd5e7d396608/Untitled.png)]

帕累托前沿，是由一组非支配解构成的。那什么是非支配解了？顾名思义就是不被支配的解，那什么是支配呢？我们简简单单举个例子，我们有三组解A（5，2），B（2，3），C（5，1）；在这里，A的第一个值比B要大，但是A的第二值比B的小，所以AB两个解互不支配，我们再来看看A C两个解，A和C的第一个值一样，但是A的值比C的值要大，通常，我们都是求最小化的值，值越小越好，所以我们认为这个时候C这个解比A要好，所以有C支配A。

在多目标优化问题上面，我们往往是找最小化的解，所以我们看到的帕累托曲线，往往是所有点构成的图形的左下方的连线，例如上面的这幅图，我们可以看到黑色的点，他们不被任何的点支配，所以构成了一个帕累托前沿，

(2)非支配排序

上面我们说到帕累托前沿，那我们怎么才能获得这一系列不被支配的解呢？一步一步获得黑点，粉点，黄点。

这就要说到非支配排序了。

所有的解构成的解集 S S S

首先第一步我们要找出所有不被支配的解，解集为 X 1 X_1 X1​(黑点)

接着我们将这些解从解集里面移除 S = S − X 1 S = S -X_1 S=S−X1​ ，这个 X 1 X_1 X1​里面的所有解都会被标上Rank = 1

然后我们回到了第一步继续找出非支配的解 X 2 X_2 X2​(粉点)

又接着移除 S = S − X 2 S = S-X2 S=S−X2

直到 S = N U L L S=NULL S=NULL为止。

2.快速非支配排序

在这里插入图片描述

这个快速非支配排序是这篇论文的最重要的地方，我们可以看到原来的算法复杂度非常的高，需要 O ( M N 3 ) O(MN^3) O(MN3)的之间复杂度，但是使用了快速非支配排序以后就会减少到 O ( M N 2 ) O(MN^2) O(MN2)

public HashMap<Integer,List<Individual>> noDominateSort(List<Individual> individuals){
    //public void setNoDominateRank(List<Individual> individuals){
        for (int i = 0; i < individuals.size(); i++) {
            individuals.get(i).setRank(0);
        }
        int len = individuals.size();
        int n[] = new int[len];//记录个体被多少个人支配
        Set<Integer> S[] = new HashSet[len];
        List<Integer> front = new LinkedList<>();
        int rank[] = new int[len];
        for (int i = 0; i < len; i++) {
            Set<Integer> set = new HashSet();
            S[i] = set;
            for (int j = 0; j < len; j++) {
                if(i==j)continue;//自己和自己比就跳过
                int isDominate = individuals.get(i).isDominate(individuals.get(j));
                if(isDominate==1){//i支配j
                    set.add(j);
                }
                else if (isDominate==-1){//j支配i
                    n[i] = n[i]+1;
                }
            }
            if(n[i]==0){
                rank[i] = 1;
                front.add(i);
            }
        }
        int i = 1;
        while(front.size()!=0){
            List<Integer> Q = new LinkedList<>();
            for (int p:
                    front) {
                for (int q:
                        S[p]) {
                    n[q] = n[q] - 1;
                    if(n[q] == 0){
                        rank[q] = i+1;
                        individuals.get(q).setRank(rank[q]);//设置每个的等级
                        Q.add(q);
                    }
                }
            }
            i = i + 1;
            front = Q;
        }
        //启用这个代码能够直接获得一个hashmap。
        HashMap<Integer,List<Individual>> res = new HashMap<>();
        for (int j = 0; j < len; j++) {
            if (res.get(rank[j])==null){
                List<Individual> list = new ArrayList<>();;
                list.add(individuals.get(j));
                res.put(rank[j],list);
            }else {
                res.get(rank[j]).add(individuals.get(j));
            }
        }

        for (int j = 0; j < len; j++) {
            individuals.get(j).setRank(rank[j]);
        }
        return res;
    }

//这个代码是Individual里面的方法
public int isDominate (Individual b){
            double[] bf = b.fitness;
            boolean flag = true;
            boolean notEqualFlag = false;
            //zheng

二，设置距离值（拥挤距离）

在这里插入图片描述

在原文中，拥挤距离的定义是在同一个rank等级里面，能画的不包括别的点的最大的框框，

d i s t a n c e = d i s t a n c e + ( f i + 1 m − f i − 1 m ) / ( f m m a x − f m m i n ) distance = distance + (f_{i+1_m}-f_{i-1_m})/(f^{max}_m-f^{min}_m) distance=distance+(fi+1m​​−fi−1m​​)/(fmmax​−fmmin​)

上面的就是距离公式了，其中fi+1m是按照当前第m个适应度适应度值排序以后的位置i的后一个位置i+1的适应度值，fi-1m则是前一个位置i-1的适应度值， f m m a x f^{max}_{m} fmmax​ 就是第m个适应度的最大值， f m m i n f^{min}_{m} fmmin​则是第m个适应度的最小值。如图所示。

在这里插入图片描述

上面这张图就是分别根据3个适应度值进行排序的出来的结果，如图所示，在m等于1的时候distance设置为无穷大的点为C，D，同理m等于2的时候距离设置为无穷的点为B，D，别的点就直接套公式就好了，每次根据前一个和后一个的适应度值设置distance。注意，distance越大越好！代表这个点离集体越远，这个是拥挤算法的精髓！

在这里插入图片描述

public void setDistance(HashMap<Integer,List<Individual>> hashMap){
        for (int rank = 1; rank <= hashMap.size() ; rank++) {
            List<Individual> individuals = hashMap.get(rank);
            int len = individuals.size();
            int fSize = individuals.get(0).fitness.length;
            for (Individual i:
                    individuals) {
                i.setDistance(0);//重置dis
            }
            for (int fIndex = 0; fIndex < fSize; fIndex++) {
                final int finalFIndex = fIndex;//保证能够插入内部类里面
                individuals.sort(new Comparator<Individual>() {//根据适应度下标排序
                    @Override
                    public int compare(Individual o1, Individual o2) {
                        double sub = o1.fitness[finalFIndex]-o2.fitness[finalFIndex];
                        if(sub==0)return 0;
                        if (sub>0){
                            return 1;
                        } else return -1;
                    }
                });
                individuals.get(0).setDistance(Double.MAX_VALUE);//开始和结束无穷大
                individuals.get(len-1).setDistance(Double.MAX_VALUE);//边界点无穷大
                double fMax = individuals.get(len-1).fitness[fIndex];
                double fMin = individuals.get(0).fitness[fIndex];
                for (int i = 1; i < len-1; i++) {//1~len-2设置值
                    double fDown = individuals.get(i-1).fitness[fIndex];
                    double fUp = individuals.get(i+1).fitness[fIndex];
                    Individual  a = individuals.get(i);
                    a.setDistance(a.getDistance()+(fUp-fDown)/(fMax-fMin));
                }
            }
        }

    }

这里的这个hashmap，键是rank值，值是这个rank值的全部个体，同志们可以酌情改变，

三，选择，交叉，变异

1.选择需要交叉的父代池（锦标赛选择）

锦标赛选择就是每次从种群抽出两个，比较优秀的加入到交配池，不优秀的不能交配，并且两个都取消下次挑出来的机会。但是不优秀的并不意味着直接从种群里面丢弃，而是丢失交配的机会而已，所以使用一个set来记录能够交配的人。

在这里插入图片描述

private List<Individual> battleSection(List<Individual> individuals){
        int n = individuals.size();
        List<Integer> set = new ArrayList<>(n);
        List<Individual> fatherPool = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            set.add(i);
        }
        while(set.size()>1){
            int rand = (int)(random()*set.size());//挑出两个battle
            Individual father1 = individuals.get(set.remove(rand));
            rand = (int)(random()*set.size());
            Individual father2 = individual其中

2.交叉以及变异 simulated binary crossover（模拟二进制交叉算法）SBX 和 polynomial mutation（多项式变异）

(1)交叉算法 SBX

关于交叉算法，使用了simulated binary crossover（模拟二进制交叉算法）SBX

在这里插入图片描述

由于找到的论文的图太不清晰了，所以借用中国科技大学的PPT来描述。这里的 X 1 j ( t ) X_{1j}(t) X1j​(t)是第1个父代的第j维度的值，上面有个波浪线的就是得到的子代。

同时 η η η在原作的里面第四节有提到，交配时候的η为20

For real-coded NSGA-II, we use distribution indexes [6] for crossover and
mutation operators as η c = 20 eta_c=20 ηc​=20and η m = 20 eta_m=20 ηm​=20, respectively.

private Individual[] getSBX(Individual a,Individual b){
        List<Double> aP = new ArrayList<>(dim);//sonA's position
        List<Double> bP = new ArrayList<>(dim);
        List<Double> faP = a.position;
        List<Double> fbP = b.position;
        double etaC = 20;//page6
        for (int j = 0; j < dim; j++) {
            double gama;
            double uj = random();
            if(random()<=0.5){
                gama = Math.pow(2.0*uj,1.0/(etaC+1.0));
            }else {
                gama = Math.pow(1.0/(2*(1.0-uj)),1.0/(etaC+1.0));
            }
            double aPP = 0.5*((1+gama)*faP.get(j)+(1-gama)*fbP.get(j));
            double bPP = 0.5*((1-gama)*faP.get(j)+(1+gama)*fbP.get(j));
            aPP = getSuitLimitX(aPP);
            bPP = getSuitLimitX(bPP);
            aP.add(aPP);
            bP.add(bPP);
        }
        Individual sonA = new Individual(aP);
        Individual sonB = new Individual(bP);
        return new Individual[]{sonA,sonB};
    }

(2) 变异算法 polynomial mutation（多项式变异）

在这里插入图片描述

这里用的是@xuxinrk博客里面的图，图中的σ的第二行是错误的，其中的 η 2 eta_2 η2​应该写成 σ 2 sigma2 σ2，其中的vk’指的是新一代子代的第k个维度的值，uk和lk这是当前维度的上界和下界。

在原论文中，推荐每个维度有1/dim的概率变异。

private Individual getPloMutation(Individual father){
        List<Double> sonPos = new ArrayList<>(dim);
        List<Double> fatPos = father.position;
        double etaM = 20;
        for (int i = 0; i < dim; i++) {
            double cur = fatPos.get(i);
            if(random()<=1.0/dim){
                double u = random();
                double sigma;
                double sigma1 = (double) (cur-lb)/(ub-lb);
                double sigma2 = (double) (random()-cur)/(ub-lb);
                if(u<=0.5){
                    sigma = Math.pow(2*u+(1-2*u)*Math.pow(1-sigma1,etaM),1.0/etaM)-1;
                }else {
                    sigma = 1 - Math.pow(2*(1-u)+2*(u-0.5)*Math.pow(1-sigma2,etaM),1.0/etaM);
                }
                cur = cur+sigma;
                cur = getSuitLimitX(cur);//获得界内的图
            }
            sonPos.add(cur);
        }
        return new Individual(sonPos);
    }

(3)（易误解点！）利用这两种算法由父代池产生新的后代。

在这里插入图片描述

文章在第四章有提到交配率为0.9，通过SBX 和 polynomial mutation ,一直产生2N个子代为止，由于我过于偷懒了，所以没有严格细写，所以会出现生成的子代大小为N+1的情况，但是问题不大，到二元锦标赛选择的时候种群的大小就会回到N了。

private List<Individual> getSons(List<Individual> fatherPool){
        int n = fatherPool.size();//n is the size of the fatherPool.
        List<Individual> sons = new ArrayList<>(populationSize);
        //although the final size of sons may not be 2*n,but inorder to save the time we set 2n;

        while(sons.size()<populationSize){
            if(random()<0.9){
                int f1 = (int)(random()*n);
                int f2 = (int)(random()*n);
                while(f1 == f2){
                    f2 = (int)(random()*n);
                }
                Individual fa = fatherPool.get(f1);
                Individual fb = fatherPool.get(f2);
                Individual[] son = getSBX(fa,fb);
                for (int j = 0; j < son.length; j++) {
                    sons.add(son[j]);
                }
            }else {
                int f = (int)(random()*n);
                Individual son = getPloMutation(fatherPool.get(f));
                sons.add(son);
            }
        }
        return sons;
    }

3.将子代和原种群的混合，进行选择得出下一代 锦标赛选择（tournamentSection）。

在这里插入图片描述

首先进行非支配排序，依次获得每个个体的rank，并且将rank一样的都放在一个队列里面，在代码里每个rank都有对应的一个ranklist，由于为了方便，所以使用haspMap来实现这个数据结构，键为rank值，值为对应的ranklist。

如何挑出子代呢？为了保证下一代足够的优秀，文章使用了精英策略，优先将rank等级高的个体放到下一代里面，直到放满为止，加入当前的子代还塞得下这个ranklist，那就直接整个放进去，那假如当前的ranklist过大，不能将整个队列加入到下一代怎么办？

这个时候就需要锦标赛选择这个方法，每轮从ranklist里面挑出两个个体，由于是在同一个ranklist里面，他们的非支配排序等级rank肯定是一样的，所以不用比较rank，这个时候比较的策略是，优先选择distance比较大的加入到下一代里面，为什么要这样？因为distance越大保证这个个体离种群越远，这样才能保证形成一个完美的帕累托前沿，每个点都将近均匀的分布在这条线上。

但是，我为了贪心一点,减少时间复杂度，直接将这个ranklist的个体根据distance进行逆序排序，直接从第一个开始放进去直到下一代的大小达到N为止

private List<Individual> tournamentSection(HashMap<Integer,List<Individual>> map,int n){
        List<Individual> result = new ArrayList<>(n);
        for (int i = 1; i < map.size(); i++) {
            List<Individual> rankList = map.get(i);
            if(result.size()+rankList.size()<=n){
                result.addAll(rankList);//全部加入
            }else {//将剩余的等级塞进去
                try{
                    rankList.sort(new Comparator<Individual>() {
                        @Override
                        public int compare(Individual o1, Individual o2) {
                            double sub = o1.distance-o2.distance;
                            if (sub==0)return 0;
                            return sub>0?-1:1;//逆序
                        }
                    });
                    result.addAll(rankList.subList(0,n-result.size()));
                }catch (Exception e){
                    System.out.println(e);
                }

            }
        }
        return result;
    }

四，全部代码

import java.util.*;

import static java.lang.Math.abs;
import static java.lang.Math.random;

public class NSGAII {
    static int fitnessDim = 2;
    static int dim;
    double ub = 1;
    double lb = 0;
    int populationSize = 500;
    int maxGen = 500;
    public NSGAII(){
        int gen = 0;
        dim = 30;
        DrawPointUtil drawPointUtil = new DrawPointUtil();
        List<Individual> pop = init(populationSize);
        HashMap<Integer,List<Individual>>hashMap = noDominateSort(pop);//this function will set the rank and distance;
        setDistance(hashMap);
        drawPointUtil.draw(pop);
        while(gen<maxGen){
            List<Individual> fatherPool = battleSection(pop);//the good Father Pool
            List<Individual> sons = getSons(fatherPool);
            pop.addAll(sons);
            HashMap<Integer,List<Individual>> rankMap = noDominateSort(pop);
            setDistance(rankMap);
            pop = tournamentSection(rankMap,populationSize);//这里的rankMap以及被污染了
            if (gen%1000==0){
                System.out.println(gen);
            }
            drawPointUtil.repaint(pop);
            gen++;
        }
    }

    public static void main(String[] args) {
        new NSGAII();
    }
    private List<Individual> getSons(List<Individual> fatherPool){
        int n = fatherPool.size();//n is the size of the fatherPool.
        List<Individual> sons = new ArrayList<>(populationSize);
        //although the final size of sons may not be 2*n,but inorder to save the time we set 2n;

        while(sons.size()<populationSize){
            if(random()<0.9){
                int f1 = (int)(random()*n);
                int f2 = (int)(random()*n);
                while(f1 == f2){
                    f2 = (int)(random()*n);
                }
                Individual fa = fatherPool.get(f1);
                Individual fb = fatherPool.get(f2);
                Individual[] son = getSBX(fa,fb);
                for (int j = 0; j < son.length; j++) {
                    sons.add(son[j]);
                }
            }else {
                int f = (int)(random()*n);
                Individual son = getPloMutation(fatherPool.get(f));
                sons.add(son);
            }
        }
        return sons;
    }
    //simulated binary crossover
    private Individual[] getSBX(Individual a,Individual b){
        List<Double> aP = new ArrayList<>(dim);//sonA's position
        List<Double> bP = new ArrayList<>(dim);
        List<Double> faP = a.position;
        List<Double> fbP = b.position;
        double etaC = 20;//page6
        for (int j = 0; j < dim; j++) {
            double gama;
            double uj = random();
            if(random()<=0.5){
                gama = Math.pow(2.0*uj,1.0/(etaC+1.0));
            }else {
                gama = Math.pow(1.0/(2*(1.0-uj)),1.0/(etaC+1.0));
            }
            double aPP = 0.5*((1+gama)*faP.get(j)+(1-gama)*fbP.get(j));
            double bPP = 0.5*((1-gama)*faP.get(j)+(1+gama)*fbP.get(j));
            aPP = getSuitLimitX(aPP);
            bPP = getSuitLimitX(bPP);
            aP.add(aPP);
            bP.add(bPP);
        }
        Individual sonA = new Individual(aP);
        Individual sonB = new Individual(bP);
        return new Individual[]{sonA,sonB};
    }
    //select n Individual
    private List<Individual> tournamentSection(HashMap<Integer,List<Individual>> map,int n){
        List<Individual> result = new ArrayList<>(n);
        for (int i = 1; i < map.size(); i++) {
            List<Individual> rankList = map.get(i);
            if(result.size()+rankList.size()<=n){
                result.addAll(rankList);//全部加入
            }else {//将剩余的等级塞进去
                try{
                    rankList.sort(new Comparator<Individual>() {
                        @Override
                        public int compare(Individual o1, Individual o2) {
                            double sub = o1.distance-o2.distance;
                            if (sub==0)return 0;
                            return sub>0?-1:1;//逆序
                        }
                    });
                    result.addAll(rankList.subList(0,n-result.size()));
                }catch (Exception e){
                    System.out.println(e);
                }

            }
        }
        return result;
    }
    //select halfOf individuals
    private List<Individual> battleSection(List<Individual> individuals){
        int n = individuals.size();
        List<Integer> set = new ArrayList<>(n);
        List<Individual> fatherPool = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            set.add(i);
        }
        while(set.size()>1){
            int rand = (int)(random()*set.size());//挑出两个battle
            Individual father1 = individuals.get(set.remove(rand));
            rand = (int)(random()*set.size());
            Individual father2 = individuals.get(set.remove(rand));
            if(father1.getRank()<father2.getRank()){
                fatherPool.add(father1);
            }else if(father1.getRank()==father2.getRank()){
                if (father1.getDistance()>father2.getDistance()){
                    fatherPool.add(father1);
                }else {
                    fatherPool.add(father2);
                }
            }else fatherPool.add(father2);
        }
        return fatherPool;
    }

    //Ploynomial mutation 多项式变异
    private Individual getPloMutation(Individual father){
        List<Double> sonPos = new ArrayList<>(dim);
        List<Double> fatPos = father.position;
        double etaM = 20;
        for (int i = 0; i < dim; i++) {
            double cur = fatPos.get(i);
            if(random()<=1.0/dim){
                double u = random();
                double sigma;
                double sigma1 = (double) (cur-lb)/(ub-lb);
                double sigma2 = (double) (random()-cur)/(ub-lb);
                if(u<=0.5){
                    sigma = Math.pow(2*u+(1-2*u)*Math.pow(1-sigma1,etaM),1.0/etaM)-1;
                }else {
                    sigma = 1 - Math.pow(2*(1-u)+2*(u-0.5)*Math.pow(1-sigma2,etaM),1.0/etaM);
                }
                cur = cur+sigma;
                cur = getSuitLimitX(cur);//获得界内的图
            }
            sonPos.add(cur);
        }
        return new Individual(sonPos);
    }
    //对这个individuals设置distance值
    public void setDistance(HashMap<Integer,List<Individual>> hashMap){
        for (int rank = 1; rank <= hashMap.size() ; rank++) {
            List<Individual> individuals = hashMap.get(rank);
            int len = individuals.size();
            int fSize = individuals.get(0).fitness.length;
            for (Individual i:
                    individuals) {
                i.setDistance(0);//重置dis
            }
            for (int fIndex = 0; fIndex < fSize; fIndex++) {
                final int finalFIndex = fIndex;//保证能够插入内部类里面
                individuals.sort(new Comparator<Individual>() {//根据适应度下标排序
                    @Override
                    public int compare(Individual o1, Individual o2) {
                        double sub = o1.fitness[finalFIndex]-o2.fitness[finalFIndex];
                        if(sub==0)return 0;
                        if (sub>0){
                            return 1;
                        } else return -1;
                    }
                });
                individuals.get(0).setDistance(Double.MAX_VALUE);
                individuals.get(len-1).setDistance(Double.MAX_VALUE);//边界点无穷大
                double fMax = individuals.get(len-1).fitness[fIndex];
                double fMin = individuals.get(0).fitness[fIndex];
                for (int i = 1; i < len-1; i++) {
                    double fDown = individuals.get(i-1).fitness[fIndex];
                    double fUp = individuals.get(i+1).fitness[fIndex];
                    Individual  a = individuals.get(i);
                    a.setDistance(a.getDistance()+(fUp-fDown)/(fMax-fMin));
                }
            }
        }

    }
    public HashMap<Integer,List<Individual>> noDominateSort(List<Individual> individuals){
    //public void setNoDominateRank(List<Individual> individuals){
        for (int i = 0; i < individuals.size(); i++) {
            individuals.get(i).setRank(0);
        }
        int len = individuals.size();
        int n[] = new int[len];//记录个体被多少个人支配
        Set<Integer> S[] = new HashSet[len];
        List<Integer> front = new LinkedList<>();
        int rank[] = new int[len];
        for (int i = 0; i < len; i++) {
            Set<Integer> set = new HashSet();
            S[i] = set;
            for (int j = 0; j < len; j++) {
                if(i==j)continue;//自己和自己比就跳过
                int isDominate = individuals.get(i).isDominate(individuals.get(j));
                if(isDominate==1){//i支配j
                    set.add(j);
                }
                else if (isDominate==-1){//j支配i
                    n[i] = n[i]+1;
                }
            }
            if(n[i]==0){
                rank[i] = 1;
                front.add(i);
            }
        }
        int i = 1;
        while(front.size()!=0){
            List<Integer> Q = new LinkedList<>();
            for (int p:
                    front) {
                for (int q:
                        S[p]) {
                    n[q] = n[q] - 1;
                    if(n[q] == 0){
                        rank[q] = i+1;
                        individuals.get(q).setRank(rank[q]);//设置每个的等级
                        Q.add(q);
                    }
                }
            }
            i = i + 1;
            front = Q;
        }
        //启用这个代码能够直接获得一个hashmap。
        HashMap<Integer,List<Individual>> res = new HashMap<>();
        for (int j = 0; j < len; j++) {
            if (res.get(rank[j])==null){
                List<Individual> list = new ArrayList<>();;
                list.add(individuals.get(j));
                res.put(rank[j],list);
            }else {
                res.get(rank[j]).add(individuals.get(j));
            }
        }

        for (int j = 0; j < len; j++) {
            individuals.get(j).setRank(rank[j]);
        }
        return res;
    }

    public List<Individual> init(int populationSize){
        List<Individual> individuals = new ArrayList<>(populationSize);
        for (int i = 0; i < populationSize; i++) {
            List<Double> list = new ArrayList<>(dim);
            for (int j = 0; j < dim; j++) {
                list.add(lb+(ub-lb)*random());
            }
            Individual individual = new Individual(list);
            individuals.add(individual);
        }
        return individuals;
    }
    private double getSuitLimitX(double x){
        if (x > ub || x < lb) {//越界判断
            x =  lb + abs(x) % (ub - lb);
        }
        return x;
    }
    class Individual{
        int rank;
        double distance;
        double[] fitness;//越小越好捏
        List<Double> position = new LinkedList<>();
        public Individual(double[] fitness) {
            this.fitness = fitness;
        }
        //will auto set fitness
        public Individual(List<Double> positon){
            this.position = positon;
            this.fitness = culFitness(position);
        }
        // a > b return 1;
        // a >< b return 0;
        // a < b return -1;
        public int isDominate (Individual b){
            double[] bf = b.fitness;
            boolean flag = true;
            boolean notEqualFlag = false;
            //先判断a是否支配b
            for (int i = 0; i < fitness.length; i++) {
                if(fitness[i]>bf[i]){//a不支配b;
                    flag = false;
                    break;
                }
                if (fitness[i]!=bf[i]){
                    notEqualFlag = true;
                }
            }
            if (flag&&notEqualFlag){
                return 1;
            }
            flag = true;
            notEqualFlag = false;
            for (int i = 0; i < fitness.length; i++) {
                if(fitness[i]<bf[i]){//b不支配a;
                    flag = false;
                    break;
                }
                if (fitness[i]!=bf[i]){
                    notEqualFlag = true;
                }
            }
            if (flag&&notEqualFlag){
                return -1;
            }else return 0;
        }

        @Override
        public String toString() {
            return new StringBuffer("rank:"+rank+",distance:"+distance+",fitness:"+Arrays.toString(fitness)).toString();
        }

        public int getRank() {
            return rank;
        }

        public void setRank(int rank) {
            this.rank = rank;
        }

        public double getDistance() {
            return distance;
        }

        public void setDistance(double distance) {
            this.distance = distance;
        }
    }
    public double[] culFitness(List<Double> position){
        return FUtil.ZDT1(position);
    }
    interface ICul{
        double[] culFitness(List<Double> position);
    }
}

五，实验结果（ZTD1）

在这里插入图片描述

public static double[] ZDT1(List<Double> x){
        double a = x.get(0);
        double gX;
        int n = x.size();
        double sum = 0;
        for (int i = 1; i < n; i++) {
            sum += x.get(i);
        }
        gX = 1 + 9.0*sum/(n-1);
        double b = gX*(1-Math.sqrt(a/gX));
        return new double[]{a,b};
    }

在这里插入图片描述

作者的话

文章加粗符号的一定要看，因为这些地方一错就得不出来结果了，同时这篇文章的主要代码我都放出来了，画图的代码由于篇幅的问题没有放出来，NSGA-II的整个代码也会在有空的时候push到GitHub上面

相关文章