人工智能第3章遗传算法38课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,人 工 智 能,Artificial Intelligence (AI),2024/10/2,人 工 智 能2022/10/10,3.4,遗传算法,生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境 。,2024/10/2,3.4 遗传算法生物群体的生存过程普遍遵循达尔文的物竞天择,遗传算法,是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一个数学仿真，属于进化计算中的一类方法。,2024/10/2,遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一,串码,：表示染色体或者个体,适应度函数,：表示一个染色体的适应能力，其最大值或者最小值就是最优化问题的解,2024/10/2,串码：表示染色体或者个体2022/10/10,一、,遗传算法的基本机理,二、遗传算法的求解步骤,三、遗传算法的收敛性（略）,2024/10/2,一、 遗传算法的基本机理2022/10/10,一、遗传算法的基本机理,1,编码与解码,2,适应度函数,3,遗传操作,2024/10/2,一、遗传算法的基本机理2022/10/10,1,编码与解码,在遗传算法中，为了模仿遗传学的遗传规律，必须对问题的解的结构进行,编码,，运行,遗传算法,后，再通过,解码,得到问题的解。,编码,解码,遗传算法,问题,2024/10/2,1 编码与解码在遗传算法中，为了模仿遗传学的遗传规律，必须,编码,：将问题解的结构转换成位串形式编码的过程,解码,：将位串形式编码转化成问题的解的过程,染色体,（个体）：位串形式编码,2024/10/2,编码：将问题解的结构转换成位串形式编码的过程2022/10/,编码与解码方法,：,二进制码方法,浮点数方法,符号方法,格雷码方法,2024/10/2,编码与解码方法：2022/10/10,二进制码方法,编码方法,：将参数的取值范围分成等长的,2,l, 1,部分，再用,l,个二进制来编码每一个等分，共有,2,l,种不同的编码。,2024/10/2,二进制码方法编码方法：将参数的取值范围分成等长的 2l ,假设,x,A, B,每一个部分的长度为,l,2,00,A,01,A,+,10,A,+2,11,A,+3,=B,A,B,2024/10/2,假设 x A, B, 每一个部分的长度为l200,解码方法,：,如果某一个体的编码为：,X,=,x,l,x,l,-1,x,2,x,1,解码公式为,2024/10/2,解码方法：如果某一个体的编码为：2022/10/10,特点,：,编码与解码简单,码串比较长,搜索空间是有限的，提高解的精度，必须加大码长,求解多个参数时，将所有的码拼接起来,2024/10/2,特点：2022/10/10,符号方法,：个体编码中的基因值只取代码含义的符号集,例,：,TSP,问题，按照一个回路中城市的序号进行编码,相互之间不能相同,2024/10/2,符号方法：个体编码中的基因值只取代码含义的符号集例：TSP问,2,适应度函数,适应度函数,：度量染色体优劣程度的函数，体现自然进化中的优胜劣汰原则。对于优化问题，适应度函数就是目标函数。,2024/10/2,2 适应度函数适应度函数：度量染色体优劣程度的函数，体现自,例,：对于,TSP,问题，要求总路径长度为最小，适应度函数可以定义为,最小化,最大化,其中，,w,n,+1,=,w,1,d,(,w,j,w,j,+1,),：两个城市之间的距离,2024/10/2,例：对于TSP问题，要求总路径长度为最小，适应度函数可以定义,3,遗传操作,三种简单的遗传操作,：,选择（,Selection,）,交叉（,Crossover,）,变异（,Mutation,）,2024/10/2,3 遗传操作三种简单的遗传操作：2022/10/10,选择操作（复制操作）,：根据,适应度函数值,所度量的,个体,的优劣程度决定此,个体,在下一代是被,淘汰,或是,被遗,。一般情况下，如果是求最大值，适应度函数值大的,个体,具有较大的,生存机会,。,2024/10/2,选择操作（复制操作）：根据适应度函数值所度量的个体的优劣程度,交叉操作,：选出两个个体作为父母个体，将两种的,部分码值,进行交换。,例,：,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,0,1,1,1,1,0,1,1,1,1,0,2024/10/2,交叉操作：选出两个个体作为父母个体，将两种的部分码值进行交换,变异操作,：改变数码串上的某一个位置的数码。,例,1,0,1,0,0,1,1,0,1,0,1,1,0,1,1,0,2024/10/2,变异操作：改变数码串上的某一个位置的数码。例10100110,二、遗传算法的求解步骤,1,遗传算法的特点,通过编码使得,解空间,是,有限,的，所有遗传算法是一种基于,空间搜索,的求解技术，通过自然,选择,、,交叉,、,变异,等操作以及达尔文的,适者生存,的理论，模拟自然进化过程来寻找问题的解。,2024/10/2,二、遗传算法的求解步骤1 遗传算法的特点2022/10/1,现在将,遗传算法,看成为一种现代的优化技术，但是不一定能找到问题的,全局最优解,。通过一定的手段，可以将误差控制在,容许的范围,内（以很大的概率找到全局最优解）。,最优解,2024/10/2,现在将遗传算法看成为一种现代的优化技术，但是不一定能找到问题,特点,：,对参数集合的编码进行进化，不是参数本身进行进化,从问题解的编码组（群体）开始，不是从单个解开始搜索,只利用适应度函数（目标函数），不需要导数等信息,只利用选择、交叉、变异等操作，不需要利用确定性规则进行随机操作,2024/10/2,特点：2022/10/10,2,遗传算法的框图,遗传算法的基本思想,：通过,随机方式,产生若干个个体，形成一个,初始种群,；利用适应度函数计算它们的,适应度函数值,，,淘汰,适应度小的个体，选择适应度高的,个体,参加遗传操作；经过遗传操作后的个体形成下一代,种群,，再对新的种群进行新的一轮,进化,。,2024/10/2,2 遗传算法的框图遗传算法的基本思想：通过随机方式产生若干,基本思想,简单的遗传算法,基本的遗传算法,复杂的遗传算法,2024/10/2,基本思想简单的遗传算法基本的遗传算法复杂的遗传算法2022/,简单遗传算法的步骤,：,初始化种群,计算种群中每一个个体的适应度函数值,根据与适应度相关联的规则确定进入下一轮的个体,2024/10/2,简单遗传算法的步骤：2022/10/10,按照某一个概率进行交叉操作,按照某一个概率进行变异操作,如果不满足终止条件，则转到,(2),，否则继续,将种群中适应度最优的个体作为问题的解,2024/10/2,按照某一个概率进行交叉操作2022/10/10,开始,初始化种群,计算适应度值,选择操作,交叉操作,变异操作,终止条件？,选取适应度最优个体作为解,结束,是,2024/10/2,开始初始化种群计算适应度值选择操作交叉操作变异操作终止条件？,算法可定义为一个8元组：,C,-,个体的编码方法；,E,-,个体适应度评价函数；,P,0,-,初始群体；,M,-,群体大小；,-选择算子；,-交叉算子； -变异算子,T,-,遗传运算终止条件。,2024/10/2,C-个体的编码方法；2022/10/10,例,用遗传算法求解优化问题,其中 为整数。,(1)确定初始种群,通过随机的方法来产生染色体的数字串，并组成初始种群。例如，为得到数字串的某位,又称之为基因,(genes),，使用计算机在,0,1,之间产生随机数,K,，并按照数,K,的变化区域来规定基因代码如下：,0,， （,0,K,0.5,）,1,， （,0.5,K,1,）,G =,2024/10/2,例 用遗传算法求解优化问题其中 为整数。(1)确定, 参数编码,将整数 x,0,1,31作为参数，采用二进制进行编码：,X=0,00000，, x=31,11111, 随机生成,例如: 01001； 11001；, 01000； 10011。,2024/10/2,2022/10/10,(2)选择,根据“适者生存”的自然选择原理,从初始种群中选择生命力强的个体(适者)产生新的种群, 确定适应度函数,适应度函数取为非负函数,且适应度增大的方向对应于目标函数的优化方向,本例取适应度函数 fitness(X)=x, 计算适应度和选择率,将初始种群的个体解码为X,并计算适应度f(X)及选择率f/,其中为适应度之和.,2024/10/2,(2)选择2022/10/10,选择适应值大的串作为母本,，使在下一代中有更多的机会繁殖其子孙。,要在四个种子个体中做选择，要求仍然得到四个染色体，可依据适应度概率比例制定如下规则：,低于,0.125,以下的染色体被淘汰；,在,0.125,0.375,之间的染色体被复制一个；,在,0.375,0.625,之间的染色体被复制两个；,在,0.625,0.875,之间的染色体被复制三个；,在,0.875,以上的染色体可复制四个。,2024/10/2,选择适应值大的串作为母本，使在下一代中有更多的机会繁殖其子孙,2024/10/2,2022/10/10, 随机选择适者个体,采用,轮盘法,，对初始种群进行选择，使得最优秀的个体获得最多的生存繁殖机会。,49.2,30.9%,14.4%,5.5%,01101,11000,11000,10011,2024/10/2, 随机选择适者个体49.230.9%14.4%5.5%0,(3),交叉,将选择出的个体存入交配池中，用,随机方法,配对交叉，以产生新一代的个体, 随机选择配对； 随机选择交叉点；, 采用单点交叉，产生新的种群,2024/10/2,(3)交叉2022/10/10,(4) 变异,在交叉过程中，可能丢失一些重要的遗传信息(特定位置的1与0 )，因而产生变异。为了获得新的遗传信息，则需引入适度的变异。,设变异概率取为,0.001,则对于种群总共有,20,个基因位,.,期望的变异串位数计算,:200.001 =0.02(,位,),故一般来说,该例中可无基因位数值的改变,.,2024/10/2,(4) 变异设变异概率取为0.001,则对于种群总共有20,2024/10/2,2022/10/10,