演化计算专题讲座精.ppt

《演化计算专题讲座精.ppt》由会员分享，可在线阅读，更多相关《演化计算专题讲座精.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、演化计算专题讲座第1页，本讲稿共73页一、可查阅的书籍1、美Z.Michalewicz著.周家驹,何险峰等译,科学出版社,2000年.2.日玄光男,程润伟著.汪定伟,唐加福黄敏译.,科学出版社,2000年.3.张文修 梁怡编著，遗传算法的数学基础，西安交通大学出版社，2000年.4.李敏强 等著，遗传算法的基本理论与应用，科学出版社，2002年。二.网上可查询的资料1.武汉大学校园网电子资源(1).中国期刊网关键词:遗传算法,进化算法(2)IEEE/IEE Electronic libraryKey word:Evolutionary Computation/Evolutionary algo

2、rithm Journals:IEEE Transactions on Evolutionary Computation，Evolutionary Computation，European Journal of Operational Research,Theoretical Computer ScienceInternational Conference：CEC,GECCO,PPSN,FOGA2.宽带网参考文献第2页，本讲稿共73页引言引言 什么是智能计算什么是智能计算智能计算（Intelligent Computing,IC)或 计算智能(Computational Intelligenc

3、e,CI)：主要指能解决大规模的复杂实际问题的有重大影响的几类关键技术，或者说当今国际上最流行、最热门的几种计算方法。其中有：（1）演化计算（Evolutionary Computation)：在微观或宏观两个不同层次上模仿生物的演化过程。（2）神经网络(Neural Networks)：在微观层次上模仿脑神经的功能。（3）模糊系统(Fuzzy Systems，Fuzzy Computing)对人在日常生活中进行近似或非精确推断、决策能力的模拟。第3页，本讲稿共73页这三种智能计算方法已成为目前智能技术的主流。1994年，关于演化计算、神经网络、模糊系统的三个 IEEE国际学术会议在美国FLO

4、RID州联合举行了“首届 计算智能世界大会”（The First IEEE World Congress on Computational Intelligence,WCCI94),把本来是不 同学科领域的专家们聚集在一起，进行了题为“模仿生模仿生 命：计算智能命：计算智能（Computational Intelligence：Imitating the Life)主题讨论会，取得了关于计算智能 的共识。以后每四年召开一次。第4页，本讲稿共73页各种智能计算方法的共同特点共同特点共同特点共同特点：（1）它们大都引入了随机因素，因此具有不确定性，甚至同时支持相互矛盾的途径去求解。（2）它们大都具

5、有自适应机制的动力体系，有时在计算过程中体系结构还在不断调整。（3）这些算法都是针对通用的一般目标而设计的，他们不同于针对特殊问题而设计的算法。第5页，本讲稿共73页“It is not the strongest of species that survive,nor the most intelligent,but the one most adaptable to change.”“适者生存适者生存”（Survival of the fittest）Charles Darwin(1809-1882)第一章第一章 什么是演化计算什么是演化计算第6页，本讲稿共73页1.什么是演化计算？什么是

6、演化计算？演化计算（演化计算（Evolutionary Computation，也称，也称“进化计进化计算算”,简称简称EC）是用计算机模拟大自然的演化过程，特别是）是用计算机模拟大自然的演化过程，特别是生物进化过程，来求解复杂问题的一类智能计算系统。生物进化过程，来求解复杂问题的一类智能计算系统。Many scientists and engineers now use the paradigms of evolutionary computation to tackle problems that are either intractable or unrealistically time

