遗传算法ppt课件

1、PPT模板下载： 行业PPT模板： 节日PPT模板： PPT素材下载： PPT图表下载： 优秀PPT下载： PPT教程： Word教程： Excel教程： 资料下载： PPT课件下载： 范文下载： 试卷下载： 教案下载： 字体下载： 遗传算法汇报人：吴钰Genetic AlgorithmALGORITM目录 CONTENTS1遗 传 算 法 定义Genetic algorithm definition2遗传算法关键技术Biological terminology3遗传算法过程Problem import4问题与代码实现General realization5遗传算法Code11-1 遗传算法的

2、科学定义 1-2 生物遗传 1-3 遗传算法图解过程遗传算法定义123 遗 传 算 法 （ G e n e t i c Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现是某种基因组合，它决定了个体的形状的外部表现 以编码空间代替问题参数空间，从代表问题可能有潜在解集的一个种群出发，按照生物进化过程中适者生存、

3、优胜略汰的原理，以适应度作为评价个体优劣的依据，重复使用选择、交叉、变异算子作用于群体，使之不断进化，逐渐接近最优解Genetic Algorithm遗传算法科学定义遗传算法TITLE 01TITLE 02Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat.TITLE 03生物遗传概念遗传算法生物遗传概念生物遗传概念遗传算法的概念遗传算法的概念基因可行解的每一分

4、量的特征染色体可行解的编码个体可行解种群通过适应度函数值选取的一组可行解交叉两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成产生一组新的可行解变异编码的某一分量发生变化的过程适应度度量某个物种对于生存环境的适应程度复制细胞分裂时，遗传物质通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。选择以一定概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程2遗 传 算 法 关 键 技 术2-1 初始化 2-2 适应度函数 2-3 选择 2-4交叉 2-5变异遗传算法步骤遗传算法 你准备要去野游 1 个月，但是你只能背一个限重 30 公斤的背包。现在你有不

5、同的必需物品，它们每一个都有自己的生存点数。因此，你的目标是在有限的背包重量下，最大化你的生存点数。 物件物件重量重量生存点数生存点数睡袋睡袋1515绳索绳索37折叠刀折叠刀210手电筒手电筒55瓶子瓶子98葡萄糖葡萄糖2017100110001110010100011001A1A2A3A4基因基因染色体染色体种群种群遗传算法初始化染色体可表达为二进制数串，在这个问题中：1 代表基因存在代表基因存在0 代表基因丢失代表基因丢失特定位置上的基因代表了上方背包问题表格中的物品。第一一个位置上是 睡袋睡袋第二二个位置上是 绳索绳索第三三个位置上是 折叠刀折叠刀第四四个位置上是 手电筒手电筒第五五个位

6、置上是 瓶子瓶子第六六个位置上是 葡萄糖葡萄糖 例如：染色体A1表示：1、睡袋；4、手电筒、5、瓶子A1(100110)A1(001110)A1(010100)A1(011001) 适应度函数遗传算法物件物件重量重量生存点生存点睡袋1515手电筒55瓶子98总和2928物件物件重量重量生存点生存点折叠刀210手电筒55瓶子98总和1623物件物件重量重量生存点生存点绳索37手电筒55总和812物件物件重量重量生存点生存点绳索37折叠刀210葡萄糖2017总和2534遗传算法选择-轮盘赌选择染色体染色体生存点生存点选择概率选择概率积累概率积累概率A1280.2890.289A2230.2370.

7、526A3160.1240.650A4340.3511.000 选择选择用来实施适者生存的原则，即把当前的群体中的个体按照一定方法，挑选出一部分个体，用于构建交配池 选择算子选择算子的作用效果是提高了群体的平均适应度。由于选择算子没有产生新个体，所以群体中最好个体的适应值不会因为选择操作而有所改变轮盘赌选择算法如图所示：选择了俩个个体A1 , A4个体00.2890.5260.6501.000第1轮第2轮 A1A2A3A4遗传算法交叉 在上一个步骤中，我们已经选择出了可以产生后代的亲本染色体。那么用生物学的话说，所谓交叉交叉，其实就是指的繁殖。现在我们来对染色体 A 1 和 A4（在上一个步骤

8、中选出来的）进行交叉交叉，见下图：100110011001011110100001ParentsOff-springs单点交叉单点交叉100110011001101010100101多点交叉多点交叉ParentsOff-springs遗传算法变异 如果现在我们从生物学的角度来看这个问题，那么请问：由上述过程产生的后代是否有和其父母一样的性状呢？答案是否。在后代的生长过程中，它们体内的基因会发生一些变化，使得它们与父母不同。这个过程我们称为变异变异，它可以被定义为染色体上发生的随机变化，正是因为变异，种群中才会存在多样性多样性。100110011001000111111000ParentsOff

