《人工智能-9遗传算法72精编版》由会员分享，可在线阅读，更多相关《人工智能-9遗传算法72精编版（73页珍藏版）》请在金锄头文库上搜索。
1、,计算智能是信息科学和生命科学相互交叉的前沿领域,是现代科学技术发展的一个重要体现。计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展反映了当代科学技术多学科交叉与集成的重要发展趋势。,贝兹德克于1994年提出了一种A，B，C智能模型，从而表示ABC与神经网络、模式识别和智能之间的关系：A：Artificial ,表示人工的、符号的（非生物的）B：Biological ,表示生物的C：Computational,表示计算的计算智能是一种智力方式的底层认知，它与人工智能的区别是认知层次从中层下降到底层而已。中层系统含有知识，底层系统没有知识。,关于A，B，C智能,计算智能与
2、人工智能的区别与联系,NN Neural Network 神经网络 PR Pattern Recognition 模式识别,计算智能系统与人工智能系统,当一个系统只涉及数值（底层）数据，含有模式识别部分，不应用于人工智能意义上的知识，而且系统能够呈现出： （1）计算适应性 （2）计算容错性 （3）接近人的计算速度 （4）计算误差率与人接近 则该系统就是计算智能系统。 当一个智能计算系统以非数值方式并加上知识，即为人工智能系统。,神经计算（Neural Computation）,神经计算研究的进展 1943年麦卡洛奇和皮茨提出神经网络模型的概念（称为MP模型） 20世纪60年代威德罗和霍夫提出了
3、自适应线性元件。 60年代末到80年代初初与研究的低潮期 80年代后又大发展,遗传算法,遗传算法简称GA（Genetic Algorithms）是1975年由美国Michigan(密歇根州)大学的J.Holland教授提出的模拟自然界生物遗传学（孟德尔）和生物进化论（达尔文）通过人工方式所构造的一类并行随机搜索最优化方法，是对生物进化过程进行的一种数学仿真，是进化计算的重要形式。,1、遗传算法,在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性。其主要特点是 (1)直接对结构对象进行操作，不存在求导和函数连续性的限定； (2)具有内在的隐含并行性和更好的全局寻优能力； (3)采用
4、概率化的寻优方法，能自动获取和指导优化的搜索空间， 自适应地调整搜索方向，不需要确定的规则。 遗传算法已被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关计算智能中的关键技术之一。 遗传算法是以达尔文的自然选择学说为基础发展起来的。自然选择学说包括以下三个方面：,1、遗传算法,（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。 （2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。 （3）生存斗争和适者生存：具有适应性
5、变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。,遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。 如：爱斯基摩人，,非洲原始部落,2、遗传算法的基本操作为： （1）复制（Reproduction Operator） 复制是从一个
6、旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。 复制操作可以通过随机方法来实现。首先产生01之间均匀分布的随机数，若某串的复制概率为40%，则当产生的随机数在0.401.0之间时，该串被复制，否则被淘汰。,（2）交叉（Crossover Operator） 复制操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。 交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。,交叉体现
7、了自然界中信息交换的思想。交叉有单点交叉、两点交叉、还有一致交叉、顺序交叉和周期交叉。单点交叉是最基本的方法，应用较广。它是指染色体切断点有一处，例：,（3）变异(Mutation Operator) 变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变为0，或由0变为1。,若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解
8、，必须采用变异操作。,17,设自变量 x 介于031，求其二次函数的最大值，即： max f(x) = x2, x 0, 31,3、遗传算法示例- f(x) = x2 极大值问题,当然，利用简单的代数运算，很容易求出该问题的解。现在改用遗传算法求解，遗传算法通常包括下述内容：,18,（1）编码 遗传算法首先要对实际问题进行编码，用字符串表达问题。这种字符串相当于遗传学中的染色体。每一代所产生的字符串个体总和称为群体。为了实现的方便，通常字符串长度固定，字符选0或1。 本例中，利用5位二进制数表示x值，采用随机产生的方法，假设得出拥有四个个体的初始群体，即：01101，11000，01000，1
9、0011。x值相应为13，24，8，19。,19,（2）计算适应度 衡量字符串（染色体）好坏的指标是适应度，它也就是遗传算法的目标函数。 本例中适应度比较简单，用x2计算。,表中还列出了当前适应度的总和f(xi)及平均值f，即： f(xi) = f(x1) + f(x2) + f(x3) + f(x4) = 1170 f = f(xi) /4 = 292.5(293) f(x1)/f=169/293=0.57679.,20,（2）计算适应度 表中第6列的 f(xi)/f 表示每个个体的相对适应度，它反映了个体之间的相对优劣性。如2号个体的 f(xi)/f 值最高（1.97），为优良个体，3号个
10、体最低（0.22），为不良个体。,21,（3）复制 为了将已有的群体变为下一代群体，遗传算法仿效进化论中“自然选择、适者生存”的原则，从旧群体中选择优良个体进行复制。选择的依据是个体适应度的大小，适应度大的个体接受复制，使之繁殖；适应度小的个体则删除掉，遭到淘汰。,22,（3）复制 在本例中，根据相对适应度的大小对个体进行取舍，2号个体性能最优，予以复制繁殖。3号个体性能最差，将它删除，使之死亡，表中的M表示传递给下一代的个体数目，其中2号个体占2个，3号个体为0，1号、4号个体保持为1个。,这样，就产生了下一代群体。,23,（3）复制,从表中的第4列可以看出，复制后产生的新一代群体的平均适应
11、度明显增加，由原来的293增加到421。造成平均适应度增加的原因有二： 1）淘汰原来最差的个体。使最小适应度由原来的64增加到169。 2）增加了优良个体（2号）的个数，使适应度累计值增加。,24,（4）交换,通过复制产生的新群体，其性能得到改善，然而它不能产生新的个体。为了产生新的个体，遗传算法仿照生物学中杂交的方法，对染色体（字符串）的某些部分进行交叉换位。被交换的母体都选自经过复制产生的新一代个体（优胜者）。,25,（4）交换,本例中，利用随机配对的方法，决定1号和2号个体、3号和4号个体分别交换，如表中第5列。再利用随机定位的方法，确定这两对母体交叉换位的位置分别从字符长度的第4位及第
12、3位开始。如：3号、4号个体从字符长度第3位开始交换。交换开始的位置称交换点。,26,（4）交换,从表中可以看出，交换后出现优异个体3号，其适应度高达729，大大高于交换前的最大值（576）。与此同时，平均适应度也从原来的421提高到439，说明交换后的群体正朝优良方向发展。,27,（5）突变,遗传算法模仿生物学中基因突变的方法，将个体字符串某位符号进行逆变，即由1变为0或由0变为1。例如，下式左侧的个体于第3位突变，得到新个体如右侧所示。,上述（2）（5）反复执行，直至得出满意的最优解。,由上可知，遗传算法参考生物中有关进化与遗传的过程，利用复制、交换、突变等操作，不断循环执行，逐渐逼近全局
13、最优解。,遗传算法中，个体是否进行突变以及在哪个部位突变，都由事先给定的概率决定。通常，突变概率很小，约为0.008，本例的第一代中就没有发生突变。,28,从数学角度看，遗传算法实质上是一种搜索寻优技术。它从某一初始群体出发，遵照一定的操作规则，不断迭代计算，逐步逼近最优解。这种搜索技术，有如下特点：,4、遗传算法的基本特征,从上述简单例子可以看出，遗传算法仿照生物进化和遗传的规律，利用复制、交换、突变等操作，使优胜者繁殖，劣败者消失，一代一代地重复同样的操作，最终找出最优解。,29,（1）智能式搜索 遗传算法的搜索策略，既不是盲目式的乱搜索，也不是穷举式的全面搜索，它是有指导的搜索。指导遗传
14、算法执行搜索的依据是适应度，也就是它的目标函数。利用适应度，使遗传算法逐步逼近目标值。 （2）渐进式优化 遗传算法利用复制、交换、突变等操作，使新一代的结果优越于旧一代，通过不断迭代，逐渐得出最优的结果，它是一种反复迭代的过程。,4、遗传算法的基本特征,30,（3）全局最优解 遗传算法由于采用交换、突变等操作，产生新的个体，扩大了搜索范围，使得搜索得到的优化结果是全局最优解而不是局部最优解。 （4）黑箱式结构 遗传算法根据所解决问题的特性，进行编码和选择适应度。一旦完成字符串和适应度的表达，其余的复制、交换、突变等操作都可按常规手续执行。个体的编码如同输入，适应度如同输出。因此遗传算法从某种意
15、义上讲是一种只考虑输入与输出关系的黑箱问题。,4、遗传算法的基本特征,31,（5）通用性强 传统的优化算法，需要将所解决的问题用数学式子表示，常常要求解该数学函数的一阶导数或二阶导数。采用遗传算法，只用编码及适应度表示问题，并不要求明确的数学方程及导数表达式。因此，遗传算法通用性强，可应用于离散问题及函数关系不明确的复杂问题，有人称遗传算法是一种框架型算法，它只有一些简单的原则要求，在实施过程中可以赋予更多的含义。 （6）并行式算法 遗传算法是从初始群体出发，经过复制、交换、突变等操作，产生一组新的群体。每次迭代计算，都是针对一组个体同时进行，而不是针对某个个体进行。因此，尽管遗传算法是一种搜
16、索算法，但是由于采用这种并行机理，搜索速度很高。这种并行式计算是遗传算法的一个重要特征。,4、遗传算法的基本特征,32,遗传算法受生物进化与遗传的启发，形成一种独特的优化方式，因此，遗传算法的运算原则常常与生物进化及遗传学说吻合，而且其术语也常常仿效生物学的术语。 遗传算法的运算基础是字符串，它就相当于生物学中的染色体。 字符串由一系列字符组成，每个字符都有特定的含义，反应所解决问题的某个特征，这就相当于基因，即染色体DNA的片段。 在进行交换、突变操作时，遗传算法只涉及到字符串某些片段，这就类似于遗传过程只涉及某些基因而不是整个染色体。,5、遗传算法的生物学含义,33,遗传学很注重等位基因，它是反映生物某一形态所对应的基因。在遗传算法的字符串中，每个字符都反映问题的某一特性，这也就相当于等位基因，至于等位基因的位置，也就相当于该字符在字符串中的位置。 在遗传学中，杂交产生的子代里显现出亲本的性状，称作显性性状，未显现出来的亲本性状叫作隐性性状。控制显性性状的基因是显性基因，用大写英文字
