遗传算法

准备每天开始写日志博客，记录每天自己学到的内容，有一个复习的地方。今天是2019年的11月20日，第一篇。
加油！
首先这几天对项目之前的算法，代码进行回顾复习。

遗传算法
遗传算法无疑分为四个部分，首先要确定染色体类，并能够解释染色体，即编码译码，我认为是整个遗传算法应用到具体项目中最关键的步骤；其次确定适应度的计算，最后就是种群进行遗传。

确定染色体类
首先要随机生成基因序列，初始化基因长度，确定基因长度后，也要记得判断染色体是否合法（在编码时就要考虑）：

    do {
            for (int i = 0; i < size; i++) {
                gene[i] = Math.random() >= 0.5;
            }
        } while (!CodeInfo.getUniqueInstance().judgeChromosome(this));

对于每一个染色体，就要涉及到它的克隆，如何遗传产生下一代，以及变异。
克隆基因就是复制一下基因：

 for (int i = 0; i < c.gene.length; i++) {
            copy.gene[i] = c.gene[i];
        }

遗传产生下一代，即是对两个现有的基因序列随机交叉（最好是对目前基因的克隆基因来进行），确定交叉位置后对位置上的基因进行交叉互换，也要记得判断时候合法。

        Chromosome c1 = clone(p1);
        Chromosome c2 = clone(p2);
        //随机产生交叉互换位置
        int size = c1.gene.length;
        CodeInfo ci = CodeInfo.getUniqueInstance();
        do {
            int a = ((int) (Math.random() * size)) % size;
            int b = ((int) (Math.random() * size)) % size;
            int min = a > b ? b : a;
            int max = a > b ? a : b;
            //对位置上的基因进行交叉互换
            for (int i = min; i <= max; i++) {
                boolean t = c1.gene[i];
                c1.gene[i] = c2.gene[i];
                c2.gene[i] = t;
            }
        } while (!ci.judgeChromosome(c1) || !ci.judgeChromosome(c2));
        List<Chromosome> list = new ArrayList<Chromosome>();
        list.add(c1);
        list.add(c2);
        return list;

至于发生变异，就是随机选择变异位置后，因为最初的基因序列设置为布尔型数组，变异就是换成相反的：

    do {
            for (int i = 0; i < num; i++) {
                //寻找变异位置
                int at = ((int) (Math.random() * size)) % size;
                //变异后的值
                boolean bool = !gene[at];
                gene[at] = bool;
            }
        } while (!ci.judgeChromosome(this));

最后，因为最初初始化时基因序列为布尔型数组，为了方便下一步的编码译码，还是应该把一段儿基因转化成对应的数字：

        long num = 0;
        int tmp = start;
        start = gene.length - end - 1;
        end = gene.length - tmp - 1;
        for (int i = start; i <= end; i++) {
            num <<= 1;
            if (gene[i]) {
                num += 1;
            }
        }

编码译码
应该是遗传算法应用到具体的项目中，最重要核心的地方，怎么针对于自己的项目进行建模，把自己需要的东西转换成一个个可以用到遗传算法中的基因序列。
因为整个问题的所有需要遗传算法计算的东西都要巧妙融合到一串基因序列中，就要把整个基因序列分成几部分，每段儿基因代表一个关键信息。这也就涉及到了转换编码的相关问题。首先要想办法获得把一个十进制数deci表示成二进制的最小位数：

        double douN = Math.log(deci) / Math.log(2);
        int biDigit = (int) douN + 1;
        if (douN == (int) douN) {
            {
                biDigit = (int) douN;
            }
        }
        return biDigit;

随后调用刚才getNum把部分基因转换成数字，且要根据具体的问题，来判断基因是否合法（根据基因长度等等）。
至于解码，项目中对于优先级的解码，用到了逆康托展开解码全排列，根据全排列的位数，进行解码，解码后的全排列，与通常的全排列有区别，全排列为1~n，这里为0 ~ n-1:

