正文

了解遗传算法2006-06-29 22:08:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/rickone/16273.html

分享到:

了解遗传算法

遗传算法是一种最优化算法,所谓最优化问题,就是这样一类问题,满足它的解(称为可行解)有很多(通常是极多)对于每一种解有一个评价函数得到一个评价值,也就确定了解集的一个偏序关系,在这个偏序关系的求最小值(或最大值)或者近似最小值(或最大值)。因为通常可行解非常之多,所以确定性算法很难做到这一点,而遗传算法是模拟了生物学中物种进化的过程的一种最优化算法,简单来说,遗传算法=遗传操作+遗传选择。

 

在算法开始之前要做一下准备工作:编码。
对于不同的问题有不同的解的形式,但要运行遗传算法就要对其进行抽象的编码,也就是确定染色体的形式,这里的染色体就是用某种特定的编码方式描述一个解,通常一个具体的解也称为个体。而多个不同的个体就组成一个种群,一个种群内有统一的编码方式。这些概念都完全等同于生物学中的概念,它们是平行的。
例如,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,产生初始种群G
2,选择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];//种群规模为40
void 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

阅读(13179) | 评论(9)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册