基于遗传算法的优化问题求解 - 快车库

生物学中的进化论的核心为“物竞天择，适者生存”，暗含了的规则是生物能否生存是不定的，但是适应环境的生物更容易生存。生物的多样性能够保持来源于繁殖和变异。
没错，你没有点错，这的确是一篇有关人工智能入门的博客。开篇先提到一些生物学的观点是因为，人工智能中遗传算法的灵感来源于生物学，它是一种仿生的概念。

一.遗传算法
那么，什么是遗传算法呢？我们来举个栗子吧。
在爬虫动物园里有着各种各样的蚂蚁，我想选出一种蚂蚁来代表动物园去参加全城动物园的蚂蚁战斗比赛。那我该怎么选呢？这里有一个聪明人提出了一个方法：首先，我们从各个蚂蚁的种群中选择出一部分来（选择初代种群），让他们相互打架，然后把胜者留下来互相繁殖（交叉产生子代，选择了比较好的基因进行遗传）。把小蚂蚁养大，然后再让它们打架，胜者繁殖（不断生成子代）。通过多次的繁殖和选择，动物园有极大的可能选出的蚂蚁是所有蚂蚁中打架最厉害的。
好吧，这个例子不是特别的好。我理解的遗传算法，就是一个多点的不定向搜索。它通过多次的实验，来找到符合适应度函数的个体。

二.基本步骤
基本的步骤如下：
1.编码：将我们可以用来搜索的部分编码，常用二进制串
2.产生初代：
3.计算每个个体的适应度及适应度占总体的比例（这里我使用了轮盘赌方案）：
4.以交叉概率选择父代母代进行交叉
5.以变异概率进行变异
6.生成满足种群容量的子代
7.进化多代

三.代码及说明
Java代码：

import java.math.BigDecimal;
import java.util.Random;

public class Genetic {
    int geneSize = 20;
    int populationSize = 50;
    int iterationNum =100;
    double crossoverPro =0.8;
    double mutationPro = 0.05;
    int [][] individual = new int[populationSize][geneSize];
    double [] realValue =new double[populationSize];
    double [] fitness =new double [50];
    double [] fitnessPro =new double [populationSize];
    double currentOpt =0;
    int currentX =0;
    Random random =new Random();
    double [] max =new double[iterationNum];

    public void init(){
        for(int i =0;i<populationSize;i++){    
            for(int j =0;j<geneSize;j++){
                if(random.nextBoolean())
                    individual[i][j] =1;
                else 
                    individual[i][j] =0;
            }
        }
    }
    
    private void CalRealValue(){
        for(int i =0;i<populationSize;i++){
            realValue[i] =0;
            double decimal = 0;
            for(int j =0;j<3;j++){
                realValue[i] = realValue[i]*2+individual[i][j];
            }
            for(int j =geneSize-1;j>=3;j--){
                decimal = decimal/2+individual[i][j];
            }
            realValue[i] += decimal/2; 
        }
    }
    
    private void CalFitnessAndFitnessPro(){
        double sum =0;
        currentOpt =0;
        currentX =0;
        for(int i =0;i<populationSize;i++){    
            fitness[i] = realValue[i]+10*Math.sin(5*realValue[i])+7*Math.cos(4*realValue[i])+17;
            if(currentOpt<fitness[i]){
                currentOpt =fitness[i];
                currentX =i;
            }
            sum+=fitness[i];
            
        }
        double section =0;
        for(int i =0;i<populationSize;i++){
            section +=fitness[i];
            fitnessPro[i] = section/sum;
        }
    }
    
    private void Reproduction(){
        int [][] temp =new int [populationSize][geneSize];
        
        //交叉
        for(int i =0;i<populationSize-1;i=i+2){
            int [] father =new int [geneSize];
            double pro = random.nextDouble();
            for(int j=0;j<populationSize;j++){
                if(fitnessPro[j]>=pro){
                    for(int k =0;k<geneSize;k++)
                        father[k] = individual[j][k];
                    break;
                }
            }
            pro =random.nextDouble();
            int [] mother =new int [geneSize];
            for(int j=0;j<populationSize;j++){
                if(fitnessPro[j]>=pro){
                    for(int k =0;k<geneSize;k++)
                        mother[k] = individual[j][k];
                    break;
                }            
            }
            double pm =random.nextDouble();
            if(pm<crossoverPro){
                int changePosition =random.nextInt(geneSize);
                for(int j=0;j<geneSize;j++){
                    if(j<changePosition){
                        temp[i][j] =father[j];
                        temp[i+1][j] = mother[j];
                    }
                    else {
                        temp[i][j] = mother[j];    
                        temp[i+1][j] = father[j];
                    }
                }
            }else{
                for(int j=0;j<geneSize;j++){
                        temp[i][j] =father[j];
                        temp[i+1][j] = mother[j];
                }
            }
        }
        
        for(int i =0;i<geneSize;i++){
            individual[populationSize-1][i] = individual[currentX][i];
        }
            
        //变异
        for(int i =0;i<populationSize-1;i++){    
            for(int j =0;j<geneSize;j++){
                if(random.nextDouble()<mutationPro)
                    individual[i][j] = 1- temp[i][j];
                else 
                    individual[i][j] = temp[i][j];
            }
        }    
    }
    
    public Genetic(){
        init();
        for(int i =0;i<iterationNum;i++){
            CalRealValue();
            CalFitnessAndFitnessPro();
            BigDecimal optTemp =new BigDecimal(currentOpt-17);
            BigDecimal valueTemp =new BigDecimal(realValue[currentX]);
            optTemp =optTemp.setScale(5, BigDecimal.ROUND_HALF_UP);
            valueTemp =valueTemp.setScale(5, BigDecimal.ROUND_HALF_UP);
            System.out.println("第"+i+"代，最大值为："+optTemp+"      对应X是："+valueTemp);
            max[i] = currentOpt-17;
            Reproduction();
        }
    }

