posts - 12,  comments - 54,  trackbacks - 0
在基因交叉之后产生的子代个体,其变量可能以很小的概率或者步长发生转变,这个过程称为变异(Mutation)。
如果进化的目标函数极值是单峰值的,那么,将变异概率p设置为种群数量n的倒数是一个比较好的选择。
如果变异概率很大,那么整个搜索过程就退化为一个随机搜索过程。所以,比较稳妥的做法是,进化过程刚刚开始的时候,取p为一个比较大的概率,随着搜索过程的进行,p逐渐缩小到0附近。
与交叉过程一样,变异的算法也可以大致分为实数编码和二进制编码两种。
(1) 实数变异
 <1>步长变异
即给数值加上或者减去一个值,这个数值称为步长。大致如下:
X' = X + 0.5 Ld 或者
X' = X - 0.5 Ld
这里
L为变量的取值范围 L = Upper - Lower
d= a(0)/2^0 + a(1)/2^1 + ... + a(m)/s^m
其中a(i)以1/m的概率取1,以 1-1/m的概率取0,一般m=20

C++ 代码
 1 template< class GENE >
 2 class Real_Gene_Mutate_Algorithm
 3 {
 4     public:
 5         void operator()( GENE& gene ) const
 6         {
 7             const unsigned int M = 20;
 8 
 9             //claculate Delta
10             long double Delta = 0.0L;
11             for ( unsigned int i = 0; i < M; ++i )
12             {
13                 const long double Boundary =
14                         1.0L / static_cast<long double>(M);
15                 const long double Ran = ran();
16                 if ( Ran < Boundary )
17                 {
18                     const unsigned int Base = 1 << i;
19                     Delta += 1.0L / static_cast<long double>( Base );
20                 }
21             }
22 
23             //claculate Sig and L
24             const long double Ran = ran();
25             long double Sig = 0;
26             long double L = 0;
27             if ( Ran > 0.5L )
28             {
29                 Sig = 1.0L;
30                 L = gene.Upper - gene.Value;
31             }
32             else
33             {
34                 Sig = -1.0L;
35                 L = gene.Value - gene.Lower;
36             }
37 
38             gene.Value += Sig * L * Delta * 0.5L;
39         }
40 
41 };
42 

<2>高斯变异
这种变异的方法就是,产生一个服从高斯分布的随机数,取代原先基因中的实数数值。这个算法产生的随机数,数学期望当为当前基因的实数数值。
一个模拟产生的算法是,产生6个服从U(0,1)的随机数,以他们的数学期望作为高斯分布随机数的近似。

 1 template<class GENE>
 2 class Gauss_Mutate_Algorithm
 3 {
 4         public:
 5             void operator()( GENE& gene )const
 6             {
 7                 long double gauss = 0.0L;
 8                 for ( unsigned int i = 0; i < 6++i )
 9                     gauss += ran();
10                 gauss /= 6.0L;
11 
12                 long double upper;
13                 long double lower;
14                 const long double Upper = gene.Upper;
15                 const long double Lower = gene.Lower;
16                 const long double Value = gene.Value;
17 
18                 ( ( Value - Lower ) > ( Upper - Value ) ) ?
19                 ( upper = Upper, lower = Value * 2.0L - Upper ) :
20                 ( lower = Lower, upper = Value * 2.0L - Lower );
21 
22                 gauss *= ( upper - lower );
23                 guass += lower;
24
25                 gene.Value = gauss;
26             }
27 };
28


(2)二进制变异
对二进制编码来讲,变异就是变量的翻转,如
10000111100001
10000101100001

c++代码
 1 template< class GENE >
 2 class Binary_Gene_Mutate_Algorithm
 3 {
 4     public:
 5         void operator()( GENE& gene )const
 6         {
 7             encoding( gene );
 8 
 9             const unsigned int Size = gene.Binary_Array.size();
10             const long double Ran = ran();
11             const unsigned int Pos = static_cast<unsigned int>
12                     ( static_cast<long double>( Size ) * Ran );
13 
14             if ( gene.Binary_Array[Pos] )
15                 gene.Binary_Array[Pos] = 0;
16             else
17                 gene.Binary_Array[Pos] = 1;
18 
19             decoding( gene );
20         }
21 };

(3)一些相关算法或者函数
 1 template< class DATA, class ALGORITHM>
 2 void mutate( DATA& d, const ALGORITHM& a )
 3 {
 4     a( d );
 5 }
 6 
 7 template< class POPULATION, class GENE_MUTATE_ALGORITHM >
 8 class Population_Mutate_Algorithm
 9 {
10     public:
11         void operator()( POPULATION& p )const
12         {
13             //chromosome numbers in the population
14             const unsigned int C_Size = p.Chromosome_Array.size();
15             //gene numbers in a chromosome
16             const unsigned int G_Size = p.Chromosome_Array[0].Gene_Array.size();
17 
18             for( unsigned int i = 0; i < C_Size; ++i )
19             {
20                 for ( unsigned int j = 0; j < G_Size; ++j )
21                 {
22                     const long double Ran = ran();
23 
24                     if ( Ran > p.Mutation_Probability )
25                     return ;
26 
27                     mutate( p.Chromosome_Array[i].Gene_Array[j],
28                             GENE_MUTATE_ALGORITHM() );
29                 }
30             }
31         }
32 };
33 



posted on 2008-06-22 16:20 Wang Feng 阅读(7110) 评论(0)  编辑 收藏 引用 所属分类: Numerical C++

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2008年6月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

常用链接

留言簿(4)

随笔分类

随笔档案

Link List

搜索

  •  

最新评论

阅读排行榜

评论排行榜