（计算机应用技术专业论文）基于进化非选择算法的可满足性问题求解.pdf

摘要 摘要 进化非选择算法是通过借鉴生物免疫进化机制与免疫非选择机制而提出的， 具有较好的全局搜索能力。可满足性问题( t h es a t i s f i a b i l i t yp r o b l e m ，s a t ) 是六 个基本的n p 完全问题之一，其他n p 完全问题均可在多项式时间内转换为可满 足性问题。因此，s a t 问题具有重要的研究价值。 本文主要分析进化非选择算法用于可满足性问题求解时的性能，并与传统的 启发式翻转方法( f l i ph e u r i s t i c ) 相结合，以设计高效的可满足性问题求解算法。 具体工作包括以下几个方面。 ( 1 ) 从实验角度分析了非选择算子在求解可满足性问题时的作用。首先， 设计了用于s a t 求解的e n s a s a t 算法( e v o l u t i o n a r yn e g a t i v es e l e c t i o n a l g o r i t h mf o rs a t ) ，通过与不含非选择的进化算法的实验比较，分析了非选择算 子在协助算法跳出局部最优方面的作用。其次，将传统的启发式翻转方法引入到 进化非选择算法中，设计了用于s a t 求解的e n s a f h s a t 算法( e v o l u t i o n a r y n e g a t i v es e l e c t i o na l g o r i t h mc o m b i n e dw i t hf l i ph e u r i s t i cf o rs a t ) ，并与不含非选 择的e s f h s a t 算法( e v o l u t i o n a r ys t r a t e g yc o m b i n e dw i t hf l i ph e u r i s t i cf o rs a t ) 在同等条件下进行实验比较，分析了非选择算子在协助算法跳出局部最优方面的 作用。 ( 2 ) 提出了用于求解可满足性问题的混合算法h e n s a s a t ( h y b r i do f e v o l u t i o n a r yn e g a t i v e s e l e c t i o n a l g o r i t h m ，f l i ph e u r i s t i c ，b a c k f o r w a r d f l i p h e u r i s t i ca n d v e r t i c a l c l i m b i n gf o rs a t ) 。h e n s a s a t 将进化非选择、启发式翻转、退步进步启 发式翻转局部搜索和垂直爬山法等相结合而设计。实验结果表明，h e n s a s a t 在求解可满足性问题，尤其是在求解大规模可满足性问题时，与当前代表性算法 g a s a t 相比具有较好的性能。同时，通过实验对非选择算子在协助算法跳出局 部最优方面的作用进行了分析，给出了参数设置的般方法。 总的来说，本文对非选择算子在求解可满足性问题时的作用作了具体分析， 提出了用于求解可满足性问题的混合算法h e n s a s a t ，不仅对可满足性问题本 身的求解有参考价值，而且在设计用于其他约束满足及组合优化问题的进化非选 择算法时有一定的指导意义。 关键词：可满足性问题进化非选择算法非选择启发式翻转 a b s t r a c t a b s t r a c t t h ee v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m ( e n s a ) i sp r o p o s e db yd r a w i n g t h em e c h a n i s m so fe v o l u t i o na n dn e g a t i v es e l e c t i o ni nb i o l o g i c a li m m u n es y s t e m t h e e n s ah a sg o o dg l o b a ls e a r c ha b i l i t y t h es a t i s f i a b i l i t yp r o b l e m ( s a t ) i so n eo ft h e s i xb a s i cn p - c o m p l e t ep r o b l e m s o t h e rn p - c o m p l e t ep r o b l e m sc o u l db et r a n s f o r m e d i n t ot h es a t i s f i a b i l i t yp r o b l e mi np o l y n o m i a lt i m e t h e r e f o r e ，t h es a t i s f i a b i l i t yh a s i m p o r t a n tr e s e a r c hv a l u e t h i st h e s i sa i m sa te v a l u a t i n gt h ep e r f o r m a n c eo ft h ee v o l u t i o n a r yn e g a t i v e s e l e c t i o na l g o r i t h mf o r t h e s a t i s f i a b i l i t yp r o b l e m i no r d e rt od e s i g ne f f i c i e n t a l g o r i t h m sf o rt h es a t i s f i a b i l i t yp r o b l e m ，t h ee n s ai sc o m b i n e dw i t ht h ec l a s s i c a l f l i ph e u r i s t i c t h em a i nw o r k si nt h i st h e s i si n c l u d et h ef o l l o w i n ga s p e c t s ( 1 ) t h ee f f e c to fn e g a t i v es e l e c t i o n ( n s ) i sa n a l y z e di nt h ee n s au s e df o rt h e s a t i s f i a b i l i t yp r o b l e mb ye x p e r i m e n t s t h ea l g o r i t h m c a l l e d e n s a - s a t ( e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h mf o rs a t ) i sd e s i g n e df o r t h es a t i s f i a b i l i t y p r o b l e m s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en sh a sg o o da b i l i t yo fh e l p i n gt h e e n s a s a te s c a p ef r o ml o c a lo p t i m ac o m p a r i n gt ot h ee v o l u t i o n a r ya l g o r i t h mw h i c h t h en si sn o ti n c l u d e d i na d d i t i o n ，t h ea l g o r i t h mc a l l e de n s a f h s a t ( e v o l u t i o n a r y n e g a t i v es e l e c t i o na l g o r i t h mc o m b i n e dw i t hf l i ph e u r i s t i cf o rs a t ) i sd e s i g n e df o r t h es a tp r o b l e m s e x p e r i m e n t a lr e s u l t sa l s os h o wt h a tt h en sc o u l dh e l pt h e e n s a f h - s a te s c a p ef r o ml o c a lo p t i m ac o m p a r i n gt ot h ee s f h - s a t ( e v o l u t i o n a r y s t r a t e g yc o m b i n e dw i t hf l i ph e u r i s t i cf o rs a t ) w h i c ht h en s i sn o ti n c l u d e d ( 2 ) ah y b r i da l g o r i t h mf o rt h es a t i s f i a b i l i t yp r o b l e m sc a l l e da st h eh e n s a - s a t i sp r o p o s e di nt h i st h e s i s t h eh e n s a - s a ti sd e s i g n e db yt h ec o m b i n a t i o no fe n s a ， t h ef l i ph e u r i s t i c ，t h eb a c k f o r w a r d f l i p h e u r i s t i cp r o c e d u r ea n dt h ev e r t i c a l c l i m b i n g m e t h o d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h eh e n s a s a ti sv e r yc o m p e t i t i v ew i t ht h e c l a s s i c a l e v o l u t i o n a r ya l g o r i t h m su s e df o r t h es a t i s f i a b i l i t yp r o b l e m s f o rt h e l a r g e - s c a l es a t i s f i a b i l i t yp r o b l e m s ，t h ep r o p o s e da l g o r i t h mh a sd o m i n a n ta d v a n t a g e s o nm o s tt e s ti n s t a n c e sc o m p a r i n gt ot h eg a s a tw h i c hi st h es t a t e - o f - t h e a r t a l g o r i t h mf o rs o l v i n gt h el a r g e - s c a l es a t i s f i a b i l i t yp r o b l e m s a l s o ，t h ee f f e c to f t h en s w h i c hc o u l dh e l pt oe s c a p ef r o ml o c a lo p t i m ai sa n a l y z e d ，a n dag e n e r a lm e t h o df o r s e t t i n gp a r a m e t e r si sg i v e n a l li na l l ，t h eh y b r i da l g o r i t h mf o r t h es a t i s f i a b i l i t yp r o b l e m sc a l l e da st h e a b s t r a c t h e n s a s a ti sp r o p o s e di nt h i st h e s i s ac o n c r e t er e s e a r c hi sm a d eo nt h ee f f e c to f n si nt h eh e n s a s a t t h ew o r ki n t h i st h e s i si sn o to n l yi m p o r t a n tf o r t h e s a t i s f i a b i l i t yp r o b l e m s ，b u ta l s oh a ss o m eg u i d i n gs i g n i f i c a n c ef o rt h ee n s a su s e d f o ro t h e rc o n s t r a i n ts a t i s f a c t i o np r o b l e m sa n dc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s k e yw o r d s ：t h es a t i s f i a b i l i t yp r o b l e m ，e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m s ， n e g a t i v es e l e c t i o n ，f l i ph e u r i s t i c i i i 表格目录 表格目录 表2 1 实验参数设置l 彳 表2 2e n s a - s a t 与e s s a t 、e s s a t - i i 的成功率和平均翻转次数( 以代数作为结束 条件) 一1 9 表2 3e n s a s a t 与e s s a t 、e s s a t - i i 实际使用的代数比较( 以代数作为结束条件) ：! ( ) 表2 4e n s a s a t 与e s s a t 、e s s a t - i i 的成功率和平均翻转次数( 以翻转次数作为 结束条件) 2 0 表2 5e s f h s a t 与e n s a f h s a t 的成功率和平均翻转次数2 4 表3 1 在s u i t e a 上的对比实验结果3 6 表3 2 在s u i t eb 上的对比实验结果3 7 表3 3 在s u i t ec 上的对比实验结果。3 7 表3 4h e n s a s a t 与h e a s a t 在g o t t l i e b 上的成功率和平均翻转次数3 8 表3 5h e n s a s a t 与h e n s a s a t i i 在g o t t l i e b 上的对比实验结果4 0 表3 6 在手工实例上的对比实验结果( 与f l i p g a 和g a s a t 比较) 4 2 表3 7 在手工实例上的对比实验结果( 与g a s a t 比较) 4 3 表3 8 在随机实例上的对比实验结果( 与f l i p g a 和g a s a t 比较) 4 4 表3 9 在随机实例上的对比实验结果( 与g a s a t 比较) 4 4 表3 1 0 在工业类实例上的对比实验结果( 与g a s a t 比较) 一4 5 v i i 插图目录 插图目录 图1 1 进化非选择算法一般流程【6 ，7 】2 图1 2 启发式翻转过程( f l i p h e u r i s t i c ) 4 0 】7 图2 1 用于异常检测的e n s a s 算法流程1 1 图2 2 采用海明距离匹配规则时自我集划分完全检测器集示意图1 2 图2 3 采用，连续匹配规则时自我集划分完全检测器集示意图1 3 图2 4 用于s a t 求解的e n s a s a t 算法流程1 5 图2 5 不同匹配阈值对e n s a s a t 成功率的影响1 8 图2 6e n s a f h s a t 算法框架2 2 图2 7 退步进步启发式翻转局部搜索过程( b a c k f o r w a r d f l i p h e u r i s t i c ) 2 3 图2 8 自我集中与可行解匹配的自我个体数目2 6 图2 9 自我集中与启发式翻转后的个体匹配的自我个体数目2 6 图2 1 0自我集中与可行解匹配的自我个体数目2 6 图2 1 l自我集中与启发式翻转后的个体匹配的自我个体数目2 7 图2 1 2自我集中与可行解匹配的自我叶体数目2 7 图2 1 3自我集中与不可行解匹配的自我个体数目2 8 图2 1 4 自我集中与启发式翻转后的个体匹配的自我个体数目( 前2 5 6 个) 2 8 图3 1 用于s a t 求解的h e n s a s a t 算法框架3 l 图3 2 垂直爬山过程( v e r t i c a i c l i m b i n g ) 。3 3 图3 3 退步进步启发式翻转局部搜索过程( b a c k f o r w a r d f l i p h e u r i s t i c ) 3 4 图3 4h e n s a s a t - i i 对父代中每个个体的操作过程3 9 图3 5 自我集中与可行解匹配的自我个体数目4 6 图3 6自我集中与不可行解匹配的自我个体数目4 7 图3 7自我集中与可行解匹配的自我个体数目4 7 图3 8自我集中与不可行解匹配的自我个体数目4 7 图3 9自我集中与局部最优个体匹配的自我个体数目4 8 图3 1 0自我集中与启发式翻转后的个体匹配的自我个体数目4 8 图3 1 l自我集中与局部最优个体匹配的自我个体数目4 9 图3 1 2 自我集中与启发式翻转后的个体匹配的自我个体数目4 9 v i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：姐签字日期2 盟1 么 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 u 么开 口保密( 年) 作者签名塑嬲 导师徘 签字日期： 、歹芝 第1 章绪论 第1 章绪论 进化非选择算法( e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m ，e n s a ) 是将 进化机制与非选择机制相结合而提出的算法，可用于异常检测和优化问题求解 等。 可满足性问题( s a t i s f i a b i l i t yp r o b l e m ，s a t ) 是六个基本n p 完全( n p c o m p l e t e ，n p c ) 问题之一，其他n p c 问题均可在多项式时间内转换为s a t 问 题。因此，s a t 问题具有重要的理论研究意义。 本文旨在将迸化非选择算法用于s a t 问题求解，并与当前代表性算法比较， 分析算法的求解性能。本章首先介绍了进化非选择算法的基本流程和研究现状， 然后对可满足性问题的基本概念以及研究现状做了概述，最后介绍了本文的主 要研究内容。 1 1 进化非选择算法概述 进化非选择算法( e n s a ) 是通过借鉴生物系统中的免疫进化机制与免疫非 选择机制而提出的算法，具有很强的非我空间搜索能力，最初主要用于异常检 测【l 】。本节首先简要介绍了生物系统的免疫机制，然后重点介绍进化非选择算 法的基本流程和研究现状。 1 1 1 生物系统中的免疫进化机制与免疫非选择机制 生物免疫系统是一个复杂的自适应系统，人体通过免疫系统来识别“自我” 和“非我”，并对“非我”成分进行破坏和清除，从而维护人体健康 2 - 4 。 当抗原进入人体时，将刺激人体某些免疫细胞的增殖。这些免疫细胞的表 面受体与抗原表位相匹配，从而能够有效识别抗原。增殖后的免疫细胞经过变 异过程产生亲和度更高的抗体，该过程即是一个包括选择和变异的进化过程 【4 】。一部分免疫细胞以记忆细胞的形式存在人体中，相同或结构相似的抗原能 够快速地识别【3 】。 免疫非选择机制是在t 细胞成熟过程中发生的。未成熟的t 细胞在胸腺中 产生，然后与“自我”做匹配比较，即检测t 细胞是否能够与自身机体组织产 生免疫反应【3 ，5 1 。若与“自我”相匹配，则在胸腺中死亡，否则将继续发育至 成熟，然后离开胸腺进入人体发挥免疫保护作用。 第l 章绪论 1 1 2 进化非选择算法概述及流程 基于生物免疫非选择机制，f o r r e s t 等人【5 】提出了一种用于检测数据变化的 非选择算法( n e g a t i v es e l e c t i o na l g o r i t h m ，n s a ) ，n s a 可分为以下三个步骤。 s t e p1 定义自我集。定义一组长度为三的字符串s 表示自我集。 s t e p2 生成成熟检测器集。随机生成长度为上的检测器，若与s 中的每个 串都不匹配则加入到成熟检测器集，否则被丢弃。匹配规则一般采用部分匹配 规则，如，连续匹配、海明距离部分匹配等。 s t e p3 通过成熟检测器集来检测s 是否发生变化。 n s a 的检测器集是固定的，并且是预先生成的，并不具有自适应能力，也 不适合于优化问题的求解。 2 图i i进化非选择算法一般流程【6 ，7 】 进化非选择算法既具有进化算法的自适应和自学习能力，又能结合非选择 第l 章绪论 算法的特性。综合了两者的优势。在此，本文将包含有进化算子与非选择算子 的算法统称为进化非选择算法( e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i h t m s ， e n s a s ) 。算法的一般流程如图1 1 。其中进化算子操作可以为重组、变异或两 者的组合。 在进化非选择算法中，不仅要针对问题设计合理的进化操作算子，还包括 自我集的定义、匹配规则的设置、自我集更新策略等非选择相关参数的设定。 自我集定义与具体问题相关，如在异常检测【l 】中，一般将需要保护的串定 义为自我集；在逻辑电路自动设计【6 】中，将每代亲和度最差的几个个体定义为 自我集。 匹配规则一般采用部分匹配规则，最常用的有海明距离匹配规则、厂连续 位匹配规则 5 】以及分段匹配规则等。 在有些情况下，并不需要对自我集进行更新，即自我集是静态的，如异常 检测中定义的自我集。但是，当自我集具有大小限制且新加入到自我集的个体 数目超过最大数目限制时，需要对自我集进行更新，即删除自我集中的部分个 体，将新的符合要求的个体加入到自我集中。常用的自我集更新策略有先进先 出和根据亲和度排序等【6 】。 因此，影响进化非选择算法性能的参数，不仅包括与进化算子相关的参数， 还包括自我集大小、自我集每次更新数目、匹配阈值等。 1 2 进化非选择算法研究现状 进化非选择算法最初多用于异常检测和网络安全【l 】，目前已应用于软硬件 划分 7 】、机器人路径规划【8 】、组合优化问题求解 9 】等多个层面。目前，进化非 选择算法的主要研究工作如下。 ( 1 ) 在异常检测和网络安全方面。f o r r e s t 等人提出的非选择算法( n e g a t i v e s e l e c t i o na l g o r i t h m ，n s a ) 用于异常检测时有两个方面的不足，一是n s a 生成 成熟检测器的时间代价较大，与自我集大小呈指数关系：二是容易生成冗余检 测器。文献 1 l e 尸将免疫非选择机制与进化学习机制相结合，提出用于异常检测 的两种进化非选择算法。l u i s 【l o 在n s a 基础上提出了一种用于异常检测的带 有自适应机制的进化非选择算法，所提算法可以在较低的时间复杂度内生成不 含冗余检测器的成熟检测器集。l e e 和m a o 等人 1 l 】提出用于家庭网络异常检 测的自适应进化非选择算法，将一些预设的异常控制规则作为检测器，检测器 可根据家庭网络的反馈自适应进化和调整，一旦家庭网络因素发生异常变化， 即能被检测到。文献【1 2 】分析了e n s a 用于异常检测时的收敛性，主要分析了 3 第1 章绪论 两种不同的变异算子对收敛性的影响。文献 1 3 】分析了e n s a 用于异常检测时 的平均时间复杂度。 ( 2 ) 在优化问题求解方面。曹先彬等人【9 】将基因库进化与非选择相结合， 提出了用于旅行商问题( t r a v e l l i n gs a l e s m a np r o b l e m ，t s p ) 求解的算法。文献 【1 4 】从实验角度分析了e n s a 在函数优化问题中的求解性能。e n s a 在函数具 有多个局部最优解的情况下，由于非选择的作用，与进化算法( e v o l u t i o n a r y a l g o r i t h m ，e a ) 相比能够更好地跳出局部最优。 ( 3 ) 在机器人路径规划方面。文献【8 】基于免疫进化非选择机制提出用于 移动机器人路径规划的e n s a 。该算法【8 】在进化过程中通过非选择的作用，避 免进化过程中产生差的个体，加快算法收敛速度，同时通过多样性控制机制来 防止种群“早熟收敛 。 ( 4 ) 在工业设计领域。文献【7 】提出了一种用于软硬件划分的进化非选择 算法e n s a h s p ，包括四种操作算子( 选择算子，变异算子，非选择算子和自 我集更新操作) 。当选择算子采用赌论法并使用精英保留策略时，e n s a h s p 是 完全收敛的。需要注意的是，e n s a h s p 中的自我集是动态变化的，并且自我 集采用先进先出更新策略，这与异常检测有些不同，异常检测中的自我集通常 是不变的。文献【6 】提出了用于逻辑电路进化设计的e n s a ，算法通过非选择的 过滤，避免种群陷入局部最优，提高了算法效率和性能。 已有研究工作 6 8 ，1 4 】表明，非选择算子在e n s a s 中能够协助算法跳出局 部最优，从而加快收敛速度并提高算法成功率。而进化算法在组合优化问题求 解及约束满足问题求解方面很容易陷入局部最优，需要通过与某种启发式技术 相结合，才能获得较好的求解性能。e n s a s 在组合优化问题求解及约束满足问 题求解方面的研究还处于初始阶段，本文针对可满足性问题( s a t i s f i a b i l i t y p r o b l e m ，s a t ) 设计了相应的进化非选择算法，并分析非选择算子在s a t 问题 求解中的作用。 1 3 进化算法求解s a t 问题的研究现状 本节首先给出了s a t 问题的基本描述，然后重点介绍了进化算法在求解 s a t 问题方面的研究现状。 1 3 1s a t 问题概述 可满足性问题【1 5 】( s a t i s f i a b i l i t yp r o b l e m ，以下简称s a t 问题) 是研究对 于一个合取范式只是否存在一个变元赋值使得罗被满足。合取范式f 为若干 4 第1 章绪论 个子句的“逻辑与”连接，一个子句c 为若干个文字的“逻辑或”连接。一个 文字工为葺或i ，其中而为个布尔变量。若f 中每个子旬c 中所包含的文字 数目均为k ，则称为肛s a t 问题。 s a t 问题可用公式( 1 1 ) 形式化描述，其中x 为疗个布尔变量的集合，f 为m 个子句的逻辑与连接，当每个子句的撕与a 之和都等于k 时，( 抑表示 k - s a t 问题。 f ( x ) = e l c 2a - c m x = “，恐，而) g 2 砀v 焉2 v - 畅v 吩l v x j 2 v x j n ( 1 1 ) i e 1 , 硎 ，之，0e l l , n j i ，厶，瓜阻川 1 9 7 1 年c o o k 【1 6 建立了n p 完全性理论并证明了s a t 问题为第一个n p c 问题( n p c o m p l e t ep r o b l e m ) 。在p 4 ：n p 的前提下，n p c 问题在最坏情况下无 多项式时间算法可解决。其他n p c 问题均可在多项式时间内规约到s a t 问题 【1 7 。s a t 问题在自动推y - 里 1 8 、计算机辅助设计【1 9 】、错误诊断和逻辑调试【2 0 ， 2 1 1 、电路设计 2 2 ，2 3 、规划问题 2 4 】、计算机结构设计、以及计算机网络设计 等领域都有着直接的应用。因此，对s a t 的研究不仅具有重要的理论意义，而 且具有重要的应用价值。 目前求解s a t 问题的算法可分为两类，即完全算法【l5 ，2 5 ，2 6 和不完全算 法 2 7 - 4 0 。 完全算法用系统的方法检查问题实例的整个搜索空间，以确保找到解或者 宣布没有解，包括d p 6 0 算法【1 5 】、d p 算法 2 6 1 和回溯法【2 5 】等。完全算法的优 势在于能够确定问题实例是否有解，并且在问题实例存在多个解的情况下，能 够找到所有解，但是完全算法在最坏情况下具有指数级的复杂度，因而问题的 求解规模受到很大限制。 不完全算法【2 7 - 4 0 】的搜索初始于搜索空间的某一点，然后不断地从当前位 置向邻域位置迁移，且每一步迁移的决策基于局部启发式知识。对不完全算法， 即使没有找到解，也不能确定该问题实例没有解。不完全算法的优势在于能够 求解更大规模的问题实例。 用于s a t 求解的进化算法属于不完全算法。已有的不完全算法主要包括 g s a t 算法【2 9 】、g u 算法【3 3 】、w a l k s a t 算法 3 0 】、g u i d e dl o c a ls e a r c h 算法【2 8 】、 5 第1 章绪论 u n i t w a l k 3 1 等。此外，用于s a t 问题求解的不完全算法还有模拟退火法 4 2 ， 4 3 、禁忌搜索法【4 4 】、神经网络法【4 5 】，d n a 算法 4 6 】、吴方法 4 7 ，4 8 】、数学 物理方法【4 9 】等。值得指出的是，g u 【4 l 】等人对s a t 问题求解算法做了全面综 述，从算法空间( a l g o r i t h ms p a c e ) 的角度研究了不同算法的原理和特性。 本文所提算法主要与用于s a t 求解的进化算法进行比较。下一小节将重 点介绍用于s a t 求解的进化算法的研究现状。 1 3 2 用于s a t 求解的进化算法的研究现状 进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 4 ，5 0 ，5 1 是一种基于启发式的不 完全求解算法，已经被用于求解s a t 问题 3 2 ，3 4 3 6 ，5 2 。 在研究初期，很多文献对e a 用于求解s a t 问题挣怀疑态度。d ej o n g 和 s p e a r s 【3 2 】在1 9 8 9 年提出用于求解s a t 问题的遗传算法( g e n e t i ca l g o r i t h m ， g a ) ，并且指出g a 并不优于经仔细调整且与特定问题相关( h i g h l yt u n e d , p r o b l e m s p e c i f i c ) 的算法。f l e u r e n t 和f e r l a n d 3 4 在1 9 9 6 年指出g a 算法在求 解s a t 问题时其性能不如局部搜索算法。 近期研究表明，e a 通过采用附加技术可以产生很好的求解结果。这些技术 包括自适应的适应度函数以及与特定问题相关的算子设计( p r o b l e m s p e c i f i c v a r i a t i o no p e r a t o r ) 【3 7 - 4 0 ，5 3 1 。 经典的用于s a t 问题求解的进化算法主要有s a w e a ( s t e p w i s ea d a p t i o no f w e i g h t se v o l u t i o n a r ya l g o r i t h m ) 【3 7 】、r f e a ( r e f i n i n gf u n c t i o ne v o l u t i o n a r y a l g o r i t h m ) 【5 4 ，5 5 、f l i p g a 4 0 、a s a p ( a d a p t i v ee v o l u t i o n a r ya l g o r i t h mf o rt h e s a t i s f i a b i l i t yp r o b l e m ) 【5 3 、g a s a t 5 6 1 等，下面分别简单介绍。 e i b e n 和h a u w 【3 9 首先将逐步自适应权重机制( s t e p w i s ea d a p t i o no f w e i g h t s ，s a w ) 引入到遗传算法中对s a t 问题进行求解，由权重大小反应相应 子句的求解难度，并引导搜索过程。具体而言，s a w 机制给每一子句赋予一个 相应的权重，初始值为l ，然后每隔2 5 0 次适应度评估进行一次权重调整，只 增加不满足子句的权重，且每次增加l 。后来，b a c k 【3 7 等人在文【3 9 】基础上做 了进一步研究，提出了改进的算法，称为s a w e a 。在s a w e a 中，采用( 1 ，a ) 进 化策略，并给出了五对应不同变量数的最佳取值，变异采用m u t e o n e 操作，即 每次随机均匀选择一个变量翻转。j o n g 和k o s t e r s 【5 7 在s a w e a 基础上，对进 化策略生成每个个体( 共旯个个体) 应用了一个附加算子，即随机选择一些子 旬并且从尚未满足的子句中随机选择一个变量翻转。一般称含有附加算子的 6 第1 章绪论 s a w e a 为l s a w e a 。 r f e a 3 8 ，5 4 ，5 5 1 通过在进化过程中引入r e f i n i n gf u n c t i o n 来引导算法的搜 索方向。当采用可满足子句数目作为个体适应值函数时，容易导致多个不同个 体具有相同的适应值，加入r e f i n i n gf u n c t i o n 即是为了区分那些具有相同适应值 的不同个体 5 4 1 。g o t t l i e b 和v o s s 【5 4 ，5 5 在1 9 9 8 年提出了多种不同的r e f i n i n g f u n c t i o n ，并研究了不同r e f i n i n gf u n c t i o n 对算法求解性能的影响，一般将基于 r e f i n i n gf u n c t i o n 的进化算法统称为r f e a 。g o t t l i e b 和v o s s 【3 8 在2 0 0 0 年对 r e f i n i n gf u n c t i o n 做了进步研究，提出了两种求解性能更好r f e a ，为了加以 区别一般称为r f e a 2 和r f e a 2 + 。r f e a 2 与r f e a 2 + 相似，两者采用的种群大 小均为4 ，父代选择都采用2 锦标赛选择，并且每次替换掉种群中的最差个体， 同时，通过删除种群中的重复个体来维护种群多样性。变异操作则是从一个不 满足子句中随机选择一个变量进行翻转。r f e a 2 + 与r f e a 2 区别在于r f e a 2 + 在r e f i n i n gf u n c t i o n 调整中引入了s a w 机制。 输入：个体c h i l d 输出：个体c h i l d f i i p h e u r i s t i c 1 产生【l , h i 的随机置换s 2 i m p r o v e 1 3 w h i l e ( i m p r o v e o ) 4 i m p r o v e 0 5 i - - l 6 w h i l e ( f = 0 ) l o 将c 厅以中对应x 变量的位翻转 l1 i m p r o v e i m p r o v e + t r a p 1 2 f 什l 1 3 r e t u r n 幽i l d 图1 2 启发式翻转过程( f l i p h e u r i s t i c ) 4 0 】 m a r c h i o r i 和r o s s i 【4 0 】在1 9 9 9 年提出用于3 - s a t 问题求解的f l i p g a 算法。 f l i p g a 将标准遗传算子与启发式翻转( f l i ph e u r i s t i c ) 相结合，一方面通过遗 传算子来探索新的搜索空间，即加强全局寻优能力，另方面通过启发式翻转 7 第l 章绪论 加强对某一区域的局部寻优能力。在f l i p g a 中，种群大小设置为l o ，每代都 进行均匀交叉，并对交叉后的个体以概率0 9 进行变异( 对每个变量以概率0 5 进行翻转) ，在进化过程中，将每代中最好的两个个体加入到下一代种群。f l i p g a 的核心操作为启发式翻转，启发式翻转的过程如下：首先产生一个l 到刀的随 机置换i l 如。如，。厶( 刀为问题实例所包含的变量数) ，以丸2 如厶的顺序 扫描每一个变量i j ，并计算每个变量的适应值增量( 变量x 的适应值增量定义 为变量x 翻转后可满足的子句数与变量x 翻转前可满足的子句数之差) 。当某一 变量的适应值增量大于等于0 时，则翻转该变量。一轮扫描结束后，若该轮中 至少有一个变量的适应值增量大于0 ，则按f 1 2 3 “的顺序开始下一轮扫描， 否则启发式翻转过程结束并返回找到的适应值最高的个体。由于在本文的算法 设计中多次用到启发式翻转，图1 2 描述了该方法的具体过程，其中c h i l d g a i n ( x ) 表示个体c h i l d 中变量工的增量。 a s a p 是f l i p g a 的变体，由r o s s i 5 3 等人于2 0 0 0 年提出。a s a p 采用( 1 + 1 ) 进化策略，并且在进化过程中引入了自适应调整机制。a s a p 通过自适应调整 机制来调整变量的变异概率，并指导算法的重启过程。a s a p 动态维护一张具 有最好适应值个体的表，表中每个个体都代表了一个局部最优。当表的大小达 到预定值时，即判断表中所有个体在某一位置上的值是否都相同( 相同位描述 了种群陷入局部最优的共同特征) ，并根据相同位的多少对变量进行变异。相同 位越多变异概率p 越大( p 0 , 0 5 】) 。当表中等价类( 表中相同的个体为同一 等价类) 数目小于预定值时，算法重启。 g o t t l i e b 等人 5 8 】于2 0 0 2 年对s a w e a 、r f e a 、f l i p g a 和a s a p 等几个 经典进化算法做了综合比较和实验。实验结果表明，与局部搜索算法w s a t 【3 0 】 相比，进化算法通过附加技术可以获得较好的性能。 g a s a t 是l a r d e u x 、s a u b i o n 和h a o 【5 6 于2 0 0 6 年提出的求解s a t