7、 consuming to solve through traditional computational strategies.-Baeck Handbook of Evolutionary Computationby Institute of Physics Publishing;May 2003.2.为什么要进行演化计算？为什么要进行演化计算？第7页，本讲稿共73页八阶非线性方程组:I1+I2+I3+I4=a(1);I1*cos(theta1)+I2*cos(theta2)+I3*cos(theta3)+I4*cos(theta4)=a(2);I1*sin(theta1)+I2*sin(

8、theta2)+I3*sin(theta3)+I4*sin(theta4)=a(3);I1*cos(theta1)*cos(theta1)+I2*cos(theta2)*cos(theta2)+I3*cos(theta3)*cos(theta3)+I4*cos(theta4)*cos(theta4)=a(4);I1*cos(theta1)*sin(theta1)+I2*cos(theta2)*sin(theta2)+I3*cos(theta3)*sin(theta3)+I4*cos(theta4)*sin(theta4)=a(5);I12+I22+I32+I42=a(6);I12*cos(th

9、eta1)+I22*cos(theta2)+I32*cos(theta3)+I42*cos(theta4)=a(7);I12*sin(theta1)+I22*sin(theta2)+I32*sin(theta3)+I42*sin(theta4)=a(8);第8页，本讲稿共73页其中a(1),a(2),a(8)有三组数据:(1.804800000000000e+004 1.365736315298172e+004 5.497052905295088e+003 1.450829635946082e+004 3.157294805334107e+003 1.055437940000000e+008

10、9.159875125016867e+007 3.347057899613227e+007)(1.624320000000000e+004 1.229162683768355e+004 4.947347614765579e+003 1.305746672351474e+004 2.841565324800696e+003 9.498941459999999e+007 8.243887612515180e+007 3.012352109651904e+007)(1.985280000000000e+004 1.502309946827989e+004 6.046758195824596e+003

11、 1.595912599540690e+004 3.473024285867518e+003 1.160981734000000e+008 1.007586263751855e+008 3.681763689574549e+007)第9页，本讲稿共73页3.演化计算的研究内容演化计算的研究内容 演化算法 演化计算的应用 演化计算的理论第10页，本讲稿共73页第二章第二章 演化算法（演化算法（Evolutionary AlgorithmEvolutionary Algorithm）1.演化算法演化算法遗传算法（遗传算法（Genetic Algorithm，简称，简称GA）J.H.Holland(

12、1975)演化规划（演化规划（Evolutionary Programming，简称，简称EP）L.J.Fogel(1966)演化策略（演化策略（Evolutionary Strategies，简称，简称ES）I.Rechenberg,H-P.Schwefel(1963)遗传程序设计（遗传程序设计（Genetic Programming，简称，简称GP）J.R.Koza(1992)以上以上 几个分支在算法实现方面具有一些细微的差别，但它们具有一个共几个分支在算法实现方面具有一些细微的差别，但它们具有一个共同的特点，即都是借助生物演化的思想和原理来解决实际题，所以在同的特点，即都是借助生物演化的

13、思想和原理来解决实际题，所以在90年代年代，这些分支互相融合，就形成了一门新的学科这些分支互相融合，就形成了一门新的学科演化计算。演化计算。第11页，本讲稿共73页求解优化问题求解优化问题 的演化算法的框架为的演化算法的框架为2.演化算法的框架演化算法的框架ALGORITHM:begin t:=0;初始化群体初始化群体P(t)=XP(t)=X1 1，X X2 2，X XN N；计算计算P(t)P(t)中的个体的适应值；中的个体的适应值；while(while(不满足停止准则不满足停止准则)do)do 由由P(t)P(t)通过遗传操作并通过选择形成新的种群通过遗传操作并通过选择形成新的种群P(t

14、+1)P(t+1)；计算计算P(t+1)P(t+1)中个体的适应值；中个体的适应值；t:=t+1;t:=t+1;ENDEND；注：其中注：其中 N 为种群为种群P(t)的大小，称为群体规模。的大小，称为群体规模。第12页，本讲稿共73页2.1.编码(code)2.1.1 二进制编码 2.1.2 实数编码 2.1.3其它编码2.2.适应值函数(fitness function)2.2.1 采用目标函数做适应值函数 2.2.2 通过对函数值进行变换得到适应值函数2.3.遗传操作 2.3.1 选择（selection）精英选择（elitist selection）锦标赛选择（tournament s

15、election）轮盘赌选择（roulette wheel selection）第13页，本讲稿共73页2.3.2 杂交（crossover）单点杂交（one-point crossover）多点杂交（multi-point crossover）均匀杂交（uniform crossover）2.3.2.1 二进制编码的杂交策略2.3.2.2 实数编码的杂交策略 算术杂交（arithmetic crossover）多父体杂交（multi-parent crossover）第14页，本讲稿共73页2.3.3 变异（mutation）2.3.3.1 二进制编码的变异策略2.3.3.2 实数编码的变异

