遗传算法介绍课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 基于遗传算法的随机优化搜索,第,4,章 基于遗传算法的随机优化搜索,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 基于遗传算法的随机优化搜索,4.1,基本概念,4.2,基本遗传算法,4.3,遗传算法应用举例,4.4,遗传算法的特点与优势,1,第4章 基于遗传算法的随机优化搜索4.1 基本概念1,4.1,基本概念,1.,个体与种群,个体就是模拟生物个体而对问题中的对象,（一般就是问题的解）的一种称呼，一个个,体也就是搜索空间中的一个点。,种群,(population),就是模拟生物种群而由若,干个体组成的群体,它一般是整个搜索空间,的一个很小的子集。,2,4.1 基本概念 2,2.,适应度与适应度函数,适应度,(fitness),就是借鉴生物个体对环境的,适应程度,而对问题中的个体对象所设计的,表征其优劣的一种测度。,适应度函数,(fitness function),就是问题中的,全体个体与其适应度之间的一个对应关系。,它一般是一个实值函数。该函数就是遗传算,法中指导搜索的评价函数。,3,2.适应度与适应度函数3,3.,染色体与基因,染色体（,chromosome,）就是,问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因,（,gene,）。,例如：,个体 染色体,9,-,1001,（,2,，,5,，,6,）,-,010 101 110,4,3.染色体与基因4,4.,遗传操作,亦称遗传算子,(genetic operator),，就是,关于染色体的运算。遗传算法中有三种遗传操作,:,选择,-,复制,(selection-reproduction),交叉,(crossover,，,亦称交换、交配或杂交,),变异,(mutation,，,亦称突变,),5,4.遗传操作5,选择,-,复制,通常做法是：对于一个规模为,N,的种群,S,按每个染色体,x,i,S,的选择概率,P,(,x,i,),所决定的选中机会,分,N,次从,S,中随机选定,N,个染色体,并进行复制。,这里的选择概率,P,(,x,i,),的计算公式为,6,选择-复制通常做法是：对于一个规模为N的种群S,按每个,交叉,就是互换两个染色体某些位上的基因。,s,1,=01000101,s,2,=10011011,可以看做是原染色体,s,1,和,s,2,的子代染色体。,例如,设染色体,s,1,=01001011,s,2,=10010101,交换其后,4,位基因,即,7,交叉 就是互换两个染色体某些位上的基因。,变异,就是改变染色体某个,(,些,),位上的基因。,例如,设染色体,s,=11001101,将其第三位上的,0,变为,1,即,s,=11,0,01101,11,1,01101=,s,。,s,也可以看做是原染色体,s,的子代染色体。,8,变异 就是改变染色体某个(些)位上的基因。8,4.2,基本遗传算法,遗传算法基本流程框图,生成初始种群,计算适应度,选择,-,复制,交叉,变异,生成新一代种群,终止,?,结束,9,4.2 基本遗传算法 遗传算法基本流程框图生成初始种群计,算法中的一些控制参数：,种群规模,最大换代数,交叉率,(crossover rate),就是参加交叉运算的染色体个数占全体染色体总数的比例，,记为,P,c,取值范围一般为,0.4,0.99,。,变异率,(mutation rate),是指发生变异的基因位数所占,全体染色体的基因总位数,的比例，,记为,P,m,，取值范围一般为,0.0001,0.1,。,10,算法中的一些控制参数：10,基本遗传算法,步,1,在搜索空间,U,上定义一个适应度函数,f,(,x,),，给定种群规模,N,，交叉率,P,c,和变异率,P,m,，代数,T,；,步,2,随机产生,U,中的,N,个个体,s,1,s,2,s,N,，组成初始种群,S,=,s,1,s,2,s,N,，置代数计数器,t,=1,；,步,3,计算,S,中每个个体的适应度,f(),；,步,4,若终止条件满足，则取,S,中适应度最大的个体作为所求结果，算法结束。,11,基本遗传算法11,步,5,按选择概率,P,(,x,i,),所决定的选中机会，,每次从,S,中随机选定,1,个,个体并将其染色体复制，共做,N,次,，然后将复制所得的,N,个染色体组成群体,S,1,；,步,6,按交叉率,P,c,所决定的参加交叉的染色体数,c,，从,S,1,中随机确定,c,个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体,S,2,；,12,步5 按选择概率P(xi)所决定的选,步,7,按变异率,P,m,所决定的变异次数,m,，从,S,2,中随机确定,m,个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体,S,3,；,步,8,将群体,S,3,作为新一代种群，即用,S,3,代替,S,，,t,=,t,+1,，转步,3,；,13,步7 按变异率Pm所决定的变异次数m，从S2中随机确定,4.3,遗传算法应用举例,例,4.1,利用遗传算法求解区间,0,31,上的二次函数,y,=,x,2,的最大值。,y,=,x,2,31,X,Y,14,4.3 遗传算法应用举例 例4.1 利用遗传算法求解区间,分析,原问题可转化为在区间,0,31,中搜索能使,y,取最大值的点,a,的问题。那么，,0,31,中的点,x,就是个体,函数值,f,(,x,),恰好就可以作为,x,的适应度，区间,0,31,就是一个,(,解,),空间。这样,只要能给出个体,x,的适当染色体编码,该问题就可以用遗传算法来解决。,15,分析 15,解,(1),设定种群规模,编码染色体，,产生初始种群。,将种群规模设定为,4,；,用,5,位二进制数编码染色体；取下列个体组成,初始种群,S,1,:,s,1,=13(01101),s,2,=24(11000),s,3,=8(01000),s,4,=19(10011),(2),定义适应度函数,取适应度函数：,f,(,x,)=,x,2,16,解16,(3),计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体,(,即,31,（,11111,）,),出现为止。,17,(3)计算各代种群中的各个体的适应度,并对其染色体进,首先计算种群,S,1,中各个体,s,1,=13(01101),s,2,=24(11000),s,3,=8(01000),s,4,=19(10011),的适应度,f,(,s,i,),。,容易求得,f,(,s,1,)=,f,(13)=13,2,=169,f,(,s,2,)=,f,(24)=24,2,=576,f,(,s,3,)=,f,(8)=8,2,=64,f,(,s,4,)=,f,(19)=19,2,=361,18,首先计算种群S1中各个体18,再计算种群,S,1,中各个体的选择概率。,选择概率的计算公式为,由此可求得,P,(,s,1,)=,P,(13)=0.14,P,(,s,2,)=,P,(24)=0.49,P,(,s,3,)=,P,(8)=0.06,P,(,s,4,)=,P,(19)=0.31,19,再计算种群S1中各个体的选择概率。选择概率的计算公式为 由此,赌轮选择示意,s,4,0.31,s,2,0.49,s,1,0.14,s,3,0.0,6,赌轮选择法,20,赌轮选择示意s4s2s1s30.06 赌轮选择,在算法中赌轮选择法可用下面的子过程来模拟,:,在,0,1,区间内产生一个均匀分布的随机数,r,。,若,r,q,1,则染色体,x,1,被选中。,若,q,k,-1,r,q,k,(2,k,N,),则染色体,x,k,被选中。其中的,q,i,称为染色体,x,i,(,i,=1,2,n,),的,积累概率,其计算公式为,21,在算法中赌轮选择法可用下面的子过程来模拟:在,选择,-,复制,设从区间,0,1,中产生,4,个随机数如下,:,r,1,=0.450126,r,2,=0.110347,r,3,=0.572496,r,4,=0.98503,染色体,适应度,选择概率,积累概率,选中次数,s,1,=01101,169,0.14,0.14,1,s,2,=11000,576,0.49,0.63,2,s,3,=01000,64,0.06,0.69,0,s,4,=10011,361,0.31,1.00,1,22,选择-复制 设从区间0,1中产生4个随机数如,于是，经复制得群体：,s,1,=11000,（,24,）,s,2,=01101,（,13,）,s,3,=11000,（,24,）,s,4,=10011,（,19,）,23,于是，经复制得群体：23,交叉,设交叉率,p,c,=100%,，即,S,1,中的全体染色体都参加交叉运算。,设,s,1,与,s,2,配对，,s,3,与,s,4,配对。分别交换后两位基因，得新染色体：,s,1,=11001,（,25,）,s,2,=01100,（,12,）,s,3,=11011,（,27,）,s,4,=10000,（,16,）,24,交叉24,变异,设变异率,p,m,=0.001,。,这样，群体,S,1,中共有,5,4,0.001=0.02,位基因可以变异。,0.02,位显然不足,1,位，所以本轮遗传操作不做变异。,25,变异25,于是，得到第二代种群,S,2,：,s,1,=11001,（,25,）,s,2,=01100,（,12,）,s,3,=11011,（,27,）,s,4,=10000,（,16,）,26,26,第二代种群,S,2,中各染色体的情况,染色体,适应度,选择概率,积累概率,估计的,选中次数,s,1,=11001,625,0.36,0.36,1,s,2,=01100,144,0.08,0.44,0,s,3,=11011,729,0.41,0.85,2,s,4,=10000,256,0.15,1.00,1,27,第二代种群S2中各染色体的情况 染色体 适应度选择概,假设这一轮选择,-,复制操作中，种群,S,2,中的,4,个染色体都被选中,，则得到群体：,s,1,=11001,（,25,）,s,2,=01100,（,12,）,s,3,=11011,（,27,）,s,4,=10000,（,16,）,做交叉运算，让,s,1,与,s,2,，,s,3,与,s,4,分别交换后三位基因，得,s,1,=11100,（,28,）,s,2,=01001,（,9,）,s,3,=11000,（,24,）,s,4,=10011,（,19,）,这一轮仍然不会发生变异。,28,假设这一轮选择-复制操作中，种群S2中的 s1=11,于是，得第三代种群,S,3,：,s,1,=11100,（,28,）,s,2,=01001,（,9,）,s,3,=11000,（,24,）,s,4,=10011,（,19,）,29,于是，得第三代种群S3：29,第三代种群,S,3,中各染色体的情况,染色体,适应度,选择概率,积累概率,估计的,选中次数,s,1,=11100,784,0.44,0.44,2,s,2,=01001,81,0.04,0.48,0,s,3,=11000,576,0.32,0.80,1,s,4,=10011,361,0.20,1.00,1,30,第三代种群S3中各染色体的情况 染色体 适应度选,设这一轮的选择,-,复制结果为：,s,1,=11100,（,28,）,s,2,=11100,（,28,）,s,3,=11000,（,24,）,s,4,=10011,（,19,）,做交叉运算，让,s,1,与,s,4,，,s,2,与,s,3,分别交换后两位基因，得,s,1,=11111,（,31,）,s,2,=11100,（,28,）,s,3,=11000,（,24,）,s,4,=10000,（,16,）,这一轮仍然不会发生变异。,31,设这一轮的选择-复制结果为：做交叉运算，,于是，得第四代种群,S,4,：,s,1,=11111,（,31,）,s,2,=11100,（,28,）,s,3,=11000,（,24,）,s,4,=10000,（,16,）,32,于是，得第四代种群S4：32,显然，在这一代种群中已经出现了适应度最高的染色体,s,1,=11111,。于是，遗传操作终止，将,染色体,“,11111,”,作为最终结果输出。,然后，将染色体,“,11111”,解码为表现型，即得所求的最优解：,31,。,将,31,代入函数,y,=,x,2,中，即得原问题的解，即函数,y,=,x,2,的最大值为,961,。,33,显然，在这一代种群中已经出现了适应度最高的染色体s1=,Y,Y,y,=,x,2,8 13 19 24,X,第一代种群及其适应度,y,=,x,2,12 16 25 27,X,Y,第二代种群及其适应度,y,=,x,2,9 19 24 28,X,Y,第三代种群及其适应度,y,=,x,2,16 24 28 31,X,第四代种群及其适应度,34,YYy=x2 8 13 19 24,例,4.2,用遗传算法求解,TSP,。,分析,由于其任一可能解,一个合法的城市序列，即,n,个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。,35,例 4.2 用遗传算法求解TSP。35,（,1,）定义适应度函数,我们将一个合法的城市序列,s,=,（,c,1,c,2,c,n,c,n+1,）,(,c,n+1,就是,c,1,),作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体,s,的适应度，从而适应度函数就是,36,（1）定义适应度函数36,（,2,）对个体,s,=,（,c,1,c,2,c,n,c,n+1,）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为,如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。,例如，对于,5,个城市的,TSP,，我们用符号,A,、,B,、,C,、,D,、,E,代表相应的城市，用这,5,个符号的序列表示可能解即染色体。,37,（2）对个体s=（c1,c2,cn,cn+1）,然后进行遗传操作。设,s,1,=,（,A,C,B,E,D,A,），,s,2,=,（,A,E,D,C,B,A,）,实施常规的交叉或变异操作，如交换后三位，得,s,1,=,（,A,C,B,C,B,A,），,s,2,=,（,A,E,D,E,D,A,）,或者将染色体,s,1,第二位的,C,变为,E,，得,s,1,=,（,A,E,B,E,D,A,）,可以看出，上面得到的,s,1,，,s,2,和,s,1,都,是非法的城市序列。,38,然后进行遗传操作。设38,为此，对,TSP,必须设计合适的染色体和相应的遗传运算。,事实上，人们针对,TSP,提出了许多编码方法和相应的特殊化了的交叉、变异操作，如,顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异,等等。从而巧妙地用遗传算法解决了,TSP,。,39,为此，对TSP必须设计合适的染色体和相应的遗,4.4,遗传算法的特点与优势,遗传算法的主要特点,遗传算法一般是直接在解空间搜索,而不像图搜索那样一般是在问题空间搜索,最后才找到解。,遗传算法的搜索随机地始于搜索空间的一个点集,而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算法。,40,4.4 遗传算法的特点与优势 遗传算法的主要特点 4,遗传算法总是在寻找优解,而不像图搜索那样并非总是要求优解,而一般是设法尽快找到解,所以遗传算法又是一种优化搜索算法。,遗传算法的搜索过程是从空间的一个点集,(,种群,),到另一个点集,(,种群,),的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索,适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。,41,遗传算法总是在寻找优解,而不像图搜索那样并非,遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验知识。,遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。,42,遗传算法的适应性强,除需知适应度函数外,几乎不需,遗传算法的应用,遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如,TSP,、背包问题）、函数的最大值以及图像处理和信号处理等等。,43,遗传算法的应用43,另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。,44,另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问,对遗传算法的进一步研究将涉及到模式定理和隐性、并行性等内容。有兴趣的同学可参阅有关专著。,45,对遗传算法的进一步研究将涉及到模式定理和隐性,