了解遗传算法 遗传算法是一种最优化算法，所谓最优化问题，就是这样一类问题，满足它的解（称为可行解）有很多（通常是极多）对于每一种解有一个评价函数得到一个评价值，也就确定了解集的一个偏序关系，在这个偏序关系的求最小值（或最大值）或者近似最小值（或最大值）。因为通常可行解非常之多，所以确定性算法很难做到这一点，而遗传算法是模拟了生物学中物种进化的过程的一种最优化算法，简单来说，遗传算法=遗传操作+遗传选择。   在算法开始之前要做一下准备工作：编码。对于不同的问题有不同的解的形式，但要运行遗传算法就要对其进行抽象的编码，也就是确定染色体的形式，这里的染色体就是用某种特定的编码方式描述一个解，通常一个具体的解也称为个体。而多个不同的个体就组成一个种群，一个种群内有统一的编码方式。这些概念都完全等同于生物学中的概念，它们是平行的。例如，N个城市的旅行商问题(TSP)，假如用1,2,...N表示这N个城市，那对于任意这样的一个排列1p2p3...pN就表示了一个解，这个串就可以认为是一个染色体，它表示一个个体的基因。   遗传算法有一些基本的操作，如选择、交叉和变异等。 选择操作：首先要知道适应度函数，所谓的适应度函数就是评价函数，通常是问题的目的函数（或它的倒数），它描述了个体的优劣程度同时也决定了选择操作的概率，设fi表示第i个个体的适应度值，那选择第i个个体的概率就是fi/∑fj，简单来说，这个概率的大小就决定了该个体是被淘汰还是被保留。通常的具体做法是用类似赌盘的方法，每个个体占它的适应度那么宽的转盘大小，每次掷色子，落到哪一格就选哪一格对应的个体。 交叉操作：交叉操作就是让2个以上的染色体进行交叉产生后代的过程，具体的交叉操作要看具体的问题。不过我觉得有一个原则，就是要有对称性，交叉得到的后代中的基因要来源于父代的所有个体中，也就是说n个个体进行交叉是和它们的排列没关系，这样子代才有机会得到更优秀的基因。交叉操作是遗传算法中最重要的操作。最简单的基本方式是交换父代中染色体片段。 变异操作：生物可以突变，有时候突变是好的，有时候却是坏的，但正是因为有了突变才让有限的种群中基因库可以非常丰富，也保证了种群的适应能力。变异操作通常是翻转个体中某段染色体，编码后的染色体在计算机中都是01串，也就可以随机的翻转某个（或多个）bit上的值。 交叉和变异不是一定要发生在选择了的个体上，而是按一定控制概率发生的，交叉概率比较高通常是0.6~0.95，而变异概率比较低通常是0.001~0.01。   这些操作就确定了子代，就构成了种群进化的方式。于是遗传算法一般的结构是： 1，产生初始种群G2，选择G，交叉、变异->G'3，是否满足某个终止条件，如果没有重复上面过程。   遗传算法的收敛：一般的遗传算法不一定收敛，但给一个条件，让每代中最优秀的个体直接进入到子代，就能保证一定收敛。   遗传算法的性能：可以收敛和收敛得有多快是两码事，这方面的研究还在进行中，也是当今一大课题。但可以知道和哪些因素有关，首先是种群规模，也就是种群中个体的数目，如果太小，显然不利于快速收敛，如果太大又会花更多的时间计算，很矛盾，通常选择100左右的种群规模。其次，父代可不可以有机会进入子代？如果某次交叉产生的子代比父代还差，那是否还要这个新个体？当然不，父代也要有机会进入子代。然后就是终止条件，一般运用遗传算法时，对最优解是不了解的，那我们就不知道算法何时停止，一般使用的终止条件是在进化m代后，每代中的最优个体没有提高时停止，这里的m的选取有时候会误导你，如果种群中有一个个体早熟，而其它个体没有，那它将作为最优个体保持m代，而事实上它却不是最优解，改进的方法可以考虑种群中适应度平均值和最大值两个方面，而m的选取，不能太小，太大又浪费时间，适中选取。   举个简单的例子，用遗传算法求根号2，（是不是有种杀鸡焉用牛刀的感觉，呵呵~） 求根号2，也就是求方程f(x)=x*x-2=0的正整数解，x=1时f(1)<0，x=2时f(2)>0，由介值定理，则1到2中间存在一个根，根据代数基本定理和根的对称性知这就是我们要找的根（废话，初中生都知道是1.414左右），由目标函数得到适应度函数，我们选择个体都在[1,2]之间，那适应度函数我可以取j(x)=40/(2+|x*x-2|)-10，由x的取值范围知j的范围是(0,10)x和y交叉就用取平均(x+y)/2，交叉概率取0.9，变异概率为0，最后得到的C++程序： #include<stdio.h>#include<stdlib.h>typedef struct _indi{ double code;//染色体 double degree;//适应度}Indi;Indi group[40];//种群规模为40void Judge(Indi &x){ double tmp=x.code*x.code-2.0; if(tmp>=0)  x.degree=40.0/(2.0+tmp)-10.0; else  x.degree=40.0/(2.0-tmp)-10.0;}int happened(double p)//发生一个p=0~1间概率的事件{ return rand()<(int)(p*RAND_MAX);}void Cross(Indi &x,Indi &y)//交叉操作，产生一个子代取代父代中最次的一个{ Indi z; z.code=(x.code+y.code)/2.0; Judge(z); if(x.degree<y.degree) {  if(z.degree<=x.degree)   return;//如果新个体不如双亲，淘汰之  x=z; } else {  if(z.degree<=y.degree)   return;  y=z; }}void main(){ int i,j,best,x,y,c; double sum,strick; for(i=0;i<40;++i)//随机得到初始种群 {  group[i].code=1.0+(double)rand()/RAND_MAX;  Judge(group[i]); } for(i=1;i<=10;++i)//固定进化10代 {  for(sum=0.0,best=0,j=0;j<40;++j)  {   sum+=group[j].degree;//求总的适应度sum   if(group[j].degree>group[best].degree)    best=j;//求当前最优个体  }  printf("第%2d代中 最优个体为 %10f(%10f) 平均适应度为 %10f\n",   i,group[best].code,group[best].degree,sum/40.0);  for(c=40;c;--c)  {   strick=(double)rand()/RAND_MAX*sum;//赌盘中的色子，选择个体x,y   for(x=0;x<40&&strick>=group[x].degree;++x)    strick-=group[x].degree;   strick=(double)rand()/RAND_MAX*sum;   for(y=0;y<40&&strick>=group[y].degree;++y)    strick-=group[y].degree;   if(happened(0.9))    Cross(group[x],group[y]);//交叉  } }} 运行结果：第 1代中 最优个体为 1.445692(适应度 9.138515) 平均适应度为 5.201076第 2代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 6.789277第 3代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 7.726777第 4代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 8.267572第 5代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 8.803805第 6代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 9.147720第 7代中 最优个体为 1.414113(适应度 9.997158) 平均适应度为 9.280602第 8代中 最优个体为 1.414205(适应度 9.999755) 平均适应度为 9.356507第 9代中 最优个体为 1.414205(适应度 9.999755) 平均适应度为 9.465438第10代中 最优个体为 1.414211(适应度 9.999931) 平均适应度为 9.553306 rickone 2006/06/29

评论