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

石家庄经济学院 第四届学生科技基金科研项目 研究报告 项目名称： 基于改进遗传算法求解可满足性问题的研究 负 责 人： 曹国生 所属学院: 信息工程学院 指导老师： 贺毅朝 2008 年 1 月 20 日 2 目 录 1. 选题依据 1 2. 国内外研究现状 5 3个人主要工作 6 4. 数据分析 8 5. 总结 9 致 谢 10 参考文献 10 附 录 10 1 摘 要 本文通过介绍遗传算法和可满足性问题的起源、描述、重要理论意义和应用价值，进而提出了 一种新的方法来解决可满足性问题，即在将 SAT 问题等价转换为0,1 n 上的多项式是否存在零点的 判断问题基础上，将局部搜索算法(LSA)与 SGA 相结合，给出一种求解 3-SAT 问题的改进混合遗 传算法(MHGA) ，并通过对随机大规模 3-SAT 问题实例的实际求解验证了 MHGA 的可行性与有效 性。 关键词：遗传算法，可满足性问题 一. 选题依据 1. 遗传算法及其重要性 遗传算法(Genetic Algorithm，GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自 适应全局优化概率搜索算法，它起源于对生物系统所进行的计算机模拟研究。早在本世纪 40 年代， 就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过 程模拟、遗传过程模拟等研究工作。如 Fraser 的模拟研究，他提出了和现在的遗传算法十分相似的 概念和思想。进入 60 年代以后，美国密执安大学的 Holland 教授及其学生们受到这种生物模拟技 术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技 术-遗传算法。70 年代 De Jong 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计 算实验。Holland 和 De Jong 的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的 缺乏，其中，Holland 于 1975 年出版的著名著作系统地阐述了遗 传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。这一理论 首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，De Jong 的重要论文将 Holland 的模式理论与他的计算实验结合起来，并提出了诸如代沟等新的遗 传操作技术，可以认为，De Jong 所做的研究工作是遗传算法发展过程中的一个里程碑。在一系列 研究工作的基础上，80 年代由 Goldberg 进行归纳总结，形成了遗传算法的基本框架。 80 年代以后， 遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题，遗传算法的 应用领域也不断扩大。 生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力 于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景， 遗传算法就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计 算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力，它所借鉴的生物学基础 就是生物的遗传和进化。 达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下 去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个 方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代； 具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个 体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然 选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境 而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种 能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动 了生物的进化和发展。 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。主要是基于达尔文 进化论中“物竞天择，适者生存”理论，模拟生物进化的步骤, 将繁殖、杂交、变异、竞争和选择 2 等概念引入到算法中，通过对一组可行解的重新组合，改进可行解在多维空间内的移动轨迹或趋向, 最终走向最优解。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存检测”的迭代过 程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的 参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群 体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实 用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。 遗传算法求解问题的基本思想是从问题的解出发的，它将问题的一些可行解进行编码，这些已 编码的解即被当作群体中的个体（染色体） ，个体对环境适应能力的评价函数就是问题的目标函数， 模拟遗传学中的杂交、变异、复制来设计遗传算子，用优胜劣汰的自然选择法则来指导学习和确定 搜索方向。对由个体组成的群体进行演化，利用遗传算子来产生具有更高平均适应度值和更好个体 的群体，经过若干代后，选出适应能力最好的个体, 它就是问题的最优解或近似最优解，通过迭代 保留优秀个体、淘汰劣等个体来进化求解。 遗传算法将搜索空间映射成遗传空间，在遗传空间的每个个体代表搜索空间的一个解，由特定 数量的个体组成一个种群，由适应度函数得出各个个体的适应度值以标识当前个体的优劣，每一代 种群个体经过交叉、变异以及选择操作，生成新一代种群个体。一般情况，新一代种群个体都比原 种群个体的平均适应度值要好，经过多代的进化，最终得到一个最优个体。遗传算法的搜索过程是 一个由已知个体向未知个体搜索并且新个体比原个体更为优秀的过程，这适合该系统从已知的规则 搜索到更合理、准确的未知规则的要求。 遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的 优势。在传统的优化算法中，是从一个点开始搜索，易于陷入局部最优解。而遗传算法在搜索中同 时考虑了问题解空间中的许多点(一个点群) 搜索，搜索过程是从一组解迭代到另一组解，采用同时 处理群体中多个个体的方法，且对初始值不作要求，从而大大减少了陷入局部最优解的可能性。另 外，在传统的算法中需要提供一些辅助信息，而遗传算法仅利用问题本身所具有的目标函数的信息。 它不受搜索空间的限制，不必要求诸如连续性、导数的存在和单峰等假设，搜索过程不直接作用在 变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、 序列、矩阵、树、图、链和表）进行操作，仅用适应度来评估个体优劣，具有很强的鲁棒性，并且 具有内在的隐并行性和更好的全局寻优能力，稳健性极强、可操作性和简单性突出。此外，采用概 率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。 我们习惯上把 Holland1975 年提出的 GA 称为经典的 GA。它的主要步骤如下： （1）编码：GA 在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这 些串结构数据的不同组合便构成了不同的点。 （2）初始群体的生成：随机产生 N 个初始串结构数据，每个串结构数据称为一个个体，N 个个 体构成了一个群体。GA 以这 N 个串结构数据作为初始点开始迭代。 （3）适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义 方式也不同。 （4）选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代 繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献 一个或多个后代的概率大。选择实现了达尔文的适者生存原则。 （5）交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新 个体组合了其父辈个体的特性。交换体现了信息交换的思想。 （6）变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串 结构数据中某个串的值。同生物界一样，GA 中变异发生的概率很低，通常取值在 0.0010.01 之间。 3 变异为新个体的产生提供了机会。 经典遗传算法(SGA)的基本流程描述如算法 1 所示。 算法 1SGA 算法 1. t0; 2. initialize P(t); /初始化个体 3. evaluate(P(t); /评价个体 4. While (not terminate condition) Do /进行选择、交叉、变异,产生新一代种群 5. P1Select(P(t); /从上一代种群中选择个体加入 P1 中 6. P2Crossover(P1); /对 P1 中的个体进行交叉操作生成 P2 7. P(t+1) Mutate(P 2); /对 P2 中的个体进行变异操作 8. Evaluate(P(t+1) ; Compute(Best); /评价新种群,并计算当前最优个体 Best 9. tt+1; 10. EndWhile; 11. Output(Best, f(Best) /输出最优个体 Best 及其对应的函数值 GA 的计算过程为：选择编码方式，产生初始群体，计算初始群体的适应性值，如果不满足条 件则进行 选择，交换，变异，进而计算新一代群体的适应性值。 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题 的种类由很强的鲁棒性，所以广泛应用于很多学科。目前遗传算法所涉及的主要领域有自动控制、 规划设计、组合优化、函数优化、生产调度问题、神经网络学习过程、机器人学习、机器学习、遗 传编程、图象处理、信号处理、自动控制和人工生命等领域。 其中，函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于 一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便 地得到较好的结果。遗传算法对于组合优化中的 NP 完全问题也非常有效，例如，遗传算法已经在 求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。现在遗传算法已成 为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分 配等方面都得到的有效的应用。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已 在其中得到了初步的应用，并显示出良好的效果。例如用遗传算法进行航空控制系统的优化、使用 遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、 基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习 等，都显示出了遗传算法在这些领域中应用的可能性。除此之外，遗传算法已经在移动机器人路径 规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面 得到研究和应用。在图像处理中的优化计算方面遗传算法也找到了用武之地，目前已在模式识别、 图像恢复、图像边缘特征提取等方面得到了应用。人工生命与遗传算法有着密切的关系，基于遗传 算法的进化模型是研究人工生命现象的重要基础理论，人工生命与遗传算法相辅相成，遗传算法为 人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。而基 于遗传算法的机器学习，特别是分类器系统，在很多领域都得到了应用。例如：遗传算法被用于学 习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好的改进模糊系统的性能；基于遗传算 法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分 类器系统也可在学习式多机器人路径规划系统中得到了成功的应用。 此外在社会科学、生物学、 商业及工程等各种不同领域也得到了越来越广泛的应用。由此可见，遗传算法的应用研究已从初期 的组合优化求解拓展到了许多更新，更工程化的应用方面。 2. 可满足性问题的意义 可满足性问题(Satisfiability Problem, SAT)是由 Cook 证明的第一个 NPC 问题，它是计算科学中 4 的典型问题之一，也是当今计算机科学和人工智能研究的核心问题。其后的 NPC 问题证明都是建立 在 SAT 问题之上，研究解决 SAT 问题的有效算法不仅具有重大的理论意义，而且在智能规划、智 能决策、定理证明、电路诊断和优化计算、人工智能、机器学习、VLSI 集成电路设计与检测和数 据库检索等诸多领域有着实际的意义。 SAT 问题的一般性描述如下： 令 P=p1,p2,， pn是 n 个不同命题变元的集合，P 上公式的一个指派是函数 t：PT, F，用 n 元布尔向量 t=表示，其中 t0,1。显然， P 上存在 2n 个不同的指派。对于 P 上公 式 A，如果存在指派 t 使得 t(A)=1，则称 A 为可满足的；如果对于任意指派 t 使得 t(A)=0，则称 A 为不可满足的(或矛盾的)。 形如 C=ci1c i2c ik cir 的公式称为子句，其中 cij 为 pij 或p ij，称 cij 为 P 上的文字 (literal)。公式 A=C1C 2 C iC m 称为合取范式， 其中 Ci 为其子句(1 im)。如果存在 指派 t 使 A 满足，则称 A 是可满足公式。易知，合取范式 A 在指派 t 下是可满足的当且仅当其每 个子句 Ci 均是可满足的。于是，SAT 问题是指对于给定 P=p1,p2,，p n上的一个 CNF A，判断是 否存在一个指派 t 使得 A 是可满足的。当公式 A 中的每个子句 Ci(1im)都只含有 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 问题，该问题是否存在多项式时间算法目前还 未解决，在这种情况下，人们开始寻找不完全的但快速且非常实用的随机算法，即不完全算法。所 谓不完全是指：如果范式是可满足的，则此算法将停机并给出一个解，否则算法可能不停机。其代 表性的算法有：Local search 算法、拟人拟物算法、遗传算法(GA)、模拟退火算(SA)法和微粒群 算法(PSO)等。 由于有些优化算法所需要的计算空间难以承受，所以算法可解的问题在实践上不一定可解。P 类问题指具有多项式求解的算法的问题类。但到目前为止，许多优化问题仍没有找到求的最优解的 多项式时间算法，通常称这种比 P 类问题更广泛的问题为非多项式确定问题，即 NP 问题。其中 SAT 问题就是一种 NP 问题。 NP 完全问题是当代计算机科学中的核心问题之一，现已证明大量重 要的计算机科学的理论和应用问题都归结为求解 NP 完全问题，但到目前为止，这一问题还没有 5 得到有效解决。经过近几十年来的研究，人们普遍认为 NP 完全问题的研究可以通过对某一特殊的 NP 完全问题作深入具体的研究来进行。SAT 问题是一典型的 NP 完全问题，对这一典型问题进行 深入的理论分析有助于 NP 完全问题研究的向前发展。SAT 问题与人工智能中的推理问题有着直 接而密切的关系，然而由于 SAT 问题是 NP 完全的因此不大可能存在一个求解该问题的通用快速算 法。但是人们没有放弃针对特殊类型 SAT 问题的算法的设计与研究。对于求解 SAT 问题的不同的 实用算法，需要有 SAT 问题的实例来衡量这些算法的性能。经常使用的是随机产生的 SAT 问题的 实例。但也有不少学者研究出了一些将其他重要的组合问题有效的转化为 SAT 问题的方法。这些 问题包括图着色积木世界规划，VLSI 设计，Job shop 排工问题等。这些问题本身也是难解问题， 由此转化的 SAT 问题实例有一定的难度，且具有一些随机产生的 SAT 问题的实例所不具有的特性。 有效的解决这类 SAT 问题不仅对理论与方法的发展很重要，而且也具有一定的应用前景。 二.国内外研究现状 以下介绍一下有关遗传算法和 SAT 问题研究的一些新进展： 1. 求解 SAT 问题的改进粒子群优化算法 利用限制性公式的相关理论将可满足性问题(SAT)等价转换为定义在 0,1n 上的多项式函数优 化问题，并将二进制粒子群优化算法(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 提出的二进制粒子群优化算法 (Binary Particle Swarm Optimizers)，基 于局部随机搜索策略，给出一种求解难 3-SAT 问题的新方法：基于局部随机搜索的改进二进制粒 子群优化算法(Modifed Binary Particle Swarm Optimizers Based on local stochastic serch,简称 MBPSO)。 数值实验表明，对于随机产生的 3-SAT 问题测试实例，该算法是一种高效实用的新方法。 6. 随机 k-SAT 问题的回溯算法分析 6 通过研究搜索树的平均节点数，分析了回溯算法求解随机 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-stage search rearrangement algorithm)正 是为克服局部搜索法的不完备性而提出的，准确地讲，它是几种算法在思想上的集成，但为明确起 见，把其最典型的分级重排过程作为名称。分级重排搜索算法在求解 SAT 问题时，能表现出优于 单一求解策略(如局部搜索法或回溯算法 )的明显特性。由于可根据约束条件的强弱来估计 SAT 问题 例的可满足性，因此能够以此来确定更有效的求解策略。 10. 组织进化算法求解 SAT 问题 基于组织的概念设计了一种新的进化算法一求解 SAT 的组织进化算法(Organizational Evolutiorrary Algorithm for SAT problem,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 算法，因此拟人退火算法是可行和有 7 效的。 三. 个人的主要工作 通过前文描述可知，SAT 问题是指对于给定 P=p1,p2,，p n上的一个 CNF A，判断是否存在 一个指派 t 使得 A 是可满足的。当公式 A 中的每个子句 Ci(1im)都只含有 k 个不互补的文字时， 公式 A 被称为 k-SAT 问题。 对于一个 SAT 问题实例 A=C1C 2C iC m，由 De Morgen 定律 7易证： A C 1C 2 CiC m (c 11c 12c 1kc 1r)( c 21c 22 c 2kc 2r)( c m1c m2c mkc mr). (1) 由于对任意指派 t，t(A)=1 t(A)=0 。因此，在(1) 式中若c ij=pij (1im，1jn)，则用 xij 替换掉c ij，若 c ij=p ij (1im，1jn)，则用(1-x ij)替换掉c ij。同时，用“+”(普通的加 法运算) 替换掉“” ，用“ ” (普通的乘法运算)替换掉“” ，则将判定 SAT 问题实例的可满足问 题等价地转换为判定0,1 n 上相应多项式函数 mi nnxfxf1221 ),.(),.( 是否存在零点的问题，其中 且 xijx 1,x2,xn。由此，可以得到如下结论： rjinif121),.( 定理 1. SAT 实例 A 可满足 对于0,1 n 上函数 ，存在 nmi nnxfxf1221 ),.(),.( 元 0-1 向量 X=(t1,t2,tn)使得 。并且以 X=(t1,t2,tn)为指派使得 A 可满足。0),.(21nttf 例如，由定理 1 可得 SAT 实例 A=(p 1p 2p 3p 4) (p1p 3p 4)(p 1p 2p 3) 在 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=为二进制向量，与 SGA 算法的个体表示天然一致；同时，由定 理 1 结论可知，利用 函数 ，个体的适应度计算也非常方便。因此， mi nxfxf12),.(),.( 将 SGA 用于求解 SAT 问题是非常自然的。 虽然容易发现 SGA 可求解 SAT 问题，但是大量的实验结果表明：直接利用 SGA 求解 SAT 问 题的效果并不理想，特别是对于较大规模的 SAT 实例，SGA 的求解成功率很低。因为遗传算法是 一种通用搜索算法，它通过模拟进化，适者生存过程，以随机形式将最适合于特定目标函数的种群 通过重组产生新的一代，在进化过程中通过选择，重组和突变逐渐产生优化问题的解决方案。但随 着人们对遗传算法的深入研究，发现现行遗传算法存在着一些缺陷，如早熟现象，即未成熟收敛； 局部搜索能力弱，易陷于局部最优点；随机性大，容易在迭代过程中破坏群体中的优秀个体，从而 导致收敛速度减慢；计算参数均是根据经验确定，很难找到最确切的值。 为了提高求解的效率，需要借鉴其他的算法或技术来改进 SGA，为此我们尝试将 SGA 与局部 搜索算法(Local Search Algorithm, LSA)相结合，在交叉运算和变异运算的基础上，利用 LSA 来优化 所得的每个个体，然后再利用选择运算实现种群的进化。由此得到一种改进的混合遗传算法 8 (Modified Hybrid Genetic Algorithm，MHGA)。 下面先介绍 LSA 算法。设待求解问题为最小优化问题，X=(x 1,x2,xn)为 n 元向量，f(X) 为目标 函数值，T=( t 1, t2,tn)为 X 在0,1 n 上的一个赋值，Neg( T, i)表示对 T 的第 i 个分量 ti 取反，即若在 T 中 ti=1，则 Neg(T, i)中 t i =0；若在 T 中 ti=0，则 Neg(T, i)中 t i =1。于是 LSA(X)算法的一般原理描 述如下： 算法 2LSA 算法 1. Random(T); /随机产生 X 的一个赋值 T 2. Compute(f(T); /计算对应的函数值 3. T1T 4. For i=1 to n Do 5. T Neg(T , i) /从上一代种群中选择个体加入 P1 中 6. If f(T )f(T 1) Then T1T 7. Return(T1, f(T1) 对随机产生的赋值 T，LSA 算法通过尝试改变其每个分量来寻找最优值，显然算法的复杂性为 (n)。由于其线性阶复杂性，实际在应用该算法求解问题时可以通过多次迭代来进行求解。下面将 此方法与 SGA 算法相结合，给出一种用于求解 3-SAT 问题的改进混合遗传算法(Modified Hybrid Genetic Algorithm，MHGA) 。 算法 3MHGA 算法 1. t0; 2. initialize P(t)=Gi(t)=(g1(t), g2(t), gn(t)| gi(t)0,11im; /初始化个体 3. evaluate(P(t); /评价个体 4. While (not terminate condition) Do /进行选择、交叉、变异,产生新一代种群 5. P1Select(P(t); /从上一代种群中选择个体加入 P1 中 6. P2Crossover(P1); /对 P1 中的个体进行交叉操作生成 P2 7. P(t+1)Mutate(P 2); /对 P2 中的个体进行变异操作 8. For i=1 to m Do 9. G1G(t) 10. For j=1 to n Do 11. G Neg(G(t), i) /从上一代种群中选择个体加入 P1 中 12. If f(G )f(G 1) Then G1G 13. EndWhile; 14. Output(Best, f(Best) /输出最优个体 Best 及其对应的函数值 虽然 MHGA 算法与 SGA 算法相比，每次迭代增加了 (mn)的计算量，但由于其吸收了 LSA 算法 的局部搜索能力，使得每次迭代所得到的个体相对更优，不但不会增加时间开销，相反使 MHGA 算法在求解质量和速度方面均优于 SGA 算法，这一点将在下一节通过实际求解大规模 SAT 问题实 例来验证。 四. 数据分析 实验环境为 Pentium(R) 4 CPU 2.19GHz, 内存 256MB，硬盘 80GB，Microsoft Windows XP Professional 版本 2002 Service Pack 2 操作系统，并采用 Microsoft Visual C+6.08编程实现。SAT 问 题实例的规模记为(n, m)，其中 n 为变元个数，m 为子句个数。固定 n=200，对 m=300,350,700 9 分别随机生成 20 个对不同规模的 SAT 问题实例，利用两个各算法分别计算，通过统计的可满足样 例求得它们的成功率和运行时间。 MHGA 算法与 SGA 算法采用的参数如下：种群体大小为为 300，交叉概率为 0.7，变异概率为 0.02，最大运行代数为 1000。两算法的求解结果比较见图 1 和图 2。由两个图的比较可以看出： MHGA 的成功率不但比 SGA 高，而且所需的迭代次数也相对较少，这说明将遗传算法与局部搜索 算法相结合来求解 SAT 问题是可行的和有效的。 MHGA与 SGA的 成 功 率 比 较 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 子 句 规 模 (x100) 成功 率( %) MHGA SGA MHGA与 SGA的 迭 代 次 数 比 较 0 200 400 600 800 1000 1200 1 2 3 4 5 6 7 8 9 子 句 规 模 (x100) 迭代 次数 MHGA SGA 五. 总结 本文利用 GA 和局部搜索算法(Local Search Algorithm, LSA)相结合，在将 SAT 问题等价转换 0,1n 上的多项式是否存在零点的判断问题基础上，给出一种求解 3-SAT 问题的改进混合遗传算法 (Modified Hybrid Genetic Algorithm，MHGA) ，并利用随机大规模 3-SAT 问题实例验证了算法的可 行性与有效性，在利用 GA 求解 SAT 问题方面进行有益的探讨。 GA 是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选 择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中物竞天择、适 者生存的进化过程。在文章中使用遗传算法求解 SAT 问题，主要是利用了遗传算法的具体求解问 题无关性以及全局优化的优点。用遗传算法求解 SAT 问题可以作为很多实际应用领域中一个基础， 因此找出求解 SAT 问题的高效的遗传算法具有很多的实际意义，而将其应用于更多领域，同时研 究应用中存在的问题也是值得关注的热点。 10 致 谢 本次项目得到石家庄经济学院科技处和石家庄经济学院学生科技基金大力支持，在此，本课题 组成员致以衷心的感谢。 本论文在贺老师的指导下完成，他认真负责的工作态度、严谨的治学精神和深厚的理论水平都 使我受益匪浅。他不仅在理论上给了我巨大的支持，而且在算法的实施上还给了我很大的帮助，在 此我向老师表达深深的谢意。 另外，我还要向帮助我支持我的各位同学表示感谢，尤其是同课题组的同学，他们在资料的查 找和研究报告的校对方面给与我很大的帮助。 参考文献 1 黄拙，张健由一阶逻辑公式得到命题逻辑可满足性问题实例J 软件学报，2005，16(3)： 329-335。 2 张德富，黄文奇，王厚祥求解 SAT 问题的拟人退火算法 J计算机学报，2002,25(2) ：148- 152。 3 贺毅朝，王彦祺，寇应展一种求解 3-SAT 问题新方法计算机工程与应用， 2006 42(16) ： 70-72。 4 徐宗本计算智能模拟进化计算北京：高等教育出版社， 2005。 5 贺毅朝，王熙照，寇应展一种具有混合编码的二进制差分演化算法计算机研究与发展， 2007，44(9)，1476-1484。 6 刘勇，康立山等非数值并行算法( 二)遗传算法北京：科学出版社，20