《人工智能第五章 (2)PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《人工智能第五章 (2)PPT讲稿.ppt（109页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能第五章第1页，共109页，编辑于2022年，星期四第第5章章计算智能计算智能(2)进化计算进化计算人工生命人工生命第2页，共109页，编辑于2022年，星期四第五章第五章计算智能计算智能(2)5.1遗传算法遗传算法5.2进化策略进化策略5.3进化编程进化编程5.4人工生命人工生命第3页，共109页，编辑于2022年，星期四第五章第五章计算智能计算智能(2)作业：作业：5-2，5-7，5-9第4页，共109页，编辑于2022年，星期四答疑时间及地点答疑时间及地点 答疑时间答疑时间：每周四：每周四5、6节节答疑地点答疑地点：三教：三教2604电子邮件电子邮件：联系方式联系方式：138108
2、42037第5页，共109页，编辑于2022年，星期四第四章第四章计算智能计算智能(1)4.1概述概述4.2神经计算神经计算4.3模糊计算模糊计算 第6页，共109页，编辑于2022年，星期四v计算智能计算智能涉及涉及神经网络、模糊逻辑神经网络、模糊逻辑、进化计算和人工进化计算和人工生命生命等领域，它的研究和发展反映了当代科学技术等领域，它的研究和发展反映了当代科学技术多学科交叉与集成的重要发展趋势。多学科交叉与集成的重要发展趋势。l计算智能是借鉴仿生学的思想，基于人们对生物体计算智能是借鉴仿生学的思想，基于人们对生物体智能机理的认识，采用智能机理的认识，采用数值计算数值计算的方法去的方法去模
3、拟和实模拟和实现现人类的智能。人类的智能。v计算智能是一种以计算智能是一种以模型模型（计算模型、数学模型）为基（计算模型、数学模型）为基础，以础，以分布、并行计算为特征分布、并行计算为特征的自然智能模拟方法。的自然智能模拟方法。第7页，共109页，编辑于2022年，星期四v进化计算进化计算（EvolutionaryComputation,EC）包括：包括：遗传算法遗传算法(geneticalgorithms，GA)进化策略进化策略(evolutionstrategies)进化编程进化编程(evolutionaryprogramming)遗传编程遗传编程(geneticprogramming)v
4、人类不满足于模仿生物进化行为，希望能够建立人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的具有自然生命特征的人造生命人造生命和人造生命系统。和人造生命系统。v人工生命人工生命是人工智能和计算智能的一个新的研究热点。是人工智能和计算智能的一个新的研究热点。v进化计算进化计算是一种对人类智能的是一种对人类智能的演化演化模拟方法，它是通模拟方法，它是通过对生物遗传和演化过程的认识，用过对生物遗传和演化过程的认识，用进化算法进化算法去模拟去模拟人类智能的进化规律的。人类智能的进化规律的。第8页，共109页，编辑于2022年，星期四l人工生命人工生命(Artificiallife，AL)是通
5、过人工模拟生命系统，来是通过人工模拟生命系统，来研究生命的领域。研究生命的领域。l人工生命的概念人工生命的概念，包括两个方面内容：，包括两个方面内容：（1）属于计算机科学领域的虚拟生命系统，涉及计算机）属于计算机科学领域的虚拟生命系统，涉及计算机软件工程与人工智能技术；软件工程与人工智能技术；（2）基因工程技术人工改造生物的工程生物系统，涉）基因工程技术人工改造生物的工程生物系统，涉及合成生物学技术。及合成生物学技术。lAL是是首先由计算机科学家首先由计算机科学家ChristopherLangton于于1987年年在在LosAlamosNationalLaboratory召开的召开的生成以及模
6、拟生生成以及模拟生命系统的国际会议命系统的国际会议上提出。上提出。第9页，共109页，编辑于2022年，星期四世界首个人工生命结构诞生世界首个人工生命结构诞生中新网中新网2010年年5月月22日电日电综合媒体报道，美国克莱格综合媒体报道，美国克莱格.文特尔研究文特尔研究所一个有华人参与的研究团队宣布，所一个有华人参与的研究团队宣布，在实验中制造出世界首个完全在实验中制造出世界首个完全由人造基因指令控制的人造生命，使人类的能力拓展到可以操纵自然由人造基因指令控制的人造生命，使人类的能力拓展到可以操纵自然世界，将来可制造有特殊功能的生物，在生产疫苗及洁净能源等领域世界，将来可制造有特殊功能的生物，
7、在生产疫苗及洁净能源等领域大派用场。大派用场。由美国生物学家文特尔领导的研究团队，重塑由美国生物学家文特尔领导的研究团队，重塑“丝状支原体丝状亚丝状支原体丝状亚种种”(Mycoplasmamycoides)这种微生物的这种微生物的DNA，并将新，并将新DNA片段片段“黏黏”在一起，植入另一种山羊支原体中。新生命于在一起，植入另一种山羊支原体中。新生命于2010年年4月诞生，月诞生，昵称昵称“Synthia”(合成体合成体)，这种微生物由蓝色细胞组成，能够生长、，这种微生物由蓝色细胞组成，能够生长、繁殖，细胞分裂了逾繁殖，细胞分裂了逾10亿次，产生一代又一代的人造生命。亿次，产生一代又一代的人造
8、生命。植入的植入的DNA片段包含约片段包含约850个基因，而人类个基因，而人类DNA图谱上共有约图谱上共有约2万个基因。万个基因。第10页，共109页，编辑于2022年，星期四v进化计算进化计算（EvolutionaryComputation,EC）包括：包括：遗传算法遗传算法(geneticalgorithms，GA)进化策略进化策略(evolutionstrategies)进化编程进化编程(evolutionaryprogramming)遗传编程遗传编程(geneticprogramming)v其中，其中，遗传算法遗传算法是进化计算中最初形成的一种具有是进化计算中最初形成的一种具有普遍影响
9、的模拟进化优化算法。因此我们主要讨论普遍影响的模拟进化优化算法。因此我们主要讨论遗传算法。遗传算法。第11页，共109页，编辑于2022年，星期四 进化计算是一种模拟自然界生物进化过程与机制进化计算是一种模拟自然界生物进化过程与机制进行问题求解的进行问题求解的自组织、自适应自组织、自适应的随机搜索技术。它将生的随机搜索技术。它将生物进化过程中的物进化过程中的繁殖繁殖（Reproduction）变异变异（Mutation）竞争竞争（Competition）选择选择（Selection）引入到了算法中。引入到了算法中。什么是进化计算什么是进化计算第12页，共109页，编辑于2022年，星期四进化计
10、算的生物学基础进化计算的生物学基础 自然界生物进化过程自然界生物进化过程是进化计算的是进化计算的生物学基础生物学基础，它主，它主要包括要包括:l遗传遗传(Heredity)l变异变异(Mutation)l进化进化(Evolution)理论理论第13页，共109页，编辑于2022年，星期四生物进化与遗传算法生物进化与遗传算法 群体群体种群种群子群子群选择选择婚配婚配变异变异遭淘汰遭淘汰的群体的群体第14页，共109页，编辑于2022年，星期四遗传算法遗传算法(GeneticAlgorithm)v达尔文进化论达尔文进化论：“物竞天择、适者生存物竞天择、适者生存”。v70年代年代由美国的密执根大学的
11、由美国的密执根大学的Holland在他的著作在他的著作AdaptationinNaturalandArtificialSystems首次提出遗传算法首次提出遗传算法，并主要由他和他的，并主要由他和他的学生发展起来。学生发展起来。v近年来，遗传算法作为一种有效的工具，已广泛近年来，遗传算法作为一种有效的工具，已广泛地地应用于最优化问题求解应用于最优化问题求解之中。之中。第15页，共109页，编辑于2022年，星期四第五章第五章计算智能计算智能(2)5.1遗传算法遗传算法5.2进化策略进化策略5.3进化编程进化编程5.4人工生命人工生命第16页，共109页，编辑于2022年，星期四5.1遗传算法遗
12、传算法v遗传算法遗传算法是模仿生物遗传学和自然选择机理，通是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的物进化过程进行的一种数学仿真，是进化计算的最重要的形式。最重要的形式。v遗传算法为那些遗传算法为那些难以找到传统数学模型的难题难以找到传统数学模型的难题指出指出了一个解决方法。了一个解决方法。v进化计算和遗传算法进化计算和遗传算法借鉴了生物科学中的某些知识，这借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。也体现了人工智能这一交叉学科的特点。第17页，共109页
13、，编辑于2022年，星期四5.1遗传算法遗传算法遗传算法的起源遗传算法的起源v自然界所提供的答案是经过漫长的自适应自然界所提供的答案是经过漫长的自适应遗传过程遗传过程获得的结果。获得的结果。v我们也可以利用这一过程本身去解决一些复杂的问我们也可以利用这一过程本身去解决一些复杂的问题。题。v遗传算法的研究主要集中在以下几个方面遗传算法的研究主要集中在以下几个方面：函数：函数优化、组合优化生产调度、自动控制、机器人优化、组合优化生产调度、自动控制、机器人学、图像处理、人工生命、演化编程和机器学学、图像处理、人工生命、演化编程和机器学习。习。第18页，共109页，编辑于2022年，星期四5.1.1遗
14、传算法的基本机理遗传算法的基本机理v霍兰德的遗传算法霍兰德的遗传算法通常称为通常称为简单遗传算法简单遗传算法（SimpleGeneticAlgorithm,SGA）。现以此。现以此作为讨论主要对象，加上适应的改进，来分析作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。遗传算法的结构和机理。5.1 5.1 遗传算法遗传算法v编码与解码编码与解码v适应度函数适应度函数v遗传操作遗传操作第19页，共109页，编辑于2022年，星期四5.1.1遗传算法的基本机理遗传算法的基本机理5.1 5.1 遗传算法遗传算法基本思想基本思想是从初始种群出发，采用优胜劣汰、适者生存是从初始种群出发，采用
15、优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。如此逐代进化，直到满足目标为止。遗传算法的基本概念遗传算法的基本概念遗传算法（遗传算法（GeneticAlgorithm）是模拟达尔文的遗传）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种选择和自然淘汰的生物进化过程的计算模型，是一种通过模通过模拟自然进化过程搜索最优解的方法。拟自然进化过程搜索最优解的方法。第20页，共109页，编辑于2022年，星期四5.1.1遗传算法的基本机理遗传算法的基本机理5.1 5.1 遗传算
16、法遗传算法遗传算法的基本概念遗传算法的基本概念遗传算法是从遗传算法是从代表问题可能潜在的解集的一个种群代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体）编码的一定数目的个体（individual）组成。）组成。初代种群产生之后，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解）演化产生出越来越好的近似解，在每一代，根据问题，在每一代，根据问题域中个体的适应度（域中个体的适应度（fitness）大小挑选（）
17、大小挑选（selection）个体，并借助于自然）个体，并借助于自然遗传学的遗传算子（遗传学的遗传算子（geneticoperators）进行组合交叉（）进行组合交叉（crossover）和）和变异（变异（mutation），产生出代表新的解集的种群。），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（应于环境，末代种群中的最优个体经过解码（decoding），可以作为），可以作为问问题近似最优解题近似最优解。第21页，共109页，编辑于2022年，星期四5.1.1
18、遗传算法的基本机理遗传算法的基本机理5.1 5.1 遗传算法遗传算法遗传算法的基本概念遗传算法的基本概念遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与与传统的优化算法相比，主要有以下特点：传统的优化算法相比，主要有以下特点：1、遗传算法以决策变量的编码作为运算对象。遗传算法以决策变量的编码作为运算对象。传统的优化算法往往传统的优化算法往往直接决策变量的实际值本身，而遗传算法处理决策变量的某种编码形直接决策变量的实际值本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自式，使得我们
19、可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便地应用遗传操作算然界生物的遗传和进化机理，也使得我们能够方便地应用遗传操作算子。子。2、遗传算法直接以适应度作为搜索信息，遗传算法直接以适应度作为搜索信息，无需导数等其它辅助无需导数等其它辅助信息。信息。3、遗传算法使用多个点的搜索信息，遗传算法使用多个点的搜索信息，具有隐含并行性。具有隐含并行性。4、遗传算法使用概率搜索技术，遗传算法使用概率搜索技术，而非确定性规则。而非确定性规则。第22页，共109页，编辑于2022年，星期四5.1.1遗传算法的基本机理遗传算法的基本机理5.1 5.1 遗传算法遗传
20、算法基本思想基本思想是从初始种群出发，采用优胜劣汰、适者生存的自是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。代进化，直到满足目标为止。遗传算法的基本概念遗传算法的基本概念种群种群（Population）：种群是初始给定的多个解的集合。它一般：种群是初始给定的多个解的集合。它一般是整个搜索空间的一个很小的子集。是整个搜索空间的一个很小的子集。个体个体（Individual）：个体是指种群中的单个元素。一个个体也就是：个体是指种群中的单个元素。一个个体也就是搜索
21、空间中的一个点。搜索空间中的一个点。染色体染色体（Chromos）：由多个基因组成，表示一个个体。染色体：由多个基因组成，表示一个个体。染色体是指对个体进行编码后所得到的编码串。染色体中的每是指对个体进行编码后所得到的编码串。染色体中的每1位称为位称为基因基因，染色体上由若干个基因构成的一个有效信息段称为染色体上由若干个基因构成的一个有效信息段称为基因组基因组。适应度适应度（Fitness）函数：）函数：适应度函数是一种用来对种群中各个个适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的
22、主要依据。主要依据。第23页，共109页，编辑于2022年，星期四第24页，共109页，编辑于2022年，星期四5.1.1遗传算法的基本机理遗传算法的基本机理5.1 5.1 遗传算法遗传算法遗传算法的基本概念遗传算法的基本概念v适应度适应度(fitness)借借鉴鉴生生物物个个体体对对环环境境的的适适应应程程度度，而而对对问问题题中中的的个个体体对对象象所设计的表征其优劣的一种测度所设计的表征其优劣的一种测度v适应度函数适应度函数(fitnessfunction)v问题中的全体个体与其适应度之间的一个对应关系问题中的全体个体与其适应度之间的一个对应关系v一般是一个实值函数一般是一个实值函数v该
23、函数就是遗传算法中指导搜索的评价函数该函数就是遗传算法中指导搜索的评价函数第25页，共109页，编辑于2022年，星期四5.1.1遗传算法的基本机理遗传算法的基本机理5.1 5.1 遗传算法遗传算法遗传算法的基本概念遗传算法的基本概念v染色体染色体(chromosome)v染色体是由若干基因组成的位串（生物学）染色体是由若干基因组成的位串（生物学）v个体对象由若干字符串组成来表示（遗传算法）个体对象由若干字符串组成来表示（遗传算法）个体个体 染色体染色体 9 -1001 （2，5，6）-010 101 110v遗传算法遗传算法(geneticalgorithm)v染色体就是问题中个体的某种字符
24、串形式的编码表示染色体就是问题中个体的某种字符串形式的编码表示v染色体以字符串来表示染色体以字符串来表示v基因是字符串中的一个个字符基因是字符串中的一个个字符第26页，共109页，编辑于2022年，星期四5.1.1遗传算法的基本机理遗传算法的基本机理5.1 5.1 遗传算法遗传算法遗传算法的基本概念遗传算法的基本概念v编码与解码编码与解码v将问题结构变换为位串形式编码表示的过程叫将问题结构变换为位串形式编码表示的过程叫编码编码；v将位串形式编码表示变换为原问题结构的过程叫将位串形式编码表示变换为原问题结构的过程叫解码或解码或译码译码。第27页，共109页，编辑于2022年，星期四vHuffma
25、n编码方法是一种效率高、方法简编码方法是一种效率高、方法简单的编码。单的编码。信源中符号出现的概率相差越大，信源中符号出现的概率相差越大，Huffman编码效果越好。编码效果越好。哈夫曼（哈夫曼（Huffman）编码）编码lHuffman编码编码一般可将数据压缩一般可将数据压缩20%至至90%，其压缩效率取决于被压缩数据的其压缩效率取决于被压缩数据的特征。特征。第28页，共109页，编辑于2022年，星期四 （1）把把信信源源符符号号xi(i=1,2,N)按按出出现现概概率率的的值值由由小小到大的顺序排列到大的顺序排列；Huffman编码步骤编码步骤（2）对对两两个个概概率率最最小小的的符符号
26、号分分别别分分配配以以“0”和和“1”，然然后后把把这这两两个个概概率率相相加加作作为为一一个个新新的的辅辅助助符符号号的的概概率；率；（3）将将这这个个新新的的辅辅助助符符号号与与其其他他符符号号一一起起重重新新按按概概率率大小顺序排列；大小顺序排列；（4）跳到第）跳到第2步，步，直到出现概率相加为直到出现概率相加为1为止为止；第29页，共109页，编辑于2022年，星期四Huffman编码步骤编码步骤 （5）用线将符号连接起来，从而得到一个码树，）用线将符号连接起来，从而得到一个码树，树的树的N个端点对应个端点对应N个信源符号个信源符号；（6）从最后一个概率为）从最后一个概率为1的节点开始
27、，沿着到的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码达信源的每个符号，将一路遇到的二进制码“0”或或“1”顺序排列起来，就是顺序排列起来，就是端点所对应的信源符号端点所对应的信源符号的码字的码字。第30页，共109页，编辑于2022年，星期四 Huffman编码方法编码方法v例如例如：信源符号分布为：信源符号分布为：a:4/22b:3/22c:2/22d:1/22e:5/22f:7/22v排序为：排序为：d,c,b,a,e,f1/222/223/224/225/227/22第31页，共109页，编辑于2022年，星期四Huffman编码方法编码方法cbafe10f=11e=01a=
28、00b=101c=1001d=1000d10101010第32页，共109页，编辑于2022年，星期四哈夫曼解码哈夫曼解码 在在通通信信中中，若若将将字字符符用用哈哈夫夫曼曼编编码码形形式式发发送送出出去去，对对方方接接收收到到编编码码后后，将将编编码码还还原原成成字字符符的的过过程程，称为称为哈夫曼解（译）码哈夫曼解（译）码。解码解码:从根结点起，每输入一个数码即沿二叉树从根结点起，每输入一个数码即沿二叉树下移一层，数码为下移一层，数码为0时移向左分支，数码为时移向左分支，数码为1时移向右时移向右分支，待达到叶子结点时即译出一个字符，再输入的分支，待达到叶子结点时即译出一个字符，再输入的数码
29、又从根结点开始重新做起。反复由根出发，直到数码又从根结点开始重新做起。反复由根出发，直到译码完成。译码完成。第33页，共109页，编辑于2022年，星期四5.1.1遗传算法的基本机理遗传算法的基本机理5.1 5.1 遗传算法遗传算法遗传算法的基本概念遗传算法的基本概念v遗传操作遗传操作（GeneticOperator）：遗传操作是指作用于）：遗传操作是指作用于种群而产生新的种群的操作。种群而产生新的种群的操作。v包括以下包括以下3种基本形式种基本形式：v选择（选择（Selection）v交叉（交叉（Crosssover）v变异（变异（Mutation）第34页，共109页，编辑于2022年，星
30、期四5.1.1遗传算法的基本机理遗传算法的基本机理5.1 5.1 遗传算法遗传算法遗传算法的基本概念遗传算法的基本概念遗传操作遗传操作v选择操作选择操作也叫也叫复制复制（reproduction）操作操作，根据，根据个体的适应度函数值所度量的优劣程度决定它在个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。下一代是被淘汰还是被遗传。v交叉操作交叉操作的简单方式是将被选择出的两个个体的简单方式是将被选择出的两个个体P1和和P2作为父母个体，将两者的部分码值进行交换。作为父母个体，将两者的部分码值进行交换。v变异操作变异操作的简单方式是改变数码串的某个位置上的的简单方式是改变数码
31、串的某个位置上的数码。二进制编码表示的简单变异操作是将数码。二进制编码表示的简单变异操作是将0与与1互互换：换：0变异为变异为1，1变异为变异为0。第35页，共109页，编辑于2022年，星期四选择算子选择算子v模拟生物界优胜劣汰的自然选择法则的一种染色体运算模拟生物界优胜劣汰的自然选择法则的一种染色体运算v从种群中选择适应度较高的染色体进行复制，以生成下一代从种群中选择适应度较高的染色体进行复制，以生成下一代种群种群算法算法：v个体适应度计算个体适应度计算v在被选集中每个个体具有一个选择概率在被选集中每个个体具有一个选择概率v选择概率取决于种群中个体的适应度及其分布选择概率取决于种群中个体的
32、适应度及其分布v个体适应度计算，即个体选择概率计算个体适应度计算，即个体选择概率计算v个体选择方法个体选择方法 按照适应度进行父代个体的选择按照适应度进行父代个体的选择第36页，共109页，编辑于2022年，星期四交叉算子交叉算子v交换、交配、杂交交换、交配、杂交v互换两个染色体某些位上的基因互换两个染色体某些位上的基因v随机化算子，生成新个体随机化算子，生成新个体变异算子变异算子v突变突变v改变染色体某个改变染色体某个/些位上的基因些位上的基因v随机化算子，生成新个体随机化算子，生成新个体v次要算子，但在恢复群体中失去的次要算子，但在恢复群体中失去的多样性多样性方面具有潜在方面具有潜在的作用
33、的作用第37页，共109页，编辑于2022年，星期四生物进化与遗传算法之间的对应关系生物进化与遗传算法之间的对应关系 生物进化中的概念遗传算法中的作用环境适应性适者生存个体染色体基因种群(群体)交叉变异第38页，共109页，编辑于2022年，星期四生物进化与遗传算法之间的对应关系生物进化与遗传算法之间的对应关系 生物进化中的概念遗传算法中的作用环境适应函数适应性函数适应值适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素种群(群体)根据适应函数选择的一组解交叉以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程第39页，共109页，编辑于2022
34、年，星期四5.1.2遗传算法的求解步骤遗传算法的求解步骤遗传算法的主要特点遗传算法的主要特点5.1 5.1 遗传算法遗传算法(1)遗遗传传算算法法利利用用目目标标函函数数的的适适应应度度这这一一信信息息而而非非利利用导数或其它辅助信息来指导搜索；用导数或其它辅助信息来指导搜索；(2)遗遗传传算算法法利利用用选选择择、交交叉叉、变变异异等等算算子子而而不不是是利用确定性规则进行随机操作。利用确定性规则进行随机操作。第40页，共109页，编辑于2022年，星期四第41页，共109页，编辑于2022年，星期四第42页，共109页，编辑于2022年，星期四遗传算法遗传算法v对种群中的染色体反复做三种遗
35、传操作对种群中的染色体反复做三种遗传操作v使其朝着使其朝着适应度增高的方向不断更新换代适应度增高的方向不断更新换代，直至出现了适应度满足目标条件的染色体直至出现了适应度满足目标条件的染色体为止为止第43页，共109页，编辑于2022年，星期四遗传算法参数遗传算法参数v种群规模种群规模种群的大小，用染色体个数表示种群的大小，用染色体个数表示v最大换代数最大换代数种群更新换代的上限，也是算法终止一个条件种群更新换代的上限，也是算法终止一个条件v交叉率交叉率Pcv参加交叉运算的染色体个数占全体染色体总数的比例参加交叉运算的染色体个数占全体染色体总数的比例v取值范围：取值范围：0.4-0.99v变异率
36、变异率Pmv发生变异的基因位数占全体染色体的基因总位数的比例发生变异的基因位数占全体染色体的基因总位数的比例v取值范围：取值范围：0.0001-0.1v染色体编码染色体编码长度长度L 第44页，共109页，编辑于2022年，星期四第45页，共109页，编辑于2022年，星期四第46页，共109页，编辑于2022年，星期四第47页，共109页，编辑于2022年，星期四遗传算法流程图遗传算法流程图(1)初始化群体初始化群体;5.1 5.1 遗传算法遗传算法(2)计算群体上每个个体的适应度值计算群体上每个个体的适应度值;(3)按按由由个个体体适适应应度度值值所所决决定定的的某某个个规规则则选选择择将
37、将进进入入下下一代的个体一代的个体;(4)按概率按概率Pc进行交叉操作进行交叉操作;(5)按概率按概率Pc进行变异操作进行变异操作;(6)若若没没有有满满足足某某种种停停止止条条件件，则则转转第第(2)步步，否否则则进进入入下下一步。一步。(7)输输出出群群体体中中适适应应度度值值最最优优的的染染色色体体作作为为问问题题的的满满意意解或最优解。解或最优解。第48页，共109页，编辑于2022年，星期四vGA算法框图算法框图第49页，共109页，编辑于2022年，星期四一般遗传算法的主要步骤如下：一般遗传算法的主要步骤如下：(1)随随机机产产生生一一个个由由确确定定长长度度的的特特征征字字符符串
38、串组组成成的的初初始始群体。群体。5.1 5.1 遗传算法遗传算法(2)对对该该字字符符串串群群体体迭迭代代地地执执行行下下面面的的步步骤骤和和，直直到到满足停止标准：满足停止标准：计算群体中每个个体字符串的适应值；计算群体中每个个体字符串的适应值；应用应用选择、交叉、变异选择、交叉、变异等遗传算子产生下一代群体。等遗传算子产生下一代群体。(3)把把在在后后代代中中出出现现的的最最好好的的个个体体字字符符串串指指定定为为遗遗传传算算法法的执行结果的执行结果，这个结果可以表示问题的一个解。，这个结果可以表示问题的一个解。第50页，共109页，编辑于2022年，星期四产生初始群体产生初始群体是否满
39、足停止准则是否满足停止准则计算每个个体的适应值计算每个个体的适应值i=M?GEN:=GEN+1依概率选择遗传操作依概率选择遗传操作执行复制执行复制选择一个个体选择一个个体i:=i+1选择两个个体选择两个个体选择一个个体选择一个个体执行变异执行变异i:=0GEN:=0复制到新群体复制到新群体i:=i+1将两个后代插入新群体将两个后代插入新群体插入到新群体插入到新群体执行杂交执行杂交指定结果指定结果结束结束是是否否是是否否变异变异复制复制交叉交叉5.1 5.1 遗传算法遗传算法流程图流程图第51页，共109页，编辑于2022年，星期四第52页，共109页，编辑于2022年，星期四第53页，共109
40、页，编辑于2022年，星期四例：求函数的最大值例：求函数的最大值第54页，共109页，编辑于2022年，星期四第55页，共109页，编辑于2022年，星期四例：求函数的最大值例：求函数的最大值v其中其中x为为0,31间的整数间的整数v编码：采用二进制形式编码编码：采用二进制形式编码v由于由于x的定义域是的定义域是0,31间的整数，刚好可以用间的整数，刚好可以用5位二进位二进制数表示，因此可以用制数表示，因此可以用5位二进制数表示该问题的解，位二进制数表示该问题的解，即染色体。如即染色体。如00000表示表示x0，10101表示表示x21，11111表示表示x31等等第56页，共109页，编辑于
41、2022年，星期四问题问题：求：求（1）编码编码：此时取均长为此时取均长为5，每个染色体，每个染色体（2）初始群体生成初始群体生成：群体大小视情况而定，此处设置：群体大小视情况而定，此处设置为为4，随机产生四个个体：，随机产生四个个体：编码：编码：01101，11000，01000，10011解码：解码：1324819适应度：适应度：16957664361（3）适应度评价适应度评价：第57页，共109页，编辑于2022年，星期四第58页，共109页，编辑于2022年，星期四（4）选择选择：选择概率：选择概率个体：个体：01101，11000，01000，10011适应度：适应度：1695766
42、4361选择概率：选择概率：0.140.490.060.31选择结果：选择结果：01101，11000，11000，10011（5）交叉操作交叉操作：发生交叉的概率较大，变异概率很小。哪两个个体配对：发生交叉的概率较大，变异概率很小。哪两个个体配对交叉是随机的。交叉是随机的。交叉点位置的选取是随机的（单点交叉）交叉点位置的选取是随机的（单点交叉）0110101100110001101111000110011001110000假设采用假设采用轮盘式选择轮盘式选择个体，四个个体依次选中次数为个体，四个个体依次选中次数为1，2，0，1。染染色体色体11001在种群中出现了在种群中出现了2次，次，而原
43、染色体而原染色体01000则因适应值太小而被则因适应值太小而被淘汰淘汰。第59页，共109页，编辑于2022年，星期四第60页，共109页，编辑于2022年，星期四第61页，共109页，编辑于2022年，星期四轮盘式选择轮盘式选择v首先计算每个个体首先计算每个个体i被选中的被选中的概率概率v然后根据概率的大小将圆盘分然后根据概率的大小将圆盘分为为n个扇形。选择时转动轮盘，个扇形。选择时转动轮盘，参考点参考点r落到扇形落到扇形i，则选择个，则选择个体体i。.p1p2pir第62页，共109页，编辑于2022年，星期四 从统计角度看，从统计角度看，个体的适应度值越大个体的适应度值越大，其对应的扇区
44、的面积越大，被选中的可能性也越其对应的扇区的面积越大，被选中的可能性也越大。大。这种方法有点类似于发放奖品使用的轮盘，这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦被称为并带有某种赌博的意思，因此亦被称为赌轮选赌轮选择择。第63页，共109页，编辑于2022年，星期四第64页，共109页，编辑于2022年，星期四交叉操作交叉操作交叉（交叉（Crossover）操作）操作是指按照某种方式对选择的父是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新代个体的染色体的部分基因进行交配重组，从而形成新的个体。的个体。交配重组交配重组是自然界中生物遗传进化的一个
45、主要环节，也是是自然界中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最主要方法。遗传算法中产生新的个体的最主要方法。基本遗传操作基本遗传操作第65页，共109页，编辑于2022年，星期四单点交叉单点交叉单点交叉也称简单交叉，单点交叉也称简单交叉，它是先在两个父代个体的编码串中随它是先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体。假设两个父分的基因进行交换，并生成子代中的两个新的个体。假设两个父代的个体串分别是：代的个体串分别是：X=x1x2xkx
46、k+1xnY=y1y2ykyk+1yn随机选择第随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方位为交叉点，若采用对交叉点后面的基因进行交换的方法，交叉后生成的两个新的个体是：法，交叉后生成的两个新的个体是：X=x1x2xkyk+1ynY=y1y2ykxk+1xn第66页，共109页，编辑于2022年，星期四例例设有两个父代的个体串设有两个父代的个体串A=001101和和B=110010，若随机交叉点为，若随机交叉点为4，则交叉后生，则交叉后生成的两个新的个体是：成的两个新的个体是：A=001110B=110001第67页，共109页，编辑于2022年，星期四（4）选择选择：选择概
47、率：选择概率个体：个体：01101，11000，01000，10011适应度：适应度：16957664361选择概率：选择概率：0.140.490.060.31选择结果：选择结果：01101，11000，11000，10011（5）交叉操作交叉操作：发生交叉的概率较大，变异概率很小。哪两个个体配：发生交叉的概率较大，变异概率很小。哪两个个体配对交叉是随机的。对交叉是随机的。交叉点位置的选取是随机的（单点交叉）交叉点位置的选取是随机的（单点交叉）0110101100110001101111000110011001110000假设采用假设采用轮盘式选择轮盘式选择个体，四个个体依次选中次数为个体，四
48、个个体依次选中次数为1，2，0，1。染色体染色体11001在种群中出现了在种群中出现了2次，次，而原染色体而原染色体01000则因适应值太小而则因适应值太小而被淘汰被淘汰。第68页，共109页，编辑于2022年，星期四（6）变异变异：发生变异的概率很小。假设本次没有发生变异，：发生变异的概率很小。假设本次没有发生变异，则变异前的种群即为进化后所得到的第则变异前的种群即为进化后所得到的第1代种群。代种群。（7）新群体的产生新群体的产生：保留上一代最优个体，一般为保留上一代最优个体，一般为10%左右，至少左右，至少1个个用新个体取代旧个体，随机取代或择优取代。用新个体取代旧个体，随机取代或择优取代
49、。11000，11011，11001，10011（8）重复上述操作。）重复上述操作。第69页，共109页，编辑于2022年，星期四第70页，共109页，编辑于2022年，星期四第71页，共109页，编辑于2022年，星期四第72页，共109页，编辑于2022年，星期四说明：说明：GA的终止条件一般人为设置；的终止条件一般人为设置；GA只能求次优解或满意解。只能求次优解或满意解。分析：分析：按第二代新群体进行遗传操作，按第二代新群体进行遗传操作，若无变异，永远也若无变异，永远也找不到最优解找不到最优解择优取代有问题。择优取代有问题。若随机地将个体若随机地将个体01101选入新群体中，选入新群体中
50、，有可能找到最有可能找到最优解。优解。在经过编码以后，在经过编码以后，遗传算法遗传算法几乎不需要任何与问题几乎不需要任何与问题有关的知识，有关的知识，唯一需要的信息是适应值的计算唯一需要的信息是适应值的计算。也不需要。也不需要使用者对问题有很深入的了解和求解技巧，使用者对问题有很深入的了解和求解技巧，通过选择、通过选择、交叉和变异等简单的操作求解复杂的问题，交叉和变异等简单的操作求解复杂的问题，是一个比较通是一个比较通用的优化算法。用的优化算法。第73页，共109页，编辑于2022年，星期四收敛性定理收敛性定理 如果在代的进化过程中，如果在代的进化过程中，遗传算法遗传算法每次保每次保留到目前为