16、策略 点变异（bitwise mutation）均匀变异（uniform mutation）均匀变异（uniform mutation）高斯变异（Gaussian mutation）第15页，本讲稿共73页例1：Ackley函数：最优解为第三章第三章 算算 法法 举举 例例第16页，本讲稿共73页（1）.随机初始化种群（产生一组初始解）V1=4.954222,0.169225,V2=-4.806207,-1.630757V3=4.672536,-1.867275,V4=1.897794,-0.196387V5=-2.127598,0.750603,V6=-3.832667,-0.959655V

17、7=-3.792383,4.064608,V8=1.182745,-4.712821V9=3.812220,-3.441115,V10=-4.515976,4.539171 Vi称之为个体,10称之为群体规模,x1,x2为基因x1x2第17页，本讲稿共73页(2)计算群体中个体的适应值(fitness)eval(v1)=f(4.954222,0.169225)=10.731945,eval(v2)=f(-4.806207,-1.630757)=12.110259 eval(v3)=f(4.672536,-1.867275)=11.788221 eval(v4)=f(1.897794,-0.19

18、6387)=5.681900 eval(v5)=f(-2.127598,0.750603)=6.757691 eval(v6)=f(-3.832667,-0.959655)=9.194728 eval(v7)=f(-3.792383,4.064608)=11.795402 eval(v8)=f(1.182745,-4.712821)=11.559363 eval(v9)=f(3.812220,-3.441115)=12.279653 eval(v10)=f(-4.515976,4.539171)=14.251764第18页，本讲稿共73页（3）对P(t)进行遗传操作（杂交、变异）杂交（杂交（c

19、rossover)(算术杂交）：算术杂交）：v1=av1+(1-a)v2,v2=av2+(1-a)v1,a(0,1)为随机数例如：v2和v6,v8和v9分别进行杂交,产生的后代为v1=-4.444387,-1.383817,v2=-4.194488,-1.206594v3=3.683262,-4.521950,v4=1.311703,-3.631985变异（变异（mutation)（均匀变异）（均匀变异）:v7=-3.792383,4.064608 v5=2.695837,4.064608生成5个后代（新个体），适应值如下：eval(v1)=f(v1)=11.927451,eval(v2)=f

20、(v2)=10.566867eval(v3)=f(v3)=13.449167,eval(v4)=f(v4)=10.538330eval(v5)=f(v5)=9.083240第19页，本讲稿共73页(4)得到新的群体得到新的群体P(t+1)V1=4.954222,0.169225,V2=1.311703,-3.631985 V3=4.672536,-1.867275,V4=1.897794,-0.196387 V5=-2.127598,0.750603,V6=-3.832667,-0.959655 V7=-3.792383,4.064608,V8=1.182745,-4.712821 V9=-4

21、.194488,-1.206594,V10=-4.068506,-0.959655相应的适应值为相应的适应值为eval(v1)=f(v1)=10.731945,eval(v2)=f(v2)=10.538330,eval(v3)=f(v3)=11.788221,eval(v4)=f(v4)=5.681900eval(v5)=f(v5)=6.757691,eval(v6)=f(v6)=9.194728eval(v7)=f(v7)=11.795402,eval(v8)=f(v8)=11.559363eval(v9)=f(v9)=10.566867,eval(v10)=f(v10)=9.083240至

22、此，我们仅完成了一次遗传迭代（繁殖一代）至此，我们仅完成了一次遗传迭代（繁殖一代）第20页，本讲稿共73页例例2.配词问题（配词问题（Freeman1994）试图用遗传算法将随机产生的字母序列变成短语试图用遗传算法将随机产生的字母序列变成短语“to be or not to be”由于短语中有由于短语中有13个字母，每个字母有个字母，每个字母有26种可能，因此种可能，因此随机方式产生正确表达短语的概率是随机方式产生正确表达短语的概率是(1/26)13=4.0303810-19,即一千亿亿次中约有即一千亿亿次中约有4次机会正次机会正确。确。编码方案：用编码方案：用ASCII整数码来编码。字符串整

23、数码来编码。字符串“to be or not to be”转换为转换为ASCII码为码为 116,111,98,101,111,114,110,111,116,116,111,98,101第21页，本讲稿共73页随机初始化种群（种群规模为随机初始化种群（种群规模为10）：114,122,102,113,100,104,117,106,97,114,100,98,101 rzfqdhujardbe110,105,101,100,119,118,121,118,106,97,104,102,106 niedwvyvjahfj115,99,121,117,101,105,115,111,115,11