9、-springs变异变异 在进行完一轮遗传变异遗传变异之后，我们用适应度函数对这些新的后代进行验证，如果函数判定它们适应度足够，那么就会用它们从总体中替代掉那些适应度不够的染色体。3遗传算法过程3-1 遗传算法步骤 3-2 遗传算法流程图 3-3 遗传算法伪代码 遗传算法遗传算法步骤evaluationselectioncrossovermutation遗传算法遗传算法流程图ProceduresGA：伪代码begininitializeP(0); / (1)初始化t=0; /t是进化的代数，一代、二代、三代.while(t=T)do /T是最大进化代数;fori=1toMdo /M是初始种群的

10、个体数,随机生成M个个体作为初始群体P（t）；EvaluatefitnessofP(t); / (2) 个体评价计算P（t）中各个个体的适应度值；endforfori=1toMdoSelectoperationtoP(t); / (3) 选择运算将选择算子作用于群体；endforfori=1toM/2doCrossoveroperationtoP(t); / (4) 将交叉算子作用于群体交叉运算;endforfori=1toMdoMutationoperationtoP(t); / (5) 将变异算子作用于群体变异运算;endforfori=1toMdoP(t+1)=P(t); / (6) 通

11、过以上运算得到下一代群体P（t+1）;endfort=t+1; /终止条件判断tT：tt+1转到步骤2endwhileEnd 遗传算法伪代码遗传算法问题导入与代码实现44-1 问题 4-2 代码实现 4-3 应用前景 4-4 案例分析 遗传算法求函数最大值其中0=X1=50=X2=5-2=X3=2F(X) = X12 X1*X2 + X3设置迭代次数,种群内个体数量，交叉率，变异率 初始化种群确定适应值函数选择遗传操作算子：选择运算交叉运算变异运算：停机条件# include #include # include # include # include # include # include

12、# include # include using namespace std;# define POPSIZE 50/种群内个体数量# define MAXGENS 1000/最大的迭代次数# define NVARS 3/变量个数，即用以表示基因型的bit数# define PXOVER 0.8/交换率# define PMUTATION 0.15/突变率struct genotypedouble geneNVARS;double fitness;double upperNVARS;double lowerNVARS;double rfitness;double cfitness; str

