2006年计算机组成原理课程设计

PAGE石家庄经济学院第四届学生科技基金科研项目研究报告项目名称：基于改进遗传算法求解可满足性问题的研究负责人：曹国生所属学院:信息工程学院指导老师：贺毅朝200目录1.选题依据 12.国内外研究现状 53．个人主要工作 64.数据分析 85.总结 9致谢 10参考文献 10附录 10PAGE1摘要本文通过介绍遗传算法和可满足性问题的起源、描述、重要理论意义和应用价值，进而提出了一种新的方法来解决可满足性问题，即在将SAT问题等价转换为{0,1}n上的多项式是否存在零点的判断问题基础上，将局部搜索算法(LSA)与SGA相结合，给出一种求解3-SAT问题的改进混合遗传算法(MHGA)，并通过对随机大规模3-SAT问题实例的实际求解验证了MHGA的可行性与有效性。关键词：遗传算法，可满足性问题一.选题依据遗传算法及其重要性遗传算法(GeneticAlgorithm，GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，它起源于对生物系统所进行的计算机模拟研究。早在本世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。如Fraser的模拟研究，他提出了和现在的遗传算法十分相似的概念和思想。进入60年代以后，美国密执安大学的Holland教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术遗传算法。70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。Holland和DeJong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏，其中，Holland于1975年出版的著名著作<<自然系统和人工系统的适配>>系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong的重要论文<<遗传自适应系统的行为分析>>将Holland的模式理论与他的计算实验结合起来，并提出了诸如代沟等新的遗传操作技术，可以认为，DeJong所做的研究工作是遗传算法发展过程中的一个里程碑。在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。80年代以后，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题，遗传算法的应用领域也不断扩大。生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景，遗传算法就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力，它所借鉴的生物学基础就是生物的遗传和进化。达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。主要是基于达尔文进化论中“物竞天择，适者生存”理论，模拟生物进化的步骤,将繁殖、杂交、变异、竞争和选择等概念引入到算法中，通过对一组可行解的重新组合，改进可行解在多维空间内的移动轨迹或趋向,最终走向最优解。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。遗传算法求解问题的基本思想是从问题的解出发的，它将问题的一些可行解进行编码，这些已编码的解即被当作群体中的个体（染色体），个体对环境适应能力的评价函数就是问题的目标函数，模拟遗传学中的杂交、变异、复制来设计遗传算子，用优胜劣汰的自然选择法则来指导学习和确定搜索方向。对由个体组成的群体进行演化，利用遗传算子来产生具有更高平均适应度值和更好个体的群体，经过若干代后，选出适应能力最好的个体,它就是问题的最优解或近似最优解，通过迭代保留优秀个体、淘汰劣等个体来进化求解。遗传算法将搜索空间映射成遗传空间，在遗传空间的每个个体代表搜索空间的一个解，由特定数量的个体组成一个种群，由适应度函数得出各个个体的适应度值以标识当前个体的优劣，每一代种群个体经过交叉、变异以及选择操作，生成新一代种群个体。一般情况，新一代种群个体都比原种群个体的平均适应度值要好，经过多代的进化，最终得到一个最优个体。遗传算法的搜索过程是一个由已知个体向未知个体搜索并且新个体比原个体更为优秀的过程，这适合该系统从已知的规则搜索到更合理、准确的未知规则的要求。遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。在传统的优化算法中，是从一个点开始搜索，易于陷入局部最优解。而遗传算法在搜索中同时考虑了问题解空间中的许多点(一个点群)搜索，搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，且对初始值不作要求，从而大大减少了陷入局部最优解的可能性。另外，在传统的算法中需要提供一些辅助信息，而遗传算法仅利用问题本身所具有的目标函数的信息。它不受搜索空间的限制，不必要求诸如连续性、导数的存在和单峰等假设，搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作，仅用适应度来评估个体优劣，具有很强的鲁棒性，并且具有内在的隐并行性和更好的全局寻优能力，稳健性极强、可操作性和简单性突出。此外，采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。我们习惯上把Holland1975年提出的GA称为经典的GA。它的主要步骤如下：

（1）编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。

（2）初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。

（3）适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。

（4）选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。

（5）交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。

（6）变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之间。变异为新个体的产生提供了机会。

经典遗传算法(SGA)的基本流程描述如算法1所示。算法1．SGA算法1.t←0;2.initializeP(t);//初始化个体3.evaluate(P(t));//评价个体4.While(notterminatecondition)Do//进行选择、交叉、变异,产生新一代种群5.P1←Select(P(t));//从上一代种群中选择个体加入P1中6.P2←Crossover(P1);//对P1中的个体进行交叉操作生成P27.P(t+1)←Mutate(P2);//对P2中的个体进行变异操作8.Evaluate(P(t+1));Compute(Best);//评价新种群,并计算当前最优个体Best9.t←t+1;10.EndWhile;11.Output(Best,f(Best))//输出最优个体Best及其对应的函数值

GA的计算过程为：选择编码方式，产生初始群体，计算初始群体的适应性值，如果不满足条件则进行

选择，交换，变异，进而计算新一代群体的适应性值。

遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类由很强的鲁棒性，所以广泛应用于很多学科。目前遗传算法所涉及的主要领域有自动控制、规划设计、组合优化、函数优化、生产调度问题、神经网络学习过程、机器人学习、机器学习、遗传编程、图象处理、信号处理、自动控制和人工生命等领域。其中，函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。遗传算法对于组合优化中的NP完全问题也非常有效，例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面都得到的有效的应用。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。除此之外，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。在图像处理中的优化计算方面遗传算法也找到了用武之地，目前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论，人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。而基于遗传算法的机器学习，特别是分类器系统，在很多领域都得到了应用。例如：遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好的改进模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也可在学习式多机器人路径规划系统中得到了成功的应用。此外在社会科学、生物学、商业及工程等各种不同领域也得到了越来越广泛的应用。由此可见，遗传算法的应用研究已从初期的组合优化求解拓展到了许多更新，更工程化的应用方面。可满足性问题的意义可满足性问题(SatisfiabilityProblem,SAT)是由Cook证明的第一个NPC问题，它是计算科学中的典型问题之一，也是当今计算机科学和人工智能研究的核心问题。其后的NPC问题证明都是建立在SAT问题之上，研究解决SAT问题的有效算法不仅具有重大的理论意义，而且在智能规划、智能决策、定理证明、电路诊断和优化计算、人工智能、机器学习、VLSI集成电路设计与检测和数据库检索等诸多领域有着实际的意义。SAT问题的一般性描述如下：令P={p1,p2,…，pn}是n个不同命题变元的集合，P上公式的一个指派是函数t：P→{T,F}，用n元布尔向量t=<t1,t2,…,tn>表示，其中t∈{0,1}。显然，P上存在2n个不同的指派。对于P上公式A，如果存在指派t使得t(A)=1，则称A为可满足的；如果对于任意指派t使得t(A)=0，则称A为不可满足的(或矛盾的)。形如C=ci1∨ci2∨…∨cik…∨cir的公式称为子句，其中cij为pij或﹁pij，称cij为P上的文字(literal)。公式A=C1∧C2∧…∧Ci∧…∧Cm称为合取范式，其中Ci为其子句(1≤i≤m)。如果存在指派t使A满足，则称A是可满足公式。易知，合取范式A在指派t下是可满足的当且仅当其每个子句Ci均是可满足的。于是，SAT问题是指对于给定P={p1,p2,…，pn}上的一个CNFA，判断是否存在一个指派t使得A是可满足的。当公式A中的每个子句Ci(1≤i≤m)都只含有k个不互补的文字时，公式A被称为k-SAT问题。简单地说，SAT问题就是给定一个包含n个变量m个子句的合取范式，判断是否有使这些子句全部为真的赋值。SAT的问题被证明是NP难解的问题。目前解决该问题的方法主要有完备的方法和不完备的方法两大类。完备的方法优点是保证能正确地判断SAT问题的可满足性，但其计算效率很低，平均的计算时间为多项式阶，最差的情况计算时间为指数阶，不适用于求解大规模的SAT问题。不完备的方法的优点是求解的时间比完备的方法快得多，但在很少数的情况下不能正确地判断SAT问题的可满足性。传统的方法有：枚举法、局部搜索法和贪婪算法等，但由于搜索空间大，问题一般难以求解。对于像SAT一类的NP难问题，采用一些现代启发式方法如演化算法往往较为有效。由于现代科技、军事以及经济管理的大量重要应用都归结为求解完全问题，所以工程技术、军事、工商管理、交通运输及自然科学研究中的许多重要问题，如程控电话的自动交换、大型数据库的维护、大规模集成电路的自动布线、软件自动开发、机器人动作规划等，都可转化成SAT问题。它的快速求解不仅具有重要的理论意义,而且在软件自动开发技术、逻辑推理机、VLSI设计、人工智能、机器学习、以及知识库维护和检测和数据库检索等许多领域都有重要的实际应用价值。此外，SAT问题还在集成电路设计、数据库检索、定理证明、数理逻辑、计算机视觉、机器人规划和空间布线等具体研究领域中有着广泛的应用。因此致力于寻找求解SAT问题的快速而有效的算法，不仅在理论研究上而且在许多应用领域都具有极其重要的意义。关于SAT问题求解的算法是国内外研究的热点之一，目前求解SAT问题存在多种算法，其中基于局部搜索或梯度下降理论的算法为完全算法，例如穷举搜索法、Davis-Putnam算法、DPLL算法等，优点是能保证正确地判断SAT问题的可满足性，但是，由于SAT问题的计算空间随着问题规模的增大呈级数增长，当SAT问题的规模较大时，完全算法不实用。而SAT问题是一个NPC问题，该问题是否存在多项式时间算法目前还未解决，在这种情况下，人们开始寻找不完全的但快速且非常实用的随机算法，即不完全算法。所谓不完全是指：如果范式是可满足的，则此算法将停机并给出一个解，否则算法可能不停机。其代表性的算法有：Localsearch算法、拟人拟物算法、遗传算法(GA)、模拟退火算(SA)法和微粒群算法(PSO)等。由于有些优化算法所需要的计算空间难以承受，所以算法可解的问题在实践上不一定可解。P类问题指具有多项式求解的算法的问题类。但到目前为止，许多优化问题仍没有找到求的最优解的多项式时间算法，通常称这种比P类问题更广泛的问题为非多项式确定问题，即NP问题。其中SAT问题就是一种NP问题。NP完全问题是当代计算机科学中的核心问题之一，现已证明大量重要的计算机科学的理论和应用问题都归结为求解NP完全问题，但到目前为止，这一问题还没有得到有效解决。经过近几十年来的研究，人们普遍认为NP完全问题的研究可以通过对某一特殊的NP完全问题作深入具体的研究来进行。SAT问题是一典型的NP完全问题，对这一典型问题进行深入的理论分析有助于NP完全问题研究的向前发展。SAT问题与人工智能中的推理问题有着直接而密切的关系，然而由于SAT问题是NP完全的因此不大可能存在一个求解该问题的通用快速算法。但是人们没有放弃针对特殊类型SAT问题的算法的设计与研究。对于求解SAT问题的不同的实用算法，需要有SAT问题的实例来衡量这些算法的性能。经常使用的是随机产生的SAT问题的实例。但也有不少学者研究出了一些将其他重要的组合问题有效的转化为SAT问题的方法。这些问题包括图着色积木世界规划，VLSI设计，Jobshop排工问题等。这些问题本身也是难解问题，由此转化的SAT问题实例有一定的难度，且具有一些随机产生的SAT问题的实例所不具有的特性。有效的解决这类SAT问题不仅对理论与方法的发展很重要，而且也具有一定的应用前景。二.国内外研究现状以下介绍一下有关遗传算法和SAT问题研究的一些新进展：1.求解SAT问题的改进粒子群优化算法利用限制性公式的相关理论将可满足性问题(SAT)等价转换为定义在{0,1}n上的多项式函数优化问题，并将二进制粒子群优化算法(BPSO)与局部爬山搜索策略相结合，给出了一种求解SAT问题的新算法：基于局部爬山搜索的改进二进制粒子群优化算法(简称IBPSO)。计算表明：对于随机3-SAT问题测试实例，IBPSO算法的求解结果均优于当前较流行的局部搜索算法SAT1-3和WARSAT算法，这说明利用IBPSO算法求解SAT问题是一种高效可行的新方法。2.利用近似解加速求解SAT问题的启发式完全算法结合DPLL

完全算法能够证明可满足性(SAT)

问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT

问题的启发式完全算法。

首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策。该算法引导完全算法优先搜索近似解所在的子空间,加速解器找到可满足解的过程,为SAT

问题的求解提供了一种新的有效途径。实验结果表明,该算法有效地提高了决策的精度和SAT

解决器的效率,对很多实例非常有效。3.SAT问题中局部搜索法的改进局部搜索方法在求解SAT问题的高效率使其成为一研究热点．提出用初始概率的方法对局部搜索算法中变量的初始随机指派进行适当的约束．使在局部搜索的开始阶段，可满足的子句数大大增加，减少了翻转的次数，加快了求解的速度．用该方法对目前的一些重要的SAT

问题的局部搜索算法(如WSAT，TSAT，NSAT，SDF等)进行改进。通过对不同规模的随机3-SAT问题的实例和一些不同规模的结构性SAT问题的实例，以及利用相变现象构造的难解SAT实例测试表明，改进后的这些局部搜索算法的求解效率有了很大的提高．该方法对其他局部搜索法的改进具有参考价值．4.

一种新的SAT问题预处理算法提出了一项新的正向推理技术：对称扩展的一元子句推倒技术。与传统的一元子句推导技术相比．文中的方法通过在一元子句推导过程中添加对称的蕴涵关系从而能够推导出更多的一元子句。基于这项新技术实现了一个可满足性问题(SAT)预处理器Snowball。实验结果验证了该项技术的有效性，表明该预处理器Snowball能够有效地化简SAT问题的规模并减少解决SAT问题的时间。5.一种求解难3-SAT问题的新方法根据Kennedy和Eberhart提出的二进制粒子群优化算法(BinaryParticleSwarmOptimizers)，基于局部随机搜索策略，给出一种求解难3-SAT问题的新方法：基于局部随机搜索的改进二进制粒子群优化算法(ModifedBinaryParticleSwarmOptimizersBasedonlocalstochasticserch,简称MBPSO)。数值实验表明，对于随机产生的3-SAT问题测试实例，该算法是一种高效实用的新方法。6.随机k-SAT问题的回溯算法分析通过研究搜索树的平均节点数，分析了回溯算法求解随机k-SAT问题的平均复杂性，结果表明：找到实例所有的解或证明其无解所需的平均节点数随变量数n的增加而指数增长；随着r(子句数/变量数)的增大求解将变得越来越容易，而且当r趋近于无穷大时，以n为指数，平均节点数的底数将无限地趋近于1。因此尽管回溯算法求解随机k-SAT问题具有指数的平均复杂性，但当r充分大以后，许多实例的求解将变得非常容易。7.采用正交免疫克隆粒子群算法求解SAT问题根据Kennedy和Eberhart提出的二进制粒子群算法，基于抗体克隆选择理论提出一种求解合取范式可满足问题的粒子群算法―正交免疫克隆粒子群算法。该算法将合取范式可满足问题转换为求解目标函数最小值的优化问题，为提高收敛速度，根据子句的先验知识计算出个体的初始指派概率对种群进行初始化。为了避免算法早熟收敛提高粒子群个体解分布的均匀性，将离散正交交叉算子用于免疫基因操作中，并给出适应于求解合取范式可满足问题的免疫粒子群进化算子。实验采用标准SATLIB库中变量个数从20-250的3700个不同规模的标准合取范式可满足问题对正交免疫克隆粒子群算法的性能作了全面的测试，并与标准粒子群算法和免疫克隆选择算法进行了比较。结果表明，正交免疫克隆粒子群算法的成功率在三个算法中最高，运行时间和评价次数最少。8.基于子句权重学习的求解SAT问题的遗传算法提出了一种求解SAT问题的改进遗传算法(SAT-WAGA)。SAT-WAGA算法有多个改进性特点：将SAT问题的结构信息量化为子句权重，增加了学习算子和判定早熟参数，学习算子能根据求解过程中的动态信息对子句权重进行调整，以便防止遗传进程的早熟，同时，算法还采用了最优染色体保存策略防止进化过程的发散。实验结果表明：与一般遗传算法相比SAT-WAGA算法在求解速度、成功率和求解问题的规模等方面都有明显的改善。9.求解SAT问题的分级重排搜索算法局部搜索法在SAT问题上的成功运用已引起越来越广泛的重视，然而，它在面对不可满足问题例时的局限性不能不被考虑。分级重排搜索算法MSRA(multi-stagesearchrearrangementalgorithm)正是为克服局部搜索法的不完备性而提出的，准确地讲，它是几种算法在思想上的集成，但为明确起见，把其最典型的分级重排过程作为名称。分级重排搜索算法在求解SAT问题时，能表现出优于单一求解策略(如局部搜索法或回溯算法)的明显特性。由于可根据约束条件的强弱来估计SAT问题例的可满足性，因此能够以此来确定更有效的求解策略。10.组织进化算法求解SAT问题基于组织的概念设计了一种新的进化算法一求解SAT的组织进化算法(OrganizationalEvolutiorraryAlgorithmforSATproblem,OEASAT)。OEASAT将SAT问题分解成若干子问题，然后用每个子问题形成一个组织，并根据SAT问题的特点设计了三种组织进化算子一自学习算子、吞并算子和分裂算子以引导组织的进化。根据组织的适应度，将所有组织分成两个种群一最优种群和非最优种群，然后用进化的方式来控制各算子，以协调各组织间的相互作用，OEASAT通过先解决子问题，再协调相冲突变量的方式来求解SAT问题。由于子问题的规模较小，相对于原问题来说较容易解决，这样就达到了降低问题复杂度的目的。实验采用标准SATLIB库中变量个数从20-250的3700个不同规模的标准SAT问题对OEASAT的性能作了全面的测试，并与著名的WalkSAT和RFEA2D的结果作了比较。结果表明，OEASAT具有更高的成功率和更高的运算效率。对于具有250个变量、1065个子句的SAT问题，OEASAT仅用了1.524s，表现出了优越的性能。11.求解SAT问题的拟人退火算法利用一个简单的变换，将可满足性问题转换为一个求相应目标函数最小值的优化问题，提出了一种用于跳出局部陷阱的拟人策略。基于模拟退火算法和拟人策略，为SAT问题的高效近似求解得出了拟人退火算法(PA)，该方法不仅具有模拟退火算法的全局收敛性质，而且具有一定的并行性、继承性。数值实验表明，对于随机产生的测试问题例，采用拟人策略的模拟退火算法的结果优于局部搜索算法、模拟退火算法以及近来国际上流行的WalkSAT算法，因此拟人退火算法是可行和有效的。三.个人的主要工作通过前文描述可知，SAT问题是指对于给定P={p1,p2,…，pn}上的一个CNFA，判断是否存在一个指派t使得A是可满足的。当公式A中的每个子句Ci(1≤i≤m)都只含有k个不互补的文字时，公式A被称为k-SAT问题。对于一个SAT问题实例A=C1∧C2∧…∧Ci∧…∧Cm，由DeMorgen定律[7]易证：﹁A﹁C1∨﹁C2∨…∨﹁Ci∨…∨﹁Cm(﹁c11∧﹁c12∧…﹁∧c1k…﹁∧c1r)∨(﹁c21∧﹁c22∧…∧﹁c2k…﹁∧c2r)∨…∨(﹁cm1∧﹁cm2∧…∧﹁cmk…﹁∧cmr).(1)由于对任意指派t，t(A)=1t(﹁A)=0。因此，在(1)式中若﹁cij=pij(1≤i≤m，1≤j≤n)，则用xij替换掉﹁cij，若﹁cij=﹁pij(1≤i≤m，1≤j≤n)，则用(1-xij)替换掉﹁cij。同时，用“+”(普通的加法运算)替换掉“∨”，用“．”(普通的乘法运算)替换掉“∧”，则将判定SAT问题实例的可满足问题等价地转换为判定{0,1}n上相应多项式函数是否存在零点的问题，其中且xij∈{x1,x2,…,xn}。由此，可以得到如下结论：定理1.SAT实例A可满足对于{0,1}n上函数，存在n元0-1向量X=(t1,t2,…,tn)使得。并且以X=(t1,t2,…,tn)为指派使得A可满足。例如，由定理1可得SAT实例A=(﹁p1∨p2∨p3∨﹁p4)∧(p1∨p3∨p4)∧(p1∨p2∨﹁p3)在{p1,p2,p3,p4}上是可满足的函数f(X)=x1(1-x2)(1-x3)x4+(1-x1)(1-x3)(1-x4)+(1-x1)(1-x2)x3在{0,1}4上存在零点，即存在4元0-1向量X=(t1,t2,,t3,t4)∈{0,1}4，使得f(X)=0。SAT问题中指派t=<t1,t2,…,tn>为二进制向量，与SGA算法的个体表示天然一致；同时，由定理1结论可知，利用函数，个体的适应度计算也非常方便。因此，将SGA用于求解SAT问题是非常自然的。虽然容易发现SGA可求解SAT问题，但是大量的实验结果表明：直接利用SGA求解SAT问题的效果并不理想，特别是对于较大规模的SAT实例，SGA的求解成功率很低。因为遗传算法是一种通用搜索算法，它通过模拟进化，适者生存过程，以随机形式将最适合于特定目标函数的种群通过重组产生新的一代，在进化过程中通过选择，重组和突变逐渐产生优化问题的解决方案。但随着人们对遗传算法的深入研究，发现现行遗传算法存在着一些缺陷，如早熟现象，即未成熟收敛；局部搜索能力弱，易陷于局部最优点；随机性大，容易在迭代过程中破坏群体中的优秀个体，从而导致收敛速度减慢；计算参数均是根据经验确定，很难找到最确切的值。为了提高求解的效率，需要借鉴其他的算法或技术来改进SGA，为此我们尝试将SGA与局部搜索算法(LocalSearchAlgorithm,LSA)相结合，在交叉运算和变异运算的基础上，利用LSA来优化所得的每个个体，然后再利用选择运算实现种群的进化。由此得到一种改进的混合遗传算法(ModifiedHybridGeneticAlgorithm，MHGA)。下面先介绍LSA算法。设待求解问题为最小优化问题，X=(x1,x2,…,xn)为n元向量，f(X)为目标函数值，T=(t1,t2,…,tn)为X在{0,1}n上的一个赋值，Neg(T,i)表示对T的第i个分量ti取反，即若在T中ti=1，则Neg(T,i)中ti=0；若在T中ti=0，则Neg(T,i)中ti=1。于是LSA(X)算法的一般原理描述如下：算法2．LSA算法1.Random(T);//随机产生X的一个赋值TCompute(f(T));//计算对应的函数值T1←T4.Fori=1tonDo5.T’←Neg(T,i)//从上一代种群中选择个体加入P1中Iff(T’)≤f(T1)ThenT1←T’7.Return(T1,f(T1))对随机产生的赋值T，LSA算法通过尝试改变其每个分量来寻找最优值，显然算法的复杂性为Θ(n)。由于其线性阶复杂性，实际在应用该算法求解问题时可以通过多次迭代来进行求解。下面将此方法与SGA算法相结合，给出一种用于求解3-SAT问题的改进混合遗传算法(ModifiedHybridGeneticAlgorithm，MHGA)。算法3．MHGA算法1.t←0;2.initializeP(t)={Gi(t)=(g1(t),g2(t),…,gn(t))|gi(t)∈{0,1}∧1≤i≤m};//初始化个体evaluate(P(t));//评价个体4.While(notterminatecondition)Do//进行选择、交叉、变异,产生新一代种群5.P1←Select(P(t));//从上一代种群中选择个体加入P1中6.P2←Crossover(P1);//对P1中的个体进行交叉操作生成P27.P(t+1)←Mutate(P2);//对P2中的个体进行变异操作Fori=1tomDoG1←G(t)Forj=1tonDo11.G’←Neg(G(t),i)//从上一代种群中选择个体加入P1中12.Iff(G’)≤f(G1)ThenG1←G’13.EndWhile;14.Output(Best,f(Best))//输出最优个体Best及其对应的函数值虽然MHGA算法与SGA算法相比，每次迭代增加了Θ(mn)的计算量，但由于其吸收了LSA算法的局部搜索能力，使得每次迭代所得到的个体相对更优，不但不会增加时间开销，相反使MHGA算法在求解质量和速度方面均优于SGA算法，这一点将在下一节通过实际求解大规模SAT问题实例来验证。四.数据分析实验环境为Pentium(R)4CPU2.19GHz,内存256MB，硬盘80GB，MicrosoftWindowsXPProfessional版本2002ServicePack2操作系统，并采用MicrosoftVisualC++6.0[8]编程实现。SAT问题实例的规模记为(n,m)，其中n为变元个数，m为子句个数。固定n=200，对m=300,350,…,700分别随机生成20个对不同规模的SAT问题实例，利用两个各算法分别计算，通过统计的可满足样例求得它们的成功率和运行时间。MHGA算法与SGA算法采用的参数如下：种群体大小为为300，交叉概率为0.7，变异概率为0.02，最大运行代数为1000。两算法的求解结果比较见图1和图2。由两个图的比较可以看出：MHGA的成功率不但比SGA高，而且所需的迭代次数也相对较少，这说明将遗传算法与局部搜索算法相结合来求解SAT问题是可行的和有效的。五.总结本文利用GA和局部搜索算法(LocalSearchAlgorithm,LSA)相结合，在将SAT问题等价转换{0,1}n上的多项式是否存在零点的判断问题基础上，给出一种求解3-SAT问题的改进混合遗传算法(ModifiedHybridGeneticAlgorithm，MHGA)，并利用随机大规模3-SAT问题实例验证了算法的可行性与有效性，在利用GA求解SAT问题方面进行有益的探讨。GA是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中物竞天择、适者生存的进化过程。在文章中使用遗传算法求解SAT问题，主要是利用了遗传算法的具体求解问题无关性以及全局优化的优点。用遗传算法求解SAT问题可以作为很多实际应用领域中一个基础，因此找出求解SAT问题的高效的遗传算法具有很多的实际意义，而将其应用于更多领域，同时研究应用中存在的问题也是值得关注的热点。致谢本次项目得到石家庄经济学院科技处和石家庄经济学院学生科技基金大力支持，在此，本课题组成员致以衷心的感谢。本论文在贺老师的指导下完成，他认真负责的工作态度、严谨的治学精神和深厚的理论水平都使我受益匪浅。他不仅在理论上给了我巨大的支持，而且在算法的实施上还给了我很大的帮助，在此我向老师表达深深的谢意。另外，我还要向帮助我支持我的各位同学表示感谢，尤其是同课题组的同学，他们在资料的查找和研究报告的校对方面给与我很大的帮助。参考文献[1]黄拙，张健．由一阶逻辑公式得到命题逻辑可满足性问题实例[J]．软件学报，2005，16(3)：329-335。[2]张德富，黄文奇，王厚祥．求解SAT问题的拟人退火算法[J]．计算机学报，2002,25(2)：148-152。[3]贺毅朝，王彦祺，寇应展．一种求解3-SAT问题新方法．计算机工程与应用，200642(16)：70-72。[4]徐宗本．计算智能—模拟进化计算．北京：高等教育出版社，2005。[5]贺毅朝，王熙照，寇应展．一种具有混合编码的二进制差分演化算法．计算机研究与发展，2007，44(9)，1476-1484。[6]刘勇，康立山等．非数值并行算法(二)―遗传算法．北京：科学出版社，2003。[7]张健．逻辑公式的可满足性判定―方法、工具及应用[M].北京：科学出版社，2000。[8]杜丁柱，葛可一，王洁．计算复杂性导引[M].北京：高等教育出版社，2002：35-37。[9]李未，黄雄．命题逻辑可满足性问题的算法分析[J]．计算机科学，1999,26(3)：1-9。[10]李未，黄文奇．一种求解SAT问题的数学物理算法．中国科学，1994,24(11)：1208-1217。[11]王文杰，叶世伟．人工智能原理与应用．北京：人民邮电出版社，2004。[12]徐宗本，张讲社，郑亚林．计算智能中的仿生学：理论与方法．北京：清华大学出版社，2001。[13]杨晋吉，苏开乐．SAT问题中局部搜索法的改进[J]．计算机研究与发展，2005,(1)：60-65。[14]吴胜．用遗传算法求解3-SAT问题[J]．福建电脑，2005,(7)：49,51。[15]王小平，曹立明．遗传算法-理论、应用与软件实现[M].西安：西安交通大学出版社，2002。[16]耿素云，屈婉玲，王捍贫．离散数学教程．北京大学出版社，2002。[17]康博创作室．VisualC++6.0高级编程．清华大学出版社，2000。附录/*****************************************************************/#include<stdio.h>#include<stdlib.h>#include<time.h>#include<math.h>/*****************************************************************/#definerdint(i)(rand()%(int)(i))#definerdft()(double)((double)rdint(30000)/(30000.0))#definePOPSIZE100#defineDIMENSION50#defineMAXITERA1000#defineN3*DIMENSION#defineM3#definePCROSS0.5#definePMUTATE0.1/*****************************************************************/structindi{ intx[DIMENSION]; intF; intH; doublefitness;}population[POPSIZE],temppop[POPSIZE],tempbest;intCNF[N][M];intgeneration;intbest,worst;FILE*fp;/*****************************************************************/voidinitialize(void);voidinitsatcnf(void);voidinitpop(void);voidinitreport(void);voidevaluate(void);voidcalculation(int);voidgennewpop(void);voidselection(void);voidgencoress(void);voidgenmutate(void);voidreplace(void);voidoutputresults(void);/*****************************************************************/voidmain(){ charch; generation=0; srand(time(NULL)); if((fp=fopen("SAT.txt","w"))==NULL) { printf("\nCannotopeninputfile\n");exit(1);} initialize(); evaluate(); outputresults(); while(generation<MAXITERA) { gennewpop(); evaluate(); //ch=getchar(); generation++; outputresults(); } fclose(fp);}/*****************************************************************/voidinitialize(void){ initsatcnf();initpop(); initreport();}/*****************************************************************/voidinitsatcnf(void){ inti,j,k; for(i=0;i<N;i++) { for(j=0;j<M;j++) { k=0; CNF[i][j]=rdint(DIMENSION); if(rand()%2==0) CNF[i][j]=-CNF[i][j]; while(j!=0&&k!=j) { for(k=0;k<j;k++) { if(abs(CNF[i][j])==abs(CNF[i][k])) break; } if(k!=j) { CNF[i][j]=rdint(DIMENSION); if(rand()%2==0) CNF[i][j]=-CNF[i][j]; } } } }}/*****************************************************************/voidinitpop(void){ inti,j; for(i=0;i<POPSIZE;i++) { for(j=0;j<DIMENSION;j++) { if(rdft()<0.5) population[i].x[j]=0; else population[i].x[j]=1; } calculation(i); }}/*****************************************************************/voidinitreport(void){ inti,j; printf("ThepolynomalofSATis:\n\n"); for(i=0;i<N;i++) { printf("["); for(j=0;j<M;j++) { if(CNF[i][j]<0) printf("x%d",-CNF[i][j]); if(CNF[i][j]>=0) printf("(1-x%d)",CNF[i][j]); } if(i<N-1)printf("]+"); elseprintf("]"); } printf("\n\n");}/*****************************************************************/voidevaluate(void){ inti,j; inttotalH=0;best=0; worst=0; for(i=1;i<POPSIZE;i++) { if(population[worst].F<population[i].F) worst=i; if(population[best].F>population[i].F) best=i; } for(i=0;i<POPSIZE;i++) { population[i].H=population[worst].F-population[i].F; totalH+=population[i].H; } for(i=0;i<POPSIZE;i++) { population[i].fitness=population[i].H/(double)totalH; for(j=0;j<DIMENSION;j++) tempbest.x[j]=population[best].x[j]; tempbest.F=population[best].F; }}/*****************************************************************/voidcalculation(intm){ inti,j; intindex; inttemp=0,tempt=1; for(i=0;i<N;i++) { tempt=1; for(j=0;j<M;j++) { index=CNF[i][j]; if(index<0) tempt*=population[m].x[-index]; else tempt*=1-population[m].x[index]; } temp+=tempt; }population[m].F=temp;}/*****************************************************************/voidselection(void){ inti,j,k; doublerand1; for(i=1;i<POPSIZE;i++) population[i].fitness+=po