自话遗传算法（带实例）

简介

出来工作快一年了，虽然有太多的茫然和挣扎，但很想找回曾经那个狂热的自己。最近想整理一下以前写的一些小东西和文章，这是整理的第一篇，既是我的过去，也将激励我的未来。

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA），这里我就直接摘抄百度百科了。

术语

种群（population）

基因（gene）

染色体（chromosome）

表现型(phenotype)

编码（codeing）

解码（decodeing）

交叉( Crossover )

突变 ( Mutation )

基本思想

正如简介所描述的那样，遗传算法是模拟达尔文的进化论思想，我想"生存竞争，适者生存"正好简要的阐述了这一算法的基本特质。用适应函数去考核每个基因的生存能力，用选择交叉变异去实现进化，搜索出种群的近似最优解，其主要步骤如下：

1.初始化种群
2.适应选择
3.交叉变异

算法描述

为了更好的描述，这里我以一个01背包问题为例子来简单的阐述遗传算法。

给定一个背包C=100，N=5个物品，其重量和价值分别如下，求这个背包能装的最大价值是多少

1     77 92
2     22 22
3     29 87
4     50 46
5     99 90

那么针对上面这个问题，首先我们要考虑编码，也就是把它转换成我们的基因型的形式，这里，我们用一个长度为5的二进制字符串表示相应物品的取舍。其基因型（染色体）就是10100,那么表现型就是选择了1号物品和3号物品。有编码自然就有解码，就是把基因型转换成表现型，编码个人认为是遗传算法中至关重要的一步，怎么根据问题去选择编码方式，直接影响了后面所提到的适应函数的简与复杂。

把问题映射到基因型上我们已经解决了，现在就是怎么去考核一个基因型对当前环境的适应度，换句话说就是更有可能存活遗传下去，那么这里我们必须得设计一个适应函数f，因为是求背包的最大值，又因为不能超过背包所能承受的总重量，所以用h(x)表示第二个不超过总重量的条件，f(y)表示背包的价值，所以得到适应函数f(h(x))。

然后就是怎么去选择的问题，我们用p(x)=f(y)/totall(f(y))来表示某个基因型占总体的概率，现在我们就采用轮盘赌的方法，什么是轮盘赌呢，这里简要提及一下，我们把各个概率放在一个轮盘里，然后转动这个轮盘，最后轮盘停止，指针停在哪里就代表选择哪个概率的事件。

比如在01背包中，我们根据适应函数算出各个基因型的适应度，也算出了每个基因型所占的比例，然后我们根据轮盘赌的方法从中选择出n条基因型出来，然后n条基因型随机两两配对交叉产生两个子代。

交叉

那么什么是交叉呢，和生物学中染色体交叉是一样的概念，就是互换某一段基因，如下图，这里我们采用的是单点交叉。

变异

变异是指，在某一个比较小的概率下，某个基因在遗传时，某个基因座上的基因由0边成1，或者由1变成0。

新产生的基因型，如果原来的种群中没有的话，就加进这个种群，然后再按上面所述去迭代，直到找到我们比较满意的基因型为止，现在我们什么都准备好了，就让它们去交配把，去创建一个种族吧。

下面给出按照上面的例子我临时打的代码.

package artiano.ga;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Chromosome{
    String key;
    double f;
    double p;
    public Chromosome(String key,double f,double p){
        this.key=key;
        this.f=f;
        this.p=p;
    }
    public Chromosome(Chromosome o){
        this.key=o.key;
        this.f=o.f;
        this.p=o.p;        
    }
}

public class GAtest { 
    public Map<String,Chromosome> SAVE=new HashMap<String,Chromosome>();
    public List<Chromosome> list;
    public double[][] B={
            {77,92},
            {22,22},
            {29,87},
            {50,46},
            {99,90}
    };
    private double M=100;
    private int N=5;
    
    public double toPhenotype(String key){ //解码成表现型

        double count=0;
        for(int i=0;i<key.length();i++){
            if(key.charAt(i)=='1'){
                count+=B[i][1];
            }
        }
        return count;        
    }
    public void init(int n){ //这里的初始化种族应该是随机的，这里为了简单起见，我随便给了一组
        SAVE.put("10000", new Chromosome("10000",0,0));
        SAVE.put("01100", new Chromosome("01100",0,0));
        SAVE.put("00001", new Chromosome("00001",0,0));
        SAVE.put("01010", new Chromosome("01010",0,0));
        
    }
    public String lunpandu(){  //轮盘赌
        double nowP=Math.random();
        Set<String> keySet=SAVE.keySet();
        Iterator it=keySet.iterator();
        double m=0;
        while(it.hasNext()){
            String key=(String)it.next();
            Chromosome o=SAVE.get(key);
            m+=o.p;
            if(nowP<=m) return key;
        }
        return "";
    } 
    public Chromosome selected(){  //选择
        Set<String> keySet=SAVE.keySet();
        Iterator it=keySet.iterator();
        double count=0;
        Chromosome max=new Chromosome("-1",0,0);
        while(it.hasNext()){
            String key=(String)it.next();
            Chromosome o=SAVE.get(key);
            count+=o.f=toPhenotype(key);
            if(o.f>max.f) max=o;
        }
        it=keySet.iterator();
        while(it.hasNext()){
            String key=(String)it.next();
            Chromosome o=SAVE.get(key);
            o.p=o.f/count;
            
            System.out.println(o.key+"    "+o.f+"   "+o.p);
        }
        list=new LinkedList<Chromosome>();
        for(int i=0;i<2;i++){
            String seleKey=lunpandu();
            list.add(new Chromosome(SAVE.get(seleKey)));
            System.out.println("--->"+seleKey);
        }
        return max;
    }
    
