遗传算法流程图?遗传算法的基本原理?遗传算法 交叉和变异?简单遗传算法MATLAB实现(2)

在开始遗传算法迭代过程之前，需要对种群进行初始化。设种群大小为pop_size，每个染色体或个体的长度为chromo_size，种群的大小决定了种群的多样性，而染色体的长度则是由前述的编码过程决定的。一般随机生成初始种群，但是如果知道种群的实际分布，也可以按照此分布来生成初始种群。假设生成的初始种群为(v1, v2, …, vpop_size)。

1.3 选择操作

选择操作即从前代种群中选择个体到下一代种群的过程。一般根据个体适应度的分布来选择个体。以初始种群(v1, v2, …, vpop_size)为例，假设每个个体的适应度为(fitness(v1), fitness(v2),…, fitness(vpop_size))，一般适应度可以按照解码的过程进行计算。以赌的方式选择个体，如下图

随机转动一下，当停止转动时，若指针指向某个个体，则该个体被选中。很明显，具有较高适应度的个体比具有较低适应度的个体更有机会被选中。但是这种选择具有随机性，在选择的过程中可能会丢失掉比较好的个体，所以可以使用精英机制，将前代最优个体直接选到下一代中，。

赌选择具体算法如下（这里假定种群中个体是按照适应度从小到大进行排列的，如果不是，可以按照某种排序算法对种群个体进行重排）：

Selection Algorithm var pop, pop_new;/*pop为前代种群，pop_new为下一代种群*/ var fitness_value, fitness_table;/*fitness_value为种群的适应度，fitness_table为种群累积适应度*/ for i=1:pop_size r = rand*fitness_table(pop_size);/*随机生成一个随机数，在0和总适应度之间，因为fitness_table(pop_size)为最后一个个体的累积适应度，即为总适应度*/ first = 1; last = pop_size; mid = round((last+first)/2); idx = -1; /*下面按照排中法选择个体*/ while (first <= last) && (idx == -1) if r > fitness_table(mid) first = mid; elseif r < fitness_table(mid) last = mid; else idx = mid; break; end if mid = round((last+first)/2); if (last - first) == 1 idx = last; break; end if end while for j=1:chromo_size pop_new(i,j)=pop(idx,j); end for end elitism p = pop_size-1; else p = pop_size; end if for i=1:p for j=1:chromo_size pop(i,j) = pop_new(i,j);/*若是精英选择，则只将pop_new前pop_size-1个个体赋给pop，最后一个为前代最优个体保留*/ end for end for

1.3 交叉操作

交叉操作是对任意两个个体进行的（在这里我们实现的算法是直接对相邻的两个个体进行的）。随机选择两个个体，如下图所示

然后随机生成一个实数0<=r<=1, 如果r<cross_rate， 0<cross_rate<1为交叉概率，则对这两个个体进行交叉，否则则不进行。如果需要进行交叉，再随机选择交叉位置(rand*chromo_size)，如果等于0或者1，将不进行交叉。否则将交叉位置以后的二进制串进行对换（包括交叉位置）。（注意：有时候还可以进行多点交叉，但是这里只讨论单点交叉的情况）

单点交叉具体算法如下：

Crossover algorithm for i=1:2:pop_size if(rand < cross_rate)/*cross_rate为交叉概率*/ cross_pos = round(rand * chromo_size);/*交叉位置*/ if or (cross_pos == 0, cross_pos == 1) continue;/*若交叉位置为0或1，则不进行交叉*/ end if for j=cross_pos:chromo_size pop(i,j)<->pop(i+1,j);/*交换*/ end for end if end for

1.4 变异操作

变异操作是对单个个体进行的。首先生成一个随机实数0<=r<=1, 如果r<mutate_rate，则对此个体进行变异操作， 0<mutate_rate<1为变异概率，一般为一个比较小的实数。对每一个个体，进行变异操作，如下图所示

如个体需要进行变异操作，首先需要确定变异位置(rand*chromo_size)，若为0则不进行变异，否则则对该位置的二进制数字进行变异：1变成0, 0变成1.（当然也可以选择多点进行变异）

单点变异的具体算法描述如下：

Mutation algorithm for i=1:pop_size if rand < mutate_rate/*mutate_rate为变异概率*/ mutate_pos = round(rand*chromo_size);/*变异位置*/ if mutate_pos == 0 continue;/*若变异位置为0，则不进行变异*/ end if pop(i,mutate_pos) = 1 - pop(i, mutate_pos);/*将变异位置上的数字至反*/ end if end for

1.5 遗传算法流程

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-13665-2.html