自话遗传算法（带实例）

简介

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

遗传算法（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)个状态，这个处理能力还是相当吃惊的。

最后编辑于：2017.12.03 03:30:46

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 223,858评论 6赞 521
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 95,753评论 3赞 402
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 170,876评论 0赞 366
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 60,560评论 1赞 300
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 69,574评论 6赞 399
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 53,097评论 1赞 314
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 41,477评论 3赞 427
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 40,452评论 0赞 278
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,980评论 1赞 324
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 39,017评论 3赞 343
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 41,168评论 1赞 354
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 36,807评论 5赞 350
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 42,497评论 3赞 336
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,976评论 0赞 25
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 34,094评论 1赞 275
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 49,659评论 3赞 380
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 46,196评论 2赞 363

自话遗传算法（带实例）

简介

术语

基本思想

算法描述

最后

推荐阅读更多精彩内容