基因交叉，或者基因重组，就是把两个父体部分结构加以替换，生成新的个体的操作，习惯上对实数编码的操作叫做重组（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 阅读(11968)
评论(1) 编辑 收藏 引用 所属分类:
Numerical C++