《遗传算法基础》PPT课件

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

1、遗传算法基础讲解人：蔡亮遗传算法的产生50，60年代Holland提出遗传算法60年代中期Holland的学生J.D.Bagley提出“遗传算法”一词70年代Holland模式定理《AdaptationinNaturalandArtificialSystems》发表Holland的学生DeJong将遗传算法用于最优化问题Grefenstette开发了第一个遗传算法软件遗传算法的发展EvolutionaryComputationcomputationalintelligence遗传算法的生物学基础生物进化理论与遗传

2、学达尔文的进化论达尔文（1858）的自然选择学说包括：1遗传2变异3生存斗争和适者生存遗传学1866孟德尔提出的分离律和自由组合律，奠定了现代遗传学的基础摩尔根进一步确立了染色体的遗传学说，认为遗传性状是由基因决定遗传算法的生物学基础遗传学的基本结论生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状染色体是由基因及其由规律的排列所构成.遗传和进化过程发生在染色体上生物的繁殖过程是由基因的复制过程来完成的通过同源染色体间的交叉和变异会产生新的物种,使生物呈现新的性状对环境适应性好的基因或染色体比适应性差的

3、基因或染色体有更多的机会遗传到下一代遗传算法的生物学基础生物进化理论与遗传学现代综合进化论没有所谓生存斗争的问题，单是个体繁殖机会的差异也能造成后代基因库组成的改变，自然选择也能够进行生物的进化实际上是种群的进化每一代个体基因型的改变会影响种群基因库的组成种群基因库的进化就是种群的进化基因库+适者繁殖=群体进化遗传算法的生物学基础生物进化理论与遗传学非达尔文式进化理论1.分子进化中性理论2.跳跃进化理论3.间断平衡进化理论非渐变进化理论的核心基础仍然是自然选择遗传算法的生物进化模型现代综合进化论选择优胜劣汰遗传保

4、持优良特性变异产生新特性遗传算法的基本术语编码：从问题域到遗传域的映射。即性状与基因的DNA序列的映射解码：从遗传域到问题域的映射。即将DNA序列解释成个体的性状适应度：种群的某个个体对生存环境的适应程度。适应度高的个体可以获得更多的繁殖机会，而适应度低的个体，其繁殖机会就会比较少，甚至逐渐灭绝选择：以一定概率从种群中选择若干个体的操作。一般而言，选择就是基于适应度的优胜劣汰的过程交叉：有性生殖生物在繁殖下一时两个同源染色体之间通过交叉而重组，即在两个染色体的相同位置处DNA被切断，前后两串分别交叉组合形成新的染

5、色体遗传算法的基本思想遗传算法的流程图编码解码遗传算法基本要素与实现技术编码与解码问题域（解空间）优化变量遗传域（基因空间）优化变量的代码表示映射二进制编码浮点数编码符号编码编码与解码二进制编码二进制编码是遗传算法中最常用、最原始的一种编码方法，它将原问题的解空间映射到二进制空间上，然后进行遗传操作。找到最优个体后再通过解码过程还原原始的数据形式进行适应度评价二进制编码的串长度取决于求解的精度编码公式解码公式编码与解码浮点编码个体的基因值用某一范围内决策变量的一个浮点数来表示，个体的编码长度等于其决策变量的个数。

6、浮点编码使用的是决策变量的真实值2.509.543.250.254.257.00X:某个优化问题含有6个变量，则它的一个基因表达为对应的表现型为x=[2.50,9.54,3.25,0.25,4.25,7.00]编码与解码符号编码个体基因值取自一个无数值含意，而只有代码含义的符号集。符号集可以是字母，也可以是数字序号。如血型A，B，AB，O可以分别用[a,b,c,d]表示，或者[a1,a2,a3,a4],也可表示为[1，2，3，4]遗传算法基本要素与实现技术最小与最大的转化个体适应度评价为正确计算个体的遗传概率，个

7、体的适应度必须为正数或者为零，不能为负数而目标函数在寻优区间有一下三种状态：个体适应度评价F（x）＝f（x）＋CF（x）F（x）F（x）遗传算法基本要素与实现技术选择算子适应度较高的个体被遗传到下一代群体中的概率较大，适应度较低的个体被遗传到下一代群体中的概率较小。选择方法比例选择法（轮盘赌）锦标赛选择法比例选择法（轮盘赌）基本思想各个个体被选中的概率与其适应度大小成正比。设群体大小为，个体的适应度大小为，则个体被选中的概率为比例选择法（轮盘赌）具体步骤1）计算各基因适应度值和选择概率2）累计所有基因选择概率值，

8、记录中间累加值S-mid和最后累加值sum=∑3）产生一个随机数N，0〈N〈14）选择对应中间累加值S-mid的基因进入交换集5）重复（3）和（4），直到获得足够的基因。比例选择法（轮盘赌）举例染色体的适应度和所占的比例锦标赛选择法基本思想每次随机选取n个个体，比较之后选择其中适应度最高的个体做为下一代种群的父本遗传算法基本要素与实现技术交叉算子选择是对优秀个体的复制，不