人工智能 智能与系统概论(英文版)第九章

1、 Negnevitsky, Pearson Education, 20051 Negnevitsky, Pearson Education, 20052 Negnevitsky, Pearson Education, 20053生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，发， 人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。系统的设计和开发提供了广阔的前景。遗传算法遗传算法(Genetic Al

2、gorithms，简称，简称GAs)就是这种生物行为的计算机模拟中就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传算法所借鉴的生物学基础就是生物的遗传和进化。 世间的生物从其父代继承特性或性状，这种生命现象就称为遗传世间的生物从其父代继承特性或性状，这种生命现象就称为遗传染色体染色体(Chromosome) 细胞中含有的一种微小的丝状化

3、合物，生物的所有细胞中含有的一种微小的丝状化合物，生物的所有遗遗信信息息都包含在这个复杂而又微小的染色体中。都包含在这个复杂而又微小的染色体中。基因基因 遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的过程中，其过程中，其遗传基因遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。也同时被复制到下一代，从而其性状也被下一代所继承。 Negnevitsky, Pearson Education, 20054 Negnevitsky, Pearson Education, 20055 地球上的生物，都是经过长期进化而形成

4、的。根据达尔文的自然选择学说，地地球上的生物，都是经过长期进化而形成的。根据达尔文的自然选择学说，地 球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通过遗传，使物种球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通过遗传，使物种 保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。正保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。正 是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资 源却是有限的。因此，为了生存，生物就需要竞争。生物在生存竞争中，根据对源

5、却是有限的。因此，为了生存，生物就需要竞争。生物在生存竞争中，根据对 环境的适应能力，适者生存，不适者消亡。环境的适应能力，适者生存，不适者消亡。自然界中的生物，就是根据这种优胜自然界中的生物，就是根据这种优胜 劣汰的原则，不断地进行进化。劣汰的原则，不断地进行进化。 生物的进化是以集团的形式共同进行的，这样的一个团体称为生物的进化是以集团的形式共同进行的，这样的一个团体称为群体群体(Population)， 或称为种群。或称为种群。 组成群体的单个生物称为组成群体的单个生物称为个体个体(Individual)， 每一个个体对其生存环境都有不同的每一个个体对其生存环境都有不同的适应能力适应能力

6、，这种适应能力称为个体的，这种适应能力称为个体的适应度适应度(Fitness)。 Negnevitsky, Pearson Education, 20056 虽然人们还未完全揭开遗传与进化的奥秘，即没有完全掌握其机制、也不完全虽然人们还未完全揭开遗传与进化的奥秘，即没有完全掌握其机制、也不完全 清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的 以下几个特点却为人们所共识：以下几个特点却为人们所共识： (1) 生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；生物的所有遗传信息都包含在其染色体

7、中，染色体决定了生物的性状； (2) 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上； (3) 生物的繁殖过程是由其基因的复制过程来完成的；生物的繁殖过程是由其基因的复制过程来完成的； (4) 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的 性状。性状。 (5) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会 遗传到下一代。遗

8、传到下一代。 Negnevitsky, Pearson Education, 20057生物进化理论生物进化理论.flv生物进化理论生物进化理论 Negnevitsky, Pearson Education, 20058最优化最优化 Negnevitsky, Pearson Education, 20059 Negnevitsky, Pearson Education, 200510 Negnevitsky, Pearson Education, 200511 Negnevitsky, Pearson Education, 200512适应性拓扑适应性拓扑是一个连续函数。是一个连续函数。它模拟

9、的环境或自然拓扑不是静态的。它模拟的环境或自然拓扑不是静态的。随着时间推移，拓扑性状发生改变，随着时间推移，拓扑性状发生改变，所有的物种要不断地经历选择。所有的物种要不断地经历选择。进化的目标就是进化的目标就是产生适应性增加的后代产生适应性增加的后代。 Negnevitsky, Pearson Education, 200513 Negnevitsky, Pearson Education, 200514美国密歇根大学心理系和计算机与电子工程系的教授美国密歇根大学心理系和计算机与电子工程系的教授复杂理论和非线性科学的先驱复杂理论和非线性科学的先驱遗传算法之父遗传算法之父获得美国获得美国“麦克阿

10、瑟天才奖麦克阿瑟天才奖”John Henry Holland1929.2.2“机器可以像动物一样被训练去适应周机器可以像动物一样被训练去适应周围的环境。进化就像学习适应环境的一围的环境。进化就像学习适应环境的一种方式。进化是次代叠加的，而不是只种方式。进化是次代叠加的，而不是只发生在某一生命周期里。发生在某一生命周期里。” Negnevitsky, Pearson Education, 200515将人造染色体的一个种群进化到另一个种群的过程。使用将人造染色体的一个种群进化到另一个种群的过程。使用“自然自然”选择机制和遗传学的交叉和突变机制。选择机制和遗传学的交叉和突变机制。1101 0 1