24、3,118,99,98 scyueisosqvcb102,98,102,118,114,97,109,116,101,107,117,118,115 fbfvramtekuvs107,98,117,113,114,116,106,116,106,101,110,115,98 kbuqrtjtjensb102,119,121,113,121,107,107,116,122,121,111,106,97fwyqykktzyoja116,98,120,98,108,115,111,105,122,103,103,119,109 tbxblsoizggwm101,111,111,117,114,104

25、,100,120,98,118,116,120,97 eoourhdxbvtxa100,116,114,105,117,111,115,114,103,107,109,98,103 dtriuosrgkmbg106,118,112,98,103,101,109,116,112,106,97,108,113 jvpbgemtpjalq第22页，本讲稿共73页适应值：取为匹配的字母数适应值：取为匹配的字母数代数 字串适应值代数字串适应值1rzfqdhujardbe 215rzcwornottobe92rzfqdhuoardbe316rzbwornottobe103rzfqghuoatdbe417r

26、zbwornottobe104rzfqghuoztobe518rzbwornottobe105rzfqghhottobe619rzbwornottobe106rzfqohhottobe720robwornottobe117rzfqohnottobe821tobwornottobe128rzfqohnottobe822tobwornottobe129rzfqohnottobe823tobeornottobe1310rzfqohnottobe824tobeornottobe1311rzfqornottobe925tobeornottobe1312rzfqornottobe926tobeornott

27、obe1313rzfwornottobe 927tobeornottobe1314rzcwornottobe928tobeornottobe13第23页，本讲稿共73页考虑函数优化问题：考虑函数优化问题：其中其中 。第三章第三章 郭涛算法郭涛算法第24页，本讲稿共73页AlgorithmGT:begin initialize P X1,X2,XN;Xi D t:=0；while abs(f(X best)-f(X worst)do select M points X1,X2,XM from P randomly to form space V;select one point X from V

28、 randomly;If f(Xson)f(X worst)then Xworst :=Xson；t:=t+1;od output t,P；end第25页，本讲稿共73页记记D中的中的M个点为个点为 Xj=(x1j,x2j,xnj),j1,2,M记它们所张成的子空间为：记它们所张成的子空间为：V X D|X=aj Xj 其中其中 ai 满足条件满足条件:ai 1,-0.5 ai 1.5。第26页，本讲稿共73页注注1.初始化初始化(initialize)是随机地从解空间是随机地从解空间D中选中选 取取N个点个点(个体个体)形成初始群体形成初始群体P；注注2.N的选取的选取,可根据问题的维数可根

29、据问题的维数 n 与与 f(X)埸埸 景的复杂性而定景的复杂性而定,当当 n 较大且埸景复杂时较大且埸景复杂时,N 可取大些可取大些,反之反之,则取小些。则取小些。一般取一般取 20 N 150;注注3.M的选取，根据我们的经验取的选取，根据我们的经验取M=7,8,9 或或 10 较合适较合适;注注4.算法采取一种随机搜索策略算法采取一种随机搜索策略,通过多次运通过多次运 行行,可以帮助我们判断复杂函数优化问题可以帮助我们判断复杂函数优化问题 的解的分布情况的解的分布情况。第27页，本讲稿共73页算法的特点算法的特点：1)算法采用了演化计算中的群体搜索策算法采用了演化计算中的群体搜索策 略，保

30、证了搜索空间的全局性，有利于搜略，保证了搜索空间的全局性，有利于搜索问题的解。索问题的解。第28页，本讲稿共73页2)算法采用随机子空间中的随机搜索算法采用随机子空间中的随机搜索(多父多父 体重组体重组)策略策略,特别是子空间中随机搜索的非凸特别是子空间中随机搜索的非凸性性:X=Xi,1,-0.5 ai 1.5，使算法搜索的子空间可复盖多父体的凸组合使算法搜索的子空间可复盖多父体的凸组合空间，保证了随机搜索的遍历性空间，保证了随机搜索的遍历性,即解空间即解空间中不存在算法搜索不到的中不存在算法搜索不到的“死角死角”。第29页，本讲稿共73页3)算法采用了算法采用了“劣汰策略劣汰策略”,每次只把

