第7章 智能最优化算法ppt课件.ppt

《第7章 智能最优化算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章智能最优化算法随着仿生学、遗传学和人工智能科学的发展，从20世纪70年代以来，科学家相继将遗传学、神经网络科学的原理和方法应用到最优化领域，形成了一系列新的最优化方法，如遗传算法、神经网络算法、蚁群算法等。这些算法不需要构造精确的数学搜索方向，不需要进行繁杂的一维搜索，而是通过大量简单的信息传播和演变方法，得到问题的最优解。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局最优化概率搜索算法。7.1遗传算法7.1.1生物的遗传与进化生物从其亲代继承特性或形状的现象称为遗传；生物在其延续生

2、存的过程中,逐渐适应生存环境，使其品质不断得到改良，这种生命现象称进化。构成生物的基本结构和功能单元是细胞细胞中含有一种微小的丝状化合物称染色体染色体主要由一种叫做核糖核酸(简称DNA)的物质构成DNA按一定规则排列的长连称基因基因是遗传的基本单位另外，在进行细胞复制时，也可能产生某些差错，从而使DNA发生某种变异，产生新的染色体。可见，同源染色体之间的复制、交叉或变异会使基因或染色体发生各种各样的变化，从而，使生物呈现新的性状，产生新的物种。细胞在分裂时，遗传物质DNA通过复制转移到新的细胞中，新细胞就继承了

3、旧细胞的基因。有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉而重组，即在两个染色体的某一相同位置处DNA被切断，然后分别交叉组合形成两个新的染色体。7.1.2基本遗传算法可以看作由n个遗传基因组成的染色体，也称个体。最简单的等位基因由0和1这两个整数组成，相应的染色体或个体就是一个二进制符号串。在遗传算法中，将设计变量用符号串表示。由m个个体组成一个群体，记作这种编码所形成的符号串称个体的基因型，与之对应的值称个体的表现型。把其中每一个看作一个遗传基因，它的所有可能的取值称等位基因。（1）遗传编码遗传算

4、法的运行不直接对设计变量本身进行操作，而是对表示可行解的个体编码进行选择、交叉和变异等遗传运算。在遗传算法中把原问题的可行解转化为个体符号串的方法称编码。现有的编码方法可以分为三类，它们是二进制编码、浮点数编码和符号编码。二进制编码所用的符号集是由0和1组成的二值符号集，它所构成的个体基因型是一个二进制符号串。符号串的长度与所要求的求解精度有关。假设某一参数的取值范围是，若用长度为的二进制符号串来表示，总共能够产生个编码。编码精度为（7-1）这里介绍常用的二进制编码方法。假设某一个体的编码是：(7-2)则对应的

5、解码公式为(7-3)就表示一个个体，称个体的基因型，对应的十进制数175就是个体的表现型，编码精度为例如，对于变量若采用10位二进制编码时，可代表个不同的个体。如在研究生物的遗传和进化现象时，生物学家使用适应度这个术语来度量物种对生存环境的适应程度。，一般由目标函数或惩罚函数（2）个体适应度在遗传算法中使用适应度这个概念来度量群体中个体的优劣程度。适应度较高的个体遗传到下一代的概率较大，反之则较小。度量个体适应度的函数称适应度函数，一般由目标函数或惩罚函数转换而来。以目标函数为例，常用的转换关系如下：对于极大化

6、问题：(7-4)式中为一适当小的正数。对于极小化问题：(7-5)为一较大的正数。式中，生物的进化是以集团为主体进行的。与此对应，遗传算法的运算对象也是由M个个体所组成的集合，称群体。第t代群体记作P（t），遗传算法的运算就是群体的反复演变过程。（3）遗传运算遗传算法将染色体中基因的复制、交叉和变异归结为各自的运算规则或遗传算子，并反复将这些遗传算子作用于群体P（t），对其进行选择、交叉和变异运算，以求得到最优的个体，即问题的最优解。生物的进化过程主要是通过染色体之间的复制、交叉和变异来完成的。1）选择运算遗传算

7、法使用选择算子来对群体中的个体进行优胜劣汰操作。适应度较高的个体有较大的概率遗传到下一代。设群体的大小为M，个体i的适应度为fi，则个体i被选中的概率Pis为：目前常用比例选择运算。其基本的操作是：个体被选中并遗传到下一代的概率与它的适应度的大小成正比。每个概率值组成一个区间，全部概率值之和为1。2）交叉运算交配重组是生物遗传进化过程中的一个重要环节。模仿这一过程，遗传算法使用交叉运算，即在两个相互配对的个体间按某种方式交换其部分基因，从而形成两个新生的个体。运算前需对群体中的个体进行随机配对，然后以不同的方式

8、确定配对个体交叉点的位置，并在这些位置上进行部分基因的交换，形成不同的交叉运算方法。目前最常用的是单点交叉运算。产生一个0到1之间的随机数，依据概率值所出现的区间来决定对应的个体被选中的次数，此法亦称轮盘法。11000000010001010011父个体1父个体211000100010001000011子个体1子个体2交叉运算交叉点交叉点单点交叉又称简单交叉，它是在个体编码串中随机地设