11、0 0 0 0 0 1 0 110 Negnevitsky, Pearson Education, 200516评估函数是为要解决问题度量染色体评估函数是为要解决问题度量染色体的性能或适应性。的性能或适应性。 Negnevitsky, Pearson Education, 200517 Negnevitsky, Pearson Education, 200518双亲染色体被选择的概率双亲染色体被选择的概率crossovermutation Negnevitsky, Pearson Education, 200519终止条件终止条件 Negnevitsky, Pearson Education,

12、 200520IntegerBinary codeIntegerBinary codeIntegerBinary code1112712381349145101561 0 1 11 1 0 01 1 0 11 1 1 01 1 1 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 1 Negnevitsky, Pearson Education, 200521编号编号 染色体串染色体串 解码后整数解码后整数 适应性适应性 适应性比率适应性比率 Negnevitsky, Pearson Education,

13、 200522100 036.743.149.575.2X1: 16.5%X2: 20.2%X3: 6.4%X4: 6.4%X5: 25.3%X6: 24.8% Negnevitsky, Pearson Education, 200523 Negnevitsky, Pearson Education, 200524 Negnevitsky, Pearson Education, 200525X6i1000010X2i0010X2i0111X5i0X1i0111X5i10100 10 0111010 Negnevitsky, Pearson Education, 200526 Negnevits

14、ky, Pearson Education, 2005270111X5i010X6i1000010X2i0 10 001 11 1X5i11 1X1i1 1X2i0 100X1i11 10 10X2i Negnevitsky, Pearson Education, 2005281010X1iGeneration i0010X2i0001X3i1110X4i0111X5if = 561001X6if = 54f = 36f = 44f = 14f = 141000X1i+1Generation (i + 1)0011X2i+11101X3i+10010X4i+10110X5i+1f = 5401

15、11X6i+1f = 56f = 56f = 50f = 44f = 44CrossoverX6i1000010X2i0010X2i0111X5i0X1i0111X5i10100 10 0111010Mutation0111X5i010X6i1000010X2i0 10 001 11 1X5i11 1X1i1 1X2i0 100X1i11 10 10X2i Negnevitsky, Pearson Education, 200529ChromosomelabelChromosomestringDecodedintegerChromosomefitnessFitnessratio, %X11 1