31、群体每次只把群体 中适应性最差中适应性最差(目标函数值最大目标函数值最大)的个体的个体 淘汰出局淘汰出局,淘汰压力最小，既保证了淘汰压力最小，既保证了 群体的多样性，也保证了适应性最好群体的多样性，也保证了适应性最好 (目标函数值最小目标函数值最小)的个体可以的个体可以“万寿无万寿无 疆疆”。这种这种“群体爬山策略群体爬山策略”,保证了整保证了整 个群体最后集体登上最高峰个群体最后集体登上最高峰(深谷深谷)。当。当 最优解不唯一时最优解不唯一时,算法可能一次同时找算法可能一次同时找 到多个最优解。到多个最优解。第30页，本讲稿共73页例例1该函数的复杂性表现如下该函数的复杂性表现如下:多峰多峰

32、(谷谷)性性,因为因为D 的面积很大的面积很大:2020400,sin(9y)与与 cos(25x)分别在不方向上是高频振荡的；分别在不方向上是高频振荡的；当当x10,y10 时时,函数的高峰函数的高峰(深谷深谷)密集密集,埸景埸景十分复杂十分复杂(见图见图1)min f1(x,y)f1(-10,9.9445695)-39.944506953367第31页，本讲稿共73页图1第32页，本讲稿共73页例例2f2(x,y)21.5+x sin(4x)+y sin(20y)D:-3 x 12.1,4.1 y 5.8 计算得计算得:Min f2(x,y)f2(11.6255448,5.7250441)

33、-38.8502944790207。这是目前我们见到的最好的结果。这是目前我们见到的最好的结果。(见图见图2)第33页，本讲稿共73页图2Min f2(x,y)f2(11.6255448,5.7250441)-38.8502944790207 第34页，本讲稿共73页例3f3(x,y)(20+x cos y+ysin x),D:0 x10，-10y0计算得计算得:Min f3(x,y)f3(10，-63376146)-33.43987020849。(见图见图3)第35页，本讲稿共73页图图3第36页，本讲稿共73页例例4f4(x,y)(x+y+xy)D:-10 x,y 10计算得计算得:Min

34、 f4(x，y)f4(10，10)f4(-10，10)f4(10，-10)f4(-10，-10)119.999999935647见图见图4第37页，本讲稿共73页图图4第38页，本讲稿共73页例5 一个挑战性的问题(NLP)Bump问题问题 1994年年A.Keane 在结构优化设计中提出：在结构优化设计中提出：subject to 0 xi10,i1,2,n由于该问题具有“三超”特性（超非线性、超多峰、超高维），是国际上通用的衡量优化算法的测试函数。第39页，本讲稿共73页 图一、图一、f的图形（不满足条件的点被被赋值为）。的图形（不满足条件的点被被赋值为）。第40页，本讲稿共73页在并行机

35、上的计算结果N=100,fbest=0.8442172N=200,fbest=0.8468442N=300,fbest=0.8486441N=400,fbest=0.8511074N=500,fbest=0.8504975N=1500,fbest=0.8449622N=10,000,fbest=0.845640749N=20,000,fbest=0.8455883N=100,000,fbest=0.8448939N=1,000,000,fbest=0.8445861(16 hours)第41页，本讲稿共73页算法特点算法特点：(1)可用于求解一般的可用于求解一般的NLP问题；问题；(2)既可串

