（计算机科学与技术专业论文）面向sat问题的免疫算法的改进研究.pdf

t h er e s e a r c ho ft h ei m p r o v e m e n to fi m m u n e a l g o r i t h m f o rs 峨p r o b l e m b y f a n c h a o d o n g b e ( n a i n a nu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g c o m p u t e ra p p l i c a t i o n i n t h e g r a d u a t es c h o o l o f h u n a n u n i v e r s i t y s u p e r v i s o r a s s o c i a t ep r o f e s s o rz h a n g y m g j i e m a y , 2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 蔷鼠 日期：a o l f 年岁月多oe l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 欠 二日期：如j | 年s 月3 0 日 日期：9 , ol1 年5 月3 口e l ；i 3 镦驻j ； 4 ， 硕士学位论文 摘要 命题可满足性问题( s a t 问题) 是第一个被证明的n p 完全问题，是一切n p 完 全问题的“种子 ，任何n p 完全问题都可在多项式时间内转化为s a t 问题进行 求解。当前s a t 求解方法在测试向量自动生成、符号模型检查及组合等价性检查 等电子设计自动化领域中得到了广泛的应用。可见，对s a t 问题的研究有着重要 的理论意义和应用价值。 目前求解s a t 问题的主要方法大致可以分为完全算法和不完全算法。如果问 题存在解，完全算法保证一定能找到问题的解。但随问题规模增大，s a t 问题的 计算复杂度呈指数增长；不完全算法虽然不能保证一定能找出问题的解，但是求 解速度快且通常能满足需求。故此，不完全算法逐渐成为求解s a t 问题的研究热 点。 本文主要针对不完全算法对s a t 问题的求解进行研究。首先介绍了s a t 问题 及其求解方法、免疫原理与免疫算法的基本知识，其次通过对s a t 问题求解和 s a t 问题全部解问题( a l l s a t 问题) 求解的研究，提出了两种分别适用于s a t 问 题和a l l s a t 问题求解的改进免疫算法。 首先，针对s a t 问题的求解，本文提出了一种基于海明距的改进免疫算法。 该算法基于海明距对抗体浓度进行定义，避免了耗时的对数计算，提高了算法效 率；鉴于传统变异算子存在的不足，算法引入了一种基于随机搜索思想的新变异 算子，该变异算子既可以加快种群进化速度，又可以防止进化后期产生“扰动 现象。实验结果表明：该算法在成功率、收敛速度等方面都比基于信息熵的免疫 算法有显著提高；与量子克隆免疫算法相比，该算法平均进化代数少、成功率高。 其次，针对a l l s a t 问题的求解，本文提出了一种改进的多种群克隆免疫算 法。该算法采用小生境方法与位爬山算法进行优化，因而具有能保持种群多样性、 收敛速度快等优点。算法首先同时进化多个种群，每个种群进行克隆、变异、选 择操作，对每个种群的最优个体进行位爬山操作。当子群进化一定代数之后，如 该子群的最优解是问题的解，则将该解放入小生境核集。然后比较种群中的个体 与小生境集合中个体的距离，如与小生境集合中某个个体距离很小则产生新个体 代替该个体构成新子群，然后重新开始多种群进化过程。对a l l s a t 问题求解的 实验结果表明：对小规模问题该算法能快速的求解出问题的所有解；对于传统方 法无法求解的大规模问题，该算法也能尽可能多地找出问题的解。 关键词：s a t 问题；a l l s a t 问题；免疫算法；海明距；多种群；小生境 i i 面向s a t 问题的免疫算法的改进研究 a b s t r a c t s a t i s f i a b i l i t yp r o b l e m ( s a tp r o b l e m ) i st h ef i r s tp r o v e dn pc o m p l e t ep r o b l e m ，a n di t i sa l s ot h e s e e d ”o fa l ln pc o m p l e t ep r o b l e m s a n yn pc o m p l e t ep r o b l e mc a nb e c o n v e r t e di n t os a tp r o b l e mt os o l v ei np o l y n o m i a lt i m e a tp r e s e n t ，t h em e t h o df o r s o l v i n gs a ti sw i d e l yu s e di nt h ea u t o m a t i cg e n e r a t i o no ft e s tv e c t o r s ，s y m b o l i c m o d e lc h e c k i n ga n de q u i v a l e n c ec h e c k i n ga sw e l la st h ef i e l do fe l e c t r o n i ca u t o m a t i o nd e s i g n t h e r e f o r e ，i ti so fg r e a ts i g n i f i c a n c ea n da p p l i e dv a l u et os t u d yt h es a t p r o b l e m c u r r e n t l yt h em a i nm e t h o df o rs o l v i n gs a tp r o b l e mc a nb ed i v i d e di n t oc o m p l e t e a l g o r i t h m sa n di n c o m p l e t ea l g o r i t h m s i ft h ep r o b l e mc a nb es o l v e d ，w ea r eb o u n dt o f i n dt h es o l u t i o nw i t ht h ec o m p l e t ea l g o r i t h m s h o w e v e r , w i t ht h ei n c r e a s i n gs c a l eo f t h ep r o b l e m ，s a tp r o b l e m s c o m p u t a t i o n a lc o m p l e x i t yw i l lg r e a t l yi n c r e a s el i k e e x p o n e n t t h ei n c o m p l e t ea l g o r i t h mc a nn o tg u a r a n t e et of i n dt h es o l u t i o no ft h e p r o b l e m ，b u ti tc a ns o l v et h ep r o b l e mw i t hg r e a ts p e e da n du s u a l l ym e e tt h er e q u i r e e m e n t s t h e r e f o r e ，i n c o m p l e t ea l g o r i t h mh a sg r a d u a l l yb e c o m ear e s e a r c hh o t s p o tf o r s o l v i n gs a tp r o b l e m t h i sp a p e rm a i n l yr e s e a r c h e dt h es a tp r o b l e m ss o l u t i o nw i t h i n c o m p l e t e a l g o r i t h mm e t h o d b a s e do nt h ei n t r o d u c a t i o no ft h es a tp r o b l e m s ，t h e i rs o l u t i o n s ， b a s i ck n o w l e d g eo fi m m u n ep r i n c i p l e sa n di m m u n e a l g o r i t h m ，t w ok i n d so fi m p r o v e d i m m u n ea l g o r i t h ma r ep r o p o s e da n da p p l i e di ns a t p r o b l e ma n da l l s a tp r o b l e mi n t h i sp a p e r f i r s t l y ，a ni m p r o v e di m m u n ea l g o r i t h mb a s e do nh a m m i n gd i s t a n c ei sp r o p o s e d f o rs o l v i n gt h es a tp r o b l e m t h ea l g o r i t h md e f i n e dt h ea n t i b o d yc o n c e n t r a t i o nw i t h h a m m i n gd i s t a n c e ，w h i c ha v o i d e dt h et i m e c o n s u m i n gc a l c u l a t i o na n di m p r o v e dt h e e f f i c i e n c yo ft h ea l g o r i t h m a c c o r d i n gt ot h es h o r t c o m i n g so ft r a d i t i o n a lm u t a t i o n o p e r a t o r , t h ea l g o r i t h mu s e dan e wm u t a t i o no p e r a t o r , w h i c hi sb a s e do nr a n d o m s e a r c h t h e m u t a t i o n o p e r a t o r n o to n l yc a na c c e l e r a t et h ee v o l u t i o n s p e e do f p o p u l a t i o n ，b u ta l s oc a np r e v e n tt h e “d i s t u r b e d ”p h e n o m e n o ni nt h el a t e rs t a g eo f e v o l u t i o n e x p e r i m e n t a lr e s u l t ss h o wt h a t ：t h ea l g o r i t h mi sb e t t e rt h a ni m m u n ea l g o r i t h mb a s e do ni n f o r m a t i o ne n t r o p yi ns u c c e s sr a t e ，c o n v e r g e n c er a t e ，e t c ，h a sl e s s a v e r a g ee v o l u t i o ng e n e r a t i o na n dh i g h e rs u c c e s sr a t et h a nq u a n t u mi m m u n ec l o n e a l g o r i t h m i i i 亡 s e c o n d l y ，a ni m p r o v e dm u l t i g r o u p c l o n i n gi m m u n ea l g o r i t h mi sp r o p o s e df o r s o l v i n ga l l s a tp r o b l e m t h i sa l g o r i t h m i so p t i m i z e dw i t hn i c h em e t h o da n d b i t c l i m b i n ga l g o r i t h m i th a st h ea d v a n t a g e so fk e e p i n gp o p u l a t i o nd i v e r s i t y , f a s t c o n v e r g e n c er a t e ，e t c a l g o r i t h me v o l v ek i n d so fp o p u l a t i o na tt h e s a m et i m e ，e a c h g r o u pc a nb ec l o n e d ，m u t a t i o n ，s e l e c t i o n ，t h eb e s ti n d i v i d u a l so fe a c hs p e c i e sw e r e c l i m b i n go p e r a t i o n w h e ns u b g r o u pe v o l v et oac e r t a i nn u m b e r ，i ft h eo p t i m a ls o l u t - i o ni st h ep r o b l e m ss o l u t i o n ，w ep u tt h i ss o l u t i o ni n t ot h en i c h ec o r es e t t h e nw e c o m p a r ee a c hi n d i v i d u a ld i s t a n c eb e t w e e ng r o u p sa n d n i c h ec o r es e t i ft h ed i s t a n c ei s v e r ys m a l l t h e ni tc a ng e n e r a t ean e wi n d i v i d u a l ，w h i c hr e p l a c et h eo l di n d i v i d u a lt o c o n s t i t u t ean e ws u b g r o u p ，a n dt h e nr e s t a r tt h ee v o l u t i o no fv a r i o u sg r o u p s t h ee x p e _ “m e n t a lr e s u i t sb a s e do nt h es o l u t i o nt oa l l s a tp r o b l e ms h o wt h a t ：f o rs m a l l s c a l e p r o b l e m s ，t h ea l g o r i t h mc a nf i n da l ls o l u t i o n sq u i c k l y a n df o rl a r g e - s c a l ep r o b l e m s ， w h i c ht r a d i t i o n a lm e t h o d sc a nn o ts o l v e ，t h ea l g o r i t h mc a nf i n da sm u c hs o l u t i o n sa s p o s s i b l e k e yw o r d s ：s a tp r o b l e m ；a l l s a tp r o b l e m ：i m m u n ea l g o r i t h m ；h a m m i n gd i s t a n c e ； a v a r i e t yo fg r o u p s ；n i c h e 面向s a t 问题的免疫算法的改进研究 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 插图索引“v i i 附表索引v i i i 第l 章绪论l 1 1 研究背景及意义”1 1 2 可满足性问题求解的研究现状2 1 2 1s a t 问题求解的研究现状“2 1 2 2a l l s a t 问题求解的研究现状3 1 3 免疫算法研究现状3 1 4 论文研究主要内容4 1 5 论文结构与章节安排“5 第2 章s a t 问题及其求解算法6 2 1s a t 问题相关定义6 2 2 求解s a t 问题的局部搜索算法7 2 3a l l s a t 问题的求解算法9 2 4s a t 及a l l s a t 问题应用领域”1 0 2 5 小结1 1 第3 章免疫优化算法概述“1 2 3 1 免疫系统一1 2 3 1 1 免疫系统分类1 2 3 1 2 免疫系统的基本机制1 3 3 1 3 免疫系统工作原理1 5 3 2 免疫算法15 3 2 1 免疫系统数学模型1 5 3 2 2 免疫算法的分类1 6 3 3 免疫算法应用2 0 3 4 小结2 2 第4 章求解s a t 问题的改进免疫算法”2 3 4 1 引言2 3 4 2 随机搜索算法2 4 4 3 改进的免疫算法一2 4 v 硕士学位论文 4 4 浓度定义等价性证明2 6 4 5s a t 问题求解2 6 4 6 实验与结果分析“2 8 4 7 小结2 9 第5 章求解a l l s a t 问题的改进多种群免疫算法3 0 5 1 引言3 0 5 2 小生境简介”3l 5 3 改进的多种群免疫算法“3 2 5 4 算法收敛性分析3 3 5 4 1 单种群克隆免疫算法收敛性分析3 3 5 4 2 改进免疫算法收敛性分析3 4 5 5 改进多种群免疫算法求解a l l s a t 问题“3 5 5 6 实验与结果分析3 6 5 6 1 求解的问题3 6 5 6 2 实验结果及分析一3 7 5 7 小结3 8 结论3 9 参考文献一41 致谢4 6 附录a ( 攻读学位期间发表的学术论文) 4 7 附录b ( 攻读学位期间参与的科研课题) 4 8 v i 插图索引 图3 1 免疫系统结构图1 2 图3 2 疫苗接种免疫算法流程图1 7 图3 3 基于信息熵的免疫算法流程图1 9 图3 4 克隆选择免疫算法流程图2 0 图5 1 改进多种群克隆免疫算法流程图3 2 v i i 硕士学位论文 附表索引 表2 1 真值表6 表4 1 四种算法的性能比较2 8 表4 2i i a 与q i c a 性能比较2 9 表5 1 多种群克隆免疫算法实验结果3 7 表5 2 两种多种群克隆免疫算法比较3 7 v i i i 面向s a t 问题的免疫算法的改进研究 1 1 研究背景及意义 第1 章绪论 给定命题变元集v = 毛，x ：， ，其中毛 o ，1 ，1 i 珂，0 表示假，l 表示真。 y 中任意一个变元翰或变元的非一翰称为文字，子句是若干文字的析取，合取范 式是若干子句的合取。命题可满足性问题( s a t i s f i a b i l i t yp r o b l e m ，以下简称s a t 问 题) 是对是否存在一个关于瓴，x ：，矗) 的真值指派，使得合取范式中所有的子句 均为真( 即使得合取范式为真) 进行判断的问题。 s a t 问题是c o o k 在19 7 1 年证明的第一个n p 完全问题【l 】。已证明任意n p 完 全问题都可在多项式时间内转化为s a t 问题而求解，因此s a t 问题的求解对n p 完全问题的研究具有重要价值，是计算机科学研究的核心问题，是解决人工智能 与计算理论中许多问题的基础。另一方面，图着色问题、皇后问题、图像匹配、 计算机辅助制造、超大规模集成电路设计、计算机体系结构设计、计算机网络系 统设计等现实生活中许多问题均可转化为s a t 问题。因此，对s a t 问题求解的 研究具有重要的理论意义与应用价值。 称求解可满足性问题全部解的问题为a l l s a t 问题。对a l l s a t 问题进行求 解在电子设计自动化中的电路优化( c i r c u i to p t i m i z a t i o n ) 、无界模型检验 ( u n b o u n d e dm o d e lc h e c k i n g ) 、形式验证( f o r m a lv e r i f i c a t i o n ) 、电路综合( c i r c u i t s y n t h e s i s ) 等方面有着重要的应用研究价值。 s a t 问题的求解方法可以分为完全算法和不完全算法两大类。完全算法主要 包括d p 【2 】及其改进算法。但是，s a t 问题属于n p 完全问题，其计算复杂度随着 问题规模的增大呈指数增长，因此在求解效率上完全算法通常难以满足需求。不 完全算法主要是指局部搜索( l o c a ls e a r c h ) 算法。局部搜索算法是在二十世纪六、 七十年代求解组合优化问题的基础上逐渐发展起来的，是解决很多n p 完全问题 常用的一种方法。不完全算法虽然不能保证一定能找到问题的解，但是由于求解 速度快且通常能满足需要，已逐渐成为国内外学者研究的重点。 遗传算法的概念于1 9 7 5 年被美国密歇根大学的霍兰德教授首先提出【3 1 ，一时 遗传算法成为人们研究的热点，许多问题用遗传算法得以解决。然而遗传算法的 很多缺陷逐渐被人们所发现，如算法易于陷入“早熟 ，从而使算法收敛于局部最 优值【4 】。免疫算法以高等脊椎动物免疫系统的运行机理为理论依据发展而来，具 有保持解群分布多样性的特性，较好地克服了遗传算法易出现“早熟 ，陷于局部 最优值的缺陷【5 j 。 硕士学位论文 量曼詈曼詈! 曼曼暑曼毫寡鲁量皇詈鼍詈鼍詈詈鼍l i l i n i 皇詈曼曼詈詈皇曼! 詈摹曼皇喜皇皇 但是，免疫算法的研究才刚刚起步，各方面都尚未完善，很多方面有待改进。 研究免疫算法的改进对算法创新和实际应用都有重大意义。 1 2 可满足性问题求解的研究现状 1 2 1s a t 问题求解的研究现状 s a t 问题自1 9 7 1 年被提出以来，一直受到世界各国的广泛关注，吸引了众多 学者参与研究，产生了许多求解s a t 问题的新方法。可满足性理论及其应用国际 大会、国际s a t 问题实用算法比赛、国际标准s a t 问题测试实例等都一定程度 上推动了s a t 问题的研究与发展。 当前求解s a t 问题的主要方法可分为完全算法和不完全算法，完全算法以回 溯搜索算法为主，而不完全算法主要是局部搜索算法。 完全算法在问题有解时，能够保证一定找出问题的解；在问题无解时，通常 能给出一个完备的证明。后者对实际问题很有意义，因为许多实际问题只需要对 无解性作出判断，如果已经证明问题无解，那么就无需花费大量的资源去试图找 问题的解。完全算法的出现早于不完全算法。d a v i s 和p u t n a m 于1 9 6 0 年提出的 d p 算法 2 】及其改进d p l l 算法是最经典的完全算法，在其基础上产生了很多改进 的完全算法。d p 及其改进而来的完全算法都是以分枝回溯策略为基础，遍历由 个布尔变量组成的完全二叉树。回溯搜索算法的基本过程是不断的对当前的部分 解进行扩展，如当前部分解已经造成矛盾而无法被继续扩展，则立即回溯到更短 的部分解并继续对其进行扩展，直至求出一个问题实例的解或者搜索完整棵完全 二叉树。近年来，完全算法的求解效率由于启发策略的引入而得到了很大程度的 提高，产生了z c h a f f 类算法【6 】等一系列求解s a t 问题的高效完全算法。 不完全算法主要是指局部搜索算法。局部搜索算法的基本思想：将可行域中 的任意一个解点视为一组变量赋值。设给定一个优化问题，其目标函数用厂表示， 可行解域为r ，对每个解点屯r ，其对应的邻域为n ( x k ) c 7 r ；每得到一当前解 点x k ，就在其邻域k ) 内搜索一个满足f ( x k + 。) f ( x k ) 的新解点；如果存在这样 的解点，则将x k + l 取代x k 而成为新的当前解点，重复继续上述局部搜索过程；否 则，就将x k 视为对应于n ( x k ) 的局部最优解。 局部搜索算法于九十年代应用于人工智能界以来逐渐成为国内外的研究热 点，产生了一系列成果，同时产生了很多求解s a t 问题的优秀算法。如s e l m a n 等提出的g s a t 算法及采用随机行走策略改进的w a l k s a t 算法、黄文奇等提出的 求解s a t 问题的拟物拟人方法、陈昊的基于演化算法的s a t 问题求解、孙强等 提出的求解s a t 问题的退火遗传算法、李阳阳等提出的求解s a t 问题的量子免 疫克隆算法等1 】都是求解s a t 问题的优良算法。 2 面向s a t 问题的免疫算法的改进研究 1 2 2a l l s a t 问题求解的研究现状 目前，s a t 问题的研究方面，对s a t 问题求单解的成果较多。但是求s a t 问题所有解有时是很有用的。称求解s a t 问题所有解的问题为a l l s a t 问题【1 2 】。 如在有界模型检验中，a l l s a t 问题的解可以产生多个用于错误检测和校正的反 例。a l l s a t 问题还可以用于对最小的开销安排进行求解【1 2 】。对于a l l s a t 问题， 当前算法通常是通过变换、化简进行求解。然而随问题规模的增大，变换、化简 的方法所消耗的时间呈指数增长。曾振柄提出了求合取范式可满足性问题全部解 的一个算法( 13 1 ，其中引入了展开合并模2 的算法商，使算法效率成倍提高，但是 这种提高是很有限的。因此这类算法只适用于对小规模问题进行求解，对于大规 模问题而言，这类将s a t 问题转换为多项式展开求解的方法显然是低效的。 实际电路问题的求解中，许多先进的求解器都是先将其转换成合取范式，然 后对合取范式进行求解，如s a t o 1 4 j 。但是，电路的结构信息，如信号的可观性 等信息，在合取范式的转换过程中被丢失了【1 5 】。然而对于解决电路相关问题而言， 这些信息是非常有用的。目前已有不少方法研究利用电路可观性，如将信号可观 性应用于电路结构描述到c n f 的转换中【l 引，将一个用以维护有关电路信息的附 加层加于s a t 算法之上，以对故障测试模式生成问题进行求解17 1 。王秀芹等【1 8 】 提出了一种利用可观无关性的方法，该方法基于不对只出现在可观无关条件中的 变量进行赋值的策略，从而能避免使用排序，同时又能保证电路的控制唯一性。 此外，因为无关条件计算时不考虑变量排序约束，因而可观无关条件的丢失减少 了。 智能进化算法作为一类优越的求解算法，已广泛应用于各类问题的求解。包 括求s a t 问题单解的进化算法，近年来出现了很多，如上所述。但是对于a l l s a t 问题，应用智能进化算法进行求解尚未出现相关报道。 1 3 免疫算法研究现状 免疫是生物体的特异性生理反应，免疫系统由具有免疫功能的器官、组织、 细胞、免疫效应分子及基因等组成【l9 1 。当外界病毒对生物系统发生侵害时，将激 活生物体的免疫系统，生物体通过免疫系统将入侵的抗原性异物予以清除，其目 标是使得生物系统基本生理功能尽可能正常运转。 2 0 世纪8 0 年代中期，国内外学者依据生物系统的免疫学原理开始提出各种 免疫算法。b e r s i n i 2 0 】于1 9 9 0 年最先使用免疫算法来解决问题。2 0 世纪末，f o r r e s t 等1 2 1 】开始在计算机安全领域应用免疫算法，同期h u n t 等【2 2 1 开始将免疫算法应用 于机器学习领域。 t o y o of u k u d a 等【2 3 j 提出了一种基于信息熵的免疫算法。该算法利用信息熵来 3 硕上学位论文 衡量种群的多样性，在保证算法收敛的同时维护了群体的多样性。但是该算法的 参数设置过于复杂，严重影响了算法的性能。因此，c h u njs 等【2 4 】提出了一种简 化算法，并证明了算法的有效性。鉴于信息熵计算中包含大量的对数计算，郑日 荣等【4 】提出了一种加快基于信息熵的人工免疫算法运行速度的方法。 以泊内特( b u r n e t ) 的细胞克隆选择学说为依据，l e a n d r o 和f e r n a n d o 提出了基 于克隆选择原理进行人工机器的学习和优化研究【2 5 1 。传统的单克隆免疫算法不采 用交叉算子，为了进一步增加克隆的多样性，改进算法的性能，刘若辰等【2 6 】提出 了一种多克隆选择算法。 依据抗体之间、抗体与抗原之间的相互作用，j e r n e 2 7 提出了独特型网络。为 进一步提高算法效率，国内外学者提出了各种各样的改进方法，如i s h i g u r o 等1 2 剐 提出了一种互联耦合免疫网络模型，h e r z e n b e r g 等【2 9 】提出了一种适合于分布式问 题的松耦合网络结构，李中华等【30 】提出了具有精英学习能力的增强型人工免疫网 络等。 免疫算法的研究方兴未艾，目前对免疫算法的研究主要有两方面：一、研究 免疫机理，提出新的免疫算法或改进现有免疫算法；二、融合其他算法的优秀思 想对现有免疫算法进行改进。 1 4 论文研究主要内容 本文针对现有s a t 问题以及a l l s a t 问题求解算法的不足，在前人研究的基 础上，对免疫算法进行改进，以使其分别适用于s a t 问题和a l l s a t 问题的求解。 最后将算法应用于s a t l i b 库中的标准问题，对算法性能进行测试，实验测试结 果表明算法是有效的。主要内容有： ( 1 ) 免疫算法改进方面的研究。分析了传统免疫算法的机制、原理、动力学模 型、分类及应用领域。针对基于信息熵的免疫算法因对数计算影响算法效率的 缺陷，采用通过海明距计算信息熵避免了对数计算，同时提出一种新的变异算子， 提高了算法效率。针对现有克隆免疫算法在求多解方面的不足，采用了多种群 的策略，针对现有算法多样性保持方面的不足，在前人研究的基础上，将小生境 思想与克隆免疫算法融合，并对算法的收敛性进行了分析。 ( 2 ) 改进算法在s a t 问题求解方面的研究。分析了s a t 问题求解的重要性及 其求解算法的研究现状，分析了现有算法的不足。将具有优秀寻优能力的免疫算 法加以改进，并将其应用于s a t 问题的求解。对s a t 问题求解的实验结果表明 该算法是有效的。 ( 3 ) 改进算法应用于a l l s a t 问题求解方面的研究。分析了a l l s a t 问题的研 究现状，说明了a l l s a t 问题求解的重要价值，将免疫算法应用于a l l s a t 问题 的求解是首次将智能算法应用于a l l s a t 问题的求解。理论证明了算法的收敛性， 4 面向s a t 问题的免疫算法的改进研究 并用仿真实验进一步验证了算法的有效性。 1 5 论文结构与章节安排 论文的研究重点主要集中在对免疫算法的改进及其在s a t 问题、a l l s a t 问 题中的应用。免疫算法收敛速度快，能较好保持种群多样性，且易于实现。采用 基于海明距的免疫算法避免了耗时的对数计算，同时引入一种具有随机搜索思想 的变异算子使算法避免产生“发散”、提高进化速率，使其适用于s a t 问题的求 解。在经典免疫算法的基础上采用多种群策略以使其适于a l l s a t 问题的求解， 采用小生境思想提高种群多样性。最后将改进后的算法分别应用于s a t 问题及 a l l s a t 问题的求解中。 论文共分五章，章节安排如下： 本章是绪论部分，阐明了课题的研究背景和研究价值，s a t 问题、a l l s a t 问题及免疫算法研究现状，本文的主要工作和研究内容，论文结构和章节安排。 第2 章介绍s a t 问题的相关概念，对现有s a t 问题及a l l s a t 问题求解算 法进行说明，分析了各种算法的主要内容与优劣，介绍了s a t 问题及a l l s a t 问 题的应用领域。 第3 章介绍免疫系统和免疫算法相关知识，阐述了免疫系统的分类及工作原 理与运行机制，分析了免疫算法的动力学模型、各类免疫算法的原理及流程、免 疫算法的应用领域等。 第4 章介绍了一种基于海明距的改进免疫算法及在s a t 问题求解中的应用， 证明了基于海明距与基于信息熵于对于免疫算法的等效性；介绍了随机搜索相关 知识，提出了一种基于随机搜索思想的新变异算子。最后用实验验证该算法的有 效性。 第5 章介绍了一种改进的多种群克隆免疫算法及其在a l l s a t 问题求解中的 应用。简要阐明了小生境原理，并且理论证明了算法能收敛到问题的所有解，最 后用实验对算法的性能进行了测试。 5 硕士学位论文 第2 章s a t 问题及其求解算法 2 1s a t 问题相关定义 对于一给定的命题逻辑公式，s a t 问题是判断是否存在赋值使公式得以满足 的问题。设布尔变元集表示为v = “，屯，) ，其中 o ，1 ) ，l 1 r a n d o m 0 ，1 】，则接受状态s l 作为当前状态； 退温t k + l = u p d a t e ( t k ) ，令拓斛l ； 如未达算法结束条件，则返回；否则，算法结束并输出结果。 ( 5 ) 求解s a t 问题的量子免疫克隆算法( q u a n t u mi n s p i r e di m m u n ec l o n a la l g o - 8 面向s a t 问题的免疫算法的改进研究 r i t h m ，q i c a ) 1 1 】。q i c a 基于量子编码的叠加性原理构造抗体，使作用在量子编码 抗体上的操作具有高效的并行性，依据当前最优抗体的信息控制变异，从而防止 了盲目搜索，使种群以大概率向优良模式进化，加快了算法收敛速度。为提高算 法的全局寻优能力，使算法在全局搜索的同时能兼顾局部搜索，算法在各个子群 内部引入量子旋转门对抗体进行操作。 q i c a 采用量子位的编码方式表达种群抗体，针对q i c a 的编码方式，算法采 用量子旋转门及动态调整旋转角度策略对抗体进行演化，加速了原有克隆算子的 收敛；能充分利用克隆算子局部寻优能力强的特点；为增强各子群间的信息交流， 算法在各子群间进行量子交叉操作，提高了种群多样性，在一定程度上防止了“早 熟 。q i c a 算法描述如下： 令k = 0 ，生成初始种群彳( o ) ，设定算法参数，计算初始种群中抗体的亲和 力； 依据抗体的亲和力及设定的克隆规模，进行克隆操作，生成种群么( 七) ； 对克隆后的各子群抗体进行量子变异操作，生成种群彳”( 妨； 对种群彳”( 妨进行克隆免疫选择，形成新种群； 令k = k + l ，计算新种群中抗体的亲和力，如满足终止条件，算法终止；否 则，对种群进行一次量子交叉操作并返回。 q i c a 将量子计算与克隆免疫算法相结合，用量子论知识优化克隆免疫算法， 李阳阳等将其应用于求解s a t l i b 库中的标准问题，取得了非常理想的效果。 近年来，求解s a t 问题的局部搜索算法成果很多，如张德富等提出的求解s a t 问题的拟人退火算法【3 2 1 ，孙强等提出的求解s a t 问题的退火遗传算法【3 3 1 ，刘静 等提出的求解s a t 问题的组织进化算法【3 4 等。但是每种算法各有优劣，有待进一 步改进完善。 2 3a l l s a t 问题的求解算法 现有的s a t 求解算法很多，但是在实际应用中，有时得到可满足性问题的全 部解是非常有用的，此即a l l s a t 问题。当前求解a l l s a t 问题的成果比较少， 有代表性的主要有毕忠勤等提出的可满足性问题全部解的求解算法【1 2 】和曾振柄 提出的求合取范式可满足性问题全部解的一个算法 1 3 】。下面分别对以上两种求解 a l l s a t 问题的算法进行简单介绍。 ( 1 ) 毕忠勤等提出的可满足性问题全部解的求解算法。该算法利用一个简单的 变换，将可满足性( s a t ) i h - 题转化为多项式形式，然后根据命题逻辑的性质及多项 式的性质，求解出s a t 问题所有解。算法描述如下： 将合取范式转换成多项式。x i 表示x i 取1 ，一x i 表示x i 取0 。按如下规则对 合取范式进行处理，如果文字为x i 则保持不变，如果文字为一x i ，则将其替换为 9 硕士学位论文 x i 。同时用“+ 替换公式中的析取符号“v ，用“奉”替换公式中的合取符号 “八i p 。o 如合取范式：( 墨v x 2v 吨) ( 而v 飞v 孔) ( 而v 吨v x 4 ) ，按上述规则进 行转化，转化结果为( 而+ 屯+ 1 ) 宰( x 2 + x 3 1 + _ ) ( 一+ 巧1 + _ ) 。 将转化后的多项式进行扩展并化简。化简规则如下： 1 、由-