基因交叉，或者基因重組，就是把兩個父體部分結構加以替換，生成新的個體的操作，習慣上對實數編碼的操作叫做重組（Recombination），對二進制編碼的操作稱為交叉（crossover）。
比較常用的一些算法介紹如下：
1.
重組算法（Recombination）
實值重組產生子個體一般是用下邊這個算法：
子個體=父個體1 + a × ( 父個體2 - 父個體1 )
這里a是一個比例因子，可以由[ -d, 1+d] 上邊服從均勻分布的隨機數產生。
不同的重組算法，a的取值是不同的，一般來講，d=0.25是一個比較好的選擇。
下邊一段c++代碼片斷，實現一個中值重組算法，其中d取值為0。
1 /*
2 Gene Crossover Algorithm
3 Linear Recombination Xover Algorithm
4
5 A crossover operator that linearly combines two parent
6 chromosome vectors to produce two new offspring a
7 ccording to the following equations:
8
9 Offspring1 = a * Parent1 + (1- a) * Parent2
10 Offspring2 = (1 – a) * Parent1 + a * Parent2
11
12
13 where a is a random weighting factor (chosen before each
14 crossover operation).
15
16 Consider the following 2 parents (each consisting of 4
17 float genes) which have been selected for crossover:
18
19 Parent 1: (0.3)(1.4)(0.2)(7.4)
20 Parent 2: (0.5)(4.5)(0.1)(5.6)
21
22 If a = 0.7, the following two offspring would be produced:
23
24 Offspring1: (0.36)(2.33)(0.17)(6.86)
25 Offspring2: (0.402)(2.981)(0.149)(6.842)
26 */
27 template< class GENE >
28 class Intermediate_Recombination_Gene_Crossover_Algorithm
29 {
30 public:
31 void operator()( GENE& g1, GENE& g2 )const
32 {
33 assert( g1.Upper == g2.Upper );
34 assert( g1.Lower == g2.Lower );
35
36 const long double Ran = ran();
37 const long double sum = g1.Value + g2.Value;
38
39 if ( sum < g1.Upper )
40 {
41 g1.Value = Ran * sum;
42 g2.Value = sum - g1.Value;
43 }
44 else
45 {
46 const long double sub = 2.0L * g1.Upper - sum;
47 g1.Value = g1.Upper - sub * Ran;
48 g2.Value = g1.Upper - sub + sub * Ran;
49 }
50 }
51 };
2. 交叉算法
如上文遺傳算法中的數據結構中所講，基因的二進制編碼有直接編碼（Normal）和Gray編碼之分，以下所說算法，均適用于這兩種算法。
假設基因的二進制編碼長度為N，那么這些編碼之間有N-1個空隙，可供交叉使用。
二進制交叉算法就是如何選擇空隙，選擇多少個空隙。
以下將各走極端的選擇一個空隙交叉的單點交叉算法，和選擇N-1個空隙進行交叉的洗牌交叉算法大致說一下。
（1） 單點交叉
在二進制編碼中，隨機選擇一個點，以這個點為界限，相互交換變量。
如
父個體1 011111110000000000
父個體2 000000001111111111
如粗體前邊位置為所選擇的交叉點，那么生成的子個體為：
子個體1 011111111111111111
子個體2 000000000000000000
以下為c++實現，采用Gray編碼，直接編碼的類似。
1 /*
2 Gene crossover algorithm
3 One Point Crossover using Gray binary encoding
4
5 A crossover operator that randomly selects a crossover point
6 within a chromosome then interchanges the two parent chromosomes
7 at this point to produce two new offspring.
8
9 Consider the following 2 parents which have been selected for
10 crossover. The “|” symbol indicates the randomly chosen
11 crossover point.
12
13 Parent 1: 11001|010
14 Parent 2: 00100|111
15
16 After interchanging the parent chromosomes at the crossover
17 point, the following offspring are produced:
18
19 Offspring1: 11001|111
20 Offspring2: 00100|010
21 */
22 template< class GENE >
23 class Gray_Binary_Single_Point_Xover_Gene_Crossover_Algorithm
24 {
25 public:
26 void operator()( GENE& g1, GENE& g2 )const
27 {
28 encoding( g1 );
29 encoding( g2 );
30 assert( g1.Binary_Array.size() == g2.Binary_Array.size() );
31
32 normal2gray( g1 );
33 normal2gray( g2 );
34
35 const unsigned int Pos = static_cast<unsigned int>
36 ( g1.Binary_Array.size() * ran() );
37
38 for ( unsigned int i = 0; i < Pos; ++i )
39 {
40 if ( g1.Binary_Array[i] xor g2.Binary_Array[i] )
41 {
42 if ( g1.Binary_Array[i] )
43 {
44 g1.Binary_Array[i] = 0;
45 g2.Binary_Array[i] = 1;
46 }
47 else
48 {
49 g1.Binary_Array[i] = 1;
50 g2.Binary_Array[i] = 0;
51 }
52 }
53 }
54
55 gray2normal( g1 );
56 gray2normal( g1 );
57 decoding( g1 );
58 decoding( g2 );
59 }
60 };
61
62
63
（2）洗牌交叉
洗牌交叉就是，將一個父基因取一半，再上來自另外一個父基因的一半，構成一個新的子基因。
算法代碼如下：
1 template< class GENE >
2 class Gray_Binary_Shuffle_Xover_Gene_Crossover_Algorithm
3 {
4 public:
5 void operator()( GENE& g1, GENE& g2 )const
6 {
7 encoding( g1 );
8 encoding( g2 );
9 assert( g1.Binary_Array.size() == g2.Binary_Array.size() );
10
11 normal2gray( g1 );
12 normal2gray( g2 );
13
14 const unsigned int Size = g1.Binary_Array.size();
15
16 for ( unsigned int i = 0; i < Size; ++i )
17 {
18 if ( ( i & 1) &&
19 ( g1.Binary_Array[i] xor g2.Binary_Array[i] )
20 )
21 {
22 if ( g1.Binary_Array[i] )
23 {
24 g1.Binary_Array[i] = 0;
25 g2.Binary_Array[i] = 1;
26 }
27 else
28 {
29 g1.Binary_Array[i] = 1;
30 g2.Binary_Array[i] = 0;
31 }
32 }
33 }
34
35 gray2normal( g1 );
36 gray2normal( g1 );
37 decoding( g1 );
38 decoding( g2 );
39 }
40 };
41
42
3. 另外的一些代碼
（1）群體中的交叉算法
將經過選擇考驗的個體放入一個群體，當放入的個體數量達到要求后，對里邊的個體進行兩兩交叉。
1 //Population Crossover Algorithm
2 //1. get the number of Chromosomes in the Population
3 //2. get the number of Gens in a Chromosome
4 //3. generate a random number
5 //4. if the random number is bigger than the probability, skip
6 //5. if the selected two genes are of the same value, skip
7 //6. crossover the two genes using the selected Gene crossover algorithm
8 template< class POPULATION, class GENE_CROSSOVER_ALGORITHM >
9 class Population_Crossover_Algorithm
10 {
11 public:
12 void operator()( POPULATION& population ) const
13 {
14 //1
15 const unsigned int C_Size = population.Chromosome_Array.size();
16 assert( C_Size > 1 );
17
18 //2
19 const unsigned int G_Size = population.Chromosome_Array[0].Gene_Array.size();
20
21 for ( unsigned int i = 0; i < C_Size / 2; ++i )
22 {
23 for( unsigned int j = 0; j < G_Size; ++j )
24 {
25 //3
26 const long double Ran = ran();
27 //4
28 if ( Ran > population.Crossover_Probability )
29 continue ;
30 //5
31 if ( population.Chromosome_Array[i].Gene_Array[j].Value ==
32 population.Chromosome_Array[C_Size-i-1].Gene_Array[j].Value
33 )
34 continue;
35 //6
36 crossover(
37 population.Chromosome_Array[i].Gene_Array[j],
38 population.Chromosome_Array[C_Size-i-1].Gene_Array[j],
39 GENE_CROSSOVER_ALGORITHM()
40 );
41 }
42 }
43 }
44 };
（2） 交叉函數定義
種群的交叉只涉及一個交叉主體，而基因/個體的交叉涉及兩個交叉主體，定義如下:
1 //Population crossover only
2 template<class POPULATION, class ALGORITHM>
3 void crossover( POPULATION& p, //the Population to perform crossover
4 const ALGORITHM& a ) //the Algorithm used for the crossover
5 {
6 assert( p.Chromosome_Array.size() > 1 );
7 a( p );
8 }
9
10
11 //gene crossover algorithm
12 template<class GENE, class ALGORITHM>
13 static void crossover( GENE &g1, //Gene1 to perform crossvoer
14 GENE &g2, //Gene2 to perform crossvoer
15 const ALGORITHM& a ) //the Algorithm employed
16 {
17 a( g1, g2 );
18 }
19
posted on 2008-06-18 15:56
Wang Feng 閱讀(12145)
評論(1) 編輯 收藏 引用 所屬分類:
Numerical C++