16、 0 0123616.5X20 1 0 044420.2X30 0 0 11146.4X41 1 1 014146.4X50 1 1 175625.7X61 0 0 195424.8x5040302060100051015f(x)(a) Chromosome initial locations.x5040302060100051015(b) Chromosome final locations. Negnevitsky, Pearson Education, 2005302222)()1 (),(33) 1(2yxyxeyxxexyxf-+-=1000110001011101yx Negnev

17、itsky, Pearson Education, 20053110012345672)138(2021202120202021)10001010(=+=and10012345672)59(2121202121212020)00111011(=+=1000 11000101 1101and Negnevitsky, Pearson Education, 2005320235294. 012566=-2470588. 030235294. 0)138(10=-=xand6117647. 130235294. 0)59(10-=-=y Negnevitsky, Pearson Education,

18、 200533 Negnevitsky, Pearson Education, 200534初始群体初始群体第第1代代全局最优结果全局最优结果局部最优结果局部最优结果 Negnevitsky, Pearson Education, 200535 Negnevitsky, Pearson Education, 200536BestAverage100G e n e r a t i o n s809060704050203010pc= 0.7, pm= 0.011.800.20.40.60.81.01.21.41.6F i t n e s spc= 0.7, pm= 0.001G e n e r

19、a t i o n sBestAverage8090100607040502030100-0.10.50.60.700.10.20.30.4F i t n e s s全局最优结果全局最优结果局部最优结果局部最优结果 Negnevitsky, Pearson Education, 200537pc= 0.7, pm= 0.001BestAverage20G e n e r a t i o n s1618121481046200.20.40.60.81.01. 21.41.61.8F i t n e s s Negnevitsky, Pearson Education, 200538 Negnev

20、itsky, Pearson Education, 200539指种群个体基因串中的相似样板指种群个体基因串中的相似样板 Negnevitsky, Pearson Education, 200540如何已知第如何已知第i代模式代模式H实例个数实例个数 ，求得第求得第i+1代该模式实例个数代该模式实例个数 ？ Negnevitsky, Pearson Education, 200541 Negnevitsky, Pearson Education, 200542突变后低秩、短模式幸存的概率要大于长模式幸存概率Schema Theorem模式定理：具有低秩、短定义长度以及平均适应度高于种群平均适应

21、度的模式在子代中呈指数增长。模式定理保证了较优的模式的数目呈指数增长，为解释遗传算法机理提供了数学基础。 Negnevitsky, Pearson Education, 200543 Negnevitsky, Pearson Education, 200544 Negnevitsky, Pearson Education, 200545 Negnevitsky, Pearson Education, 200546 Negnevitsky, Pearson Education, 200547Unit 1:10100 100101Unit 2:10100 100101Unit 3:10000 10

22、01000001Unit 4:10000 1001000001Unit 5:10000 1001000001Unit 6:10000 1001000001Unit 7:10000 10010000010110010100011000001001001000Unit 1Unit 3Unit 2Unit 4Unit 6Unit 5Unit 7 Negnevitsky, Pearson Education, 200548 Negnevitsky, Pearson Education, 2005490110 0101 000110000010 0100 1000Parent 11010 0110 00

23、1000010100 1000 0010Parent 20110 0101 000110000100 1000 0010Child 11010 0110 001000010010 0100 1000Child 21010011000100001001001001000001010100110001000010010010010000001 Negnevitsky, Pearson Education, 200550 Negnevitsky, Pearson Education, 2005510306090120150Unit2Unit2Unit7Unit1Unit6Unit1Unit3Unit

24、5Unit41234T ime intervalNet reserves:15353525N=20, pc=0.7, pm=0.001BestAverage51525351030204045500-10-5051015G e n e r a t i o n sF i t n e s sM WGenerations030601234T ime intervalNet reserves:40252025Un it2Un it2Un it7Un it1Un it6Un it1Un it3Un it5Un it490120150N=20, pc=0.7, pm=0.001BestAverage1030

25、507020060408090100-1001020GenerationsF i t n e s s Negnevitsky, Pearson Education, 2005521234T imei nterval35252525Un it2Un it7Un it1Un it6Un it1Unit3Un it5Un it40306090120150N=100, pc=0.7, pm=0.001GenerationsNet reserves:BestAverage1030507020060408090100-100102030F i t n e s s1234Time i ntervalNet

26、reserves:25253030Unit 2Unit 2Unit 7Unit 6Unit 1Unit 3Unit 5Unit 40306090120150Unit 1N=100,c= 0.7,m = 0.01Generations1030507020060408090100BestAverage-20-100103020F i t n e s s Negnevitsky, Pearson Education, 200553ES模仿生物进化原理，假设不论基因发生何种变化，产生的结果（性状）总遵循零均值、某一方差的高斯分布。 Negnevitsky, Pearson Education, 200

27、554 Negnevitsky, Pearson Education, 200555xx1m ax1min,xx2m ax2min, . . . ,Nm axNminxx, Negnevitsky, Pearson Education, 200556 Negnevitsky, Pearson Education, 200557,0axxii+=NxxxfX=,.,21 Negnevitsky, Pearson Education, 200558 Negnevitsky, Pearson Education, 200559 Negnevitsky, Pearson Education, 2005

28、60 Negnevitsky, Pearson Education, 200561n 遗传编程是一种特殊的利用进化算法的机器学习技术遗传编程是一种特殊的利用进化算法的机器学习技术, , 它开始于一群它开始于一群由随机生成的千百万个计算机程序组成的由随机生成的千百万个计算机程序组成的 人群人群 ，然后根据一个程序，然后根据一个程序完成给定的任务的能力来确定某个程序的适合度，应用达尔文的自然完成给定的任务的能力来确定某个程序的适合度，应用达尔文的自然选择（适者生存）确定胜出的程序，计算机程序间也模拟两性组合，选择（适者生存）确定胜出的程序，计算机程序间也模拟两性组合，变异，基因复制，基因删除等代代

29、进化，直到达到预先确定的某个中变异，基因复制，基因删除等代代进化，直到达到预先确定的某个中止条件为止。止条件为止。 Negnevitsky, Pearson Education, 200562 Negnevitsky, Pearson Education, 200563 Negnevitsky, Pearson Education, 200564任何任何LISPLISP的的S S表达式都可以表达成一棵用节点标记的有根的、具有有序表达式都可以表达成一棵用节点标记的有根的、具有有序分枝的树。分枝的树。BA*C- Negnevitsky, Pearson Education, 200565 Negnevitsky, Pearson Education, 20056622bac+=勾股定理勾股定理SideaSidebHy potenu secSideaSidebHy potenu sec355. 830952121015. 62049981416. 12451521 621. 84033018 218. 110770748. 062258321133. 837849162428. 844410435. 000000299. 21