学步园

        我们来研究一下遗传算法（GA）。GA的理论部分可以去google或者Wikipedia上问，现在我们通过一个具体的例子来说明一下。
        首先，遗传算法可以解决很多问题。比如训练神经网络~，本文主要通过下面这个例子来讲解：
        假设有10张卡牌，上面数字为1-10，要求将这10张卡牌分为两组，每组5张，第一组的5个数字只和为36，第二组的5个数字之积为360；
        当然这个问题也可以通过其他方法求解，这里我们要介绍的是通过遗传算法解决。遗传算法是一种通过模拟自然进化过程搜索最优解的方法。其           计算过程如下：
a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价：计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。
e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。
f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
        简单说就是这样子：从解决方案集合中随机选择两个解决方案 ；判断哪个方案的结果更接近想要的结果，表示为成功方案；用成功方案代替失败方案，或者将修改失败方案使之更接近成功方案，形成新的解决方案集合。

        代码实现过程是这样子的：首先初始化一个解决方案集合

private void init(){
      //初始化解决方案集合
        for (int i = 0; i < pop; i++){
            for (int j = 0; j < len; j++){
                if (random.nextDouble() < 0.5){
                    matr[i][j] = 0;
                }else{
                    matr[i][j] = 1;
                }
            }
        }
    }

然后写判断方案的函数

private double evaluate(int n){//判断成功方案
        int sum = 0;
        int prod = 1;
        double sumError = 0;
        double prodError = 0;
        for(int i = 0; i < len; i++){
            if(matr[n][i] == 0){
                sum += (i + 1);
            }else {
                prod *= (i + 1);
            }
        }
        sumError = (sum - sumTarget)/sumTarget;
        prodError = (prod - prodTarget)/prodTarget;
        
        return Math.abs(sumError) + Math.abs(prodError);
    }

最后写迭代遗传

public int[] run(){
        int winner = 0;
        int loser = 0;
        int[] ret = new int[10];
        while(times-- > 1){
            int a = (int)(random.nextDouble() * pop);
            int b = (int)(random.nextDouble() * pop);
            if(evaluate(a) < evaluate(b)){
                winner = a;
                loser = b;
            }else{
                winner = b;
                loser = a;
            }
            for(int i = 0; i < len; i++){
                if(random.nextDouble() > 0.1){//10%概率不发生交叉
                    matr[loser][i] = matr[winner][i];
                }
                if(random.nextDouble() < 0.1){//10%概率发生突变
                    matr[loser][i] = 1 - matr[loser][i];
                }
                if(evaluate(loser) == 0){//获取最优解
                    ret = getResult(loser);
                    System.out.println("经过"+(1000 - times)+"代获取最优解");
                    return ret;
                }
            }
            if(ret[0] == 0 && times == 1){//如果经最后一次计算，获取给特殊解：0+0+0+0+0 = 0 和 0*0*0*0*0 = 0；再重新计算一次
                times++;
            }
        }
        return ret;
    }