遗传算法C++详解

遗传算法 C++详解

（1）基本概念 http://www.cppblog.com/feng/archive/2008/06/15/53363.html

遗传算法的基本概念

遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：

一、串(String) 它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

二、群体(Population) 个体的集合称为群体，串是群体的元素

三、群体大小(Population Size) 在群体中个体的数量称为群体的大小。

四、基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

五 、基因位置(Gene Position) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。

//以下五到九可以不看

六、基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

七、串结构空间SS 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

八、参数空间S这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。 P

九、非线性 它对应遗传学中的异位显性(Epistasis)

//

十、适应度(Fitness) 表示某一个体对于环境的适应程度。

遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。

遗传算法的原理

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体” 群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

一、遗传算法的目的

典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：

考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

bi∈{0,1}L (3-84)

给定目标函数f，有f(bi)，并且0

同时 f(bi)≠f(bi+1)

求满足下式

max{f(bi)|bi∈{0,1}L} (3-85)

的bi。

很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。

遗传算法的基本原理

长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：

1．选择(Selection) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。

2．交叉(Crossover) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

3．变异(Mutation) 这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。 遗传算法的原理可以简要给出如下：

choose an intial population

determine the fitness of each individual

perform selection

repeat

perform crossover

perform mutation

determine the fitness of each individual

perform selection

until some stopping criterion applies

这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。

(2)数据结构和与之相关的操作

遗传算法系列 （2） 遗传算法中的数据结构和与之相关的一些数值算法 生存竞争的整个群体称为种群(Population)，种群中所有参与进化的个体(Chromosome)的数量一般为一个定值，而每个个体可能含有多于一个基因(Gene)。

例如，求解一个Camel函数在区间-100

f(x,y)=[4 - 2.1(x^2) + (x^3)/3](x^2) + xy +[-4 +4(y^2)](y^2) 这时候就需要两个基因，每个基因上限是100,下限是-100.

假设数值求解的精度为10^(-7)，那么对应的二进制编码长度N可以这样确定 (2^N)-1 >= [ 100 - ( -100 ) ] / [ 10^(-7) ]

于是，将一个十进制数字x转化为二进制

x' = [x- (-100)] * [(2^N) -1] / [ 100 - ( -100 ) ]

同样，也可以将一个二进制数字x'转化为十进制数字x

程序中，数据结构可以这样定义

1 struct Gene

