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

FeedBack:
# re: 遗传算法系列 (3) 交叉算法
2010-02-12 00:32 | hello
请教:“洗牌交叉”如果按该文的代码,和单点交叉又有何区别呢?
“洗牌交叉”应该在交叉之前在父代中有shuffle运算,交叉后在子代中有unshuffle运算,但不知道是如何进行的,作者如有知晓,不吝赐教,谢谢:)
email: hwei2007@qq.com  回复  更多评论
  

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



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

常用链接

留言簿(4)

随笔分类

随笔档案

Link List

搜索

  •  

最新评论

阅读排行榜

评论排行榜