36、行执行，又可异步并行执行既可串行执行，又可异步并行执行(SPMD)；(3)统一处理各种约束条件；统一处理各种约束条件；(4)可得到全局最优可得到全局最优(群体上山策略群体上山策略)；(5)据此可以开发出一种据此可以开发出一种Robust、通用的傻、通用的傻瓜瓜NLP软件软件。第42页，本讲稿共73页Parallel AlgorithmGT(i):begin initialize P X1,X2,XN;Xi D t:=0；Xbest arg ；Xworst arg ；Qi :=Xbest ;while abs(f(X best)-f(X worst)do select M points X1,X

37、2,XM from P+Q randomly;select one point Xson from V randomly;If f(Xson)f(X worst)then Xworst :=Xson；t:=t+1;X best arg ；X worst arg ；Qi:=Xbest;od print t,P,Q；end第43页，本讲稿共73页1、演化算法的特征、演化算法的特征观点观点：演化计算是智能计算的基础演化计算是智能计算的基础；智能计算是计算科学的未来智能计算是计算科学的未来。智能特征智能特征：自适应性自适应性 自组织性自组织性 自学习性自学习性 自优化性自优化性 第四章第四章 演化算法

38、的应用演化算法的应用第44页，本讲稿共73页算法特点：算法特点：原理的简明性原理的简明性 演化的随机性演化的随机性 计算的并行性计算的并行性 应用的广应用的广 泛性泛性第45页，本讲稿共73页第46页，本讲稿共73页2、.演化计算新的研究方向演化计算新的研究方向 （新领域（新领域、新方向举例新方向举例）1.演化算法演化算法+程序结构程序结构=自动程序设计自动程序设计2.演化算法演化算法+可编程器件编程器件=演化硬件演化硬件3.演化算法演化算法+数据结构数据结构=Data Mining自动化自动化4.演化算法演化算法+神经网络结构神经网络结构=演化神经网络演化神经网络（人工脑）人工脑）5.演化算

39、法演化算法+细胞自动机细胞自动机=演化自动机演化自动机 （可实现复杂流体流动仿真）（可实现复杂流体流动仿真）6.演化算法演化算法+基本乐理基本乐理=演化音乐演化音乐第47页，本讲稿共73页演化机器人学演化机器人学(Evolutionary Robotics)演化设计演化设计(Evolutionary Design)人工生命人工生命(A-life)，自适应行为，自适应行为(Adaptive Behavior)智能体智能体(Agents)，蚁群优化，蚁群优化(Ant Colony Optimization)DNA与分子计算与分子计算(DNA and Molecular Computing)量子计算

40、量子计算(Quantum Computing)分类系统分类系统(Classifier Systems)第48页，本讲稿共73页软计算（Soft Computing,SC)L.A.Zadeh 提出的用来包容处理复杂的工业和商业系统诊断，评价和控制问题中有关非精确和非确定信息，不完备领域知识的一整套计算技术：演化计算模糊逻辑（Fuzzy Logic,FL)神经计算（Neural Computing,NC)概率计算(Probabilistic Computing,PC)第49页，本讲稿共73页第五章第五章 自动程序设计与演化自动程序设计与演化建模建模第50页，本讲稿共73页一一.自动程序设计自动程序

41、设计1、什么是程序？、什么是程序？1976年，年，N.Worth:Algorithms+Data Structures=Programs 算法算法 +数据结构数据结构 =程序程序 第51页，本讲稿共73页 2、什么是算法？、什么是算法？是求解给定问题的计算方法，它是求解给定问题的计算方法，它可以用某种计算机程序设计语言来可以用某种计算机程序设计语言来描述（或指令序列）。描述（或指令序列）。第52页，本讲稿共73页 3、什么是数据结构？、什么是数据结构？数据（信息）在计算机中存储的形式，如数据（信息）在计算机中存储的形式，如实型、整型、符号型、数组型、树（二叉实型、整型、符号型、数组型、树（二叉

42、树、树、m叉树）、图表（有向图、无向图）叉树）、图表（有向图、无向图）等等。等等。第53页，本讲稿共73页4、什么是自动程序设计、什么是自动程序设计?“How can computers learn to solve problems without being explicitly programmed?In other words,how can computers be made to do what is needed to be done without being told exactly how to do it?”Attributed to Arthur Samual(1959

43、)第54页，本讲稿共73页“Genetic Programming is Automatic Programming”John Holland(1998)第55页，本讲稿共73页自自 动动 程程 序序 设设 计计=演演 化化 算算 法法+程程 序序 结结 构构Kang,Chen,Pan,Li (1997)第56页，本讲稿共73页什么是程序结构（什么是程序结构（PS）?用用O表示运算符和函数的集合表示运算符和函数的集合,用用 D 表示数表示数据结构的集合据结构的集合,那么程序结构可表示成：那么程序结构可表示成：PS=O D即程序结构是由即程序结构是由 O 和和 D 复合而成。复合而成。其中其中:

44、O=+,-,*,/,sin,cos,exp,D=real,integer,array,tree,graph,第57页，本讲稿共73页程序结构示例：程序结构示例：F=+,-,*O,T=R,x D,PS=a+b,a b,a*b,a+x,a x,a*x,a*b,x*x 第58页，本讲稿共73页二、数学模型二、数学模型1、分类、分类 按应用领域分类：按应用领域分类：经济模型，人口模型，气象模型，天体模型，通经济模型，人口模型，气象模型，天体模型，通 信信模型，物理模型，化学动力学模型，模型，物理模型，化学动力学模型，按数学方法分类：按数学方法分类：函数模型，常微分方程模型，人工神经网络模型，函数模型，

