第7讲(遗传算法).ppt

《第7讲(遗传算法).ppt》由会员分享，可在线阅读，更多相关《第7讲(遗传算法).ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遗传算法的提出遗传算法的提出o遗传算法是根据自然界“物竞天择、适者生存”的现象而提出的一种随机搜索算法；o20世纪70年代由美国密执根大学的霍兰德（Holland）首先提出的；o遗传算法把优化问题看作是自然界中的生物进化过程，通过模拟大自然中生物进化过程的遗传规律，来达到寻优的目的。o生物进化圈示意图婚配选择变异子群种群群体遭淘汰的群体人类进化图生物进化的特性生物进化的特性o进化过程发生在染色体上，而不是发生在他们所编码的生物体上；o自然选择把染色体以及由他们所译成的结构的表现联系在一起，适应性好的个体染色体比差的染色体有更多的繁殖机会；o繁殖过程发生在进化那一刻。变异可以使生物体子代的染色体

2、不同于他们的父代染色体；通过结合两个父代染色体中的物质，重组过程可以产生在子代中有很大差异的染色体；o生物进化没有记忆。遗传算法的基本思想遗传算法的基本思想o遗传算法通过自然选择中“优胜劣汰”的策略在每次搜索中利用各种随机的遗传算子生成问题一些新的解，淘汰较差的解，保留较好的以及有希望的解，从而不断对搜索空间中新的未知区域进行探索。它有效地利用了许多历史信息，使得搜索每次都向着最好的方向前进。o对优化问题的解进行编码，编码后的一个解称为染色体，组成染色体的元素称为基因；o一个群体由若干染色体组成，染色体的个数称为群体的规模；o用适应度函数表示环境，它是已编码的解的函数，是一个解适应环境程度的评

3、价；适应函数的构造一般与优化问题的指标函数相关；遗传算法的基本思想遗传算法的基本思想o适应函数值大表示所对应的染色体适应环境的能力强，自然选择规律将以适应函数值的大小来决定染色体是否继续生存下去的概率；o生存下来的染色体称为种群，他们中的部分或全部以一定的概率进行交配、繁衍，从而得到下一代群体；o交配是一个生殖过程，发生在两个染色体之间，作为双亲的染色体，交换部分基因后，生殖出两个新的染色体，即问题的新解；o在进化过程中，染色体的某些基因可能会发生变异，即染色体的编码发生了某些变化。一个群体的进化需要染色体的多样性，变异对于保持群体的多样性具有一定的作用。生物进化与遗传算法之间的对应关系生物进

4、化与遗传算法之间的对应关系生物进化中的概念生物进化中的概念遗传算法中的作用遗传算法中的作用环境适应函数适应性适应函数值适者生存适应值大的解被保留的概率大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群按适应函数选择的一组解（编码表示）交配以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程遗传算法的基本模型遗传算法的基本模型（1）遗传算法可以形式化地描述如下：（2）表示初始群体；（3）表示长度为l 的符号串全体，为字母表；若使用二进制编码，则 ；（4）N 为一个正整数，表示种群中含有个体的个数；（5）l 为一个正整数，表示符号串的长度；（6）表示选择策略；（7）g

5、 表示遗传算子，通常包括复制算子 、交叉算子 和变异算子 ；（8）p 表示操作概率，包括复制概率 、交叉概率 和变异概率 ；（9）是适应度函数；（10）是终止准则。遗传算法的基本操作遗传算法的基本操作o简单遗传算法的遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。o选择操作选择操作实现从群体中选择存活的个体(染色体)。根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。o交叉操作交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的基因进行交换，产生

6、新个体的染色体。o变异操作变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。选择操作选择操作q选择概率：设群体规模为N，F(xi)(i=1,N)是N个染色体的适应值，则第i个染色体被选中的概率由下式计算：P(xi)=F(xi)/F(xj)q“轮盘赌”选择法：一个转盘划分为N个扇区，每个xi在转盘上占有一个扇区，扇区的大小与选择概率P(xi)成正比。在选择一个染色体时，先转动轮盘，等轮盘停下后，指针指向的区所对应的xi应是被选中的染色体。q“分组淘汰”选择法：设群体规模为N，按 P(xi)由大到小对染色体进行排序，再依次分为相等

