遗传算法

最近写了一个亦（sang）可（xin）赛（bing）艇（kuang）的遗传算法。什么是遗传算法呢？

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

一段话太抽象了，来看一张流程图：

1、初始化种群

随机生成一组染色体。

2、获取个体适应值

根据适应度函数计算个体在繁衍竞争中的适应值。

3、选择 SELECT

选择出能够将染色体传递给下一代的父母，其他的皆为淘汰者。

选择机制应该满足：

1）适应值越高的个体越可能繁殖后代（使用轮盘赌选择）。

2）适应值最高的个体能够绝对保留（避免退化）。

4、交叉 CROSS

即产生下一代。使用单点交叉法，以某个点为中心，交叉交换染色体，以产生新个体。

5、变异 MUTATE

对于每个新产生的个体，根据变异概率进行变异，即染色体的某一位发生随机变化。

那我的遗传算法是干什么的呢？用一百个半透明彩色三角形，叠加出一张目标图片。

code:

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<ctime>
#include<cmath>
using namespace std;
const unsigned randmx=0xffffffff;
unsigned x,y,z,w;
unsigned random(){//随机数生成器 
    unsigned t=x^(x<<11);
    x=y;
    y=z;
    z=w;
    return w=w^(w>>19)^t^(t>>8);
}
struct color{//颜色 
    unsigned char b,g,r;//RGB，由于BMP文件格式是BGR，因此以此顺序 
    color(unsigned char x=255,unsigned char y=255,unsigned char z=255){r=x;g=y;b=z;}
};
struct trngl{//三角形 
    struct vct{//二维向量 
        int x,y;
        vct(int xx=0,int yy=0){x=xx;y=yy;}
        vct operator-(const vct &b){return vct(x-b.x,y-b.y);}//减法 
        int operator*(const vct &b){return x*b.y-y*b.x;}//只考虑长度的叉乘 
        void rand(int h,int w){x=random()%h+1;y=random()%w+1;}//随机 
    };
    vct a,b,c;//三个顶点 
    color co;//颜色 
    trngl(int ax,int ay,int bx,int by,int cx,int cy,color cl):a(vct(ax,ay)),b(vct(bx,by)),c(vct(cx,cy)),co(cl){}
    trngl(vct aa=vct(),vct bb=vct(),vct cc=vct(),color cl=color()):a(aa),b(bb),c(cc),co(cl){}
    int area(){return abs((b-a)*(c-b));}//面积 
    bool vctin(vct p){return trngl(p,a,b).area()+trngl(p,c).area()+trngl(p,c).area()==area();}//判断点是否在三角形内，面积法 
    bool vctin(int px,int py){return vctin(vct(px,py));}
    void rand(int h,int w){//随机形状 
        a.rand(h,w);
        b.rand(h,w);
        while(a.x==b.x&&a.y==b.y)b.rand(h,w);
        c.rand(h,w);
        while((a.x==c.x&&a.y==c.y)||(b.x==c.x&&b.y==c.y))c.rand(h,w);
    }
    void cord(){co=color(random()%256,random()%256,random()%256);}//随机颜色 
};
struct genetic{
    static const int h=80,w=80,trn=100,maxp=100;//高，宽，三角形数，最大种群大小 
    static const double chgp=0.003,cgcp=0.005;//形状变异概率，颜色变异概率 
    template<int H,int W,int T>
    struct pic{//一个图像 
        trngl trns[T+1];//三角形 
        color co[H+1][W+1];//每个像素的颜色 
        int con[H+1][W+1],bes;//每个像素上的三角形数，适应值 
        pic(){bes=0;}
        void init(){//从三角形初始化图形 
            for(int i=1;i<=H;i++){
                for(int j=1;j<=W;j++){//所有三角形颜色取平均 
                    int r=0,g=0,b=0;
                    con[i][j]=0;
                    co[i][j]=color();
                    for(int t=1;t<=T;t++){//累计 
                        if(trns[t].vctin(i,j)){
                            r+=trns[t].co.r;
                            g+=trns[t].co.g;
                            b+=trns[t].co.b;
                            con[i][j]++;
                        }
                    }
                    if(con[i][j])co[i][j]=color(b/con[i][j],g/con[i][j],r/con[i][j]);
                }
            }
        }
        //与目标比较颜色差异得出适应值
        void comp(pic &b){for(int i=1;i<=H;i++)for(int j=1;j<=W;j++)bes+=abs(co[i][j].r-b.co[i][j].r)+abs(co[i][j].g-b.co[i][j].g)+abs(co[i][j].b-b.co[i][j].b);} 
        void read(FILE *fin){//从文件读BMP文件 
            short tmps[27];
            unsigned char tmpc;
            fread(tmps,sizeof(short),27,fin);//没什么卵用的文件文件头 
            for(int i=H;i>=1;i--){//BMP是从下至上存储 
                fread(co[i]+1,sizeof(color),W,fin);//读像素点 
                if(W*3%4)for(int j=0;(W*3+j)%4;j++)fread(&tmpc,sizeof(char),1,fin);//对齐为整数个字（四字节） 
            }
        }
        void turnbmp(int g){//输出为BMP 
            char f[21];
            sprintf(f,"%d.bmp",g);
            FILE *fout=fopen(f,"wb");
            short BM=0x4d42,pl=1,cl=24;
            int wt=W*3/4*4,siz=H*(wt+(W*3%4?4:0))+54,ep=0,to=0x36,si=0x28,h=H,w=W;
            unsigned char epc=0;
            fwrite(&BM,fout);//BM，文件类型标识 
            fwrite(&siz,sizeof(int),fout);//文件大小，文件头54字节+对齐后的主数据区大小 
            fwrite(&ep,fout);//空 
            fwrite(&to,fout);//偏移量，没有调色板的情况下为54 
            fwrite(&si,fout);//文件信息大小，为40 
            fwrite(&w,fout);//宽 
            fwrite(&h,fout);//高 
            fwrite(&pl,fout);//平面数，显然为1 
            fwrite(&cl,fout);//颜色类型，这里为24位 
            fwrite(&ep,fout);//表示图片的压缩属性，bmp图片是不压缩的，为0 
            fwrite(&ep,fout);//表示bmp图片数据区的大小，当上一个数值为0时，这里的值可以省略不填，为0 
            fwrite(&ep,fout);//表示图片X轴每米多少像素，可省略，为0 
            fwrite(&ep,fout);//表示图片Y轴每米多少像素，可省略，为0 
            fwrite(&ep,fout);//索引图使用了多少个索引，这里为0 
            fwrite(&ep,fout);//表示有多少个重要的颜色，0表示所有的颜色都很重要 
            for(int i=H;i>=1;i--){//从下至上存储 
                fwrite(co[i]+1,fout);
                if(W*3%4)for(int j=0;(W*3+j)%4;j++)fwrite(&epc,fout);//对齐 
            }
            fclose(fout);
        }
        void rand(){//随机 
            for(int i=1;i<=T;i++){
                trns[i].rand(h,w);
                trns[i].cord();
            }
            init();
        }
        pic cross(pic &b){//交叉，单点交叉法 
            int c=random()%(T-1)+1;//随机交叉点 
            pic<H,T>ans;
            for(int i=1;i<=T;i++)ans.trns[i]=(i<=c?trns[i]:b.trns[i]);//从一个点交换 
            ans.init();
            return ans;
        }
        void mutate(){//变异 
            for(int i=1;i<=T;i++){
                if(double(random())/randmx<=cgcp)trns[i].cord();//颜色变异 
                else if(double(random())/randmx<=chgp)trns[i].rand(h,w);//形状变异 
            }
            init();
        }
    };
    pic<h,w,trn>best;//目标 
    vector< pic<h,trn> >popu,inv;//种群，父母 
    bool kil[maxp];//淘汰的个体 
    int bes[maxp];//适应值前缀和 
    genetic(){
        FILE *be=fopen("best.bmp","rb");//读入目标 
        best.read(be);
        fclose(be);
        for(int i=0;i<maxp;i++){//随机种群 
            kil[i]=false;
            pic<h,trn>ne;
            ne.rand();
            ne.comp(best);
            popu.push_back(ne);
        }
    }
    void start(){//开始 
        int age=0,sq;
        while(true){//下一代
            age++;
            int maxi=-1,minn=0x7fffffff,maxn=0;
            for(int i=0;i<maxp;i++){//计算适应值前缀和以划分区间 
                if(popu[i].bes<minn){//维护最小值 
                    minn=popu[i].bes;
                    maxi=i;
                }
                if(popu[i].bes>maxn)maxn=popu[i].bes;//维护最大值 
                bes[i]=(!i?0:bes[i-1])+popu[i].bes;
            }
            sq=sqrt(age);
            if(sq*sq==age){//是否为完全平方数 
                printf("sqrt:%dtAGE:%dtBEST:%dtDIFFERENCE:%dn",sq,age,minn,maxn-minn);//平方根，代数，最好个体的适应值，适应值最大差距 
                popu[maxi].turnbmp(age);//输出 
            }
            int kld=0;
            while(kld<maxp/2){//杀一半 
                int r=random()%(bes[maxp-1]+1);//选择位置 
                for(int j=0;j<maxp;j++){
                    if(bes[j]>=r){//是否选择了这个位置 
                        if(j==maxi)break;//精英策略，不杀最好的 
                        if(!kil[j]){//没杀过就杀了 
                            kil[j]=true;
                            kld++;
                        }
                        break; 
                    }
                }
            }
            inv.clear();
            for(int i=0;i<maxp;i++){//选择 
                if(kil[i])kil[i]=false;
                else inv.push_back(popu[i]);
            }
            popu=inv;
            for(int i=1;i<(signed)inv.size();i++){//交叉，变异 
                pic<h,trn>c=popu[i-1].cross(popu[i]);
                c.mutate();
                c.comp(best);
                popu.push_back(c);
            }
            if(!(maxp%2)){//零头 
                pic<h,trn>c=popu[inv.size()-1].cross(popu[0]);
                c.mutate();
                c.comp(best);
                popu.push_back(c);
            }
        }
    }
};
int main(){
    srand(time(0));
    x=rand()*rand()*4U+rand();//初始化随机数生成器 
    y=rand()*rand()*4U+rand();
    z=rand()*rand()*4U+rand();
    w=rand()*rand()*4U+rand();
    genetic g;
    g.start();//开始 
}

目标必须为24位非索引图，可用画图更改格式

此代码效率极其低下，请务必使用-Ofast编译优化以使其速度暴涨。

使用方法详见代码。

图像的进步速度基本和平方成正比，因此全家福中图片都是完全平方数代数的最优解。

1、chorme

目标：

2、firefox

目标：