《智能计算简介》PPT课件.ppt

,智能计算,智能计算,计算智能是以数据为基础，通过训练建立联系，进行问题求解，特点是：1、以分布式方式存储信息 2、以并行方式处理信息 3、具有自组织、自学习能力4、计算智能适用于于解决那些难以建立确定性数学逻辑模型，或不存在可形式化模型的问题,智能计算,计算智能以连接主义的思想为基础，有众多发展方向。人工神经网络（ANN）、遗传算法、蚁群算法、人工免疫算法等都可以包括在计算智能中。,遗传算法发展历史,进化计算的研究起源于20世纪50年代。1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。大约在同一时期：Rechenberg和Schwefel提出了进化策略。Fogel提出了进化规划。,遗传算法发展历史,1975年Holland出版了他的著名专著自然系统和人工系统的适应性该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schemata theory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong在论文遗传自适应系统的行为分析中把Holland的模式理论与他的计算使用结合起来。,遗传算法与自然进化的比较,自然界,染色体,基因,等位基因(allele),染色体位置(locus),基因型(genotype),表型(phenotype),遗传算法,字符串,字符,特征,特征值,字符串位置,结构,参数集,译码结构,新达尔文进化理论的主要论点,个体是基本的选择目标;随机过程在进化中起重大作用,遗传变异大部分是偶然现象;基因型变异大部分是重组的产物,部分是突变;逐渐进化可能与表型不连续有关;不是所有表型变化都是自然选择的必然结果;进化是在适应中变化的,形式多样,不仅是基因的变化;选择是概率型的,而不是决定型的。,进化计算的三大主流板块,Holland提出的遗传算法(Genetic Algorithm)。Rechenberg和Schwefel提出的进化策略(Evolutionary Strategies)。Fogel提出的进化规划(Evolutionary Programming)，又称为进化程序设计。,进化计算的三大主流板块,三种算法既有许多相似之处，同时也有很大的不同 进化规划和进化策略都把 变异作为主要的搜索算子，而在标准遗传算法中，变异只处于次要地位 交叉在标准遗传算法中起着重要作用，而在进化规划中被完全省去，在进化策略中与自适应结合在一起使用非常重要；标准遗传算法和进化规划都强调 随机选择机制的重要性，而从进化策略的角度看，选择是完全确定的，没有合理的根据表明随机选择原则的重要性；进化规划和进化策略确定地把某些个体排除在被选择复制之外，而标准遗传算法一般对每个个体都指定一个非零选择概率。,遗传算法的基础：孟德尔遗传学,在孟德尔遗传学中，基因型被详细模型化，而表型 和环境被忽略。简单起见，假设一个基因具有n 等位基因a1,an。二倍基因型以元组(ai,aj)为特征。我们定义 pij 为总群体中基因型(ai,aj)的频度。假设基因型与表型相等。质量函数给每个表型赋值。q(ai,aj)=qij qij 可以被解释为出生率减去死亡率,遗传算法的基础：孟德尔遗传学,假设 pi,j是下一代表型(ai,aj)的频度。然后达尔文选择根据选择方程调整表型的分布:,是群体的平均适应度。,遗传算法的基础：孟德尔遗传学,设 pi 是群体中等位基因的频率。如果 pi,j=pi pj那么，我们得到在 GS中的一个选择方程为,遗传算法的基础：孟德尔遗传学,这个离散的选择方程可以用连续方程近似:,如果 qi,j=qj,i,那么,遗传算法的基础：孟德尔遗传学,可以证明:,这个结果称作菲希尔(Fisher)基本定理。它说明平均适应度随适应度的差别呈正比例增加。实际上，全部可能的基因型仅有一部分实现。这就是遗传操纵子探索基因型空间的任务，其个体数目相当小。这些操纵子是群体遗传变异性的来源。最重要的操纵子是突变和重组。,遗传算法思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法(以字符串表示状态空间)。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。,遗传算法,遗传算法的特点,特点：通用鲁棒次优解、满意解遗传算法能解决的问题：优化高度复杂的非线性问题,遗传算法,遗传算法先将搜索结构编码为字符串形式,每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。,遗传算法,与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。常用的遗传算子有复制、杂交、变异和反转。,遗传算法与传统优化算法的主要不同,遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;遗传算法不是从单个点,而是在群体中从一个点开始搜索;遗传算法利用适应值信息,无需导数或其它辅助信息;遗传算法利用概率转移规则,而非确定性规则。,遗传算法的准备工作,确定表示方案;确定适应值的度量;确定控制该算法的参数和变量;确定怎样指定结果及程序运行结束的标准。,基本遗传算法,基本遗传算法(Simple Genetic Algorithm:SGA)又称为简单遗传算法，只使用选择算子、交叉算子和变异算子这三种基本的遗传算子。其遗传操作简单、容易理解，是其它遗传算法的雏形和基础。基本遗传算法的构成要素：1、染色体编码方法：首先必须对问题的解空间进行编码，使之能用遗传算法进行操作。较常用的是二进制编码方法，现在使用非二进制编码的也逐渐增多。2、适应度函数（fitness function，又称为适应值适值函数）用来评价一个染色体的好坏。,基本遗传算法的构成要素,3、遗传算子 选择算子(selection)：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择。交叉算子(crossover)：又称为杂交算子。将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。如使用单点一致交叉。变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值。,基本遗传算法的构成要素,4、运行参数N：群体大小，即群体中包含的个体的数量。T：遗传算法终止的进化代数。Pc：交叉概率，一般取为 0.40.99。Pm：变异概率，一般取为 0.00010.1。,基本遗传算法,随机产生一个由固定长度字符串组成的初始群体;对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：计算群体中的每个个体字符串的适应值;应用下述三种操作(至少前两种)来产生新的群体:复制:把现有的个体字符串复制到新的群体中。杂交:通过遗传重组随机选择两个现有的子字符串,产生新的字符串。变异:将现有字符串中某一位的字符随机变异。把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解(或近似解)。,基本遗传算法流程图,概率地选择遗传操作,根据适应值选择一个个体,完成交叉,i:=i+1,i:=i+1,复制个体,p(r)选择,（接上页）,基于适应值选择两个个体,把新的两个孩子加到群体中,p(c)交叉,变异p(m),把新的孩子加入到群体中,完成变异,根据适应值选择一个个体,把变异后个体加入到群体中,1,轮盘式选择,首先计算每个个体 i 被选中的概率然后根据概率的大小将将圆盘分为 n个扇形，每个扇形的大小为。选择时转动轮盘，参考点r落到扇形i则选择个体i。,单点一致交叉,首先以概率pc从种群中随机地选择两个个体p1、p2。在1,2,.,l内随机选择一个数i,作为交叉的位置，称为交叉点。然后将两个个体交叉点后面的部分交换。例如：0110 101100 0110 011001 1100 011001 1100 101100,一致变异,以概率pm对种群中所有个体的每一位进行变异。对于个体pi的第j位，在0,1的范围内随机地生成一个数r,如果 r pm,则对第j位取反，否则保持第j位不变。,遗传算法举例,问题：求（1）编码：此时取均长为5，每个染色体（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体：编码：01101，11000，01000，10011 解码：13 24 8 19 适应度：169 576 64 361（3）适应度评价：,（4）选择：选择概率 个体：01101，11000，01000，10011 适应度：169 576 64 361 选择概率：0.14 0.49 0.06 0.31选择结果：01101，11000，11000，10011（5）交叉操作：发生交叉的概率较大 哪两个个体配对交叉是随机的 交叉点位置的选取是随机的（单点交叉）0110 1 01100 11 000 11 011 1100 0 11001 10 011 10 000,（6）变异：发生变异的概率很小（7）新群体的产生：保留上一代最优个体，一般为10%左右，至少1个 用新个体取代旧个体，随机取代或择优取代。11000，11011，11001，10011（8）重复上述操作：说明：GA的终止条件一般人为设置；GA只能求次优解或满意解。分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解择优取代有问题。若随机的将个体01101选入新群体中，有可能找到最优解。,遗传算法的理论基础,11.5.1 模式的定义遗传算法的理论基础是遗传算法的二进制表达式及模式的含义。模式是能对染色体之间的相似性进行解释的模板。定义1 设GA的个体,记集合则称 为一个模式，其中是通配符。即模式(schema)是含有通配符(*)的一类字符串的通式表达。每个“*”可以取“1”或者“0”。,模式举例,模式*10101110与以下两个字符串匹配：010101110 110101110而模式*1010110与以下四个字符串匹配：010100110 010101110110100110 110101110,模式的定义,定义2 一个模式s的阶是出现在模式中的“0”和“1”的数目，记为o(s)。如：模式“0*”的阶为1，模式“10*1*”的阶为3。定义3 一个模式s的长度是出现在模式中第一个确定位置和最后一个确定位置之间的距离，记为。如：模式“01*”的长度为1，模式“0*1*”的长度为3。,模式定理,假定在给定的时间步t,一个特定的模式s在群体P(t)中包含有m个代表串，记为m=m(s,t)。首先，我们暂不考虑交叉和变异操作。每个串根据适应值的大小获得不同的复制概率。串i的复制概率为：,（1）,模式定理,则在群体P(t+1)中，模式s的代表串的数量的期望值为：,其中，表示模式s在t时刻的所有代表串的适应值的均值，称为模式s的适应值。,（2）,模式定理,若记P(t)中所有个体的适应值的平均值为：,（3）,则(2)式可以表示为：,模式定理,(3)式表明，模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值。即：适应值高于群体平均值的模式在下一代的代表串数目将会增加，而适应值低于群体平均值的模式在下一代的代表串数目将会减少。假设模式的适应值为,其中c是一个常数，则(3)式可写为：,模式定理,（4）,上式表明，在平均适应值之上（之下）的模式，将会按指数增长（衰减）的方式被复制。,模式定理,复制的结果并没有生成新的模式。因而，为了探索搜索空间中的未搜索部分，需要利用交叉和变异操作。下面先探索交叉对模式的影响。模式s1=“*1*0”和s2=“*10*”交叉会改变模式的一部分，模式的长度越长，被破坏的概率越大。,模式定理,假定模式s在交叉后不被破坏的概率为ps，则：若交叉概率为pc,则s不被破坏的概率为,模式定理,（5）,所以，再考虑交叉时，(3)式可表示为最后，考虑变异算子对模式的影响。变异算子以概率pm随机地改变个体某一位的值。只有当o(s)个确定位的值不被破坏时，模式s才不被破坏。,模式定理,模式s在变异后不被破坏的概率：Pm1,可近似地表示为,模式定理,（6）,因此，考虑交叉和变异时，(3)式可表示为,模式定理,由(6)我们得到一个重要的定理。定理1 模式定理(Schema Theorem)适应值在群体适应值之上的，长度较短的，低阶的模式在GA的迭代中将按指数增长方式被复制。,积木块假设,Holland和Goldberg在模式定理的基础上提出了“积木块假设”(Building Block Hypothesis):低阶、长度较短、高于平均适应度的模式(积木块)在遗传算子的作用下，相互结合，能生成高阶、长度较长、适应度较高的模式，并得到全局最优解。,人工免疫算法,免疫算法的思想来自模拟人体的免疫系统免疫系统通过一套复杂的机制来重组基因,以产生抗体对付入侵的抗原,达到消灭抗原的目的为了有效地提供防御功能,免疫系统必须进行模式识别,把自身的分子和细胞与抗原区分开来除了具有识别能力之外,免疫系统与其它低级生物防御系统的区别在于它能够学习,并且有记忆能力因为上述特点,免疫系统对同一抗原的防御反应,第二次比第一次来得更快、更强烈,人工免疫算法,上述特点使得免疫算法有不同于其它算法的附加优化步骤 1)计算亲和性 2)计算期望值 3)构造记忆单元,人工免疫算法,免疫算法模仿了人体的免疫系统,并从体细胞理论和网络理论中得到启发,实现了类似于免疫系统的自我调节功能和生成不同抗体的功能免疫算法具有随机优化方法所具有的优点，但免疫算法与其它随机优化算法(如遗传算法等)之间有如下的区别:1)在记忆单元基础上运行,确保快速收敛于全局最优解 2)它有计算亲和性的程序,反映了真实的免疫系统的多样性3)它通过促进或抑制抗体的产生,体现了免疫反应的自我调节功能,人工免疫算法,上述特点使得免疫算法有不同于其它算法的附加优化步骤 1)计算亲和性 2)计算期望值 3)构造记忆单元,人工免疫算法,免疫系统中的抗原和抗体分别对应于优化问题的目标函数和可能解免疫算法的亲和性有两种形式:一种形式说明了抗体和抗原之间的关系,即解和目标的匹配程度;另一种形式解释了抗体之间的关系,这个独有的特性保证了免疫算法具有多样性计算期望值的作用是控制适用于抗原(目标)的相同抗体的过多产生用一组记忆单元保存用于防御抗原的一组抗体(优化问题的候选解),人工免疫算法,人工免疫算法,刺激和抑制抗体的产生通过计算抗体的期望值实现,期望值低的抗体将受到抑制，高期望值和低密度的抗体得到刺激为了有利于优化过程的进行,某些与抗原有较高亲和性的抗体也必须受到抑制由于高亲和性的抗体得到促进,而高密度的抗体受到抑制,体现了控制机制的多样性,人工免疫算法,更新记忆库时，通常将与抗原的亲和性高的抗体加入到记忆单元中 由于记忆单元数目有限,所以在记忆单元中用新加入的抗体取代与其亲和性最高的原有抗体通过重复的优化过程和记忆训练,能够很快得到最优解 因为对于曾经出现过的抗原,免疫算法产生相应抗体的速度比以前更快,