在基因交叉之后产生的子代个体，其变量可能以很小的概率或者步长发生转变，这个过程称为变异(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）二进制变异
对二进制编码来讲，变异就是变量的翻转，如
100001
11100001
100001
01100001
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 阅读(14113)
评论(0) 编辑 收藏 引用 所属分类:
Numerical C++