    public void crossover(){ //交叉
        for(int i=0;i<list.size()/2;i++){
            Chromosome o1=list.get(i*2); 
            Chromosome o2=list.get(i*2+1);
            int index=(int)Math.round(1+Math.random() * 2);
            String o11=o1.key.substring(0, index);
            String o12=o1.key.substring(index, o1.key.length());
            String o21=o2.key.substring(0, index);
            String o22=o2.key.substring(index, o1.key.length());
            System.out.println("|||| "+o11+" | "+o12);
            System.out.println("|||| "+o21+" | "+o22);
            o1.key=o11+o22;
            o2.key=o21+o12;
            System.out.println("|||| "+o1.key);
            System.out.println("|||| "+o2.key);
            long bianyi=Math.round(Math.random() * 10000);
            if(bianyi<100);
            
            if(hefa(o1.key) && SAVE.get(o1.key)==null) SAVE.put(o1.key, o1);
            if(hefa(o2.key) && SAVE.get(o2.key)==null) SAVE.put(o2.key, o2);
        }
    }
    public boolean hefa(String key){ //是否满足h(x)
        double m=0;
        for(int i=0;i<N;i++){
            if(key.charAt(i)=='1'){
                m+=B[i][0];
            }
        }
        if(m<=M)return true;
        return false;
    }
    public void iteration(int n){ //种群迭代
        for(int i=0;i<n;i++){
            System.out.println("========="+(i+1));
            Chromosome max=selected();
            if(max.f>=133){
                System.out.println("                [----"+max.key+"  "+max.f+"  "+max.p+"-----]");
                break;
            }
            crossover();
        }

        
    }
    public static void main(String[] args){
        GAtest ts=new GAtest();
        ts.init(6);
        ts.iteration(510);
        
    }

}

打印结果:

