在基因交叉之后產生的子代個體，其變量可能以很小的概率或者步長發生轉變，這個過程稱為變異(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 閱讀(14339)
評論(0) 編輯 收藏 引用 所屬分類:
Numerical C++