13、uct genotype populationPOPSIZE+1;/旧种群 struct genotype newpopulationPOPSIZE+1; /新种群int main ( );void crossover ( int &seed );/交叉操作。void elitist ( );/储存旧的种群 void evaluate ( );/进化 int i4_uniform_ab ( int a, int b, int &seedint Int_uniform_ab(int a, int b)void initialize ( string , int &seed

14、 );void keep_the_best ( );void mutate ( int &seed );double r8_uniform_ab ( double a, double b, int &seed ); double Dou_uniform_ab(double a, double b);void report ( int generation );void selector ( int &seed );double round(double number);void timestamp ( );void Xover ( int one, int two, i

15、nt &seed ); main() freopen(E:output.txt, w+, stdout);string = simple_ga_input.txt;int generation;int i;int seed; timestamp ( );cout “n;cout SIMPLE_GA:n;cout C+ versionn;cout A simple example of a genetic algorithm.n; if ( NVARS 2 )cout n;cout The crossover modification will not be available,n; c

16、out since it requires 2 = NVARS.n; seed = 123456789;srand(unsigned)time(NULL); /产生伪随机数序列 initialize ( , seed ); evaluate ( ); keep_the_best ( ); for ( generation = 0; generation MAXGENS; generation+ )selector ( seed );crossover ( seed );mutate ( seed );report ( generation );evaluate ( );elitist ( );

17、 cout n;cout Best member after MAXGENS generations:n;cout n; for ( i = 0; i NVARS; i+ )cout var( i ) = populationPOPSIZE.genei n; cout n;cout Best fitness = populationPOPSIZE.fitness n;cout n;cout SIMPLE_GA:n;cout Normal end of execution.n;cout n;timestamp ( ); return 0; void crossover ( int &se

18、ed ) /交叉运算交叉运算const double a = 0.0;const double b = 1.0;int mem;int one;int first = 0;double x; for ( mem = 0; mem POPSIZE; +mem )x = Dou_uniform_ab( a, b);if ( x PXOVER ) +first;if ( first % 2 = 0 )Xover ( one, mem, seed );elseone = mem; return;void elitist ( )int i;double best;int best_mem;double

19、worst;int worst_mem; best = population0.fitness;worst = population0.fitness; for ( i = 0; i POPSIZE - 1; +i )if ( populationi+1.fitness populationi.fitness )if ( best = populationi.fitness )best = populationi.fitness;best_mem = i;if ( populationi+1.fitness = worst )worst = populationi+1.fitness;wors

20、t_mem = i + 1; else if ( populationi.fitness = worst ) worst = populationi.fitness;worst_mem = i; if ( best = populationi+1.fitness ) best = populationi+1.fitness;best_mem = i + 1; if ( populationPOPSIZE.fitness = best )for ( i = 0; i NVARS; i+ )populationPOPSIZE.genei = populationbest_mem.genei;pop

21、ulationPOPSIZE.fitness = populationbest_mem.fitness;elsefor ( i = 0; i NVARS; i+ )populationworst_mem.genei = populationPOPSIZE.genei;populationworst_mem.fitness = populationPOPSIZE.fitness; return;void evaluate ( ) /实现用户定义的评估功能实现用户定义的评估功能 int member;int i;double xNVARS+1; for ( member = 0; member P

22、OPSIZE; member+ )for ( i = 0; i NVARS; i+ )xi+1 = populationmember.genei; populationmember.fitness = ( x1 * x1 ) - ( x1 * x2 ) + x3;return; int Int_uniform_ab(int a, int b)int tmp;tmp = (rand() % (b-a+1)+ a;return tmp; int i4_uniform_ab ( int a, int b, int &seed )int c;const int i4_huge = 214748

23、3647;int k;float r;int value;if ( seed = 0 )cerr n;cerr I4_UNIFORM_AB - Fatal error!n;cerr Input value of SEED = 0.n;exit ( 1 );if ( b a )c = a;a = b;b = c;k = seed / 127773;seed = 16807 * ( seed - k * 127773 ) - k * 2836;if ( seed 0 )seed = seed + i4_huge; r = ( float ) ( seed ) * 4.656612875E-10;r

24、 = ( 1.0 - r ) * ( ( float ) a - 0.5 ) + r * ( ( float ) b + 0.5 );value = round ( rif ( value a )value = a;if ( b value )value = b; return value; void initialize ( string , int &seed ) /初始化种群初始化种群int i;ifstream input;int j;double lbound;double ubound;input.open ( ( ) );if ( !input )cerr n;cerr

25、INITIALIZE - Fatal error!n;cerr Cannot open the input file!n;exit ( 1 );for ( i = 0; i lbound ubound;for ( j = 0; j POPSIZE; j+ )populationj.fitness = 0;populationj.rfitness = 0;populationj.cfitness = 0;populationj.loweri = lbound;populationj.upperi= ubound;/populationj.genei = r8_uniform_ab ( lboun

26、d, ubound, seed );populationj.genei = Dou_uniform_ab( lbound, ubound ); input.close ( ); return; void keep_the_best ( )int cur_best;int mem;int i; cur_best = 0; for ( mem = 0; mem POPSIZE; mem+ )if ( populationPOPSIZE.fitness populationmem.fitness )cur_best = mem;populationPOPSIZE.fitness = populati

27、onmem.fitness;for ( i = 0; i NVARS; i+ )populationPOPSIZE.genei = populationcur_best.genei; return;void mutate ( int &seed ) /变异运算变异运算const double a = 0.0;const double b = 1.0;int i;int j;double lbound;double ubound;double x; for ( i = 0; i POPSIZE; i+ )for ( j = 0; j NVARS; j+ )/x = r8_uniform_

28、ab ( a, b, seed );x = Dou_uniform_ab( a, b);if ( x PMUTATION )lbound = populationi.lowerj;ubound = populationi.upperj; /populationi.genej = r8_uniform_ab ( lbound, ubound, seed );populationi.genej = Dou_uniform_ab( lbound, ubound ); return;double r8_uniform_ab ( double a, double b, int &seed )in

29、t i4_huge = 2147483647;int k;double value;if ( seed = 0 )cerr n;cerr R8_UNIFORM_AB - Fatal error!n;cerr Input value of SEED = 0.n;exit ( 1 );k = seed / 127773;seed = 16807 * ( seed - k * 127773 ) - k * 2836;if ( seed 0 )seed = seed + i4_huge;value = ( double ) ( seed ) * 4.656612875E-10;value = a +

30、( b - a ) * value;return value; double Dou_uniform_ab(double a, double b)double tmp;tmp = a + static_cast(rand()/RAND_MAX*(b-a);return tmp;void report ( int generation )double avg;double best_val;int i;double square_sum;double stddev;double sum;double sum_square; if ( generation = 0 )cout n;cout Gen

31、eration Best Average Standard n;cout number value fitness deviation n;cout n;sum = 0.0;sum_square = 0.0;for ( i = 0; i POPSIZE; i+ )sum = sum + populationi.fitness;sum_square = sum_square + populationi.fitness * populationi.fitness;avg = sum / ( double ) POPSIZE;square_sum = avg * avg * POPSIZE;stdd

32、ev = sqrt ( ( sum_square - square_sum ) / ( POPSIZE - 1 ) );best_val = populationPOPSIZE.fitness;cout setw(8) generation setw(14) best_val setw(14) avg setw(14) stddev n; return;void selector ( int &seed ) /选择运算选择运算 const double a = 0.0; const double b = 1.0; int i; int j; int mem; double p; double sum; sum = 0.0; for ( mem = 0; mem POPSIZE; mem+ ) sum = sum + populationmem.fitness; for ( mem = 0; mem POPSIZE; mem+ ) populationmem.rfitness = populationmem.fitness / sum; popul