《遗传算法简介》PPT课件

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

1、遗传算法遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘

2、汰，适应性高的基因结构得以保存下来。遗传与进化的系统观生物的所有遗传信息都包含在染色体中，染色体决定生物的性状。染色体是由基因及其有规律的排列构成，遗传进化过程发生在染色体上。生物的繁衍由基因的复制过程完成。通过同源染色体之间的交叉或染色体的变异会产生新物种，使生物呈现新性状。对环境适应性好的基因比适应性差的基因有更多机会遗传到下一代。遗传算法的基本概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：串(String)它是个体(Indivi

3、dual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。群体(Population)个体的集合称为群体，串是群体的元素。群体大小(PopulationSize)在群体中个体的数量称为群体的大小。遗传算法的基本概念基因(Gene)基因是串中的元素，用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。基因位置(GenePosition)一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左

4、向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。基因特征值(GeneFeature)在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。遗传算法的基本概念串结构空间SS在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。参数空间SP这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phe

5、notype)的集合。非线性它对应遗传学中的异位显性(Epistasis)适应度(Fitness)表示某一个体对于环境的适应程度。遗传算法的基本实现编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型数据，这些数据的不同组合便构成了不同的点。初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。遗传算法的基本实现选择：选择的目的

6、是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之间。变异

7、为新个体的产生提供了机会。遗传算法的基本实现GA的计算过程为：选择编码方式；产生初始群体；计算初始群体的适应性值；如果不满足条件{  选择  交换  变异  计算新一代群体的适应性值}一、遗传算法的描述例子：为四个连锁饭店寻找最好的经营决策，其中一个经营饭店的决策包括要做出以下三项决定：（1）价格汉堡包的价格应该定在50美分还是1美元？（2）饮料和汉堡包一起供应的应该是酒还是可乐？（3）服务速度饭店应该提供慢的还是快的服务？目的：找到这三个决定的组合以产生最高的利润。共有8种表示方案。用遗传算法解这个

8、问题的第一步就是选取一个适当的表示方案。。饭店编号价格饮料速度二进制表示1高可乐快0112高酒快0013低可乐慢1104高可乐慢010表1饭店问题的表示方案（其中的4个）群体规模N＝4第0代i串xi适应值f（xi）10113200113110640102总和12最小值1平均值3.00最大值6表2初始群体中经营决策的适应值一个简单的遗传算法由选择、交叉、变异三个算子组成。第0代交叉池i串