=========1
00001    90.0   0.25069637883008355
10000    92.0   0.2562674094707521
01010    68.0   0.1894150417827298
01100    109.0   0.30362116991643456
--->01100
--->01100
|||| 01 | 100
|||| 01 | 100
|||| 01100
|||| 01100
=========2
00001    90.0   0.25069637883008355
10000    92.0   0.2562674094707521
01010    68.0   0.1894150417827298
01100    109.0   0.30362116991643456
--->01100
--->01100
|||| 0 | 1100
|||| 0 | 1100
|||| 01100
|||| 01100
=========3
00001    90.0   0.25069637883008355
10000    92.0   0.2562674094707521
01010    68.0   0.1894150417827298
01100    109.0   0.30362116991643456
--->10000
--->00001
|||| 10 | 000
|||| 00 | 001
|||| 10001
|||| 00000
=========4
00000    0.0   0.0
00001    90.0   0.25069637883008355
10000    92.0   0.2562674094707521
01010    68.0   0.1894150417827298
01100    109.0   0.30362116991643456
--->01100
--->00001
|||| 011 | 00
|||| 000 | 01
|||| 01101
|||| 00000
=========5
00000    0.0   0.0
00001    90.0   0.25069637883008355
10000    92.0   0.2562674094707521
01010    68.0   0.1894150417827298
01100    109.0   0.30362116991643456
--->00001
--->10000
|||| 00 | 001
|||| 10 | 000
|||| 00000
|||| 10001
=========6
00000    0.0   0.0
00001    90.0   0.25069637883008355
10000    92.0   0.2562674094707521
01010    68.0   0.1894150417827298
01100    109.0   0.30362116991643456
--->00001
--->01100
|||| 00 | 001
|||| 01 | 100
|||| 00100
|||| 01001
=========7
00000    0.0   0.0
00001    90.0   0.20179372197309417
10000    92.0   0.2062780269058296
01010    68.0   0.15246636771300448
00100    87.0   0.19506726457399104
01100    109.0   0.24439461883408073
--->01100
--->01010
|||| 0 | 1100
|||| 0 | 1010
|||| 01010
|||| 01100
=========8
00000    0.0   0.0
00001    90.0   0.20179372197309417
10000    92.0   0.2062780269058296
01010    68.0   0.15246636771300448
00100    87.0   0.19506726457399104
01100    109.0   0.24439461883408073
--->10000
--->01100
|||| 10 | 000
|||| 01 | 100
|||| 10100
|||| 01000
=========9
00000    0.0   0.0
00001    90.0   0.19230769230769232
10000    92.0   0.19658119658119658
01000    22.0   0.04700854700854701
01010    68.0   0.1452991452991453
00100    87.0   0.1858974358974359
01100    109.0   0.2329059829059829
--->00100
--->00100
|||| 0 | 0100
|||| 0 | 0100
|||| 00100
|||| 00100
=========10
00000    0.0   0.0
00001    90.0   0.19230769230769232
10000    92.0   0.19658119658119658
01000    22.0   0.04700854700854701
01010    68.0   0.1452991452991453
00100    87.0   0.1858974358974359
01100    109.0   0.2329059829059829
--->10000
--->01010
|||| 10 | 000
|||| 01 | 010
|||| 10010
|||| 01000
=========11
00000    0.0   0.0
00001    90.0   0.19230769230769232
10000    92.0   0.19658119658119658
01000    22.0   0.04700854700854701
01010    68.0   0.1452991452991453
00100    87.0   0.1858974358974359
01100    109.0   0.2329059829059829
--->01100
--->01100
|||| 01 | 100
|||| 01 | 100
|||| 01100
|||| 01100
=========12
00000    0.0   0.0
00001    90.0   0.19230769230769232
10000    92.0   0.19658119658119658
01000    22.0   0.04700854700854701
01010    68.0   0.1452991452991453
00100    87.0   0.1858974358974359
01100    109.0   0.2329059829059829
--->00001
--->10000
|||| 000 | 01
|||| 100 | 00
|||| 00000
|||| 10001
=========13
00000    0.0   0.0
00001    90.0   0.19230769230769232
10000    92.0   0.19658119658119658
01000    22.0   0.04700854700854701
01010    68.0   0.1452991452991453
00100    87.0   0.1858974358974359
01100    109.0   0.2329059829059829
--->00100
--->00001
|||| 001 | 00
|||| 000 | 01
|||| 00101
|||| 00000
=========14
00000    0.0   0.0
00001    90.0   0.19230769230769232
10000    92.0   0.19658119658119658
01000    22.0   0.04700854700854701
01010    68.0   0.1452991452991453
00100    87.0   0.1858974358974359
01100    109.0   0.2329059829059829
--->00100
--->00100
|||| 00 | 100
|||| 00 | 100
|||| 00100
|||| 00100
=========15
00000    0.0   0.0
00001    90.0   0.19230769230769232
10000    92.0   0.19658119658119658
01000    22.0   0.04700854700854701
01010    68.0   0.1452991452991453
00100    87.0   0.1858974358974359
01100    109.0   0.2329059829059829
--->10000
--->01100
|||| 1 | 0000
|||| 0 | 1100
|||| 11100
|||| 00000
=========16
00000    0.0   0.0
00001    90.0   0.19230769230769232
10000    92.0   0.19658119658119658
01000    22.0   0.04700854700854701
01010    68.0   0.1452991452991453
00100    87.0   0.1858974358974359
01100    109.0   0.2329059829059829
--->00001
--->00100
|||| 00 | 001
|||| 00 | 100
|||| 00100
|||| 00001
=========17
00000    0.0   0.0
00001    90.0   0.19230769230769232
10000    92.0   0.19658119658119658
01000    22.0   0.04700854700854701
01010    68.0   0.1452991452991453
00100    87.0   0.1858974358974359
01100    109.0   0.2329059829059829
--->01010
--->00100
|||| 010 | 10
|||| 001 | 00
|||| 01000
|||| 00110
=========18
00000    0.0   0.0
00001    90.0   0.1497504159733777
10000    92.0   0.15307820299500832
01000    22.0   0.036605657237936774
01010    68.0   0.11314475873544093
00110    133.0   0.22129783693843594
00100    87.0   0.1447587354409318
01100    109.0   0.18136439267886856
--->00001
--->01100
                [----00110  133.0  0.22129783693843594-----]

最后

正如我们看见的那样，遗传算法，每次迭代都会从整个集合中去计算选择，然后通过交叉变异去产生新的种群，这样的好处显而易见，不会像梯度下降，贪心这类算法会陷入局部最优,至于其编码的选择，我想编码的好坏决定了适应函数的简单还是复杂的程度，适应函数设计的好坏决定了，整个算法是否能更快更好的收敛于近似最优。注意这里，遗传算法不能保证会得到最优解，但是在整个迭代过程，它会不断的接近于最优。

值得一提的是，遗传算法是基于图式理论的，其基因型从各个特征进行描述，这样就隐含了其搜索过程是并行处理的，对于隐含并行能力，现在已经给出了证明，每次迭代，对于n的种群，大致处理了O(n^3)个状态，这个处理能力还是相当吃惊的。