public int[] decodeTotalPermutation(int digitsPermutaion, long num) {
        int[] ansPermutation = new int[digitsPermutaion];
        long[] fact = new long[digitsPermutaion + 1];
        fact[0] = 1;
        for (int i = 1; i < digitsPermutaion + 1; i++) {
            fact[i] = i * fact[i - 1];
        }
        boolean[] vis = new boolean[digitsPermutaion + 2];//已访问数组
        int i, j;
        long k;
        for (i = 0; i < digitsPermutaion; i++) {
            k = num / fact[digitsPermutaion - i - 1];
            for (j = 1; j <= digitsPermutaion; j++)
                if (!vis[j]) {
                    if (k == 0) {
                        break;
                    }
                    --k;
                }
            ansPermutation[i] = j - 1;
            vis[j] = true;
            num %= fact[digitsPermutaion - i - 1];///余数
        }
        return ansPermutation;
    }

其实对于基因序列中每个部分的解码，就需要根据它这个部分的具体问题，来考虑，或许每个部分的解码方式都不一样，最后再整体组合到一起。

适应度计算
因为遗传算法，在每代筛选父代来进行交叉组合产生子代时，肯定要选择比较好的父代，选择适应度高的。根据自己的问题选择合适的因素作为适应度，来选择更加符合自己期待的结果。
在项目中，因为是考虑选择路径最终的时间，因此就拿时间来当做最后的适应度，计算每个基因序列所代表的路径的时间，筛选用时少的，那么就是时间的倒数作为高的适应度。
在计算时间时，因为是多条路径，采用了类似于银行家算法的资源分配策略，每一轮分配资源，然后记录下该轮的资源分配情况，计算出未完成的任务的最短时间，以及这个未完成任务剩余货量，下一轮将所有路径资源返还后，进行未完成任务的下一路分配，一轮轮进行，最终所有任务完成，计算出最短的总时间，将这个时间转换成遗传算法中的分数，即适应度。

遗传算法具体流程
当所有的准备工作搞定后，就开始遗传算法的具体执行了。首先要确定合理的种群数量以及迭代次数（会大幅度影响算法的运行时间，但还是要根据具体的数据量来做一个平衡，如果数据量很小，很快就能最优解，无疑可以调低；但如果数据量比较大，则需要多一些迭代，但运行时间就相应变长），基因的变异概率，变异步长。在这些必要的系数确定后，可以再创建一些变量存储一些想得到的信息，历代最好的染色体，历代最高得分，当前代的得分，等等。
算法具体分为：
1.初始化种群
2.计算当前种群的适应度
3.种群进行遗传（轮盘赌选择可以遗传的染色体，并发生突变）
4.新种群替换旧种群
5.计算新种群的适应度
6.不断地迭代3 ~5，直到最大迭代次数

    public void calculte() {
        //初始化种群
        numGenerationOfCur = 0;
        init();
        while (numGenerationOfCur < maxIterNum) {
            //种群遗传
            evolve();
            numGenerationOfCur++;
        }
    }
    private void init() {
        population = new ArrayList<>();
        for (int i = 0; i < popSize; i++) {
            Chromosome chro = new Chromosome(geneSize);
            population.add(chro);
        }
        calculteScoreOfCurPop();
    }
    private void evolve() {
        List<Chromosome> childPopulation = new ArrayList<>();
        //生成下一代种群
        while (childPopulation.size() < popSize) {
            Chromosome p1 = getParentChromosome();
            Chromosome p2 = getParentChromosome();
            List<Chromosome> children = Chromosome.genetic(p1, p2);
            if (children != null) {
                for (Chromosome chro : children) {
                    childPopulation.add(chro);
                }
            }
        }
        //新种群替换旧种群
        List<Chromosome> t = population;
        population = childPopulation;
        t.clear();
        t = null;
        //基因突变
        mutation();
        //计算新种群的适应度
        calculteScoreOfCurPop();
    }
    private Chromosome getParentChromosome() {
        double slice = Math.random() * totalScoreOfCurPop;
        double pre = 0;
        double cur = population.get(0).getScore();
        for (Chromosome chro : population) {
            if (pre <= slice && cur > slice) {
                return chro;
            }
            pre = cur;
            cur += chro.getScore();
        }
        return null;
    }
    private void mutation() {
        for (Chromosome chro : population) {
            if (Math.random() < mutationRate) { //发生基因突变
                int mutationNum = (int) (Math.random() * maxMutationNum);
                chro.mutation(mutationNum);
            }
        }
    }

遗传算法在项目中的具体使用，大概就这些流程。
以后对于遗传算法有新的体会再逐渐添加到自己的日志中。
加油，不断成长。