正交量子免疫克隆算法在sat问题中的应用

《正交量子免疫克隆算法在sat问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、参變乃苗义遺乂ｆ＾ＳＯＵＴＨＷＥＳＴＩＩＶＥＩＢ缉ＪＡＯＴＯＮＧＵＮＲＳＴＹ胃硕±学位论文Ｍ乂ＳＴＥＲＤＩＳＳＥＲＴＡＴＩＯＮｈｆ论女颗目：正交量備臟猫編喔用Ｉ字黎－ｆｃ＾哇＊理学硕壬；学位類—应巧化学学科专业：■一■二Ｑ级■：：年级１％；究生圣圣羣：；指导教师：丞皿－燃１１：－…ＪＩ国内图书分类号：０２９国际图书分类号：５１０密级：公开西南交通大学研究生学位论文正巧量子免疫克隆算法在ＳＡＴ问题中的应用年级二零一兰级姓名王天磊

2、申请学位级别理学硕±专业应用数学指导老师夫振明教授二零一六年五月ＣｌａｓｓｉｆｉｅｄＩｎｄｅｘ：０２９Ｕ．Ｄ．Ｃ：５１０ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎＵｎｉｖｅｒｓｉｔｇｙＭａｓｔｅｒＤｅｒｅｅＴｈｅｓｉｓｇＯｒｔｈｏｏｎａｌｕａｎｔｕｍｉｍｍｕｎｅｃｌｏｎｅａｌｏｒｉｔｈｍｇｑｇｆｏｒｔｈｅＳＡＴｒｏｂｌｅｍｐＧｒａｄｅ：２０１３Ｃａｎ出ｄａｔｅ：ＷａｎｇＴｉａｎｌｅｉＡｃａｄｅｍｉｃＤｅｇｒｅｅＡｐｐｌｉｅｄｆｏｒ：ＭａｓｔｅｒＳｅｃｉａｌｉ

3、ｔ：ＡｌｉｅｄＭａｔｈｅｍａｔｉｃｓｐｙｐｐＳｕｅｒｖｉｓｏｒ：Ｐｒｏｆ．ＺｈｅｎｍｉｎＳｏｎｐｇｇＭａ２０１６ｙ，西南交通大学学位论文版奴使用巧枚书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部口或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可Ｗ将本论文的全部或部分内容编入有关数据库进行检索，可Ｗ采用影印、缩印或扫描等复印手段保存和汇编本学位论文。本学位论文属于１．保密□，在年解密后适用本授权书；２．不保密味使用本授权书。＂

4、＂（请在ｙｊｌ上方框内打Ｖ）：学位论文作者签名：指导老师签名曰期：＞化曰親？矣．女／／．２占少西南交通大学硕±学位论文主要工作（贡献）声明本文的主要研究工作如下；本文主要是研究ＳＡＴ问题并提出求解ＳＡＴ问题新的算法。对于ＳＡＴ问题的求解，主要是实现求解效率快并且成功率商。本文首先介绍ＳＡＴ问题的研究背景及其意义，随后着重总结研究免疫克隆算法，量子进化算法Ｗ及基于正交性解决ＳＡＴ问题的思想，分析其算法的优点。，Ｗ及在求解效率或求解成功率等方面的不足ＳＡＴ—在分析研究上述算法的基础之上，提出求解问题新的算法正交量

5、子免疫克隆算法（ＯＱＩＣＡ）。该算法吸收了上述算法的优点，在子句组的等价的正交化处理基础上，首先判定ＳＡＴ问题的属性，同时有效地消除子句的重叠信息Ｗ及削减子句的规。模，而后通过量子免疫算法，利用量子运算的良好性质快速求得问题的解随后本文对该算法的收敛性进行了讨论，证明了ＯＱＩＣＡ是收敛并且是Ｗ概率１收敛的。最后通。过实验验证，ＯＱＩＣＡ有效提升了ＳＡＴ问题的求解成功率本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过

6、的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。一切法律责任将由本人承担本人完全了解违反上述声明所引起的。；ｉ＾学位论文作者签名＾曰期；：２＾占．夕．２＾西南交通大学硕±研究生学位论文第Ｉ页摘要ＳＡＴ问题的研究具有重要的理论意义和应用价值，目前求解ＳＡＴ问题的方法大致分为完全算法和不完全算法两大类。由于ＳＡＴ问题是ＮＰ完全问题，其计算复杂度随着问题规模的増大呈指数増长，因此完全算法在求解效率上通常难Ｗ满足需求；不完一全算法尽管不定能找到问题的解，但是其求解效率窩并且通常能够满足需要，

7、逐步成为求解ＳＡＴ问题的研究热点。本文主要针对求解ＳＡＴ问题的不完全算法进行研究。首先对求解ＳＡＴ问题的免疫克隆算法、量子进化算法Ｗ及正交法的基本思想作了较详尽的分析。综合分折上述算法的优势，基于正交法的化简与属性判定，为ＳＡＴ问题的求解提供了新的思路。ＳＡＴ基于对量子免疫克隆算法Ｗ及问题正交性的研究分析，本文在第Ｈ章提出新的求解ＳＡＴ问题的算法，即结合量子免疫克隆算法巧正交性的正交量子免疫算法（ＯＱＩＣＡ）。该算法首先对ＳＡＴ问题进行等价的正交化处理，消陈子句之间重叠信息的同时有效的判定问题的属性，当问题可满足时，

8、在正交子句组的基础上利用量子运算的髙效性快速获得可满足的解。最后本文理论分析了ＯＱＩＣＡ是Ｗ概率１收敛的，并通过