单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第 4 章 基于遗传算法的随机优化搜索,第4章 基于遗传算法的随机优化搜索,4.1 基本概念,4.2 基本遗传算法,4.3 遗传算法应用举例,4.4 遗传算法的特点与优势,4.1 基本概念,1.个体与种群,个体就是模拟生物个体而对问题中的对象,（一般就是问题的解）的一种称呼，一个个,体也就是搜索空间中的一个点种群(population)就是模拟生物种群而由若,干个体组成的群体,它一般是整个搜索空间,的一个很小的子集2.适应度与适应度函数,适应度,(fitness),就是借鉴生物个体对环境的,适应程度,而对问题中的个体对象所设计的,表征其优劣的一种测度适应度函数,(fitness function),就是问题中的,全体个体与其适应度之间的一个对应关系它一般是一个实值函数该函数就是遗传算,法中指导搜索的评价函数3.染色体与基因,染色体（,chromosome）就是,问题中个体的某种字符串形式的编码表示字符串中的字符也就称为基因,（gene）例如：,个体 染色体,9,-,1001,（2，5，6）,-,010 101 110,4.遗传操作,亦称遗传算子,(genetic operator)，就是,关于染色体的运算。
遗传算法中有三种遗传操作,:,选择,-,复制,(selection-reproduction),交叉,(crossover，,亦称交换、交配或杂交),变异,(mutation，,亦称突变,),选择-复制,通常做法是：对于一个规模为,N,的种群,S,按每个染色体,x,i,S,的选择概率,P,(,x,i,)所决定的选中机会,分,N,次从,S,中随机选定,N,个染色体,并进行复制这里的选择概率,P,(,x,i,),的计算公式为,交叉,就是互换两个染色体某些位上的基因s,1,=01000101,s,2,=10011011,可以看做是原染色体,s,1,和,s,2,的子代染色体例如,设染色体,s,1,=01001011,s,2,=10010101,交换其后4位基因,即,变异,就是改变染色体某个(些)位上的基因例如,设染色体,s,=11001101,将其第三位上的0变为1,即,s,=11,0,01101,11,1,01101=,s,s,也可以看做是原染色体,s,的子代染色体4.2 基本遗传算法,遗传算法基本流程框图,生成初始种群,计算适应度,选择-复制,交叉,变异,生成新一代种群,终止?,结束,算法中的一些控制参数：,种群规模,最大换代数,交叉率,(crossover rate),就是参加交叉运算的染色体个数占全体染色体总数的比例，,记为,P,c,取值范围一般为0.40.99。
变异率,(mutation rate),是指发生变异的基因位数所占,全体染色体的基因总位数,的比例，,记为,P,m,，取值范围一般为0.00010.1基本遗传算法,步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,中适应度最大的个体作为所求结果，算法结束步5,按选择概率,P,(,x,i,)所决定的选中机会，,每次从,S,中随机选定1个,个体并将其染色体复制，共做,N,次,，然后将复制所得的,N,个染色体组成群体,S,1,；,步6,按交叉率,P,c,所决定的参加交叉的染色体数,c,，从,S,1,中随机确定,c,个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体,S,2,；,步7,按变异率,P,m,所决定的变异次数,m,，从,S,2,中随机确定,m,个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体,S,3,；,步8,将群体,S,3,作为新一代种群，即用,S,3,代替,S,，,t,=,t,+1,，转步,3,；,4.3 遗传算法应用举例,例4.1,利用遗传算法求解区间0,31上的二次函数,y,=,x,2,的最大值。
y,=,x,2,31,X,Y,分析,原问题可转化为在区间0,31中搜索能使y取最大值的点,a,的问题那么，0,31 中的点,x,就是个体,函数值,f,(,x,)恰好就可以作为,x,的适应度，区间0,31就是一个(解)空间这样,只要能给出个体,x,的适当染色体编码,该问题就可以用遗传算法来解决解,(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,(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止首先计算种群,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,再计算种群,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,赌轮选择示意,s,4,0.31,s,2,0.49,s,1,0.14,s,3,0.0,6,赌轮选择法,在算法中赌轮选择法可用下面的子过程来模拟:在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,)的,积累概率,其计算公式为,选择-复制,设从区间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,于是，经复制得群体：,s,1,=11000（24）,s,2,=01101（13）,s,3,=11000（24）,s,4,=10011（19）,交叉,设交叉率,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）,变异,设变异率,p,m,=0.001这样，群体,S,1,中共有,5,4,0.001=0.02,位基因可以变异0.02位显然不足1位，所以本轮遗传操作不做变异于是，得到第二代种群,S,2,：,s,1,=11001（25）,s,2,=01100（12）,s,3,=11011（27）,s,4,=10000（16）,第二代种群,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,假设这一轮选择,-,复制操作中，种群,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,）,这一轮仍然不会发生变异。
于是，得第三代种群,S,3：,s,1,=11100（28）,s,2,=01001（9）,s,3,=11000（24）,s,4,=10011（19）,第三代种群,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,设这一轮的选择-复制结果为：,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,）,这一轮仍然不会发生变异于是，得第四代种群,S,4,：,s,1,=11111（31）,s,2,=11100（28）,s,3,=11000（24）,s,4,=10000（16）,显然，在这一代种群中已经出现了适应度最高的染色体,s,1,=11111。
于是，遗传操作终止，将,染色体“,11111,”,作为最终结果输出然后，将染色体“,11111,”解码为表现型，即得所求的最优解：,31,将,31,代入函数,y,=,x,2,中，即得原问题的解，即函数,y,=,x,2,的最大值为,961,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,第四代种群及其适应度,例,4.2,用遗传算法求解TSP分析,由于其任一可能解 一个合法的城市序列，即,n,个城市的一个排列，都可以事先构造出来于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解这正适合用遗传算法求解1）定义适应度函数,我们将一个合法的城市序列,s,=（,c,1,c,2,c,n,c,n+1,）(,c,n+1,就是,c,1,)作为一个个体这个序列中相邻两城之间的距离之和的倒数就可作为相应个体,s,的适应度，从而适应度函数就是,（2）对个体,s,=,（,c,1,c,2,c,n,c,n+1,）进行编码。
但对于这样的个体如何编码却不是一件直截了当的事情因为,如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解例如，对于,5,个城市的,TSP,，我们用符号,A,、,B,、,C,、,D,、,E,代表相应的城市，用这,5,个符号的序列表示可能解即染色体然后进行遗传操作设,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。