45、常微分方程模型，人工神经网络模型，连续模型，离散模型，连续模型，离散模型，按是否与时间有关分类：按是否与时间有关分类：静态模型，动态模型静态模型，动态模型第59页，本讲稿共73页2、优化问题：、优化问题：数据数据:(xi,yi),i=1,2,.,m,其中其中 yi R,xi R,Y=f(X)求求 f*M(模型空间模型空间,由运算集由运算集O与树高决定与树高决定)使使:即建模问题可以看成一个优化问题：即建模问题可以看成一个优化问题：第60页，本讲稿共73页编码方案（个体的表示）在GP中，用二叉树来表示个体（解）例:(3.5/z)-x2 -*_-x x/3.5 z3.5/z x 2第61页，本讲稿

46、共73页遗传操作：遗传操作：杂交（杂交（Operation for Computer Programs）在评估适应值的基础上随机选择两个父体。在评估适应值的基础上随机选择两个父体。对两个父体程序的每一个，随机选择一个对两个父体程序的每一个，随机选择一个节点。以选取的节点为根，定义两棵子树。节点。以选取的节点为根，定义两棵子树。如下图所示：如下图所示：第62页，本讲稿共73页Parent 1:(+(*0.234 z)(-x 0.789)Parent 2:(*(*z y)(+y(*0.314 z)+-_-0.789 x*0.234 z0.234z+x 0.789*+_-y*z yz y(y+0.3

47、14 z)*0.314 z第63页，本讲稿共73页杂交杂交(Two Offspring Version)Offspring 1:(+(+y(*0.314 z)(-x 0.789)Offspring 2:(*(*z y)(*0.234 z)+_-y*0.314 z+-_-0.789 xY+0.314 z 0.789*z y0.234z2y *0.234 z第64页，本讲稿共73页变异变异 在树上随机选取一个节点，然后剪掉以在树上随机选取一个节点，然后剪掉以该节点为根节点的子树或者随机生成一棵该节点为根节点的子树或者随机生成一棵子树替代它。子树替代它。第65页，本讲稿共73页ALOGRITHM G

48、P(i):begin t:=0;initialize P(t);P(t)=x1(t),x2(t),xn(t)evaluate P(t);F(P(t)=F(x1(t),F(x2(t),F(xn(t)while(not termination condition)do Pc(t)=crossover P(t);Pm(t)=mutation Pc(t);evaluate Pm(t);P(t+1)=select Pm(t)U Q;t:=t+1 if t0(mod T)then Qi:=xbest （*）od print xbest,F(xbest);end其中其中 Q=Q1,Q2,Qp 为为共享共享数

49、据数据。第66页，本讲稿共73页三、实例三、实例（Data Mining自动化自动化）1.三峡岩石分类模型三峡岩石分类模型：观测数据观测数据(yi,x1i,x2i,x3i,x4i),i=1,2,m 其中其中 x1i移动率，移动率，x2i结合率，结合率，x3i强度强度,x4i 变形系数变形系数第67页，本讲稿共73页Y=1.69+x1 +0.238/x3Y=2+x1 x4 +0.225/x3Y=ln(5.09 x2+0.39+12.78 x1/x3Y=exp 1.50(cos x3 cos x1)+cos(1.71 )Y=x2(1.84)第68页，本讲稿共73页2.美国人口增长模型美国人口增长模

50、型 观测数据（观测数据（1790-1950年）计算机自年）计算机自动发现的一些模型如下：动发现的一些模型如下：=20.574356(1.384360 tx)(x+1.48616)=30.912327 x 0.151000 x2 =(21.926580 x+111.811684)cos(tx)=(1 x/xm)x 其中其中=31 xm=197其中第二个模型与人口统计专家发现的其中第二个模型与人口统计专家发现的Logistic模型模型完全一致完全一致第69页，本讲稿共73页3.中国经济产值模型中国经济产值模型：根据我国根据我国 1978-1983 每年的社会生产总产值（每年的社会生产总产值（x1）