2 {

3 long double Upper; //upper boundary of the value

4 long double Lower; //lower boundary of the value

5 long double Value; //decimal value of the gene

6 std :: vector Binary_Array; //binary form of the value 7 long double Accuracy; //accuracy of the value 8 };

9

10 struct Chromosome

11 {

12 std :: vector Gene_Array; //Gene[]

13 long double Fitness; //the weigh of the chromosome in ga

14 };

15

16 struct Population

17 {

18 std :: vector Chromosome_Array; //Chromosome[] 19

20 long double Mutation_Probability; //probability of mutation

21 long double Crossover_Probability; //probability of crossover

22 };

2. 与数据结构相关的基本算法

1） 基因的自动初始化 --在搜索区间中随机生成初始基因

1 //generate random value

2 void initialize( Gene& g)

3 {

4 const long double Ran = ran();

5 const long double Upper = g.Upper;

6 const long double Lower = g.Lower;

7 //const long double Accuracy = g.Accuracy;

8 assert( Upper > Lower );

9

10 g.Value = Lower + Ran * ( Upper - Lower );

11 }

12

2） 基因的二进制编码--将十进制数据编码为二进制

1 //decimal value -> binary form

2 void encoding( Gene& g )

3 {

4 const long double Value = g.Value;

5 const long double Upper = g.Upper;

6 const long double Lower = g.Lower;

7 const long double Accuracy = g.Accuracy;

8

9 unsigned int Size = 1 +

10 static_cast

11 (

12 log( ( Upper - Lower ) / ( Accuracy ) ) /

13 log( 2.0 )

14 );

15

16 if ( Size > 63 )

17 Size = 63;

18

19 const unsigned long long Max = 1

20

21 unsigned long long x =

22 static_cast

23 (

24 static_cast( Max -1 ) *

25 ( Value - Lower ) /

26 ( Upper - Lower )

27 );

28

29 std :: vector Binary_Array;

30

31 for ( unsigned int i = 0; i

32 {

33 if ( x & 1 ) //case odd

34 {

35 Binary_Array.push_back( 1 );

36 }

37 else //case even

38 {

39 Binary_Array.push_back( 0 );

40 }

41 x >>= 1;

42 }

43

44 g.Binary_Array = Binary_Array;

45

46 }

47

3）二进制向十进制的解码--将二进制数据解码为十进制

1 //binary form -> decimal value

2 void decoding( Gene& g )

3 {

4 const unsigned int Size = g.Binary_Array.size();

5 assert( Size > 0 );

6

7 const long double Upper = g.Upper;

8 const long double Lower = g.Lower;

9 //const long double Accuracy = g.Accuracy;

10 const std::vector Binary_Array = g.Binary_Array; 11

12 const unsigned long long Max = 1

13 unsigned long long x = 0;

14

15 for( unsigned int i = Size; i > 0; --i )

16 {

17 x += Binary_Array[i-1];

18 x

19 }

20 //x += Binary_Array[0];

21

22 const long double Value = Lower +

23 static_cast( x ) /

24 static_cast( Max - 1 ) *

25 ( Upper - Lower );

26

27 g.Value = Value;

28 }

4）普通二进制编码转到格雷码

多说一点，在进行二进制交叉的时候，使用格雷码比普通的二进制编码要有效一点。

例如，如果采用普通二进制编码，8可以表示为1000，而7则表示为0111，四个位都是不同的，7与8仅仅相差了1，但是普通二进制编码却相差了这么多，如果对他们进行交叉的话，出来的结果偏离7与8实在太远了，而使用格雷码则可以避免这种尴尬。

这里（http://baike.baidu.com/view/358724.htm）是百度一个有关格雷码的介绍，我就不复制了，有兴趣的话过去看看。

1 //Normal Binary Form --> Gray Binary Form

2 void normal2gray( Gene& g )

3 {

4 const unsigned int Size = g.Binary_Array.size();

5 assert( Size > 0 );

6

7 std :: vector G_Binary_Array; //gray code

8 const std :: vector Binary_Array = g.Binary_Array; 9

10 G_Binary_Array.push_back( Binary_Array[0] );

11 for ( unsigned int i = 1; i

12 {

13 G_Binary_Array.push_back( ( Binary_Array[i-1] +

Binary_Array[i] ) & 1 );

14 }

15 g.Binary_Array = G_Binary_Array;

16 }

17

5） 格雷码转换到普通二进制编码

1 //Gray Binary Form --> Normal Binary Form

2 void normal2binary( Gene& g )

3 {

4 const unsigned int Size = g.Binary_Array.size();

5 assert( Size > 0 );

6

7 std :: vector N_Binary_Array; //Normal Binary Form 8 const std :: vector Binary_Array = g.Binary_Array; 9

10 unsigned int result = 0;

11 for ( unsigned int i = 0; i

12 {

13 result += Binary_Array[i];

14 N_Binary_Array.push_back( result & 1 );

15 }

16

17 g.Binary_Array = N_Binary_Array;

18 }

19

20

6） 进化种群初始化函数一 -- 生成进化个体

1 void initialize( Population& population,

2 const unsigned int size

3 )

4 {

5 Chromosome* chromosome = new Chromosome;

6

7 population.Generation = 1;

8

9 for ( unsigned int i = 0; i

10 {

11

12 population.Chromosome_Array.push_back( *chromosome ); 13 }

14

15 delete chromosome;

16 }

17

7） 进化种群初始化函数二 -- 对种群中的每个个体，初始化其基因

如上边的Camel函数，因为里边有两个自变量需要搜索，那么需要调用这个函数两次，分别对应于x和y

append_gene( p, 100, -100, 1E-7);

append_gene( p, 100, -100, 1E-7);

1 void append_gene( Population& population,

2 const long double& upper,

3 const long double& lower,

4 const long double& accuracy

5 )

6 {

7 assert( upper > lower );

8 assert( accuracy > 0 );

9

10 Gene* gene = new Gene;

11

12 gene -> Upper = upper;

13 gene -> Lower = lower;

14 gene -> Accuracy = accuracy;

15

16 const unsigned int Size = population.Chromosome_Array.size(); 17 for ( unsigned int i = 0; i

18 {

19 initialize( *gene );

20 population.Chromosome_Array[i].Gene_Array.push_back( *gene );

21 }

22

23 delete gene;

24 }

25

8） 搜寻最佳适应度个体 -- 进化到指定年代后，找出最佳个体

1 const std :: vector elite( const Population& population ) 2 {

3 const unsigned int Size = population.Chromosome_Array.size(); 4 assert( Size > 0 );

5 long double max = population.Chromosome_Array[0].Fitness;

6 unsigned int index = 0;

7 for ( unsigned int i = 1; i

8 {

9 if ( population.Chromosome_Array[i].Fitness > max ) 10 {

11 index = i;

12 max = population.Chromosome_Array[i].Fitness; 13 }

14 }

15

16 std :: vector Elite;

17 const unsigned int G_Size =

population.Chromosome_Array[0].Gene_Array.size();

18 for ( unsigned int i = 0; i

19 Elite.push_back( population.Chromosome_Array[index].Gene_Array[i].Value );

20

21 return Elite;

22 }

9） 随机函数

由于遗传算法是一种随机搜索算法，执行的时候需要大量的随机数（记得之前搜索四个未知数，种群100个体，进化800代，大概整个运行过程用了10^10数量级的随机数），库里的随机数生成函数肯定不行。当前使用了一个Kruth推荐的（Kruth, D. E. 1997, Seminumerical Algorithms, vol2. $3）、基于相减方法的随机数生成算法，比基于线性同余方法的快一点。

1 #include

2

3 static long double _ran( int& seed );

4

5 long double ran()

6 {

7 static int seed = static_cast ( time( NULL ) ); 8 return _ran( seed );

9 }

10

11 static long double _ran( int& seed )

12 {

13

14 const int MBIG = 1000000000;

15 const int MSEED = 161803398;

16 const int MZ = 0;

17 const long double FAC = 1.0E-9L;

18

19 static int inext, inextp;

20 static long ma[56];

21 static int iff = 0;

22 long mj, mk;

23 int i, ii, k;

24

25 if ( seed

26 {

27 iff = 1;

28 mj = MSEED - (seed

29 mj %= MBIG;

30 ma[55] = mj;

31 mk = 1;

32 for (i = 1; i

33 ii = (21 * i) % 55;

34 ma[ii] = mk;

35 mk = mj - mk;

36 if (mk

37 mk += MBIG;

38 mj = ma[ii];

39 }

40 for (k = 1; k

41 for (i = 1; i

42 {

43 ma[i] -= ma[1 + (i + 30) % 55];

44 if (ma[i]

45 ma[i] += MBIG;

46 }

47 inext = 0;

48 inextp = 31;

49 seed = 1;

50 }

51 if (++inext == 56)

52 inext = 1;

53 if (++inextp == 56)

54 inextp = 1;

55 mj = ma[inext] - ma[inextp];

56 if (mj

57 mj += MBIG;

58 ma[inext] = mj;

59 return mj * FAC;

60 }

（3）交叉算子

基因交叉，或者基因重组，就是把两个父体部分结构加以替换，生成新的个体的操作，习惯上对实数编码的操作叫做重组（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

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

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 [***********]

父个体2 [***********]

如粗体前边位置为所选择的交叉点，那么生成的子个体为：

子个体1 [***********]

子个体2 [***********]

以下为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

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 36 ( g1.Binary_Array.size() * ran() ); 37

38 for ( unsigned int i = 0; 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;

51 }

52 }

53 }

54

55 gray2normal( g1 );

56 gray2normal( g1 );

57 decoding( g1 );

58 decoding( g2 );

59 }

60 };

61

62

63

（2）洗牌交叉

洗牌交叉就是，将一个父基因取一半，再上来自另外一个父基因的一半，构成一个新的子基因。

算法代码如下：

1 template

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

18 if ( ( i & 1) &&

19 ( g1.Binary_Array[i] xor

g2.Binary_Array[i] )

20 )

21 {

22 if ( g1.Binary_Array[i] )

23 {

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 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

23 for( unsigned int j = 0; j

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

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

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 }

（4） 变异算子 http://www.cppblog.com/feng/archive/2008/06/22/54291.html Copy Righ t Owe to http://www.cppblog.com/feng/

在基因交叉之后产生的子代个体，其变量可能以很小的概率或者步长发生转变，这个过程称为变异(Mutation)。如果进化的目标函数极值是单峰值的，那么，将变异概率p设置为种群数量n的倒数是一个比较好的选择。如果变异概率很大，那么整个搜索过程就退化为一个随机搜索过程。所以，比较稳妥的做法是，进化过程刚刚开始的时候，取p为一个比较大的概率，随着搜索过程的进行，p逐渐缩小到0附近。

与交叉过程一样，变异的算法也可以大致分为实数编码和二进制编码两种。

（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

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

12 {

13 const long double Boundary =

14 1.0L / static_cast(M); 15 const long double Ran = ran();

16 if ( Ran

17 {

18 const unsigned int Base = 1

19 Delta += 1.0L / static_cast( 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

高斯变异

这种变异的方法就是，产生一个服从高斯分布的随机数，取代原先基因中的实数数值。这个算法产生的随机数，数学期望当为当前基因的实数数值。

一个模拟产生的算法是，产生6个服从U(0,1)的随机数，以他们的数学期望作为高斯分布随机数的近似。

1 template

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

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）二进制变异

对二进制编码来讲，变异就是变量的翻转，如

[1**********]001

[1**********]001

c++代码

1 template

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

12 ( static_cast( 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

2 void mutate( DATA& d, const ALGORITHM& a )

3 {

4 a( d );

5 }

6

7 template

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

19 {

20 for ( unsigned int j = 0; j

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 };

遗传算法 C++详解

（1）基本概念 http://www.cppblog.com/feng/archive/2008/06/15/53363.html

遗传算法的基本概念

遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：

一、串(String) 它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。

二、群体(Population) 个体的集合称为群体，串是群体的元素

三、群体大小(Population Size) 在群体中个体的数量称为群体的大小。

四、基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

五 、基因位置(Gene Position) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。

//以下五到九可以不看

六、基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

七、串结构空间SS 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。

八、参数空间S这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。 P

九、非线性 它对应遗传学中的异位显性(Epistasis)

//

十、适应度(Fitness) 表示某一个体对于环境的适应程度。

遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。

遗传算法的原理

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体” 群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

一、遗传算法的目的

典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：

考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有

bi∈{0,1}L (3-84)

给定目标函数f，有f(bi)，并且0

同时 f(bi)≠f(bi+1)

求满足下式

max{f(bi)|bi∈{0,1}L} (3-85)

的bi。

很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。

遗传算法的基本原理

长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：

1．选择(Selection) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。

2．交叉(Crossover) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

3．变异(Mutation) 这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。 遗传算法的原理可以简要给出如下：

choose an intial population

determine the fitness of each individual

perform selection

repeat

perform crossover

perform mutation

determine the fitness of each individual

perform selection

until some stopping criterion applies

这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。

(2)数据结构和与之相关的操作

遗传算法系列 （2） 遗传算法中的数据结构和与之相关的一些数值算法 生存竞争的整个群体称为种群(Population)，种群中所有参与进化的个体(Chromosome)的数量一般为一个定值，而每个个体可能含有多于一个基因(Gene)。

例如，求解一个Camel函数在区间-100

f(x,y)=[4 - 2.1(x^2) + (x^3)/3](x^2) + xy +[-4 +4(y^2)](y^2) 这时候就需要两个基因，每个基因上限是100,下限是-100.

假设数值求解的精度为10^(-7)，那么对应的二进制编码长度N可以这样确定 (2^N)-1 >= [ 100 - ( -100 ) ] / [ 10^(-7) ]

于是，将一个十进制数字x转化为二进制

x' = [x- (-100)] * [(2^N) -1] / [ 100 - ( -100 ) ]

同样，也可以将一个二进制数字x'转化为十进制数字x

程序中，数据结构可以这样定义

1 struct Gene

2 {

3 long double Upper; //upper boundary of the value

4 long double Lower; //lower boundary of the value

5 long double Value; //decimal value of the gene

6 std :: vector Binary_Array; //binary form of the value 7 long double Accuracy; //accuracy of the value 8 };

9

10 struct Chromosome

11 {

12 std :: vector Gene_Array; //Gene[]

13 long double Fitness; //the weigh of the chromosome in ga

14 };

15

16 struct Population

17 {

18 std :: vector Chromosome_Array; //Chromosome[] 19

20 long double Mutation_Probability; //probability of mutation

21 long double Crossover_Probability; //probability of crossover

22 };

2. 与数据结构相关的基本算法

1） 基因的自动初始化 --在搜索区间中随机生成初始基因

1 //generate random value

2 void initialize( Gene& g)

3 {

4 const long double Ran = ran();

5 const long double Upper = g.Upper;

6 const long double Lower = g.Lower;

7 //const long double Accuracy = g.Accuracy;

8 assert( Upper > Lower );

9

10 g.Value = Lower + Ran * ( Upper - Lower );

11 }

12

2） 基因的二进制编码--将十进制数据编码为二进制

1 //decimal value -> binary form

2 void encoding( Gene& g )

3 {

4 const long double Value = g.Value;

5 const long double Upper = g.Upper;

6 const long double Lower = g.Lower;

7 const long double Accuracy = g.Accuracy;

8

9 unsigned int Size = 1 +

10 static_cast

11 (

12 log( ( Upper - Lower ) / ( Accuracy ) ) /

13 log( 2.0 )

14 );

15

16 if ( Size > 63 )

17 Size = 63;

18

19 const unsigned long long Max = 1

20

21 unsigned long long x =

22 static_cast

23 (

24 static_cast( Max -1 ) *

25 ( Value - Lower ) /

26 ( Upper - Lower )

27 );

28

29 std :: vector Binary_Array;

30

31 for ( unsigned int i = 0; i

32 {

33 if ( x & 1 ) //case odd

34 {

35 Binary_Array.push_back( 1 );

36 }

37 else //case even

38 {

39 Binary_Array.push_back( 0 );

40 }

41 x >>= 1;

42 }

43

44 g.Binary_Array = Binary_Array;

45

46 }

47

3）二进制向十进制的解码--将二进制数据解码为十进制

1 //binary form -> decimal value

2 void decoding( Gene& g )

3 {

4 const unsigned int Size = g.Binary_Array.size();

5 assert( Size > 0 );

6

7 const long double Upper = g.Upper;

8 const long double Lower = g.Lower;

9 //const long double Accuracy = g.Accuracy;

10 const std::vector Binary_Array = g.Binary_Array; 11

12 const unsigned long long Max = 1

13 unsigned long long x = 0;

14

15 for( unsigned int i = Size; i > 0; --i )

16 {

17 x += Binary_Array[i-1];

18 x

19 }

20 //x += Binary_Array[0];

21

22 const long double Value = Lower +

23 static_cast( x ) /

24 static_cast( Max - 1 ) *

25 ( Upper - Lower );

26

27 g.Value = Value;

28 }

4）普通二进制编码转到格雷码

多说一点，在进行二进制交叉的时候，使用格雷码比普通的二进制编码要有效一点。

例如，如果采用普通二进制编码，8可以表示为1000，而7则表示为0111，四个位都是不同的，7与8仅仅相差了1，但是普通二进制编码却相差了这么多，如果对他们进行交叉的话，出来的结果偏离7与8实在太远了，而使用格雷码则可以避免这种尴尬。

这里（http://baike.baidu.com/view/358724.htm）是百度一个有关格雷码的介绍，我就不复制了，有兴趣的话过去看看。

1 //Normal Binary Form --> Gray Binary Form

2 void normal2gray( Gene& g )

3 {

4 const unsigned int Size = g.Binary_Array.size();

5 assert( Size > 0 );

6

7 std :: vector G_Binary_Array; //gray code

8 const std :: vector Binary_Array = g.Binary_Array; 9

10 G_Binary_Array.push_back( Binary_Array[0] );

11 for ( unsigned int i = 1; i

12 {

13 G_Binary_Array.push_back( ( Binary_Array[i-1] +

Binary_Array[i] ) & 1 );

14 }

15 g.Binary_Array = G_Binary_Array;

16 }

17

5） 格雷码转换到普通二进制编码

1 //Gray Binary Form --> Normal Binary Form

2 void normal2binary( Gene& g )

3 {

4 const unsigned int Size = g.Binary_Array.size();

5 assert( Size > 0 );

6

7 std :: vector N_Binary_Array; //Normal Binary Form 8 const std :: vector Binary_Array = g.Binary_Array; 9

10 unsigned int result = 0;

11 for ( unsigned int i = 0; i

12 {

13 result += Binary_Array[i];

14 N_Binary_Array.push_back( result & 1 );

15 }

16

17 g.Binary_Array = N_Binary_Array;

18 }

19

20

6） 进化种群初始化函数一 -- 生成进化个体

1 void initialize( Population& population,

2 const unsigned int size

3 )

4 {

5 Chromosome* chromosome = new Chromosome;

6

7 population.Generation = 1;

8

9 for ( unsigned int i = 0; i

10 {

11

12 population.Chromosome_Array.push_back( *chromosome ); 13 }

14

15 delete chromosome;

16 }

17

7） 进化种群初始化函数二 -- 对种群中的每个个体，初始化其基因

如上边的Camel函数，因为里边有两个自变量需要搜索，那么需要调用这个函数两次，分别对应于x和y

append_gene( p, 100, -100, 1E-7);

append_gene( p, 100, -100, 1E-7);

1 void append_gene( Population& population,

2 const long double& upper,

3 const long double& lower,

4 const long double& accuracy

5 )

6 {

7 assert( upper > lower );

8 assert( accuracy > 0 );

9

10 Gene* gene = new Gene;

11

12 gene -> Upper = upper;

13 gene -> Lower = lower;

14 gene -> Accuracy = accuracy;

15

16 const unsigned int Size = population.Chromosome_Array.size(); 17 for ( unsigned int i = 0; i

18 {

19 initialize( *gene );

20 population.Chromosome_Array[i].Gene_Array.push_back( *gene );

21 }

22

23 delete gene;

24 }

25

8） 搜寻最佳适应度个体 -- 进化到指定年代后，找出最佳个体

1 const std :: vector elite( const Population& population ) 2 {

3 const unsigned int Size = population.Chromosome_Array.size(); 4 assert( Size > 0 );

5 long double max = population.Chromosome_Array[0].Fitness;

6 unsigned int index = 0;

7 for ( unsigned int i = 1; i

8 {

9 if ( population.Chromosome_Array[i].Fitness > max ) 10 {

11 index = i;

12 max = population.Chromosome_Array[i].Fitness; 13 }

14 }

15

16 std :: vector Elite;

17 const unsigned int G_Size =

population.Chromosome_Array[0].Gene_Array.size();

18 for ( unsigned int i = 0; i

19 Elite.push_back( population.Chromosome_Array[index].Gene_Array[i].Value );

20

21 return Elite;

22 }

9） 随机函数

由于遗传算法是一种随机搜索算法，执行的时候需要大量的随机数（记得之前搜索四个未知数，种群100个体，进化800代，大概整个运行过程用了10^10数量级的随机数），库里的随机数生成函数肯定不行。当前使用了一个Kruth推荐的（Kruth, D. E. 1997, Seminumerical Algorithms, vol2. $3）、基于相减方法的随机数生成算法，比基于线性同余方法的快一点。

1 #include

2

3 static long double _ran( int& seed );

4

5 long double ran()

6 {

7 static int seed = static_cast ( time( NULL ) ); 8 return _ran( seed );

9 }

10

11 static long double _ran( int& seed )

12 {

13

14 const int MBIG = 1000000000;

15 const int MSEED = 161803398;

16 const int MZ = 0;

17 const long double FAC = 1.0E-9L;

18

19 static int inext, inextp;

20 static long ma[56];

21 static int iff = 0;

22 long mj, mk;

23 int i, ii, k;

24

25 if ( seed

26 {

27 iff = 1;

28 mj = MSEED - (seed

29 mj %= MBIG;

30 ma[55] = mj;

31 mk = 1;

32 for (i = 1; i

33 ii = (21 * i) % 55;

34 ma[ii] = mk;

35 mk = mj - mk;

36 if (mk

37 mk += MBIG;

38 mj = ma[ii];

39 }

40 for (k = 1; k

41 for (i = 1; i

42 {

43 ma[i] -= ma[1 + (i + 30) % 55];

44 if (ma[i]

45 ma[i] += MBIG;

46 }

47 inext = 0;

48 inextp = 31;

49 seed = 1;

50 }

51 if (++inext == 56)

52 inext = 1;

53 if (++inextp == 56)

54 inextp = 1;

55 mj = ma[inext] - ma[inextp];

56 if (mj

57 mj += MBIG;

58 ma[inext] = mj;

59 return mj * FAC;

60 }

（3）交叉算子

基因交叉，或者基因重组，就是把两个父体部分结构加以替换，生成新的个体的操作，习惯上对实数编码的操作叫做重组（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

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

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 [***********]

父个体2 [***********]

如粗体前边位置为所选择的交叉点，那么生成的子个体为：

子个体1 [***********]

子个体2 [***********]

以下为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

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 36 ( g1.Binary_Array.size() * ran() ); 37

38 for ( unsigned int i = 0; 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;

51 }

52 }

53 }

54

55 gray2normal( g1 );

56 gray2normal( g1 );

57 decoding( g1 );

58 decoding( g2 );

59 }

60 };

61

62

63

（2）洗牌交叉

洗牌交叉就是，将一个父基因取一半，再上来自另外一个父基因的一半，构成一个新的子基因。

算法代码如下：

1 template

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

18 if ( ( i & 1) &&

19 ( g1.Binary_Array[i] xor

g2.Binary_Array[i] )

20 )

21 {

22 if ( g1.Binary_Array[i] )

23 {

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 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

23 for( unsigned int j = 0; j

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

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

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 }

（4） 变异算子 http://www.cppblog.com/feng/archive/2008/06/22/54291.html Copy Righ t Owe to http://www.cppblog.com/feng/

在基因交叉之后产生的子代个体，其变量可能以很小的概率或者步长发生转变，这个过程称为变异(Mutation)。如果进化的目标函数极值是单峰值的，那么，将变异概率p设置为种群数量n的倒数是一个比较好的选择。如果变异概率很大，那么整个搜索过程就退化为一个随机搜索过程。所以，比较稳妥的做法是，进化过程刚刚开始的时候，取p为一个比较大的概率，随着搜索过程的进行，p逐渐缩小到0附近。

与交叉过程一样，变异的算法也可以大致分为实数编码和二进制编码两种。

（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

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

12 {

13 const long double Boundary =

14 1.0L / static_cast(M); 15 const long double Ran = ran();

16 if ( Ran

17 {

18 const unsigned int Base = 1

19 Delta += 1.0L / static_cast( 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

高斯变异

这种变异的方法就是，产生一个服从高斯分布的随机数，取代原先基因中的实数数值。这个算法产生的随机数，数学期望当为当前基因的实数数值。

一个模拟产生的算法是，产生6个服从U(0,1)的随机数，以他们的数学期望作为高斯分布随机数的近似。

1 template

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

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）二进制变异

对二进制编码来讲，变异就是变量的翻转，如

[1**********]001

[1**********]001

c++代码

1 template

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

12 ( static_cast( 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

2 void mutate( DATA& d, const ALGORITHM& a )

3 {

4 a( d );

5 }

6

7 template

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

19 {

20 for ( unsigned int j = 0; j

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 };


相关文章

  • 为何要学编程

    • 一.为何要学编程? 每个人的动机不一样.大致有: 1.为了找个好工作:或为了有更好的机会和更好的发展. 2.看到别人超厉害,所以也想学. 3.实际工作中很多场合需要. 4.从小就立志做个程序员,做软件工程师. 5.振兴中国的软件事业. .. ...查看


  • 09级计科专业毕业设计题目

    • 09级计算机科学与技术专业毕业设计题目指南 说明:1. 每个题目的选择人数最多不能超过2名同学,否则将退回重选.(如题目要求可多 人合作,则以题目要求为准),请各班级同学自行协调解决选题冲突问题. 2.学习委员上报题目请用EXCEL 表格, ...查看


  • matlab学习入门及资料

    • matlab学习入门及资料 2009-09-06 21:23 matlab博大精深,说到底我也只不过是个初学者,只是学的时间比新手长了一点,现在写几句给新手,希望能给你们有点帮助 1 学Matlab并不难,难的是学会怎么用. 2不要试图掌握 ...查看


  • PDF417二维码原理

    • PDF417条码编码原理及Visual C++实现 张瑜,黄朝兵5 (武汉理工大学信息工程学院,武汉 430070) 摘要:介绍了PDF417条码的编码原理,采用字节压缩(BC)模式,应用Visual C++编程实现PDF417条码的绘制, ...查看


  • 2013阿里巴巴暑期实习生试题及答案详解

    • 说明:材料大部分来自互联网,如有偏差请谅解. 答题说明: 1.答题时间90分钟,请注意把握时间: 2.试题分为四个部分:单项选择题(10题,20分).不定向选择题(4题,20分).填空问答(5题,40分).综合体(1题,20分): 3.考试 ...查看


  • vc++课程设计实验报告

    • VC++课程设计报告 一.设计时间 2010年12月 27日----12月31日 二.设计地点 三.设计目的 <VC++程序设计>是计算机科学与技术专业的必修专业基础课程,其实践性.应用性很强.实践教学环节是必不可少的一个重要环 ...查看


  • 数据结构课程设计实验报告心得体会C++

    • 专业班级:姓 名:学 号:设计时间:指导教师: 排序算法比较分析 08软件工程2班 汪伟 08010xxxxx 2010-9-15--2010-9-27 杨薇薇 课程设计报告的内容 一.题目:排序算法比较 1. 设计目的 1． 掌握各种排序 ...查看


  • 字符串替换算法和模式匹配算法 - 微软亚洲工程院 - C++博客

    • 字符串替换算法和模式匹配算法 设有主串s和子串t,子串t定位是指在主串s中找到一个与子串t相等的子串.通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配.模式匹配成功是指在目标串s中找到一个模式串t.        传统的字 ...查看


  • c语言算法 猴子吃桃的问题

    • 来源:本站整理  发布时间:2016-01-07  人气:234 最新c语言算法 猴子吃桃的问题 以下是三零网为大家整理的最新c语言算法 猴子吃桃的问题的文章,希望大家能够喜欢! #include main() { int loop,tot ...查看


热门内容