7、数目的k组，每组按淘汰概率Pi(i=1,.,k)淘汰本组染色体，各组剩余者合并为种群。淘汰概率满足：P1 P2 Pk。选择操作选择操作q“确定性”选择法：设群体规模为N，一个选择概率为P(xi)的染色体被选中的次数的期望值e(xi)=P(xi)N。对于群体中的每一个xi，首先选择e(xi)次，这样共得e(xj)个染色体。再按e(xi)-e(xi)由小到大对染色体进行排序，依次取出N-e(xj)个染色体，这样共得到N个染色体组成种群。交配操作交配操作q交配操作发生在两个父代染色体之间，经过杂交产生两个具有双亲的部分基因的新染色体。q单点交配：q 多点交配：a1 a2ai ai+1 an b1 b

8、2bi bi+1 bna1 a2ai bi+1 bn b1 b2bi ai+1 ana1ai ai+1 aj aj+1 an b1bi bi+1 bj bj+1 bna1ai bi+1 bj aj+1 an b1bi ai+1 aj bj+1 bn变异操作变异操作q 变异操作是发生在某一个基因上的随机变化，模拟基因突变现象，有利于保持群体的多样性，但也有很强的破坏作用。q 二进制基因的变异操作，可以是简单地按变异概率翻转某一个位，即某位由0变1，或由1变0。q 字符基因的变异操作将某一个基因字符上的随机地换为任一其他可能基因字符。序号种群是否变异变异位新群体适应值111011N11011729

9、211001Y311101841310000N10000256遗传算法的基本流程遗传算法的基本流程遗传算法的描述遗传算法的描述1.给定群体规模N，交配概率pc和变异概率pm2.随机生成一个N个初始解组成的初始群体；3.计算当前初始群体各染色体xi的适应度函数值F(xi)；4.如果满足停止准则，则转10；5.对群体中的每一个染色体xi计算概率p(xi)；6.依据概率值从群体中随机选择N个染色体，得到种群；7.依交配概率pc按交叉算子Oc进行交配，其子代进入新的群体，未进行交配的染色体直接复制到新群体中；8.依变异概率pm从种群中选择染色体按变异算子Om进行变异，用变异后的染色体代替新群体中的原染

10、色体；9.用新群体代替旧群体，t=t+1，转310.进化过程中适应值最大的染色体，经解码后作为最优解输出；11.结束。遗传算法的应用遗传算法的应用 函数优化问题一般可以直接应用遗传算法进行求解，但是，更多的现实问题中应用遗传算法，首先需要转换为函数优化问题。这些应用中有多个共同问题：o编码问题o适应值函数o交配规则o变异规则o性能评价用于求解函数优化问题用于求解函数优化问题例如：求函数f(x)=x2的最大值，其中x为0，31间的整数。利用遗传算法进行求解，关键要解决如下问题：o编码与解码：染色体由五个二进制位组成，可能的染色体有：0000011111共32个。o适应度函数：F(x)=f(x)o

11、选择操作：轮盘赌o交配操作：单点交配o变异操作：位翻转o控制参数：N=4，Pc=100%,Pm=1%o求解过程：用于求解函数优化问题用于求解函数优化问题-2第0代：随机生成，设为01101,11000,01000,10011从第0代中选择产生的种群：01101,11000,11000,10011假定按顺序两两交配，即01101与11000、11000与10011，产生4个新个体为：01100，11001，11011，10000 作为第1代群体。序号群体F(xi)P(xi)e(xi)选中次数1011011690.140.5812110005760.491.972301000640.050.220

12、4100113610.311.231用于求解函数优化问题用于求解函数优化问题-2第1代：01100，11001，11011，10000从第1代中选择产生的种群：11001,11011,11011,10000假定按顺序两两交配，即11001与11011、11011与10000，产生4个新个体为：11011，11101，10000，11011 作为第2代群体。序号群体F(xi)P(xi)e(xi)选中次数1011011440.080.3302110016250.361.4213110117290.421.6624100002560.150.581用于求解函数优化问题用于求解函数优化问题-2第2代：

13、11011，11101，10000，11011从第2代中选择产生的种群:11011,11101,10000,11011假定按顺序两两交配，即11011与11101、10000与11011，产生4个新个体为：11001，11111，10001，11010 作为第3代群体。(以后过程略)序号群体F(xi)P(xi)e(xi)选中次数1110117290.291.1412111018410.331.3113100002560.100.4014110117290.291.141编码问题编码问题o利用遗传算法进行问题求解首先是表示问题，即将问题的解以适合于遗传算法求解的形式进行编码。o进行编码时，要考虑

14、交配和变异等操作。o采用什么样的编码形式与具体的问题有关。o可以采用二进制编码，简单，但长度大。o也可以采用整数编码、实数编码、符号编码等形式。例7.7 函数在实数区间上的最优化问题。例7.8 十杆桁架问题。例7.9 人工蚁问题。例7.10 TSP问题。二进制编码二进制编码-求函数的最大值o求函数f(x)=x2的最大值，其中x为0，31间的整数。由于x的定义域是0,31之间的整数，因此可以用五位二进制数表示该问题的解，如用10101表示x=21，0、1为基因。o求函数f(x)=x2的最大值，其中x为0，31间的实数，最大误差为1/8。对于区间a,b上的实数，当用n位的二进制向量表示时，其最大误

15、差为(b-a)/(2n-1),所以有(b-a)/(2n-1)1/8，所以需要用8位二进制向量来表示。x与8位二进制向量之间的关系为：x=31*(y/255)，其中y为0-255之间的二进制数。二进制编码二进制编码-十杆桁架问题o十杆桁架问题如图所示，有10个截面积为A1A2 A10。如何设计每个杆的截面使建造这个桁架的材料总费用最小？o假设每个杆的截面积在0.1至10.0之间，取16种可能的值。用4位二进制表示截面的面积，即0000对应0.1,1111对应10.0。问题的解是10个杆的面积，要用40位二进制串表示一个解。例如，该问题的一个染色体为：0010 1110 0001 0011 101

16、1 0011 1111 0011 0011 1010100kg100kg303030A2A1A3A4A5A6A7A8A9A10二进制编码二进制编码-人工蚁问题o人工蚁问题如图所示，有一人工蚁在3232的网格中移动。二进制编码二进制编码-人工蚁问题o“圣菲轨道”是一条不规则的弯曲轨道，上面放有89块食物。轨道上的食物不是连续排放，有些位置是空的。o人工蚁的视力有限，只能看到正面邻格中的是否有食物。它只有四种动作：00-不动01-左转90度(原地)10-右转90度(原地)11-走进正面相邻的网格中，如果有食物，就吃到该食物q要求设计一个有限状态自动机，该自动机能在有限步内引导人工蚁吃到所有的食物。

17、二进制编码二进制编码-人工蚁问题o四状态自动机，容易验证：如果食物是不间断排列，该自动机可以在有限步引导人工蚁吃到所有食物。001110011/前进1/前进0/右转0/左转0/左转0/右转1/前进1/前进 O O O二进制编码二进制编码-人工蚁问题o自动机可以用状态转换表等价表示。前面的四状态自动机可等价地表示为下表，实际上只要给定了初始状态和表的最后两列，就可以确定该自动机，因此，只要34个二制位位即可表示一个四状态自动机，例如：00 0110 0011 10010011 1101 0011 0010 0011序号当前状态输入下一状态动作100001102001001130101001401

18、1001151001101610100117110001081110011二进制编码二进制编码-人工蚁问题o四状态自动机不能解决有间隔的“圣菲轨道”问题，需要更多的状态。oJefferson将状态增加到 32个，状态转换表需要64行，动作仍用2位表示，因此表示一个自动机需要的二进制位数为：5+(5+2)*64=453。o适应值函数是自动机x引导人工蚁吃到的食物数，最大值为89。o成功求解的参数设置：N=65535，M=200整数编码整数编码-旅行商问题用遗传算法求解旅行商问题，应如何进行编码？o二进制编码 可以用一个矩阵来表示一个可能解。如四城市问题，可用一个4*4矩阵来表示一个可能解，将该矩

