遗传算法及其在图像分割中的应用.ppt

《遗传算法及其在图像分割中的应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、遗传算法及其在图像分割中的应用目录遗传算法简介图像分割简介一维最大熵阈值分割二维最大熵阈值分割9/21/20212遗传算法简称GA（GeneticAlgorithms）遗传算法是20世纪60~70年代主要由美国JohnHolland教授提出。其内涵哲理启迪于自然界生物从低级、简单到高级、复杂，乃至人类这样一个漫长而绝妙的进化过程。借鉴Darwin的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传的机理。其本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传

2、算法9/21/20213遗传算法基本思想从初始化的群体出发，通过随机选择(复制)（使群体中优秀的个体有更多的机会传给下一代），交叉（体现了自然界中群体内个体之间的信息交换），和变异（在群体中引入新的变种确保群体中信息的多样性）等遗传操作，使最具有生存能力的染色体以最大可能生存,群体一代一代地进化到搜索空间中越来越好的区域.9/21/20214基本遗传算法的构成要素(1)染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x

3、；100111001000101101就可表示一个个体，该个体的染色体长度是l＝18。(2)个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。9/21/20215(3)遗传算子基本遗传算法使用下述三种遗传算子：•选择运算：使用比例选择算子；•交叉运算：使用单点交叉算子；•变异运算：使用基本位变异算子。(4)基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定：•M：群体大小，即群体中所含个体的数量，一般取为20~100。•T：遗传运算的终止进化代数，一般取为100~5

4、00•pc：交叉概率，一般取为0.4~0.99•pm：变异概率，一般取为0.0001~0.19/21/20216基本遗传算法的形式化定义基本遗传算法可定义为一个7元组：GA＝(M,F,s,c,m,pc,pm)M——群体大小；F——个体适应度评价函数；s——选择操作算于；c——交叉操作算子：m——变异操作算于；pc——交叉概率；pm——变异概率；9/21/20217基本遗传算法描述ProcedureGABegininitializeP(0);t=0;while(t<=T)dofori=1toMdoEvaluatefitnessofP(t

5、);endforfori=1toMdoSelectoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endforfori=1toMdoP(t+1)=P(t);endfort=t+1endwhileend9/21/20218基本遗传算法的实现根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计算机语言来实现这个基本遗传算法。现对具体实现过程中的问题作以下说明：一）编码与解

6、码(1)编码假设某一参数的取值范围是[umin,umax]，用长度为l的二进制编码符号串来表示该参数，则它总共能够产生2l种不同的编码，参数编码时的对应关系如下：00000000…00000000＝0umin00000000…00000001＝1umin+00000000…00000010＝2umin+2……11111111…11111111=2l–1umax9/21/20219其中，为二进制编码的编码精度，其公式为：(2)解码假设某一个体的编码是：则对应的解码公式为：9/21/202110二）个体适应度评价一般情况下，根据目标

7、函数值来进行种群中个体适应度值的计算。(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(X)就等于相应的目标函数值f(X)，即：F(X)＝f(X)(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：minf(X)＝max(-f(X))9/21/202111三）选择算子(1)选择算子或复制算子的作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。(2)最常用和最基本的选择算子：比例选择算子。(3)比例选择算子：指个体被选

8、中并遗传到下一代群体中的概率与该个体的适应度大小成正比。(4)执行比例选择的手段是轮盘选择。轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度：pi=fi/fi(i=1,2,…,M)式中pi——个体i被选中的概