可满足性问题的改进型类组织P系统的求解研究
发布时间：2018-11-09 11:51
【摘要】：作为首个被证明了的NP完全问题,布尔逻辑表达式的可满足性问题(SAT问题)为计算机复杂性理论奠定了夯实的基础,在硬件电路可行性的测试、计算机科学(包括定理机器证明、机器视觉、数据库)等众多领域都有广泛应用。虽然大多数SAT问题都在表示为合取范式的基础上求解的,但鉴于实际中的布尔表达式有两种形式：合取范式(CNF)和析取范式(DNF),DNF更是其标准形式,但是却鲜有关于DNF可满足性的求解。因此本文将可满足性问题进行了细分扩展,将可满足性问题扩展成两部分来求解。一部分是传统的基于CNF的SAT问题的求解,另一部分是基于DNF的SAT问题的求解。这种划分方式就能够比较全面的涵括可满足性问题的所有情况,大大拓宽了现实中的应用范围。 本文利用膜计算的极大并行性,结合基本类组织P系统,模仿自然界中带电生物体组织的生命活动,提出了一种基于细胞分裂的识别型可进化类组织P系统,来求解可满足性问题。该系统能够在短时间内通过细胞分裂得到呈指数型增长的计算细胞,使每个计算细胞处理一种真值分配情况。运用交流规则、分裂规则、进化规则和输出规则在多项式时间内对布尔表达式进行并行处理,这不仅符合生物化学理论和实践,从而能够向环境中输出对象yes或no,以此表明布尔表达式是否满足。通过空间换时间这种方法来在很大程度上增强计算效率。 最后,在软件和硬件上分别做了仿真与验证。在软件方面,使用塞尔维亚大学自然科学研究组专门开发出来的编程语言pLingua编写本算法,并结合配套的专用于P系统仿真的pLinguaPlugin完成算法的仿真。在硬件方面,采用了具有并行特性的FPGA,通过VHDL语言对硬件的描述建立了相应的膜系统。并且,最终均证明本算法为正确可行的。 一直以来,很多学者都致力于SAT问题的求解,将其细分求解并用膜计算解决的并不多见,且膜计算一直面临着软硬件难实现的问题。本文将SAT问题进行细分处理解决,在很大程度上拓宽了现实中的应用范围；利用膜计算高效的计算能力和效率,克服了以往大多数算法由于串行计算而导致计算效率不高的缺点；最后还分别通过软硬件使得该算法得以实现,尤其是通过硬件电路FPGA实现P系统,克服了传统的生化反应实现,推动了膜计算硬件实现的步伐。综上可知,探索膜计算求解SAT问题有着重要现实价值与应用意义。
[Abstract]:As the first proved NP complete problem, Boolean logic expression satisfiability problem (SAT problem) lays a solid foundation for computer complexity theory, and tests the feasibility of hardware circuit. Computer science (including theorem machine proof, machine vision, database) and many other fields have been widely used. Although most SAT problems are solved on the basis of representation as conjunctive normal form, in view of the fact that there are two forms of Boolean expressions in practice: (CNF) and (DNF), DNF are their standard forms. However, there are few solutions about DNF satisfiability. In this paper, the satisfiability problem is subdivided into two parts to solve the problem. One is the traditional SAT problem based on CNF, the other is the SAT problem based on DNF. This method can cover all the cases of satisfiability problem, and widen the range of application in reality. Based on the maximal parallelism of membrane computing and the basic tissue P system, a novel evolutionary tissue P system based on cell division is proposed in this paper, which mimics the life activities of charged organisms in nature. To solve the satisfiability problem. The system can obtain exponential growth computing cells through cell division in a short period of time, which enables each computing cell to deal with a distribution of true values. Using exchange rule, split rule, evolution rule and output rule to process Boolean expression in polynomial time in parallel, this not only accords with biochemistry theory and practice, thus can output object yes or no, to the environment. This indicates whether the Boolean expression is satisfied. To a great extent, the computational efficiency is enhanced by the method of changing space for time. Finally, the software and hardware are simulated and verified. In the aspect of software, the algorithm is programmed with the programming language pLingua, which is specially developed by the Natural Science Research Group of the University of Serbia, and the simulation of the algorithm is completed with the matching pLinguaPlugin which is dedicated to the simulation of P system. In the aspect of hardware, FPGA, with parallel characteristics is used to describe the hardware in VHDL language, and the corresponding membrane system is established. Finally, the algorithm is proved to be correct and feasible. Many scholars have been devoted to solving the SAT problem, but it is rare to solve it by subdivision and membrane computing, and membrane computing has always been faced with the problem of hardware and software difficult to implement. In this paper, the SAT problem is solved by subdivision, which to a great extent widens the scope of application in reality. The high efficiency and efficiency of membrane computing overcomes the shortcoming that most of the previous algorithms are not efficient because of serial computation. Finally, the algorithm is implemented by software and hardware, especially the P system is realized by hardware circuit FPGA, which overcomes the traditional biochemical reaction and promotes the realization of membrane computing hardware. In summary, it has important practical value and application significance to explore the solution of SAT problem by membrane calculation.
【学位授予单位】：安徽理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.1;O141
本文编号：2320335
[Abstract]:As the first proved NP complete problem, Boolean logic expression satisfiability problem (SAT problem) lays a solid foundation for computer complexity theory, and tests the feasibility of hardware circuit. Computer science (including theorem machine proof, machine vision, database) and many other fields have been widely used. Although most SAT problems are solved on the basis of representation as conjunctive normal form, in view of the fact that there are two forms of Boolean expressions in practice: (CNF) and (DNF), DNF are their standard forms. However, there are few solutions about DNF satisfiability. In this paper, the satisfiability problem is subdivided into two parts to solve the problem. One is the traditional SAT problem based on CNF, the other is the SAT problem based on DNF. This method can cover all the cases of satisfiability problem, and widen the range of application in reality. Based on the maximal parallelism of membrane computing and the basic tissue P system, a novel evolutionary tissue P system based on cell division is proposed in this paper, which mimics the life activities of charged organisms in nature. To solve the satisfiability problem. The system can obtain exponential growth computing cells through cell division in a short period of time, which enables each computing cell to deal with a distribution of true values. Using exchange rule, split rule, evolution rule and output rule to process Boolean expression in polynomial time in parallel, this not only accords with biochemistry theory and practice, thus can output object yes or no, to the environment. This indicates whether the Boolean expression is satisfied. To a great extent, the computational efficiency is enhanced by the method of changing space for time. Finally, the software and hardware are simulated and verified. In the aspect of software, the algorithm is programmed with the programming language pLingua, which is specially developed by the Natural Science Research Group of the University of Serbia, and the simulation of the algorithm is completed with the matching pLinguaPlugin which is dedicated to the simulation of P system. In the aspect of hardware, FPGA, with parallel characteristics is used to describe the hardware in VHDL language, and the corresponding membrane system is established. Finally, the algorithm is proved to be correct and feasible. Many scholars have been devoted to solving the SAT problem, but it is rare to solve it by subdivision and membrane computing, and membrane computing has always been faced with the problem of hardware and software difficult to implement. In this paper, the SAT problem is solved by subdivision, which to a great extent widens the scope of application in reality. The high efficiency and efficiency of membrane computing overcomes the shortcoming that most of the previous algorithms are not efficient because of serial computation. Finally, the algorithm is implemented by software and hardware, especially the P system is realized by hardware circuit FPGA, which overcomes the traditional biochemical reaction and promotes the realization of membrane computing hardware. In summary, it has important practical value and application significance to explore the solution of SAT problem by membrane calculation.
【学位授予单位】：安徽理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.1;O141
【参考文献】
相关期刊论文 前10条
1 刘辉;;基于EP1C3T144C8的FPGA的开发板设计[J];电子技术;2009年01期
2 孟磊;周兰江;;基于CNF权重学习求解3-SAT问题的进化算法[J];贵州大学学报(自然科学版);2009年05期
3 刘蕴韬;;FPGA应用实例——实现I2C总线主机控制器[J];电子世界;2014年06期
4 邢洁清;郭平;朱庆生;王春腾;;基于膜系统的逻辑运算研究[J];电脑知识与技术;2009年13期
5 劳胜领;董会锦;;单片机扩展FPGA应用技术研究[J];电子技术与软件工程;2014年16期
6 李小龙;孟李林;邵瑞瑞;张小磊;;基于FPGA的PCI Express应用平台设计[J];电子科技;2014年12期
7 谭用秋,杨克昌,方建超;求解可满足性问题的改进的模拟退火算法[J];计算机工程与应用;2002年11期
8 王芙;周育人;叶立;;调查传播算法和蚁群算法相结合求解可满足性问题[J];计算机科学;2012年04期
9 张德富,黄文奇,汪厚祥;求解SAT问题的拟人退火算法[J];计算机学报;2002年02期
10 张葛祥;潘林强;;自然计算的新分支——膜计算[J];计算机学报;2010年02期
相关博士学位论文 前3条
1 陈海珠;膜计算应用研究[D];重庆大学;2011年
2 牛云云;求解计算困难问题的膜计算模型与算法研究[D];华中科技大学;2012年
3 杨世品;P系统优化算法及应用研究[D];浙江大学;2013年
，本文编号：2320335
本文链接：https://www.wllwen.com/kejilunwen/yysx/2320335.html
