遗传算法 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)的集合。 八、参数空间SP 这是串空间在物理系统中的映射,它对应于遗传学中的表现型 (Phenotype)的集合。 九、非线性 它对应遗传学中的异位显性(Epistasis) // 十、适应度(Fitness) 表示某一个体对于环境的适应程度。 遗传算法还有一些其它的概念,这些概念在介绍遗传算法的原理和执行过程时, 再进行说明。 遗传算法的原理 遗传算法 GA 把问题的解表示成“染色体”,在算法中也即是以二进制编码的串。 并且,在执行遗传算法之前,给出一群“染色体”,也即是假设解。然后,把这 些假设解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境 的“染色体”进行复制,再通过交叉,变异过程产生更适应环境的新一代“染色 体” 群。这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体” 上,它就是问题的最优解。 一、遗传算法的目的 典型的遗传算法 CGA(Canonical Genetic Algorithm)通常用于解决下面这一类 的静态最优化问题: 考虑对于一群长度为L的二进制编码bi,i=1,2,…,n;有 bi∈{0,1}L (3-84) 给定目标函数f,有f(bi),并且 0= [ 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< int > 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 > Gene_Array; //Gene[] 13 long double Fitness; //the weigh of the chromosome in ga 14 }; 15 16 struct Population 17 { 18 std :: vector< Chromosome > 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< unsigned int > 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 << Size; 20 21 unsigned long long x = 22 static_cast< unsigned long long > 23 ( 24 static_cast< long double>( Max -1 ) * 25 ( Value - Lower ) / 26 ( Upper - Lower ) 27 ); 28 29 std :: vector Binary_Array; 30 31 for ( unsigned int i = 0; i <= Size; ++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 << Size; 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 <<= 1; 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 < Size; ++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 < Size; ++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 < size; ++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 < Size; ++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< long double > 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 < Size; ++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 < G_Size; ++i ) 19 Elite.push_back( population.Chromosome_Array[index].Gene_A rray[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 < unsigned int >( 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 < 0 || iff == 0) 26 { 27 iff = 1; 28 mj = MSEED - (seed < 0 ? -seed : seed); 29 mj %= MBIG; 30 ma[55] = mj; 31 mk = 1; 32 for (i = 1; i <= 54; i++) { 33 ii = (21 * i) % 55; 34 ma[ii] = mk; 35 mk = mj - mk; 36 if (mk < MZ) 37 mk += MBIG; 38 mj = ma[ii]; 39 } 40 for (k = 1; k <= 4; k++) 41 for (i = 1; i <= 55; i++) 42 { 43 ma[i] -= ma[1 + (i + 30) % 55]; 44 if (ma[i] < MZ) 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 < MZ) 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< 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 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].G ene_Array[j].Value 33 ) 34 continue; 35 //6 36 crossover( 37 population.Chromosome_Array[i].Gene_Ar ray[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) 实数变异 <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(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( 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 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)二进制变异 对二进制编码来讲,变异就是变量的翻转,如 10000111100001 10000101100001 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 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< 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 };
还剩20页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

p3n5

贡献于2016-01-21

下载需要 5 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf