遗传算法初步

维基百科：

https://zh.wikipedia.org/wiki/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95

遗传算法（英语：genetic algorithm (GA) ）是计算数学中用于解决最佳化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。

遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。

遗传算法的机理

在遗传算法里，优化问题的解被称为个体，它表示为一个变量序列，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，不过也有其他的依赖于特殊问题的表示方法适用，这一过程称为编码。首先，算法随机生成一定数量的个体，有时候操作者也可以干预这个随机产生过程，以提高初始种群的质量。在每一代中，都会评价每一个体，并通过计算适应度函数得到适应度数值。按照适应度排序种群个体，适应度高的在前面。这里的“高”是相对于初始的种群的低适应度而言。

下一步是产生下一代个体并组成种群。这个过程是通过选择和繁殖完成，其中繁殖包括交配（crossover，在算法研究领域中我们称之为交叉操作）和突变（mutation）。选择则是根据新个体的适应度进行，但同时不意味着完全以适应度高低为导向，因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，我们称之为早熟。作为折中，遗传算法依据原则：适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后，被选择的个体进入交配过程。一般的遗传算法都有一个交配概率（又称为交叉概率），范围一般是0.6~1，这个交配概率反映两个被选中的个体进行交配的概率。例如，交配概率为0.8，则80%的“夫妻”会生育后代。每两个个体通过交配产生两个新个体，代替原来的“老”个体，而不交配的个体则保持不变。交配父母的染色体相互交换，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段并不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。再下一步是突变，通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变常数（又称为变异概率），通常是0.1或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是改变染色体的一个字节（0变到1，或者1变到0）。

经过这一系列的过程（选择、交配和突变），产生的新一代个体不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为总是更常选择最好的个体产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：评价每个个体，计算适应度，两两交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。一般终止条件有以下几种：

• 进化次数限制；
• 计算耗费的资源限制（例如计算时间、计算占用的内存等）；
• 一个个体已经满足最优值的条件，即最优值已经找到；
• 适应度已经达到饱和，继续进化不会产生适应度更好的个体；
• 人为干预；
• 以及以上两种或更多种的组合。

个人理解：

所谓遗传算法，是一种随机化算法，像这类随机化算法是从平时生活中总结出来的，而遗传算法就是从生物的遗传之中总结出来的，其思想与生物遗产类似，具体代码可以根据不同问题进行改变。

经典例题：旅行商问题（TSP）

假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，

而且最后要回到原来出发的城市。 

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

算法介绍：

根据达尔文的进化论，我们可以总结出遗传算法的一般步骤：

达尔文进化论：

1.评估每条染色体所对应个体的适应度。

2.遵照适应度越高，选择概率越大的原则，从种群中选择两个个体作为父方和母方。

3.抽取父母双方的染色体，进行交叉，产生子代。

4.对子代的染色体进行变异。

5.重复2，3，4步骤，直到新种群的产生。

遗传算法步骤：

1.  初始化   t←0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体    P（t）；

2.  个体评价 计算P（t）中各个个体的适应度值；

3.  选择运算 将选择算子作用于群体；

4.  交叉运算 将交叉算子作用于群体；

5.  变异运算 将变异算子作用于群体，并通过以上运算得到下一代群体P（t + 1）;

6.  终止条件判断  t≦T：t← t+1 转到步骤2；

t>T：终止 输出解。 、

▲Procedures  GA：   伪代码

   begin

initialize P(0);

t = 0;             //t是进化的代数，一代、二代、三代...

while(t <= T) do

       for i = 1 to M  do     //M是初始种群的个体数

              Evaluate fitness of P(t);  //计算P（t）中各个个体的适应度

       end for

       for i = 1 to M  do

              Select operation to P(t);  //将选择算子作用于群体

       end for

       for i = 1 to M/2  do

              Crossover operation to P(t); //将交叉算子作用于群体

       end for

       for i = 1 to M  do

              Mutation operation to P(t);  //将变异算子作用于群体

       end for

       for i = 1 to M  do

              P(t+1) = P(t);      //得到下一代群体P（t + 1）

        end for

        t = t + 1;      //终止条件判断  t≦T：t← t+1 转到步骤2

  end while

end

这里的一些专业术语会在下面的程序中具体介绍到。

下面来看代码，其中有较详细注释：

