第7讲(遗传算法).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,遗传算法的提出,遗传算法是根据自然界“物竞天择、适者生存”的现象而提出的一种随机搜索算法；,20,世纪,70,年代由美国密执根大学的霍兰德（,Holland,）,首先提出的；,遗传算法把优化问题看作是自然界中的生物进化过程，通过模拟大自然中生物进化过程的遗传规律，来达到寻优的目的。,生物进化圈示意图,婚配,选择,变异,子群,种群,群体,遭淘汰,的群体,人类进化图,生物进化的特性,进化过程发生在染色体上，而不是发生在他们所编码的生物体上；,自然选择把染色体以及由他们所译成的结构的表现联系在一起，适应性好的个体染色体比差的染色体有更多的繁殖机会；,繁殖过程发生在进化那一刻。变异可以使生物体子代的染色体不同于他们的父代染色体；通过结合两个父代染色体中的物质，重组过程可以产生在子代中有很大差异的染色体；,生物进化没有记忆。,遗传算法的基本思想,遗传算法通过自然选择中“优胜劣汰”的策略在每次搜索中利用各种随机的遗传算子生成问题一些新的解，淘汰较差的解，保留较好的以及有希望的解，从而不断对搜索空间中新的未知区域进行探索。它有效地利用了许多历史信息，使得搜索每次都向着最好的方向前进。,对优化问题的解进行编码，编码后的一个解称为染色体，组成染色体的元素称为基因；,一个群体由若干染色体组成，染色体的个数称为群体的规模；,用适应度函数表示环境，它是已编码的解的函数，是一个解适应环境程度的评价；适应函数的构造一般与优化问题的指标函数相关；,遗传算法的基本思想,适应函数值大表示所对应的染色体适应环境的能力强，自然选择规律将以适应函数值的大小来决定染色体是否继续生存下去的概率；,生存下来的染色体称为种群，他们中的部分或全部以一定的概率进行交配、繁衍，从而得到下一代群体；,交配是一个生殖过程，发生在两个染色体之间，作为双亲的染色体，交换部分基因后，生殖出两个新的染色体，即问题的新解；,在进化过程中，染色体的某些基因可能会发生变异，即染色体的编码发生了某些变化。一个群体的进化需要染色体的多样性，变异对于保持群体的多样性具有一定的作用。,生物进化与遗传算法之间的对应关系,生物进化中的概念,遗传算法中的作用,环境,适应函数,适应性,适应函数值,适者生存,适应值大的解被保留的概率大,个体,问题的一个解,染色体,解的编码,基因,编码的元素,群体,被选定的一组解,种群,按适应函数选择的一组解（编码表示）,交配,以一定的方式由双亲产生后代的过程,变异,编码的某些分量发生变化的过程,遗传算法的基本模型,（,1,）遗传算法可以形式化地描述如下：,（,2,）表示初始群体；,（,3,）表示长度为,l,的符号串全体，,为字母表；,若使用二进制编码，则 ；,（,4,）,N,为一个正整数，表示种群中含有个体的个数；,（,5,）,l,为一个正整数，表示符号串的长度；,（,6,）表示选择策略；,（,7,）,g,表示遗传算子，通常包括复制算子 、交叉算子,和变异算子 ；,（,8,）,p,表示操作概率，包括复制概率 、交叉概率 和变异概率 ；,（,9,）是适应度函数；,（,10,）是终止准则。,遗传算法的基本操作,简单遗传算法的遗传操作主要有有三种,:,选择,(selection),、,交叉,(crossover),、,变异,(mutation),。,改进的遗传算法大量扩充了遗传操作，以达到更高的效率。,选择操作,实现从群体中选择存活的个体,(,染色体,),。,根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。,交叉操作,的简单方式是将被选择出的两个个体,P,1,和,P,2,作为父母个体，将两者的基因进行交换，产生新个体的染色体。,变异操作,的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将,0,与,1,互换：,0,变异为,1,，,1,变异为,0,。,选择操作,选择概率：,设群体规模为,N,，,F(,x,i,)(,i,=1,N),是,N,个染色体的适应值，则第,i,个染色体被选中的概率由下式计算：,P,(,x,i,)=,F,(,x,i,)/,F(x,j,),“,轮盘赌”选择法：,一个转盘划分为,N,个扇区，每个,x,i,在,转盘上占有一个扇区，扇区的大小与选择概率,P,(,x,i,),成正比。在选择一个染色体时，先转动轮盘，等轮盘停下后，指针指向的区所对应的,x,i,应是被,选中的染色体。,“分组淘汰”,选择法：,设群体规模为,N,，按,P,(,x,i,),由大到小对染色体进行排序，再依次分为相等数目的,k,组，每组按,淘汰,概率,P,i,(,i,=1,.,k,),淘汰本组,染色体，各组剩余者合并为种群,。,淘汰,概率满足：,P,1,P,2,P,k,。,选择操作,“确定性”选择法：,设群体规模为,N,，,一个选择概率为,P,(,x,i,),的染色体被选中的次数的期望值,e,(,x,i,)=,P,(,x,i,)N,。,对于群体中的每一个,x,i,，,首先选择,e,(,x,i,),次，这样共得,e,(,x,j,),个染色体,。再按,e,(,x,i,)-,e,(,x,i,),由小到大,对染色体进行排序，依次取出,N-,e,(,x,j,),个染色体，这样共得到,N,个染色体组成种群。,交配操作,交配操作发生在两个父代染色体之间，经过杂交产生两个具有双亲的部分基因的新染色体。,单点交配：,多点交配：,a,1,a,2,a,i,a,i+,1,a,n,b,1,b,2,b,i,b,i+,1,b,n,a,1,a,2,a,i,b,i+,1,b,n,b,1,b,2,b,i,a,i+,1,a,n,a,1,a,i,a,i+,1,a,j,a,j+,1,a,n,b,1,b,i,b,i+,1,b,j,b,j+,1,b,n,a,1,a,i,b,i+,1,b,j,a,j+,1,a,n,b,1,b,i,a,i+,1,a,j,b,j+,1,b,n,变异操作,变异操作是发生在某一个基因上的随机变化，模拟基因突变现象，有利于保持群体的多样性，但也有很强的破坏作用。,二进制基因的变异操作，可以是简单地按变异概率翻转某一个位，即某位由,0,变,1,，或由,1,变,0,。,字符基因的变异操作将某一个基因字符上的随机地换为任一其他可能基因字符。,序号,种群,是否变异,变异位,新群体,适应值,1,11011,N,11011,729,2,11,0,01,Y,3,11,1,01,841,3,10000,N,10000,256,遗传算法的基本流程,遗传算法的描述,给定群体规模,N,，,交配概率,p,c,和变异概率,p,m,随机生成一个,N,个初始解组成的初始群体；,计算当前初始群体各染色体,x,i,的适应度函数值,F(x,i,),；,如果满足停止准则，则转,10,；,对群体中的每一个染色体,x,i,计算概率,p(x,i,),；,依据概率值从群体中随机选择,N,个染色体，得到种群；,依交配概率,p,c,按交叉算子,O,c,进行交配，其子代进入新的群体，未进行交配的染色体直接复制到新群体中；,依变异概率,p,m,从种群中选择染色体按变异算子,O,m,进行变异，用变异后的染色体代替新群体中的原染色体；,用新群体代替旧群体，,t,=,t,+1,，转,3,进化过程中适应值最大的染色体，经解码后作为最优解输出；,结束。,遗传算法的应用,函数优化问题一般可以直接应用遗传算法进行求解，但是，更多的现实问题中应用遗传算法，首先需要转换为函数优化问题。这些应用中有多个共同问题：,编码问题,适应值函数,交配规则,变异规则,性能评价,用于求解函数优化问题,例如：求函数,f(x),=,x,2,的最大值，其中,x,为,0,，,31,间的整数。,利用遗传算法进行求解，关键要解决如下问题：,编码与解码：染色体由五个二进制位组成，可能的染色体有：,0000011111,共,32,个。,适应度函数：,F(,x,)=,f(x),选择操作：轮盘赌,交配操作：单点交配,变异操作：位翻转,控制参数：,N=4,，,P,c,=100%,P,m,=1%,求解过程：,用于求解函数优化问题,-2,第,0,代：随机生成，设为,01101,11000,01000,10011,从第,0,代中选择产生的种群：,01101,11000,11000,10011,假定按顺序两两交配，即,01101,与,11000,、,11000,与,10011,，产生,4,个新个体为：,01100,，,11001,，,11011,，,10000,作为第,1,代群体。,序号,群体,F,(,x,i,),P,(,x,i,),e,(,x,i,),选中次数,1,01101,169,0.14,0.58,1,2,11000,576,0.49,1.97,2,3,01000,64,0.05,0.22,0,4,10011,361,0.31,1.23,1,用于求解函数优化问题,-2,第,1,代：,01100,，,11001,，,11011,，,10000,从第,1,代中选择产生的种群：,11001,11011,11011,10000,假定按顺序两两交配，即,11001,与,11011,、,11011,与,10000,，产生,4,个新个体为：,11011,，,11101,，,10000,，,11011,作为第,2,代群体。,序号,群体,F,(,x,i,),P,(,x,i,),e,(,x,i,),选中次数,1,01101,144,0.08,0.33,0,2,11001,625,0.36,1.42,1,3,11011,729,0.42,1.66,2,4,10000,256,0.15,0.58,1,用于求解函数优化问题,-2,第,2,代：,11011,，,11101,，,10000,，,11011,从第,2,代中选择产生的种群,:11011,11101,10000,11011,假定按顺序两两交配，即,11011,与,11101,、,10000,与,11011,，产生,4,个新个体为：,11001,，,11111,，,10001,，,11010,作为第,3,代群体。,(,以后过程略,),序号,群体,F,(,x,i,),P,(,x,i,),e,(,x,i,),选中次数,1,11011,729,0.29,1.14,1,2,11101,841,0.33,1.31,1,3,10000,256,0.10,0.40,1,4,11011,729,0.29,1.14,1,编码问题,利用遗传算法进行问题求解首先是表示问题，即将问题的解以适合于遗传算法求解的形式进行编码。,进行编码时，要考虑交配和变异等操作。,采用什么样的编码形式与具体的问题有关。,可以采用二进制编码，简单，但长度大。,也可以采用整数编码、实数编码、符号编码等形式。,例,7.7,函数在实数区间上的最优化问题。,例,7.8,十杆桁架问题。,例,7.9,人工蚁问题。,例,7.10 TSP,问题。,二进制编码,-,求函数的最大值,求函数,f(x),=,x,2,的最大值，其中,x,为,0,，,31,间的整数。,由于,x,的定义域是,0,31,之间的整数，因此可以用五位二进制数表示该问题的解，如用,10101,表示,x,=21,，,0,、,1,为基因。,求函数,f(x)=x,2,的最大值，其中,x,为,0,，,31,间的实数，最大误差为,1/8,。,对于区间,a,b,上的实数，当用,n,位的二进制向量表示时，其最大误差为,(,b,-,a,)/(2,n,-1),所以有,(,b,-,a,)/(2,n,-1)1/8,，,所以需要用,8,位二进制向量来表示。,x,与,8,位二进制向量之间的关系为：,x,=31*(,y,/255),，,其中,y,为,0-255,之间的二进制数。,二进制编码,-,十杆桁架问题,十杆桁架问题如图所示，有,10,个截面积为,A,1,A,2,A,10,。如何设计每个杆的截面使建造这个桁架的材料总费用最小？,假设每个杆的截面积在,0.1,至,10.0,之间，取,16,种可能的值。用,4,位二进制表示截面的面积，即,0000,对应,0.1,1111,对应,10.0,。问题的解是,10,个杆的面积，要用,40,位二进制串表示一个解。例如，该问题的一个染色体为：,0010 1110 0001 0011 1011 0011 1111 0011,0011,1010,100,kg,100,kg,30,30,30,A,2,A,1,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,二进制编码,-,人工蚁问题,人工蚁问题,如图所示，有一人工蚁在,3232,的网格中移动。,二进制编码,-,人工蚁问题,“圣菲轨道”是一条不规则的弯曲轨道，上面放有,89,块食物。轨道上的食物不是连续排放，有些位置是空的。,人工蚁的视力有限，只能看到正面邻格中的是否有食物。它只有四种动作：,00-,不动,01-,左转,90,度,(,原地,),10-,右转,90,度,(,原地,),11-,走进正面相邻的网格中，如果有食物，就吃到该食物,要求设计一个有限状态自动机，该自动机能在有限步内引导人工蚁吃到所有的食物。,二进制编码,-,人工蚁问题,四,状态自动机，容易验证：如果食物是不间断排列，该自动机可以在有限步引导人工蚁吃到所有食物。,00,11,10,01,1/,前进,1/,前进,0/,右转,0/,左转,0/,左转,0/,右转,1/,前进,1/,前进,O,O,O,二进制编码,-,人工蚁问题,自动机可以用状态转换表等价表示。前面的四状态自动机可等价地表示为下表，实际上只要给定了初始状态和表的最后两列，就可以确定该自动机，因此，只要,34,个二制位位即可表示一个四状态自动机，例如：,00 0110 0011 10010011 1101 0011 0010 0011,序号,当前状态,输入,下一,状态,动作,1,00,0,01,10,2,00,1,00,11,3,01,0,10,01,4,01,1,00,11,5,10,0,11,01,6,10,1,00,11,7,11,0,00,10,8,11,1,00,11,二进制编码,-,人工蚁问题,四状态自动机不能解决有间隔的“圣菲轨道”问题，需要更多的状态。,Jefferson,将状态增加到,32,个，状态转换表需要,64,行，动作仍用,2,位表示，因此表示一个自动机需要的二进制位数为：,5+(5+2)*64=453,。,适应值函数是自动机,x,引导人工蚁吃到的食物数，最大值为,89,。,成功求解的参数设置：,N=65535,，,M=200,整数编码,-,旅行商问题,用遗传算法求解旅行商问题，应如何进行编码？,二进制编码,可以用一个矩阵来表示一个可能解。如四城市问题，可用一个,4*4,矩阵来表示一个可能解，将该矩阵展开得到一个,4*4,的二进制向量。对,n,城市问题，则需要一个,n*n,位二进制向量。可能解在整个状态空间中是非常稀疏的，导致求解效率低下。,整数编码,对城市进行编号，每个城市分别用,1,到,n,之间的不同整数表示，,n,个整数的一个排列就代表了,TSP,问题的一个可能解。,适应度函数,为了评价染色体的适应能力，引入了对问题中的每一个染色体都能进行评价的函数，叫,适应度函数,（,fitness function,）。,一般情况下，可以直接选取问题的指标函数作为适应度函数。,例,1,：求,f(x),的最大值问题，可以直接采用,f(x),作为适应度函数，即,F(x),=,f(x),。,例,2,：,TSP,问题，目标是路径总长度最短，因此可以将路径总长度作为,TSP,问题的适应度函数。,适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。,适应度函数,某些情况下，,f(x),在最大值附近的变化可能非常小，以至于很难区分哪个染色体更优，这时应如何定义适应度函数，才能有效反映染色体与最优解染色体的差异,?,非线性加速适应函数,线性加速适应函数,利用染色体指标函数值从小到大的排列号作为适应函数值。,按定义，选择概率计算式为：,二进制编码的交配规则,双亲双子法,参与交配的两个双亲染色体确定后，随机地产生一个交配位，双亲染色体交换各自的交配位后的基因给对方，得到两个子染色体。,变化交配法,随机产生交配位时，排除与双亲一样的交配位。,多交配位法,产生多个交配位进行交配，在交配时采用交配区间交替进行的方法。,双亲单子法,两个染色体交配后只得到一个子染色体。一般选择适应值大的。,二进制交配操作的例子,如下表所示，第,0,代种群为：,01101,11000,11000,10011,。假定交配概率的,100%,，即种群中所有染色体均参与交配，并按顺序两两交配。,交配后得到的子群为：,01100,11001,11011,10000,序号,种群,交配对象,交配位,子代,适应值,1,01101,2,4,01100,144,2,11000,1,4,11001,625,3,11000,4,2,11011,729,4,10011,3,2,10000,256,整数编码的交配规则,-1,整数编码的交配规则必须保持编码的有效性。,下面以,TSP,问题的整数编码为例进行说明,(P318),。,常规交配法,与二进制编码的双亲双子法类似。子代,1,交配位之前的基因采用父代,1,交配位之前的基因，交配位之后的基因从父代,2,中按顺序选取那些没有出现过的基因。,父代,1,：,1,23,4,5,6,7,8,父代,2,：,5,23,7,3,8,4,6,子代,1,：,12345786,子代,2,：,5237,1468,整数编码的交配规则,-2,基于次序的交配法,对于两个选定的父代染色体父代,1,和父代,2,，首先随机地选择一组位置，设父代,1,中所选位置对应的数字从左到右依次为,x,1,x,2,x,k,，,然后从父代,2,中也找到这,k,个数字，并从父代,2,删除，空位置用,x,1,x,2,x,k,依次填入，就得到子代,1,。子代,2,同理。,父代,1,：,1,2,3,4,5,6 7,8,9 10,父代,2,：,5,9,2,4,6,1 10,7,3 8,选 定：*,子代,1,：,2,9,3,4 6 1 10 7,5,8,子代,2,：,1,9,3 4 5,2,6,8,7,10,父代,2,：,b,9,b,4 6 1 10 7,b,b,父代,1,：,1,b,3 4 5,b,b,8,b,10,整数编码的交配规则,基于位置的交配法,对于两个选定的父代染色体父代,1,和父代,2,，首先随机地选择一组位置，对于这些位置上的基因，子代,1,从父代,2,直接得到，子代,1,其他位置的基因，按顺序从父代,1,中选取那些不相重的基因。子代,2,同理。,父代,1,：,1,2,3,4,5,6 7,8,9,父代,2,：,5,9,2,4,6,1 7,3,8,选 定：*,子代,1,：,1,9,2,4,6,5 7,3,8,子代,2,：,9,2,3,4,5,6 1,8,7,整数编码的交配规则,基于部分映射的交配法,对于两个选定的父代染色体父代,1,和父代,2,，随机产生两个位置，两个父代在这两个位置之间的基因产生对应对，然后用这种对应对分别去替换两个父代的基因，从而产生两个子代。,父代,1,：,2 6 4,3 8 1,5 7 9,父代,2,：,8 5 1,7 6 2,4 3 9,选 定：*,子代,1,：,1,8,4,7,6,2 5,3,9,子代,2,：,6 5 2 3 8 1 4 7 9,变异操作,变异操作发生在某个染色体的某个基因上，它将可变性引入群体中，增强了群体的多样性，从而提供了从局部最优中跳出来的一种手段。,一般通过一个很小的变异概率来控制变异,对二进制编码，随机产生一个变异位，被选中的基因由,0,变为,1,，或者由,1,变为,0,。,序号,种群,是否变异,变异位,新群体,适应值,1,11011,N,11011,729,2,11001,Y,3,11101,841,3,10000,N,10000,256,整数编码的变异规则,对整数编码，必须考虑变异后染色体的合理性。,常用的变异规则有如下几种（祥见,P320,）：,基于位置的变异,随机地产生两个变异位，然后将第二个变异位上的基因移动到第一个变异位之前。,基于次序的变异,随机地产生两个变异位，然后交换这两个变异位上的基因。,打乱变异,随机选取染色体上的一段，然后打乱在该段内的基因次序。逆序交换方式是打乱变异的一个特例。,控制参数,遗传算法的控制参数主要包括：,群体规模,每一代中群体的规模一般是固定的。扩大群体的规模可以防止早熟现象的发生。,停止准则,一般可以通过规定进化的最大代数来定义；或者定义为经过连续的几代进化后，得到的最优解没有任何变化。,进化代数,根据实际需要以及时间约束设置。,交配概率,变异概率,遗传算法的特点,遗传算法是对参数集合的编码而非针对参数本身进行进化；,遗传算法是从问题解的编码组开始而非从单个解开始搜索；,遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；,遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。,随机性：遗传算法是一个随机搜索算法，每一次运行得到的结果可能是不一样的。,通用性：遗传算法经过编码表示后除适应值计算外几乎不需要任何与问题有关的知识，而且对待求解问题的指标函数没有什么特殊的要求；,并行性：遗传算法具有天然的并行性，适用于并行求解；,遗传算法的收敛性定理,如果在代的进化过程中，遗传算法每次保留到目前为止的最好解，并且算法以交配和变异为其随机化操作，则对于一个全局最优化问题，当进化代数趋于无穷时，遗传算法找到最优解的概率为,1,。,该定理从理论上保证了只要进化代数足够多，则遗传算法找到最优解的可能性非常大。,实际使用中，要考虑在可接受的有限时间内终止算法，因此解的质量与算法的控制参数，如群体的规模、进化代数等有很大的关系。,求解,SAT,的遗传算法,SAT,问题,SAT-GA,设计,测试结果分析,SAT,问题,可满足性,(SAT),问题是命题逻辑中的一个经典问题，也是计算机科学理论与应用的一个核心问题。研究解决,SAT,问题的有效算法不仅具有重大的理论意义和实际的应用价值。自从,SAT,问题提出后，一直有不少学者在研究，有的学者致力寻找可行的算法，也有不少学者致力于研究,SAT,问题的内在规律，获得了不少成果和认识。,在算法研究方面，分为完全算法和不完全算法研究两大类。前者的主要成果有：早期的在上世纪,60,、,70,年代的,DP,算法,1,、归结法等，近期的贺思敏,00,等的吴方法求解方法等。完全算法理论上能保证找到解，但是,SAT,问题是一个,NP,完全问题，不太可能找到效率可行的完全算法。上世纪,90,年代以来，有关,SAT,问题的算法研究热点转向了不完全算法研究。不完全算法虽然不能保证一定能在有限时间内找到解，但多数情况下其求解速度比完全算法快，实用性更高。,SAT,问题描述,近年来不完全算法的研究成果非常丰富，如,Selman,和,Kautz,的,GSAT,算法和,WALKSAT,算法、梁东敏等的,WALKSAT,改进算法、李未等的数学物理方法和拟人拟物算法、张德富等的拟人退火算法、顾均的,SAT1.3,算法等等。虽然近期有用遗传算法求解,NP,问题的文章中，以,NP,的一个例子的形式提到了,SAT,问题，如张铃、张钹的佳点集遗传算法等等。,SAT,问题描述,定义,1,用符号,U,表示一个命题变元的集合。对,n,个命题变元,u,1,u,2,u,n,组成，那么，,U=u,1,u,2,u,n,，,用,|U|,表示集合,U,的元素数目。,定义,2 U,的一个真值指派,t,是一个映射,:U0,1,，,它可用一个,n,维向量,表，其中,t,i,0,1,，,0,和,1,分别代表命题常元,False,和,True,。,对任意一个命题变元,u,i,，,如果其在真值指派,t,下取真，则记为,t(u,i,)=1,，,否则，,t(u,i,)=0,。,在,U,上，存在,2,n,个不同的真值指派，所有真值指派构成的,n,维向量空间，记为,U,a,。,定义,3,对任意一个变元,u,，,称符号,u,和,u,是其文字，且称,u,是正文字，,u,是负文字。,用符号,L,表示一个文字。,SAT,问题描述,定义,4,子句是,U,上的若干个文字的析取，用,C,表示。用,|C|,表示,C,中的文字数，称为子句长度。,定义,5,子句集,A,是由,U,的子句组成的集合。它在真值指派,t,下是可满足的当且仅当其中每个子句在真值指派,t,下都是真。,定义,6 SAT,问题可以定义为：给定命题变元集,U,的子句集,A,，,问是否存在一个关于,U,的真值指派,t,，,使得,A,是可满足的，记为,P(U,A),。,对任一,P(U,A),，,设,|U|=n,，,|A|=m,，用,Z,P,表示整数集,0,1,2,2,n,-1,和用,Z,q,表示整数集,0,1,m-1,。,定义,7,从整数集,Z,p,到,Z,q,的函数,s,：,Z,P,Z,q,，,即任一个二进制整数,k=t,1,t,2,t,n,，,s(k),就是真值指派,所能满足的子句数目，显然,0s(k)m,。,SAT,问题描述,例如：,U=x,y,z,，,A=xy,，,xz,，,zy,，,|U|=3,，,|A|=3,，,Z,P,=0,1,2,3,4,5,6,7,，,Z,q,=0,1,2,3,假设有一个真值指派,t,：,=,。,真值指派,能满足,A,中的,3,个子句，所以，,s(101,B,)=3,。,本例的真值指派集,Ua,=,，,各真值指派可满足的子句数目对应为：,2,、,2,、,2,、,3,、,1,、,3,、,1,和,3,。,SAT-GA,染色体是一个由,n,个二进制位的位串，实际上就是指真值指派中各变元的取值构成的。设,|U|=n,，,对任一变元,u,，,如果在一个真值指派,t,中，有,t(u)=1,，则,t(u)=0,，,反之亦然，所以只要,n,个二进制位就可以表示一个真值指派,t,。,用二进制的位串表示真值指派的染色体是很直观的编码方法，采用这种编码方案，充分利用了,SAT,本身的特点，便于计算适应值函数和设计各种遗传算子。,SAT-GA,适应值函数,f,1,前文定义,7,所定义的函数,s,。,真值指派能满足的子句数量能一定程度上反映其优劣。这个函数必存在最大值，若子句集是可满足的，其最大值为子句数目。,这个目标函数的设计是合理且直观的,计算也简单，实验表明该函数具有一定的导向能力，能快速引导个本向解的进化，缺点是搜索的最后阶段算法易出现平台现象，求解成功率偏低。,适应值函数,f,2,定义为,f,2,(t)=,真值指派,t,下为真的子句的静态权重之和。,在结构化,SAT,问题中求解中，子句长短不一，实验中发现，短子句难满足，长子句易满足，因此子句长度是反映子句满足的难易程度的信息，是,SAT,问题求解时自身存在的、可用以引导进化搜索的很重要的启发信息。,SAT-GA,描述,SAT-GA,算法如下：,1).,输入变元集和子句集，初始化参数，随机生成,M,个真值指派作为初始第一代的群体；,2).,对每一个真值指派,t,，,求其适应值，同时计算出当代群体的总适应值和最优的真值指派的适应值，进而计算每个真值指派的选择概率，构成选择种群的概率滚花轮,;,3).,若满足结束条件，算法结束。,4).,选择种群：当代的一个最优的真值指派直接复制到种群中，其余的,M-1,个体由模拟滚花轮的方式从当代群体中选择。,5).,产生下一代：当代的一个最优个体直接复制到下一代中，其余,M-1,个真值指派的产生过程是：顺序地从种群中选出一个真值指派作为父亲，以概率,Pc,参与交叉，若要交叉，则从种群中随机配对，找到另一个真值指派作为母亲，然后进行交叉操作，产生两个下一代的真值指派，对新真值指派实施变异操作，放入下一代中。如此重复，直到产生了,M-1,个的新一代群体为止。,6).,累计代数加,1,，转第二步；,SAT-GA,实验结果,变元数,m=100,算法名称,子句数,=,200,子句数,=,300,子句数,=,400,子句数,=,500,子句数,=,600,成功,时间,成功,时间,成功,时间,成功,时间,成功,时间,SAT-GA,100,0.2,100,0.3,100,0.7,100,1.6,100,1.9,GSAT,100,1.2,100,2.4,100,10.4,80,20.8,90,38.3,WALKSAT,100,0.6,100,1.0,100,2.3,100,8.0,100,11.3,SAT,、,GSAT,和,WALKSAT,求解,3-SAT,问题,SAT-GA,实验结果,100 200 300 400 500 600,子句,时间,45,40,35,30,25,20,15,10,5,400 500 600 700 800 900,子句,时间,450,400,350,300,250,200,150,100,50,300 400 500 600 700 800,子句,时间,450,400,350,300,250,200,150,100,50,图,1 100,变元的,3-SAT,样本求解时间对比图,图,2 200,变元的,3-SAT,样本求解时间对比图,图,3 300,变元的,3-SAT,样本求解时间对比图,SAT-GA,实验结果,问题,规模,子句集规模,(,子句长度不多于变元数的,10%),1,2,3,4,5,6,成功,时间,成功,时间,成功,时间,成功,时间,成功,时间,成功,时间,1024,变元,100,1.5,100,6.5,100,13.6,100,23.2,100,31.3,100,53.8,2048,变元,100,9.6,100,32.2,100,44.3,100,78.2,-,-,-,-,4096,变元,100,16.4,100,80.4,-,-,-,-,-,-,-,-,8172,变元,100,502.0,-,-,-,-,-,-,-,-,-,-,SAT,求解结构化,SAT,问题,