19、阵展开得到一个4*4的二进制向量。对n城市问题，则需要一个n*n位二进制向量。可能解在整个状态空间中是非常稀疏的，导致求解效率低下。o整数编码 对城市进行编号，每个城市分别用1到n之间的不同整数表示，n个整数的一个排列就代表了TSP问题的一个可能解。适应度函数适应度函数o为了评价染色体的适应能力，引入了对问题中的每一个染色体都能进行评价的函数，叫适应度函数适应度函数（fitness function）。o一般情况下，可以直接选取问题的指标函数作为适应度函数。o例1：求f(x)的最大值问题，可以直接采用f(x)作为适应度函数，即F(x)=f(x)。o例2：TSP问题，目标是路径总长度最短，因此可

20、以将路径总长度作为TSP问题的适应度函数。o适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数适应度函数o某些情况下，f(x)在最大值附近的变化可能非常小，以至于很难区分哪个染色体更优，这时应如何定义适应度函数，才能有效反映染色体与最优解染色体的差异?非线性加速适应函数 线性加速适应函数 利用染色体指标函数值从小到大的排列号作为适应函数值。按定义，选择概率计算式为：二进制编码的交配规则二进制编码的交配规则o双亲双子法 参与交配的两个双亲染色体确定后，随机地产生一个交配位，双亲染色体交换各自的交配位后的基因给对方，得到两个子染色体。o变化交配法 随机产生交配位时，排除与双

21、亲一样的交配位。o多交配位法 产生多个交配位进行交配，在交配时采用交配区间交替进行的方法。o双亲单子法 两个染色体交配后只得到一个子染色体。一般选择适应值大的。二进制交配操作的例子二进制交配操作的例子o如下表所示，第0代种群为：01101,11000,11000,10011。假定交配概率的100%，即种群中所有染色体均参与交配，并按顺序两两交配。o交配后得到的子群为：01100,11001,11011,10000序号种群交配对象交配位子代适应值1011012401100144211000141100162531100042110117294100113210000256整数编码的交配规则整数编

22、码的交配规则-1整数编码的交配规则必须保持编码的有效性。下面以TSP问题的整数编码为例进行说明(P318)。o常规交配法 与二进制编码的双亲双子法类似。子代1交配位之前的基因采用父代1交配位之前的基因，交配位之后的基因从父代2中按顺序选取那些没有出现过的基因。父代1：12345678父代2：52373846子代1：12345786子代2：52371468整数编码的交配规则整数编码的交配规则-2o基于次序的交配法 对于两个选定的父代染色体父代1和父代2，首先随机地选择一组位置，设父代1中所选位置对应的数字从左到右依次为x1,x2,xk，然后从父代2中也找到这k个数字，并从父代2删除，空位置用x1

23、,x2,xk依次填入，就得到子代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整数编码的交配规则整数编码的交配规则o基于位置的交配法 对于两个选定的父代染色体父代1和父代2，首先随机地选择一组位置，对于这些位置上的基因，子代1从父代2直接得到，子代1其他位置的基因，按顺序从父代1中选取那些不相重的基因。子代2同理。父代1：1 2

24、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整数编码的交配规则整数编码的交配规则o基于部分映射的交配法 对于两个选定的父代染色体父代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变异操作变异操作o变异操作发生在

25、某个染色体的某个基因上，它将可变性引入群体中，增强了群体的多样性，从而提供了从局部最优中跳出来的一种手段。o一般通过一个很小的变异概率来控制变异o对二进制编码，随机产生一个变异位，被选中的基因由0变为1，或者由1变为0。序号种群是否变异变异位新群体适应值111011N11011729211001Y311101841310000N10000256整数编码的变异规则整数编码的变异规则对整数编码，必须考虑变异后染色体的合理性。常用的变异规则有如下几种（祥见P320）：o基于位置的变异 随机地产生两个变异位，然后将第二个变异位上的基因移动到第一个变异位之前。o基于次序的变异 随机地产生两个变异位，然后

