《遗传算法》PPT课件

《《遗传算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章遗传算法1GA的基本思想来源于Darwin的进化论和Mendel的遗传学说。Darwin的进化论认为每一物种在不断的发展过程中都是越来越适应环境。物种的每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来。在某一环境中也是那些更能适应环境的个体特征能被保留下来，这就是适者生存的原理。遗传算法的由来2达尔文进化论3同样的，人类也是一代比一代聪明，可以说人类近百年创造的文明比人类前面几千年创造的文明还要多。4因此：我们得到的结论是：生物一代比一代优生物虽然

2、一代比一代优，但并不是说后一代与前一代没有任何的关系，后一代或多或少总与前一代有些相同，也有一些不同。生物的后一代总是或多或少的继承了前一代的一些特性，这就叫遗传。而后一代又不完全像前一代，这叫变异。生物在进化的过程中既有遗传，又有变异，生物就是在这样的遗传、变异的作用那个下，一代一代的繁衍下去，而且得到的是一代比一代优。58.1遗传算法的基本概念1.个体与种群●个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。●种群(population)就是

3、模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。62.适应度与适应度函数●适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。●适应度函数(fitnessfunction)就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。73.染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如

4、：个体染色体9----1001染色体长度l=4（2，5，6）----010101110l=38遗传算法基本概念和术语进化（evolution）生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。94.遗传操作亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作:●选择-复制(selection-reproduction)●交叉(crossover，亦称交换、交配或杂交)●变异(muta

5、tion，亦称突变)10遗传算法基本概念和术语选择（selection）按照一定概率随机地选择两对个体进行繁殖(即生成后继状态)遗传算法在很大程度上是一种偶然性现象，随机过程在其中起重要作用。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。11复制(又称繁殖)是从一个旧种群(oldpopulation)中选择生命力强的个体位串(或称字符串)产生新种群的过程。或者说，复制是个体位串根据其目标函数(即适应度函数)拷贝自己的过程。根据位串的适应度值拷贝位串意味着，具有较高适应度值的位串更有可能在下一

6、代中产生一个或多个后代。显然，这个操作是模仿自然选择现象，将达尔文的适者生存理论应用于位串的复制，适应度值是该位串被复制或被淘汰的决定因素。8.1遗传算法基本原理12选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为13遗传算法基本概念和术语交叉（crossover）有性生殖生物在繁殖下一代时，两个同源染色体通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切

7、断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组（recombination），俗称“杂交”。14交叉就是互换两个染色体某些位上的基因。s1′=01000101,s2′=10011011可以看做是原染色体s1和s2的子代染色体。例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即15遗传算法基本概念和术语变异（mutation）在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。1

8、6变异就是改变染色体某个(些)位上的基因。（0变为1或1变为0）例如,设染色体s=11001101将其第三位上的0变为1,即s=11001101→11101101=s′。s′也可以看做是原染色体s的子代染色体。其中变异的位置是随机的。17遗传学相关概念遗传学遗传算法数学1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体