正交量子免疫克隆算法在SAT问题中的应用
本文关键词： SAT问题 免疫克隆 量子进化 正交性 出处：《西南交通大学》2016年硕士论文 论文类型：学位论文
【摘要】：SAT问题的研究具有重要的理论意义和应用价值,目前求解SAT问题的方法大致分为完全算法和不完全算法两大类。由于SAT问题是NP完全问题,其计算复杂度随着问题规模的增大呈指数增长,因此完全算法在求解效率上通常难以满足需求；不完全算法尽管不一定能找到问题的解,但是其求解效率高并且通常能够满足需要,逐步成为求解SAT问题的研究热点。本文主要针对求解SAT问题的不完全算法进行研究。首先对求解SAT问题的免疫克隆算法、量子进化算法以及正交法的基本思想作了较详尽的分析。综合分析上述算法的优势,基于正交法的化简与属性判定,为SAT问题的求解提供了新的思路。基于对量子免疫克隆算法以及SAT问题正交性的研究分析,本文在第三章提出新的求解SAT问题的算法,即结合量子免疫克隆算法和正交性的正交量子免疫算法(OQICA)。该算法首先对SAT问题进行等价的正交化处理,消除子句之间重叠信息的同时有效的判定问题的属性,当问题可满足时,在正交子句组的基础上利用量子运算的高效性快速获得可满足的解。最后本文理论分析了OQICA是以概率1收敛的,并通过实验验证,正交量子免疫克隆算法比遗传算法和量子免疫克隆算法具有更高的求解成功率。
[Abstract]:The study of SAT problem has important theoretical significance and application value. At present, the methods of solving SAT problem are divided into two categories: complete algorithm and incomplete algorithm. Because SAT problem is NP complete problem. The computational complexity increases exponentially with the increase of the scale of the problem, so it is difficult for the complete algorithm to meet the demand in solving efficiency. Although incomplete algorithm can not always find the solution of the problem, but its efficiency is high and usually can meet the needs. Gradually become the research hotspot of solving SAT problem. This paper mainly focuses on the incomplete algorithm for solving SAT problem. Firstly, the immune clone algorithm for solving SAT problem is proposed. The quantum evolutionary algorithm and the basic idea of orthogonal method are analyzed in detail. The advantages of these algorithms are analyzed synthetically and based on the simplification and attribute determination of orthogonal method. Based on the analysis of the Quantum immune Clone algorithm and the orthogonality of the SAT problem, a new algorithm for solving the SAT problem is proposed in chapter 3. This algorithm combines Quantum immune Clone algorithm with orthogonal Quantum immune algorithm (OQI). Firstly, the SAT problem is treated with equivalent orthogonalization. Eliminate overlapping information between clauses while effectively determining the properties of the problem when the problem is satisfiable. On the basis of orthogonal clause set, the satisfied solution is obtained quickly by using the high efficiency of quantum operation. Finally, this paper theoretically analyses that OQICA converges by probability 1, and verifies it by experiment. Orthogonal quantum immune clone algorithm has higher success rate than genetic algorithm and quantum immune clone algorithm.
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【相似文献】
相关期刊论文 前10条
1 李晓丽;;基于改进免疫克隆算法的终端区航班进场调度[J];计算机测量与控制;2013年06期
2 刘士荣;张波涛;;采用生物信息机制的量子免疫克隆算法[J];模式识别与人工智能;2011年03期
3 朱建东;蒋卫菊;;基于免疫克隆算法的课表编排方案[J];计算机工程;2011年22期
4 刘洋;黄晋英;;免疫克隆算法收敛性及其在路径规划中的应用[J];信息技术与信息化;2014年01期
5 漆杨;秦子玄;陈霞;于中华;;基于免疫克隆算法的容量受限工厂选址问题研究[J];计算机应用;2009年01期
6 王娟;李飞;;一种基于实数编码的量子免疫克隆算法[J];计算机工程;2012年18期
7 吴秋逸;焦李成;李阳阳;邓晓政;;自适应量子免疫克隆算法及其收敛性分析[J];模式识别与人工智能;2008年05期
8 唐正;胡珉;;空间自适应免疫克隆选择优化算法[J];计算机应用;2009年02期
9 徐海黎;朱志松;王恒;朱龙彪;;环境变异免疫克隆算法解决有约束优化问题[J];系统仿真学报;2011年11期
10 张敏辉;;基于结合鲍德温效应和周期变异的免疫克隆优化算法的研究[J];电脑与信息技术;2012年02期
相关会议论文 前3条
1 马威;顾幸生;;一种求解多目标flow shop调度问题的免疫克隆算法[A];上海市化学化工学会2010年度学术年会论文集（自动化专题）[C];2010年
2 戴键;杨宏晖;;用于水声目标识别的自适应免疫克隆特征选择算法[A];2011'中国西部声学学术交流会论文集[C];2011年
3 王芸;杨宏晖;戴健;;加权免疫克隆样本选择与特征选择融合算法[A];第三届上海——西安声学学会学术会议论文集[C];2013年
相关重要报纸文章 前3条
1 聂晓刚;免疫克隆公司又遇麻烦[N];科技日报;2002年
2 曹嘉智;免疫克隆公司迎来黎明？[N];医药经济报;2003年
3 ;免疫克隆公司遭遇最后通牒[N];科技日报;2002年
相关博士学位论文 前2条
1 孙奕菲;基于小世界网络模型和免疫克隆优化的智能计算方法以及应用[D];西安电子科技大学;2014年
2 刘若辰;免疫克隆策略算法及其应用研究[D];西安电子科技大学;2005年
相关硕士学位论文 前10条
1 王天磊;正交量子免疫克隆算法在SAT问题中的应用[D];西南交通大学;2016年
2 李润心;基于免疫克隆选择的维数缩减及其应用[D];西安电子科技大学;2010年
3 王娟;量子免疫克隆算法研究及在压缩感知重构中的应用[D];南京邮电大学;2012年
4 张丽霞;免疫克隆智能优化算法的研究与应用[D];西北大学;2008年
5 冯静;基于免疫克隆的投影寻踪聚类算法及其应用[D];西安电子科技大学;2010年
6 张国龙;基于免疫克隆算法的船舶远程故障诊断研究[D];大连海事大学;2015年
7 张晓琳;基于免疫克隆选择算法的作业车间调度问题研究[D];西安电子科技大学;2009年
8 马红梅;基于Curvelet冗余字典和免疫克隆优化的压缩感知重构[D];西安电子科技大学;2012年
9 杨茸;求解随机机会约束规划的免疫克隆混合算法及应用[D];太原理工大学;2012年
10 马威;基于免疫克隆算法的多目标flow shop生产调度的研究[D];华东理工大学;2011年
，本文编号：1453125
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/1453125.html
