• NSGA-II看这篇够了

    原文: 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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    一，快速非支配排序

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70

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

    在这里插入图片描述

    在原文中，拥挤距离的定义是在同一个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));
                }
            }
        }

    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    这里的这个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其中

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    四，全部代码

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361

    五，实验结果（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};
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在这里插入图片描述

    作者的话

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

  • 相关阅读:
    零基础入门JavaWeb——JS的事件驱动
    opencv：从0到实现人脸识别
    Spring Boot中发送邮件时，如何让发件人显示别名
    换种方式看后端参数接收、建议躺着看！！！
    SpringBoot-AOP-Logback用切面拦截操作日志
    Python国庆祝福
    PX4模块设计之三十：Hysteresis类
    高德地图系列（一）：vue项目如何使用高德地图、入门以及基本控件使用
    关于微前端，你理解到究极奥义了么？
    基于php+MYSQL的旅游景点攻略的设计与实现毕业设计源码301216
  • 原文地址：https://blog.csdn.net/qq_43445553/article/details/127642565