26、交换这两个变异位上的基因。o打乱变异 随机选取染色体上的一段，然后打乱在该段内的基因次序。逆序交换方式是打乱变异的一个特例。控制参数控制参数遗传算法的控制参数主要包括：o群体规模 每一代中群体的规模一般是固定的。扩大群体的规模可以防止早熟现象的发生。o停止准则 一般可以通过规定进化的最大代数来定义；或者定义为经过连续的几代进化后，得到的最优解没有任何变化。o进化代数 根据实际需要以及时间约束设置。o交配概率o变异概率遗传算法的特点遗传算法的特点o遗传算法是对参数集合的编码而非针对参数本身进行进化；o遗传算法是从问题解的编码组开始而非从单个解开始搜索；o遗传算法利用目标函数的适应度这一信息而非利

27、用导数或其它辅助信息来指导搜索；o遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。o随机性：遗传算法是一个随机搜索算法，每一次运行得到的结果可能是不一样的。o通用性：遗传算法经过编码表示后除适应值计算外几乎不需要任何与问题有关的知识，而且对待求解问题的指标函数没有什么特殊的要求；o并行性：遗传算法具有天然的并行性，适用于并行求解；遗传算法的收敛性定理遗传算法的收敛性定理o如果在代的进化过程中，遗传算法每次保留到目前为止的最好解，并且算法以交配和变异为其随机化操作，则对于一个全局最优化问题，当进化代数趋于无穷时，遗传算法找到最优解的概率为1。o该定理从理论上保证了只要进化代数

28、足够多，则遗传算法找到最优解的可能性非常大。o实际使用中，要考虑在可接受的有限时间内终止算法，因此解的质量与算法的控制参数，如群体的规模、进化代数等有很大的关系。求解求解SAT的遗传算法的遗传算法oSAT问题oSAT-GA设计o测试结果分析SAT问题问题o可满足性(SAT)问题是命题逻辑中的一个经典问题，也是计算机科学理论与应用的一个核心问题。研究解决SAT问题的有效算法不仅具有重大的理论意义和实际的应用价值。自从SAT问题提出后，一直有不少学者在研究，有的学者致力寻找可行的算法，也有不少学者致力于研究SAT问题的内在规律，获得了不少成果和认识。o在算法研究方面，分为完全算法和不完全算法研究两

29、大类。前者的主要成果有：早期的在上世纪60、70年代的DP算法1、归结法等，近期的贺思敏00等的吴方法求解方法等。完全算法理论上能保证找到解，但是SAT问题是一个NP完全问题，不太可能找到效率可行的完全算法。上世纪90年代以来，有关SAT问题的算法研究热点转向了不完全算法研究。不完全算法虽然不能保证一定能在有限时间内找到解，但多数情况下其求解速度比完全算法快，实用性更高。SAT问题描述问题描述o近年来不完全算法的研究成果非常丰富，如Selman和Kautz的GSAT算法和WALKSAT算法、梁东敏等的WALKSAT改进算法、李未等的数学物理方法和拟人拟物算法、张德富等的拟人退火算法、顾均的SA

30、T1.3算法等等。虽然近期有用遗传算法求解NP问题的文章中，以NP的一个例子的形式提到了SAT问题，如张铃、张钹的佳点集遗传算法等等。SAT问题描述问题描述定义1用符号U表示一个命题变元的集合。对n个命题变元u1,u2,un组成，那么，U=u1,u2,un，用|U|表示集合U的元素数目。定义2U的一个真值指派t是一个映射:U0,1，它可用一个n维向量表，其中ti0,1，0和1分别代表命题常元False和True。对任意一个命题变元ui，如果其在真值指派t下取真，则记为t(ui)=1，否则，t(ui)=0。在U上，存在2n个不同的真值指派，所有真值指派构成的n维向量空间，记为Ua。定义3对任意一

31、个变元u，称符号u和u是其文字，且称u是正文字，u是负文字。用符号L表示一个文字。SAT问题描述问题描述o定义4子句是U上的若干个文字的析取，用C表示。用|C|表示C中的文字数，称为子句长度。o定义5子句集A是由U的子句组成的集合。它在真值指派t下是可满足的当且仅当其中每个子句在真值指派t下都是真。o定义6SAT问题可以定义为：给定命题变元集U的子句集A，问是否存在一个关于U的真值指派t，使得A是可满足的，记为P(U,A)。o对任一P(U,A)，设|U|=n，|A|=m，用ZP表示整数集0,1,2,2n-1和用Zq表示整数集0,1,m-1。o 定义7 从整数集Zp到Zq的函数s：ZPZq，即任

