高级人工智能计算智能.pptx
- 文档编号:18715584
- 上传时间:2023-10-17
- 格式:PPTX
- 页数:82
- 大小:621.96KB
高级人工智能计算智能.pptx
《高级人工智能计算智能.pptx》由会员分享,可在线阅读,更多相关《高级人工智能计算智能.pptx(82页珍藏版)》请在冰点文库上搜索。
人工智能,计算智能,2016年秋季,罗平,本章内容,概述演化计算模糊计算,本章内容,概述演化计算模糊计算,计算智能(ComputationalIntelligence,CI)计算智能是在神经网络(NeuralNetworks,NN)、演化计算(EvolutionaryComputation,EC)及模糊系统(FuzzySystem,FS)这3个领域发展相对成熟的基础上形成的一个统一的学科概念。
什么是计算智能,神经网络是一种对人类智能的结构模拟方法,它是通过对大量人工神经元的广泛并行互联,构造人工神经网络系统去模拟生物神经系统的智能机理。
演化计算是一种对人类智能的演化模拟方法,它是通过对生物遗传和演化过程的认识,用进化算法去模拟人类智能的进化规律的。
模糊计算是一种对人类智能的逻辑模拟方法,它是通过对人类处理模糊现象的认知能力的认识,用模糊逻辑去模拟人类的智能行为的。
本章内容,概述演化计算模糊计算,7,演化计算(EvolutionaryComputation,EC):
在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术和计算模型。
思想源于生物遗传学和适者生存的自然规律基于达尔文(Darwin)的进化论和孟德尔(Mendel)的遗传变异理论典型代表:
遗传算法(GeneticAlgorithm,GA)进化策略(EvolutionaryStrategy,ES)进化规划(EvolutionaryProgramming,EP)遗传规划(GeneticProgramming,GP),演化计算,达尔文的自然选择学说是一种被人们广泛接受的生物进化学说:
生物要生存下去,就必须进行生存斗争。
具有有利变异的个体容易存活下来,并且有更多的机会将有利变异传给后代;具有不利变异的个体就容易被淘汰,产生后代的机会也少的多。
适者生存,不适者淘汰:
自然选择。
遗传和变异是决定生物进化的内在因素。
(相对稳定+新的物种),演化计算,9,孟德尔基因遗传原理遗传以密码方式存在细胞中,并以基因形式包含在染色体内。
每个基因有特殊的位置并控制某种特殊性质;所以,每个基因产生的个体对环境具有某种适应性。
基因突变和基因杂交可产生更适应于环境的后代。
经过存优去劣的自然淘汰,适应性高的基因结构得以保存下来。
演化计算,10,演化计算:
一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。
演化规则:
“物竞天择、适者生存”演化操作:
繁殖(Reproduction)变异(Mutation)竞争(Competition)选择(Selection),演化计算及其生物学基础,遗传算法的基本思想是从初始种群出发,采用优胜劣汰、适者生存的自然法则选择个体,并通过杂交、变异来产生新一代种群,如此逐代进化,直到满足目标为止基本概念:
种群(Population):
多个备选解的集合。
个体(Individual):
种群中的单个元素,通常由一个用于描述其基本遗传结构的数据结构来表示。
例如,长度为L的0、1串染色体(Chromos):
对个体仿照基因编码进行编码后所得到的编码串。
染色体中的每一位称为基因,染色体上由若干个基因构成的一个有效信息段称为基因组。
遗传算法,基本概念:
适应度(Fitness)函数:
用来对种群中各个个体的环境适应性进行度量的函数,函数值是遗传算法实现优胜劣汰的主要依据遗传操作(GeneticOperator):
作用于种群而产生新的种群的操作。
选择(Selection)交叉(Cross-over)变异(Mutation),遗传算法,遗传算法主要由染色体编码、初始种群设定、适应度函数设定、遗传操作设计等几大部分所组成,算法基本步骤:
选择编码策略,将问题搜索空间中每个可能的点用相应的编码策略表示出来,即形成染色体;定义遗传策略,包括种群规模N,交叉、变异方法,以及选择概率Pr、交叉概率Pc、变异概率Pm等遗传参数;令t=0,随机选择N个染色体初始化种群P(0);定义适应度函数f;计算P(t)中每个染色体的适应值;t=t+1;运用选择算子,从P(t-1)中得到P(t);对P(t)中的每个染色体,按概率Pc参与交叉;对染色体中的基因,以概率Pm参与变异运算;判断群体性能是否满足预先设定的终止标准,若不满足返回(5)。
遗传算法,遗传算法,遗传算法生物进化适应函数环境适应函数值适应性适应函数值最大的解被保留的概率最大适者生存问题的一个解个体解的编码染色体编码的元素基因被选定的一组解群体根据适应函数选择的一组解(以编码形式表示)种群以一定的方式由双亲产生后代的过程繁殖编码的某些分量发生变化的过程变异,遗传算法与生物进化之间对应关系,二进制编码(Binaryencoding)二进制编码是将原问题的结构变换为染色体的位串结构。
假设某一参数的取值范围是A,B,A来表示。
优点:
易于理解和实现,可表示的模式数最多主要缺点:
海明悬崖。
例如,7和8的二进制数分别为0111和1000,当算法从7改进到8时,就必须改变所有的位。
遗传编码,格雷编码(Grayencoding)要求两个连续整数的编码之间只能有一个码位不同,其余码位都是完全相同的。
有效地解决了海明悬崖问题。
基本原理:
二进制码-格雷码(编码):
从最右边一位起,依次将每一位与左边一位异或(XOR),作为对应格雷码该位的值,最左边一位不变;格雷码-二进制码(解码):
从左边第二位起,将每位与左边一位解码后的值异或,作为该位解码后的值,最左边一位依然不变。
遗传编码,符号编码(Symbolencoding)个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。
由于是回路,记wn+1=w1。
它其实是1,n的一个循环排列。
要注意w1,w2,wn是互不相同的。
遗传编码,例如,对于TSP问题,采用符号编码方法,按一条回路中城市的次序进行编码,一般情况是从城市w1开始,依次经过城市w2,wn,最后回到城市w1,我们就有如下编码表示:
适应度函数是一个用于对个体的适应性进行度量的函数。
个体的适应度值越大,它被遗传到下一代种群中的概率越大常用的适应度函数原始适应度函数:
直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函数。
例如:
求最大值时,f(x)即为x的原始适应度函数。
优点:
能够直接反映出待求解问题的最初求解目标,缺点:
有可能出现适应度值为负的情况,适应度函数,TSP的目标是路径总长度为最短,路径总长度可作为TSP问题的适应度函数:
适应度函数,标准适应度函数在遗传算法中,一般要求适应度函数非负,并其适应度值越大越好。
这就往往需要对原始适应函数进行某种变换,将其转换为标准的度量方式,以满足进化操作的要求,这样所得到的适应度函数被称为标准适应度函数fNormal(x)。
例:
对极小化问题,其标准适应度函数可定义为其中,fmax(x)是原始适应函数f(x)的一个上界。
如果fmax(x)未知,则可用当前代或到目前为止各演化代中的f(x)的最大值来代替。
fmax(x)是会随着进化代数的增加而不断变化的。
适应度函数,极大化问题对极大化问题,其标准适应度函数可定义为其中,fmin(x)是原始适应函数f(x)的一个下界。
如果fmin(x)未知,则可用当前代或到目前为止各演化代中的f(x)的最小值来代替。
适应度函数,遗传算法中的基本遗传操作包括选择、交叉和变异。
选择(selection)操作:
根据选择概率按某种策略从当前种群中挑选出一定数目的个体,使它们能够有更多的机会被遗传到下一代中常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。
比例选择基本思想是:
各个个体被选中的概率与其适应度大小成正比。
基本遗传操作,轮盘赌选择个体被选中的概率取决于该个体的相对适应度。
而相对适应度的定义为:
其中,P(xi)是个体xi的相对适应度,即个体xi被选中的概率;f(xi)是个体xi的原始适应度;是种群的累加适应度。
轮盘赌选择算法的基本思想是:
根据每个个体的选择概率P(xi)将一个圆盘分成N个扇区,其中第i个扇区的中心角为:
并再设立一个固定指针。
当进行选择时,可以假想转动圆盘,若圆盘静止时指针指向第i个扇区,则选择个体i。
基本遗传操作,从统计角度看,个体的适应度值越大,其对应的扇区的面积越大,被选中的可能性也越大。
这种方法有点类似于发放奖品使用的轮盘,并带有某种赌博的意思,因此亦被称为轮盘赌选择。
基本遗传操作,交叉(crossover)操作:
按照某种方式对选择的父代个体的染色体的部分基因进行交配重组,从而形成新的个体。
常见的交叉操作:
二进制交叉:
二进制编码情况下所采用的交叉操作,它主要包括:
单点交叉两点交叉多点交叉均匀交叉,基本遗传操作,单点交叉先在两个父代个体的编码串中随机设定一个交叉点,然后对这两个父代个体交叉点前面或后面部分的基因进行交换,并生成子代中的两个新的个体。
假设两个父代的个体串分别是:
X=x1x2xkxk+1xnY=y1y2ykyk+1yn随机选择第k位为交叉点,交叉后生成的两个新的个体是:
X=x1x2xkyk+1ynY=y1y2ykxk+1xn设有两个父代的个体串A=001101和B=110010,若随机交叉点为4,则交叉后生成的两个新的个体是:
A=001111B=110000,基本遗传操作,两点交叉先在两个父代个体的编码串中随机设定两个交叉点,然后再按这两个交叉点进行部分基因交换,生成子代中的两个新的个体。
假设两个父代的个体串分别是:
X=x1x2xixjxnY=y1y2yiyj,yn随机设定第i、j位为两个交叉点(其中ijn),交叉后生成的两个新的个体是:
X=x1x2xiyi+1yjxj+1xnY=y1y2yixi+1xjyj+1yn例:
设有两个父代的个体串A=001101和B=110010,若随机交叉点为3和5,则交叉后的两个新的个体是:
A=001011B=110100,基本遗传操作,均匀交叉先随机生成一个与父串具有相同长度的二进制串(交叉模版),然后再利用该模版对两个父串进行交叉,即将模版中1对应的位进行交换,而0对应的位不交换,依此生成子代中的两个新的个体。
事实上,这种方法对父串中的每一位都是以相同的概率随机进行交叉的。
例5.10设有两个父代的个体串A=001101和B=110010,若随机生成的模版T=010011,则交叉后的两个新的个体是A=011010和B=100101。
即A:
001101B:
110010T:
010011A:
011110B:
100001,基本遗传操作,实值交叉在实数编码情况下所采用的交叉操作,主要包括离散交叉和算术交叉部分离散交叉:
先在两个父代个体的编码向量中随机选择一部分分量,然后对这部分分量进行交换,生成子代中的两个新的个体。
整体交叉:
对两个父代个体的编码向量中的所有分量,都以1/2的概率进行交换,从而生成子代中的两个新的个体。
假设两个父代个体的n维实向量分别是X=x1x2xixkxn和Y=y1y2yiykyn,若随机选择对第k个分量以后的所有分量进行交换,则生成的两个新的个体向量是:
X=x1x2xkyk+1ynY=y1y2ykxk+1xn,基本遗传操作,变异(Mutation)操作:
对选中个体的染色体中的某些基因进行变动,以形成新的个体。
遗传算法中的变异操作增加了算法的局部随机搜索能力,从而可以维持种群的多样性。
变异虽然可以带来群体的多样性,但因其具有很强的破坏性,因此一般通过一个很小的变异概率来控制它的使用。
根据个体编码方式的不同,变异操作可分为二进制变异和实值变异两种类型。
二进制变异先随机地产生一个变异位,然后将该变异位置上的基因值由“0”变为“1”,或由“1”变为“0”,产生一个新的个体。
例5.12设变异前的个体为A=001101,若随机产生的变异位置是2,则该个体的第2位由“0”变为“1”。
变异后的新的个体是A=011101。
基本遗传操作,实值变异用另外一个在规定范围内的随机实数去替换原变异位置上的基因值,产生一个新的个体。
最常用的实值变异操作有:
基于次序的变异:
先随机地产生两个变异位置,然后交换这两个变异位置上的基因。
例:
设选中的个体向量D=201216192130,若随机产生的两个变异位置分别时2和4,则变异后的新的个体向量是:
D=201916122130,基本遗传操作,精英主义(Elitism)仅仅从产生的子代中选择基因去构造新的种群可能会丢失掉上一代种群中的很多信息。
也就是说当利用交叉和变异产生新的一代时,我们有很大的可能把在某个中间步骤中得到的最优解丢失。
使用精英主义(Elitism)方法,在每一次产生新的一代时,我们首先把当前最优解原封不动的复制到新的一代中,其他步骤不变。
这样任何时刻产生的一个最优解都可以存活到遗传算法结束。
上述各种算子的实现是多种多样的,而且许多新的算子正在不断地提出,以改进GA某些性能。
基本遗传操作,例5.15用遗传算法求函数f(x)=x2的最大值,其中x为0,31间的整数。
解:
(1)编码由于x的定义域是区间0,31上的整数,由5位二进制数即可全部表示。
因此,可采用二进制编码方法,其编码串的长度为5。
例如,用二进制串00000来表示x=0,11111来表示x=31等。
其中的0和1为基因值。
(2)生成初始种群若假设给定的种群规模N=4,则可用4个随机生成的长度为5的二进制串作为初始种群。
再假设随机生成的初始种群(即第0代种群)为:
s01=01101s02=11001s03=01000s04=10010,遗传算法应用,(3)计算适应度要计算个体的适应度,首先应该定义适应度函数。
由于本例是求f(x)的最大值,因此可直接用f(x)来作为适应度函数。
即:
f(s)=f(x)其中的二进制串s对应着变量x的值。
根据此函数,初始种群中各个个体的适应值及其所占比例为。
可以看出,在4个个体中S02的适应值最大,是当前最佳个体。
遗传算法应用,(4)选择操作假设采用轮盘赌方式选择个体,且依次生成的4个随机数(相当于轮盘上指针所指的数)为0.85、0.32、0.12和0.46,经选择后得到的新的种群为:
S01=10010S02=11001S03=01101S04=11001其中,染色体11001在种群中出现了2次,而原染色体01000则因适应值太小而被淘汰,14%53%5%27%-|-|-|-*-|个体1个体2个体30.85个体4随机数为0.85落在了个体4的端内.本次选择了个体4.,遗传算法应用,(5)交叉假设交叉概率Pi为50%,则种群中只有1/2的染色体参与交叉。
若规定种群中的染色体按顺序两两配对交叉,且有S01与S02交叉,S03与S04不交叉,则交叉情况为:
可见,经交叉后得到的新的种群为:
S01=10001S02=11010S03=01101S04=11001,遗传算法应用,(6)变异变异概率Pm一般都很小,假设本次循环中没有发生变异,则变异前的种群即为进化后所得到的第1代种群。
即:
S11=10001S12=11010S13=01101S14=11001然后,对第1代种群重复上述(4)-(6)的操作,选择情况如下:
其中若假设按轮盘赌选择时依次生成的4个随机数为0.14、0.51、0.24和0.82,经选择后得到的新的种群为:
S11=10001S12=11010S13=11010S14=11001可以看出,染色体11010被选择了2次,而原染色体01101则因适应值太小而被淘汰。
遗传算法应用,对第1代种群,其交叉情况:
可见,经杂交后得到的新的种群为:
S11=10010S12=11001S13=11001S14=11010可以看出,第3位基因均为0,已经不可能通过交配达到最优解。
这种过早陷入局部最优解的现象称为早熟。
为解决这一问题,需要采用变异操作。
遗传算法应用,对第1代种群,其变异情况:
它是通过对S14的第3位的变异来实现的。
变异后所得到的第2代种群为:
S21=10010S22=11001S23=11001S24=11110接着,再对第2代种群同样重复上述(4)-(6)的操作:
遗传算法应用,对第2代种群,同样重复上述(4)-(6)的操作。
其中若假设按轮盘赌选择时依次生成的4个随机数为0.42、0.15、0.59和0.91,经选择后得到的新的种群为:
S21=11001S22=10010S23=11001S24=11110,遗传算法应用,对第2代种群,其交叉情况:
这时,函数的最大值已经出现,其对应的染色体为11111,经解码后可知问题的最优解是在点x=31处。
求解过程结束。
遗传算法应用,例子:
8皇后问题,目标:
任何一个皇后都不会攻击到其他的皇后(皇后可以攻击和它在同一行、同一列或同一对角线上的皇后)适应度函数取作可以彼此攻击的皇后对的数目(忽略障碍),8皇后的例子,其中每个状态用一个长度为8的字符串来表示,适应度函数取作不相互攻击的皇后对数目。
问题表示:
从k个随机生成的状态(种群)开始每个个体用一个有限长度的字符串表示-通常用0,1表示,例子:
8皇后问题,通过把两个父状态结合来生成后继,例子:
8皇后问题,遗传算法特点自组织、自适应和自学习性概率转移准则,非确定性规则确定进化方案后,算法将利用进化过程中得到的信息自行组织搜索;基于自然的选择策略,优胜劣汰;遗传算法很快就能找到良好的解,即使是在很复杂的解空间中采用随机方法进行最优解搜索,选择体现了向最优解迫近交叉体现了最优解的产生,变异体现了全局最优解的复盖本质并行性-群体搜索算法本身非常适合大规模并行,各种群分别独立进化,不需要相互间交换信息;二是可以同时搜索解空间的多个区域并相互间交流信息,使得演化计算能以较少的计算获得较大的收益。
遗传算法特点,不需要其他知识,只需要影响搜索方向的目标函数和相应的适应度函数对待求解问题的指标函数没有什么特殊的要求,如不要求连续性、导数存在、单峰值等假设容易形成通用算法程序遗传算法不能解决那些“大海捞针”的问题,所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题,遗传算法对这类问题无法找到收敛的路径。
应用广泛遗传算法擅长解决的问题是全局最优化问题,例如,解决时间表安排问题就是它的一个特长,很多安排时间表的软件都使用遗传算法,遗传算法特点,理论上证明算法的收敛性很困难多用于解决实际问题汽车设计,包括材料选择、多目标汽车组件设计、减轻重量等。
机电系统设计。
分布计算机网络的拓扑结构。
电路设计,此类用途的遗传算法叫做进化电路。
移动通讯优化结构。
煤气管道的最优控制、通信网络链接长度的优化问题、铁路运输计划优化、喷气式收音机涡轮机的设计、VLSI版面设计、键盘排列优化抓到老鼠的猫都是好猫,本章内容,概述演化计算模糊计算,模糊计算,美国加州大学扎德(Zadeh)教授于1965年提出的模糊集合与模糊逻辑理论是模糊计算的数学基础。
发表了文章模糊集(Fuzzysets,InformationandControl,8,338-353)主要用来处理现实世界中因模糊而引起的不确定性。
模糊理论已经在推理、控制、决策等方面得到了非常广泛的应用,模糊计算,“模糊不是罪过”:
模糊”糊涂”,“朦胧”,”傻冒”,“痴呆”取得精确数据不可能或很困难例如:
粒种子肯定不能叫一堆,粒也不是,粒也不是那么多少粒种子叫一堆呢?
适当的界限在哪里呢?
我们能否说粒种子不叫一堆,而粒种子叫一堆呢?
没有必要获取精确数据例如:
要从一片西瓜地里找出一个最大的西瓜,那是件很麻烦的事。
必须把西瓜地里所有的西瓜都找出来,再比较一下,才知道哪个西瓜最大。
西瓜越多,工作量就越大。
如果按通常说的,到西瓜地里去找一个较大的西瓜,这时精确的问题就转化成模糊的问题,反而容易多了。
由此可见,适当的模糊能使问题得到简化。
清晰的概念:
对象是否属于这个概念是明确的。
例如;人、自然数、正方形。
模糊性的概念:
对象从属的界限是模糊的,随判断人的思维而定“最大的”与“较大的”都是有区别的两个概念。
但是它们的区别都是逐渐的,而不是突变的,两者之间并不存在明确的界限一个人很高或很胖,但是究竟多少厘米才算高,多少千克才算胖呢?
高和胖都很模糊。
饭什么时候才算熟了?
衣服什么样才能算洗干净?
例如:
美不美?
早不早?
便宜不便宜?
在客观世界中,上述的模糊概念要比清晰概念多得多。
模糊计算,要使计算机能够模仿人脑,对复杂系统进行识别和判断,出路何在?
1965年扎德(Zadeh)教授开创了对“模糊数学”的研究。
他认为数学是可以模糊的,主张从精度方面“后退”一步。
他提出用隶属函数使模糊概念数学化。
例如“年轻”和“年老”这两个模糊概念。
扎德教授本人根据统计资料,拟合了这两个概念的隶属函数图象。
图中横坐标表示年龄,纵坐标表示隶属程度。
模糊计算,定义设U是给定论域,是把任意uU映射为0,1上某个实值的函数,即:
U0,1则称为定义在U上的一个隶属函数,由(对所有)所构成的集合F称为U上的一个模糊集,称为u对F的隶属度。
模糊集F完全是由隶属函数来刻画的,把U中的每一个元素u都映射为0,1上的一个值。
的值表示u隶属于F的程度,其值越大,表示u隶属于F的程度越高。
当仅取0和1时,模糊集F便退化为一个普通集合。
模糊集的定义,55,例5.15设论域U=20,30,40,50,60给出的是年龄,请确定一个刻画模糊概念“年轻”的模糊集F。
解:
由于模糊集是用其隶属函数来刻画的,因此需要先求出描述模糊概念“青年”的隶属函数。
假设对论域U中的元素,其隶属函数值分别为:
则可得到刻画模糊概念“年轻”的模糊集F=1,0.8,0.4,0.1,0,模糊集的定义,随机与模糊:
是否与多少,模糊性:
事件发生的程度,而不是一个事件是否发生.随机性:
描述事件发生的不确定性,即,一个事件发生与否.,离散且为有限论域的表示方法设论域U=u1,u2,un为离散论域,则其模糊集可表示为:
F=,为了能够表示出论域中的元素与其隶属度之间的对应关系,扎德引入了一种模糊集的表示方式:
先为论域中的每个元素都标上其隶属度,然后再用“+”号把它们连接起来,即也可写其中,为ui对F的隶属度;“/ui”不是相除关系,只是一个记号;“+”也不是算术意义上的加,只是一个连接符号。
模糊集的表示,在这种表示方法中,当某个ui对F的隶属度=0时,可省略不写。
例如,模糊集F可表示为:
F=1/20+0.8/30+0.6/40+0.2/50有时,模糊集也可写成如下两种形式:
其中,前一种称为单点形式,后一种称为序偶形式。
模糊集的表示,连续论域的表示方法如果论域是连续的,则其模糊集可用一个实函数来表示。
例如,扎德以年龄为论域,取U=0,100,给出了“年轻”与“年老”这两的模糊概念的隶属函数一般表示方法不管论域U是有限的还是无限的,是连续的还是离散的,扎德又给出了一种类似于积分的一般表示形式:
这里的记号不是数学中的积分符号,也不是求和,只是表示论域中各元素与其隶属度对应关系的总括。
模糊集的表示,定义设F、G分别是U上的两个模糊集,对任意uU,都有成立,则称F等于G,记为F=G。
定义设F、G分别是U上的两个模糊集,对任意uU,都有成立,则称F包含G,记为FG。
模糊集的运算,定义设F、G分别是U上的两个模糊集,则FG、FG分别称为F与G的并集、交集,它们的隶属函数分别为:
定义设F为U上的模糊集,称F为F的补集,其隶属函数为:
模糊集的运算,62,例5.16设U=1,2,3,F和G分别是U上的两个模糊集,即F=小=1/1+0.6/2+0.1/3G=大=0.1/1+0.6/2+1/3则FG=(10.1)/1+(0.60.6)/2+(0.11)/3=1/1+0.6/1+1/3FG=(10.1)/1+(0.60.6)/2+(0.11)=0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高级 人工智能 计算 智能