    public double[] getMax(){
        return max;
    }
    
    public static void main(String[] args) {
        
        Genetic genetic =new Genetic();
    }
}

这里我使用了二进制编码，单点交叉，轮盘赌加精英选择（没代向下完整保留最优个体）。我目标是计算f(x) = x+ 10sin5x + 7cos4x 在[0,9]区间上的极大值，之所以在适应度函数里加入还加了17是因为f(x)在某些位置的时候是取到负数（最小-17），而参与轮盘赌计算的函数必须是正数，所以我加了17.

四.小尝试
二进制编码在0.001这样的数的时候是不精确的，于是我想能不能用十进制来解决这个问题呢？下面我尝试做了十进制编码（精确度是0.00001）
Java代码：

import java.math.BigDecimal;
import java.util.Random;

public class DecimalGenetic {
    int geneSize = 6;
    int populationSize = 50;
    int iterationNum =100;
    double crossoverPro =0.8;
    double mutationPro = 0.01;
    int [][] individual = new int[populationSize][geneSize];
    double [] realValue =new double[populationSize];
    double [] fitness =new double [50];
    double [] fitnessPro =new double [populationSize];
    double currentOpt =0;
    int currentX =0;
    Random random =new Random();
    double []max =new double[iterationNum];
    
    public void init(){
        for(int i =0;i<populationSize;i++){        
            for(int j =0;j<geneSize;j++){
                if(j == 0)
                    individual[i][j] =random.nextInt(9);
                else
                    individual[i][j] =random.nextInt(10);
            }        
        }
    }
    
    private void CalRealValue(){
        for(int i =0;i<populationSize;i++){
            realValue[i] =0;
            realValue[i]+=individual[i][0];
            double decimal = 0;
            for(int j =geneSize-1;j>0;j--){
                decimal = decimal/10+individual[i][j];
            }
            realValue[i] += decimal/10; 
        //    System.out.println(realValue[i]+"   "+i);
        }
    }
    
    private void CalFitnessAndFitnessPro(){
        double sum =0;
        currentOpt =0;
        currentX =0;
        for(int i =0;i<populationSize;i++){    
            fitness[i] = realValue[i]+10*Math.sin(5*realValue[i])+7*Math.cos(4*realValue[i])+17;
            if(currentOpt<fitness[i]){
                currentOpt =fitness[i];
                currentX =i;
            }
            sum+=fitness[i];    
        }
        double section =0;
        for(int i =0;i<populationSize;i++){
            section +=fitness[i];
            fitnessPro[i] = section/sum;
        }
    }
    
    private void Reproduction(){
        int [][] temp =new int [populationSize][geneSize];
        
        //产生交叉
        for(int i =0;i<populationSize-1;i=i+2){
            int [] father =new int [geneSize];
            double pro = random.nextDouble();
            for(int j=0;j<populationSize;j++){
                if(fitnessPro[j]>=pro){
                    for(int k =0;k<geneSize;k++)
                        father[k] = individual[j][k];
                    break;
                }
            }
            pro =random.nextDouble();
            int [] mother =new int [geneSize];
            for(int j=0;j<populationSize;j++){
                if(fitnessPro[j]>=pro){
                    for(int k =0;k<geneSize;k++)
                        mother[k] = individual[j][k];
                    break;
                }            
            }
            double pm = random.nextDouble();
            if(pm<crossoverPro){
                int changePosition =random.nextInt(geneSize);
                for(int j=0;j<geneSize;j++){
                    if(j<changePosition){
                        temp[i][j] =father[j];
                        temp[i+1][j] =mother[j];
                    }
                    else {
                        temp[i][j] = mother[j];    
                        temp[i+1][j] = father[j];    
                    }
                }
            }
            else{
                for(int j=0;j<geneSize;j++){
                    temp[i][j] =father[j];
                    temp[i+1][j] =mother[j];
                }
            }
        }
        
        for(int i =0;i<geneSize;i++){
            individual[populationSize-1][i] = individual[currentX][i];
        }
            
        //变异
        for(int i =0;i<populationSize-1;i++){
            for(int j =0;j<geneSize;j++){
                if(random.nextDouble()<mutationPro)
                    individual[i][j] = random.nextInt(10);
                else 
                    individual[i][j] = temp[i][j];
            }
        }
    }
    
    public DecimalGenetic(){
        init();
        for(int i =0;i<iterationNum;i++){
            CalRealValue();
            CalFitnessAndFitnessPro();
            BigDecimal optTemp =new BigDecimal(currentOpt-17);
            optTemp =optTemp.setScale(5, BigDecimal.ROUND_HALF_UP);
            System.out.println("第"+i+"代，最大值为："+optTemp+"      对应X是："+realValue[currentX]);
            max[i] = currentOpt-17;
            Reproduction();
        }
    }
    
    public double[] getMax(){
        return max;
    }

    
    public static void main(String[] args) {
        DecimalGenetic decimalGenetic =new DecimalGenetic();
    }

}

实现和二进制大部分一致，但是在变异部分我用了取随机数这个方法。

五.思考：
关于编码，我在做完之后有一些思考，想和大家分享.我们编码一个数据，用0-1串表示，每一位是没有差别的，但是转换为数字的时候，每一位的权值是不同的。对于真正的自然界，每个性状对于生物的存活几率的影响也是不同的。比如果蝇的翅膀大小和眼色对于它的生存几率的影响是不同的，那反应成我们这里的编码就是位置不同，权重不同.这里算是遗传算法的奇妙之处吧.

下面推荐一个讲述比较完整的博客：https://segmentfault.com/a/1190000004155021