/*************************************************************************
	> File Name: yichuan.cpp
	> Author:chudongfang 
	> Mail:1149669942@qq.com 
	> Created Time: 2016年06月19日 星期日 23时50分57秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF (1ll<<60)-1

#define city_num    10//城市的数目
#define unit_num    100//种群中个体的数目
#define probability 60//变异概率
#define genmax      100//最大产生代数
#define group_num   100//产生种群数量

using namespace std;
typedef long long ll;


typedef struct individual //一个个体
{
	int path[city_num];//个体的路径
    int lenth;         //路径的长度
}INDI;


typedef struct unit//一个种群
{
    INDI group[unit_num]; //数组存储个体
    INDI best;            //最优个体
    int  best_gen;        //最优个体所在的代数
    int  cur_gen;         //种群当前的代数
}UNIT;

//1.初始化t←0进化代数计数器；genmax是最大进化代数；随机生成unit_num个个体作为初始群体P(t)；
void init();

//2.个体评价
void assess();

//3.选择运算 将选择算子作用于群体
void choose(int gen);

//4.交叉运算 将交叉算子作用于群体，保留较优个体，淘汰较差个体
void cross();

//5.变异运算 将变异算子作用于群体，并通过以上运算得到下一代群体p(t+1)
void mutation();

//总调用函数，决定一个种群的进化
void sovel();

//子模块
INDI  cross_once(int father,int mother);
void mutation_one(int x);

//打印，供测试用
void print();

//城市距离表，邻接矩阵方式储存无向图
int length_table[10][10] = 
{
    {0,1,1272,2567,1653,2097,1425,1177,3947,1},
    {1,0,1,2511,1633,2077,1369,1157,3961,1518},
    {1272,1,0,1,380,1490,821,856,3660,385},
   	{2567,2511,1,0,1,2335,1562,2165,3995,933},
   	{1653,1633,380,1,0,1,1041,1135,3870,456},
   	{2097,2077,1490,2335,1,0,1,920,2170,1920},
   	{1425,1369,821,1562,1041,1,0,1,4290,626},
   	{1177,1157,856,2165,1135,920,1,0,1,1290},
   	{3947,3961,3660,3995,3870,2170,4290,1,0,1},
   	{1,1518,385,993,456,1920,626,1290,1,0}
};

//创建一个种群
UNIT  Group;


//储存每个种群进化的结果
INDI  bestsovel[group_num];

//在这里创建了多个种群，这样使得解更具有准确性。
int main(int argc,char *argv[])
{
    //时间种子产生随机数
	srand(time(0));

    //对产生的种群进行一一求解
    for(int i=0;i<group_num;i++)
    {
        sovel();
        bestsovel[i]=Group.best;
    }

    //输出每个种群的最优个体（解）
    for(int i=0;i<group_num;i++)
        printf("%dth=%d\n",i,bestsovel[i].lenth);
    
    //排序，并输出所有种群的最优解
    INDI t;
    for(int i=0;i<group_num;i++)
    {
        for(int j=i;j<group_num;j++)
        {
            if(bestsovel[i].lenth>bestsovel[j].lenth)
            {
                t=bestsovel[i];
                bestsovel[i]=bestsovel[j];
                bestsovel[j]=t;
            }
        }
    }
    

    printf("最优解：");
    for(int i=0;i<city_num;i++)
        printf("%4d",bestsovel[0].path[i]);

    printf("\n最优值：%d",bestsovel[0].lenth);

    return 0;
}


//对一个种群进行求解。
void sovel()
{    
    init();
    for(int  i=1;i<=genmax;i++) //种群繁杂代数
    {
        Group.cur_gen=i;
        assess();               //评估
        choose(Group.cur_gen);  //找最优个体
        cross();                //交叉,优胜劣汰，保留较优个体，淘汰较差个体
        mutation();             //变异
    }
}



void init()
{
    Group.best.lenth=0x3f3f3f3f;//初始化一个很大的值，便于下面比较
    Group.best_gen=0;//记录产生最好结果的代数
    Group.cur_gen=0;//当前代数为0
    
    //把每一个个体随机初始化
    for(int i=0;i<unit_num;i++)//unit_num个个体
    {
        bool  flag[city_num]={0};//用来标记其是否已经储存过
        for(int j=0;j<city_num;j++)
        {     
            int t=rand()%city_num;
            //保证每个数字不重复
            while(flag[t])
                t=rand()%city_num;
             
            flag[t]=true;
            Group.group[i].path[j]=t;
        }
    }
}


//个体评价
void assess()
{
    //计算出每个个体的适应度值，即其路径长度
    for(int k=0;k<unit_num;k++)
    {
        int rel=0;
        for(int i=1;i<city_num;i++)//根据其经过的节点，计算其路径
            rel+=length_table[Group.group[k].path[i-1]][Group.group[k].path[i]];
    
        rel+=length_table[Group.group[k].path[city_num-1]][Group.group[k].path[0]];
        Group.group[k].lenth=rel;
    }
}

//先进行排序，然后选择出最优解
void choose(int gen)
{
    //进行排序
    INDI t;
    for(int i=0;i<unit_num;i++)
    {
        for(int j=i;j<unit_num;j++)
        {
            if(Group.group[i].lenth>Group.group[j].lenth)
            {
                t             =Group.group[i];
                Group.group[i]=Group.group[j];
                Group.group[j]=t;
            }
        }
    }
    
    //选出这个种群的最优个体，并储存
    if(Group.best.lenth>Group.group[0].lenth)
    {
        Group.best.lenth=Group.group[0].lenth;
        for(int i=0;i<city_num;i++)
            Group.best.path[i]=Group.group[0].path[i];
        Group.best_gen        =gen;
    }
}




//对一个种群中的个体，按一定方式进行交叉运算,并淘汰掉一部分，保存较优个体
void cross()
{
    for(int i=unit_num/2;i<unit_num;i++)//很容易看出，这里淘汰了后部分个体
        Group.group[i]=cross_once(i-unit_num/2,i-unit_num/2+1);
}


//交叉两个个体
INDI  cross_once(int father,int mother)
{
    INDI son;
    int t;
    int pos=0;
    int l=rand()%city_num;//随机生成两个数
    int r=rand()%city_num;
    if(l>r)
    {
        t=l;
        l=r;
        r=t;
    }
    
    bool flag[city_num]={0};
        
    for(int i=l;i<=r;i++)
        flag[Group.group[father].path[i]]=true;

    for(int i=0;i<l;i++)
    {
        while(flag[Group.group[mother].path[pos]])
            pos++;
        son.path[i]=Group.group[mother].path[pos++];
    }
    
    //父亲的一段全部放在儿子中
    for(int i=l;i<=r;i++)
        son.path[i]=Group.group[father].path[i];

    //母亲的在不与父亲的一段重复的情况下，把其元素放在儿子中
    for(int i=r+1;i<city_num;i++)
    {
        while(flag[Group.group[mother].path[pos]])
            pos++;
        son.path[i]=Group.group[mother].path[pos++];
    }
    
    return son;
}



//对一个种群的全部个体都进行变异运算
void mutation()
{
    for(int i=0;i<unit_num;i++)
    {
        mutation_one(i);
    }
}


//对一个个体的变异运算
void mutation_one(int x)
{
    int pro=rand()%100;
    if(pro>probability)  
        return ;
    //随机生成两个数
    int first =rand()%city_num;
    int second=rand()%city_num;
    
    while(first==second)
        second=rand()%city_num;

    //进行交换
    int t;
    t=Group.group[x].path[first];
    Group.group[x].path[first]=Group.group[x].path[second];
    Group.group[x].path[second]=t;
}


void print()
{
    for(int i=0;i<unit_num;i++)
    {
        for(int j=0;j<city_num;j++)
        {
            printf("%4d",Group.group[i].path[j]);
        }
        printf("\n");
    }
    printf("\n\n\n");
}

运行结果：

0th=10
1th=10
2th=10
3th=10
4th=10
5th=10
6th=10
7th=10
8th=10
9th=10
10th=10
11th=10
12th=10
13th=10
14th=10
15th=10
16th=10
17th=10
18th=10
19th=10
20th=10
21th=10
22th=10
23th=10
24th=10
25th=10
26th=10
27th=10
28th=10
29th=10
30th=1811
31th=10
32th=10
33th=10
34th=10
35th=10
36th=10
37th=10
38th=10
39th=10
40th=10
41th=10
42th=10
43th=10
44th=10
45th=10
46th=10
47th=10
48th=10
49th=10
50th=10
51th=10
52th=10
53th=10
54th=10
55th=10
56th=10
57th=10
58th=10
59th=10
60th=10
61th=10
62th=10
63th=10
64th=10
65th=10
66th=1969
67th=1811
68th=10
69th=10
70th=10
71th=10
72th=10
73th=10
74th=10
75th=1969
76th=10
77th=10
78th=10
79th=10
80th=10
81th=10
82th=10
83th=10
84th=10
85th=10
86th=10
87th=10
88th=10
89th=10
90th=10
91th=10
92th=10
93th=10
94th=10
95th=10
96th=10
97th=10
98th=10
99th=10
最优解：   6   5   4   3   2   1   0   9   8   7
最优值：10
real 0m0.585s
user 0m0.580s
sys 0m0.004s

参数分析：

在这里，以下参数越大其结果越精确，不过其耗时也相应变大，所以这里要充分衡量其参数大小，以便于在耗时较少的情况下的到更优的解。

#define unit_num    100//种群中个体的数目
#define probability 60//变异概率
#define genmax      100//最大产生代数
#define group_num   100//产生种群数量

简单总结一下遗传算法，遗传算法是一个根据生物进化的过程中总结出来的，其与生物进化相似，优胜劣汰，遗传变异。其大概就分为：初始化、个体评估、选择、交叉、变异这几个过程，可以根据具体不同的问题，编不同的程序，但大致思想一样。

以上内容不足之处请多多指教！

 转载请注明出处：http://write.blog.csdn.net/postedit/51720607