本文關(guān)鍵詞： SAT問題 免疫克隆 量子進(jìn)化 正交性　出處：《西南交通大學(xué)》2016年碩士論文　論文類型：學(xué)位論文

【摘要】：SAT問題的研究具有重要的理論意義和應(yīng)用價(jià)值,目前求解SAT問題的方法大致分為完全算法和不完全算法兩大類。由于SAT問題是NP完全問題,其計(jì)算復(fù)雜度隨著問題規(guī)模的增大呈指數(shù)增長(zhǎng),因此完全算法在求解效率上通常難以滿足需求；不完全算法盡管不一定能找到問題的解,但是其求解效率高并且通常能夠滿足需要,逐步成為求解SAT問題的研究熱點(diǎn)。本文主要針對(duì)求解SAT問題的不完全算法進(jìn)行研究。首先對(duì)求解SAT問題的免疫克隆算法、量子進(jìn)化算法以及正交法的基本思想作了較詳盡的分析。綜合分析上述算法的優(yōu)勢(shì),基于正交法的化簡(jiǎn)與屬性判定,為SAT問題的求解提供了新的思路�；趯�(duì)量子免疫克隆算法以及SAT問題正交性的研究分析,本文在第三章提出新的求解SAT問題的算法,即結(jié)合量子免疫克隆算法和正交性的正交量子免疫算法(OQICA)。該算法首先對(duì)SAT問題進(jìn)行等價(jià)的正交化處理,消除子句之間重疊信息的同時(shí)有效的判定問題的屬性,當(dāng)問題可滿足時(shí),在正交子句組的基礎(chǔ)上利用量子運(yùn)算的高效性快速獲得可滿足的解。最后本文理論分析了OQICA是以概率1收斂的,并通過實(shí)驗(yàn)驗(yàn)證,正交量子免疫克隆算法比遺傳算法和量子免疫克隆算法具有更高的求解成功率。
[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.
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李曉麗;;基于改進(jìn)免疫克隆算法的終端區(qū)航班進(jìn)場(chǎng)調(diào)度[J];計(jì)算機(jī)測(cè)量與控制;2013年06期

2 劉士榮;張波濤;;采用生物信息機(jī)制的量子免疫克隆算法[J];模式識(shí)別與人工智能;2011年03期

3 朱建東;蔣衛(wèi)菊;;基于免疫克隆算法的課表編排方案[J];計(jì)算機(jī)工程;2011年22期

4 劉洋;黃晉英;;免疫克隆算法收斂性及其在路徑規(guī)劃中的應(yīng)用[J];信息技術(shù)與信息化;2014年01期

5 漆楊;秦子玄;陳霞;于中華;;基于免疫克隆算法的容量受限工廠選址問題研究[J];計(jì)算機(jī)應(yīng)用;2009年01期

6 王娟;李飛;;一種基于實(shí)數(shù)編碼的量子免疫克隆算法[J];計(jì)算機(jī)工程;2012年18期

7 吳秋逸;焦李成;李陽陽;鄧曉政;;自適應(yīng)量子免疫克隆算法及其收斂性分析[J];模式識(shí)別與人工智能;2008年05期

8 唐正;胡珉;;空間自適應(yīng)免疫克隆選擇優(yōu)化算法[J];計(jì)算機(jī)應(yīng)用;2009年02期

9 徐海黎;朱志松;王恒;朱龍彪;;環(huán)境變異免疫克隆算法解決有約束優(yōu)化問題[J];系統(tǒng)仿真學(xué)報(bào);2011年11期

10 張敏輝;;基于結(jié)合鮑德溫效應(yīng)和周期變異的免疫克隆優(yōu)化算法的研究[J];電腦與信息技術(shù);2012年02期

相關(guān)會(huì)議論文 前3條

1 馬威;顧幸生;;一種求解多目標(biāo)flow shop調(diào)度問題的免疫克隆算法[A];上海市化學(xué)化工學(xué)會(huì)2010年度學(xué)術(shù)年會(huì)論文集（自動(dòng)化專題）[C];2010年

2 戴鍵;楊宏暉;;用于水聲目標(biāo)識(shí)別的自適應(yīng)免疫克隆特征選擇算法[A];2011'中國(guó)西部聲學(xué)學(xué)術(shù)交流會(huì)論文集[C];2011年

3 王蕓;楊宏暉;戴健;;加權(quán)免疫克隆樣本選擇與特征選擇融合算法[A];第三屆上�！靼猜晫W(xué)學(xué)會(huì)學(xué)術(shù)會(huì)議論文集[C];2013年

相關(guān)重要報(bào)紙文章 前3條

1 聶曉剛;免疫克隆公司又遇麻煩[N];科技日?qǐng)?bào);2002年

2 曹嘉智;免疫克隆公司迎來黎明？[N];醫(yī)藥經(jīng)濟(jì)報(bào);2003年

3 ;免疫克隆公司遭遇最后通牒[N];科技日?qǐng)?bào);2002年

相關(guān)博士學(xué)位論文 前2條

1 孫奕菲;基于小世界網(wǎng)絡(luò)模型和免疫克隆優(yōu)化的智能計(jì)算方法以及應(yīng)用[D];西安電子科技大學(xué);2014年

2 劉若辰;免疫克隆策略算法及其應(yīng)用研究[D];西安電子科技大學(xué);2005年

相關(guān)碩士學(xué)位論文 前10條

1 王天磊;正交量子免疫克隆算法在SAT問題中的應(yīng)用[D];西南交通大學(xué);2016年

2 李潤(rùn)心;基于免疫克隆選擇的維數(shù)縮減及其應(yīng)用[D];西安電子科技大學(xué);2010年

3 王娟;量子免疫克隆算法研究及在壓縮感知重構(gòu)中的應(yīng)用[D];南京郵電大學(xué);2012年

4 張麗霞;免疫克隆智能優(yōu)化算法的研究與應(yīng)用[D];西北大學(xué);2008年

5 馮靜;基于免疫克隆的投影尋蹤聚類算法及其應(yīng)用[D];西安電子科技大學(xué);2010年

6 張國(guó)龍;基于免疫克隆算法的船舶遠(yuǎn)程故障診斷研究[D];大連海事大學(xué);2015年

7 張曉琳;基于免疫克隆選擇算法的作業(yè)車間調(diào)度問題研究[D];西安電子科技大學(xué);2009年

8 馬紅梅;基于Curvelet冗余字典和免疫克隆優(yōu)化的壓縮感知重構(gòu)[D];西安電子科技大學(xué);2012年

9 楊茸;求解隨機(jī)機(jī)會(huì)約束規(guī)劃的免疫克隆混合算法及應(yīng)用[D];太原理工大學(xué);2012年

10 馬威;基于免疫克隆算法的多目標(biāo)flow shop生產(chǎn)調(diào)度的研究[D];華東理工大學(xué);2011年

，

本文編號(hào)：1453125