32、一个二进制整数k=t1t2tn，s(k)就是真值指派所能满足的子句数目，显然0s(k)m。SAT问题描述问题描述o例如：U=x,y,z，A=xy，xz，zy，|U|=3，|A|=3，ZP=0,1,2,3,4,5,6,7，Zq=0,1,2,3 假设有一个真值指派t：=。真值指派能满足A中的3个子句，所以，s(101B)=3。本例的真值指派集Ua=,，各真值指派可满足的子句数目对应为：2、2、2、3、1、3、1和3。SAT-GAq染色体是一个由n个二进制位的位串，实际上就是指真值指派中各变元的取值构成的。设|U|=n，对任一变元u，如果在一个真值指派t中，有t(u)=1，则t(u)=0，反之亦然，

33、所以只要n个二进制位就可以表示一个真值指派t。q用二进制的位串表示真值指派的染色体是很直观的编码方法，采用这种编码方案，充分利用了SAT本身的特点，便于计算适应值函数和设计各种遗传算子。SAT-GAq 适应值函数f1 前文定义7所定义的函数s。真值指派能满足的子句数量能一定程度上反映其优劣。这个函数必存在最大值，若子句集是可满足的，其最大值为子句数目。这个目标函数的设计是合理且直观的,计算也简单，实验表明该函数具有一定的导向能力，能快速引导个本向解的进化，缺点是搜索的最后阶段算法易出现平台现象，求解成功率偏低。q 适应值函数f2 定义为f2(t)=真值指派t下为真的子句的静态权重之和。在结构化

34、SAT问题中求解中，子句长短不一，实验中发现，短子句难满足，长子句易满足，因此子句长度是反映子句满足的难易程度的信息，是SAT问题求解时自身存在的、可用以引导进化搜索的很重要的启发信息。SAT-GA描述描述SAT-GA算法如下：1).输入变元集和子句集，初始化参数，随机生成M个真值指派作为初始第一代的群体；2).对每一个真值指派t，求其适应值，同时计算出当代群体的总适应值和最优的真值指派的适应值，进而计算每个真值指派的选择概率，构成选择种群的概率滚花轮;3).若满足结束条件，算法结束。4).选择种群：当代的一个最优的真值指派直接复制到种群中，其余的M-1个体由模拟滚花轮的方式从当代群体中选择。

35、5).产生下一代：当代的一个最优个体直接复制到下一代中，其余M-1个真值指派的产生过程是：顺序地从种群中选出一个真值指派作为父亲，以概率Pc参与交叉，若要交叉，则从种群中随机配对，找到另一个真值指派作为母亲，然后进行交叉操作，产生两个下一代的真值指派，对新真值指派实施变异操作，放入下一代中。如此重复，直到产生了M-1个的新一代群体为止。6).累计代数加1，转第二步；SAT-GA实验结果实验结果变元数m=100算法名称子句数=200子句数=300子句数=400子句数=500子句数=600成功时间成功时间成功时间成功时间成功时间SAT-GA1000.21000.31000.71001.61001.

36、9GSAT1001.21002.410010.48020.89038.3WALKSAT1000.61001.01002.31008.010011.3SAT、GSAT和WALKSAT求解3-SAT问题SAT-GA实验结果实验结果100 200 300 400 500 600 子子句句时间时间45403530252015105400 500 600 700 800 900 子子句句时间时间45040035030025020015010050300 400 500 600 700 800 子句子句时间时间45040035030025020015010050图图1 100变变元元的的3-SAT样样本本求求解解时间对比图时间对比图图图2 200变变元元的的3-SAT样样本本求求解时间对比图解时间对比图图图3 300变变元元的的3-SAT样样本本求求解解时间对比图时间对比图SAT-GA实验结果实验结果问题规模子句集规模(子句长度不多于变元数的10%)123456成功时间成功时间成功时间成功时间成功时间成功时间1024变元1001.51006.510013.610023.210031.310053.82048变元1009.610032.210044.310078.2-4096变元10016.410080.4-8172变元100502.0-SAT求解结构化SAT问题