2006年計算機組成原理課程設(shè)計

PAGE石家莊經(jīng)濟學院第四屆學生科技基金科研項目研究報告項目名稱：基于改進遺傳算法求解可滿足性問題的研究負責人：曹國生所屬學院:信息工程學院指導老師：賀毅朝200目錄1.選題依據(jù) 12.國內(nèi)外研究現(xiàn)狀 53．個人主要工作 64.數(shù)據(jù)分析 85.總結(jié) 9致謝 10參考文獻 10附錄 10PAGE1摘要本文通過介紹遺傳算法和可滿足性問題的起源、描述、重要理論意義和應用價值，進而提出了一種新的方法來解決可滿足性問題，即在將SAT問題等價轉(zhuǎn)換為{0,1}n上的多項式是否存在零點的判斷問題基礎(chǔ)上，將局部搜索算法(LSA)與SGA相結(jié)合，給出一種求解3-SAT問題的改進混合遺傳算法(MHGA)，并通過對隨機大規(guī)模3-SAT問題實例的實際求解驗證了MHGA的可行性與有效性。關(guān)鍵詞：遺傳算法，可滿足性問題一.選題依據(jù)遺傳算法及其重要性遺傳算法(GeneticAlgorithm，GA)是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率搜索算法，它起源于對生物系統(tǒng)所進行的計算機模擬研究。早在本世紀40年代，就有學者開始研究如何利用計算機進行生物模擬的技術(shù)，他們從生物學的角度進行了生物的進化過程模擬、遺傳過程模擬等研究工作。如Fraser的模擬研究，他提出了和現(xiàn)在的遺傳算法十分相似的概念和思想。進入60年代以后，美國密執(zhí)安大學的Holland教授及其學生們受到這種生物模擬技術(shù)的啟發(fā)，創(chuàng)造出了一種基于生物遺傳和進化機制的適合于復雜系統(tǒng)優(yōu)化計算的自適應概率優(yōu)化技術(shù)遺傳算法。70年代DeJong基于遺傳算法的思想在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗。Holland和DeJong的創(chuàng)造性研究成果改變了早期遺傳算法研究的無目標性和理論指導的缺乏，其中，Holland于1975年出版的著名著作<<自然系統(tǒng)和人工系統(tǒng)的適配>>系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極為重要的模式理論。這一理論首次確認了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性。同年，DeJong的重要論文<<遺傳自適應系統(tǒng)的行為分析>>將Holland的模式理論與他的計算實驗結(jié)合起來，并提出了諸如代溝等新的遺傳操作技術(shù)，可以認為，DeJong所做的研究工作是遺傳算法發(fā)展過程中的一個里程碑。在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進行歸納總結(jié)，形成了遺傳算法的基本框架。80年代以后，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了十分熱門的課題，遺傳算法的應用領(lǐng)域也不斷擴大。生物在自然界中的生存繁衍，顯示出了其對自然環(huán)境的優(yōu)異自適應能力。受其啟發(fā)，人們致力于對生物各種生存特性的機理研究和行為模擬，為人工自適應系統(tǒng)的設(shè)計和開發(fā)提供了廣闊的前景，遺傳算法就是這種生物行為的計算機模擬中令人矚目的重要成果?；趯ι镞z傳和進化過程的計算機模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應能力和優(yōu)化能力，它所借鑒的生物學基礎(chǔ)就是生物的遺傳和進化。達爾文的自然選擇學說是一種被人們廣泛接受的生物進化學說。這種學說認為，生物要生存下去，就必須進行生存斗爭。生存斗爭包括種內(nèi)斗爭、種間斗爭以及生物跟無機環(huán)境之間的斗爭三個方面。在生存斗爭中，具有有利變異的個體容易存活下來，并且有更多的機會將有利變異傳給后代；具有不利變異的個體就容易被淘汰，產(chǎn)生后代的機會也少的多。因此，凡是在生存斗爭中獲勝的個體都是對環(huán)境適應性比較強的。達爾文把這種在生存斗爭中適者生存，不適者淘汰的過程叫做自然選擇。它表明，遺傳和變異是決定生物進化的內(nèi)在因素。自然界中的多種生物之所以能夠適應環(huán)境而得以生存進化，是和遺傳和變異生命現(xiàn)象分不開的。正是生物的這種遺傳特性，使生物界的物種能夠保持相對的穩(wěn)定；而生物的變異特性，使生物個體產(chǎn)生新的性狀，以致于形成新的物種，推動了生物的進化和發(fā)展。遺傳算法是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。主要是基于達爾文進化論中“物競天擇，適者生存”理論，模擬生物進化的步驟,將繁殖、雜交、變異、競爭和選擇等概念引入到算法中，通過對一組可行解的重新組合，改進可行解在多維空間內(nèi)的移動軌跡或趨向,最終走向最優(yōu)解。它的思想源于生物遺傳學和適者生存的自然規(guī)律，是具有“生存＋檢測”的迭代過程的搜索算法。遺傳算法以一種群體中的所有個體為對象，并利用隨機化技術(shù)指導對一個被編碼的參數(shù)空間進行高效搜索。其中，選擇、交叉和變異構(gòu)成了遺傳算法的遺傳操作；參數(shù)編碼、初始群體的設(shè)定、適應度函數(shù)的設(shè)計、遺傳操作設(shè)計、控制參數(shù)設(shè)定五個要素組成了遺傳算法的核心內(nèi)容。作為一種新的全局優(yōu)化搜索算法，遺傳算法以其簡單通用、魯棒性強、適于并行處理以及高效、實用等顯著特點，在各個領(lǐng)域得到了廣泛應用，取得了良好效果，并逐漸成為重要的智能算法之一。遺傳算法求解問題的基本思想是從問題的解出發(fā)的，它將問題的一些可行解進行編碼，這些已編碼的解即被當作群體中的個體（染色體），個體對環(huán)境適應能力的評價函數(shù)就是問題的目標函數(shù)，模擬遺傳學中的雜交、變異、復制來設(shè)計遺傳算子，用優(yōu)勝劣汰的自然選擇法則來指導學習和確定搜索方向。對由個體組成的群體進行演化，利用遺傳算子來產(chǎn)生具有更高平均適應度值和更好個體的群體，經(jīng)過若干代后，選出適應能力最好的個體,它就是問題的最優(yōu)解或近似最優(yōu)解，通過迭代保留優(yōu)秀個體、淘汰劣等個體來進化求解。遺傳算法將搜索空間映射成遺傳空間，在遺傳空間的每個個體代表搜索空間的一個解，由特定數(shù)量的個體組成一個種群，由適應度函數(shù)得出各個個體的適應度值以標識當前個體的優(yōu)劣，每一代種群個體經(jīng)過交叉、變異以及選擇操作，生成新一代種群個體。一般情況，新一代種群個體都比原種群個體的平均適應度值要好，經(jīng)過多代的進化，最終得到一個最優(yōu)個體。遺傳算法的搜索過程是一個由已知個體向未知個體搜索并且新個體比原個體更為優(yōu)秀的過程，這適合該系統(tǒng)從已知的規(guī)則搜索到更合理、準確的未知規(guī)則的要求。遺傳算法作為一種快捷、簡便、容錯性強的算法，在各類結(jié)構(gòu)對象的優(yōu)化過程中顯示出明顯的優(yōu)勢。在傳統(tǒng)的優(yōu)化算法中，是從一個點開始搜索，易于陷入局部最優(yōu)解。而遺傳算法在搜索中同時考慮了問題解空間中的許多點(一個點群)搜索，搜索過程是從一組解迭代到另一組解，采用同時處理群體中多個個體的方法，且對初始值不作要求，從而大大減少了陷入局部最優(yōu)解的可能性。另外，在傳統(tǒng)的算法中需要提供一些輔助信息，而遺傳算法僅利用問題本身所具有的目標函數(shù)的信息。它不受搜索空間的限制，不必要求諸如連續(xù)性、導數(shù)的存在和單峰等假設(shè)，搜索過程不直接作用在變量上，而是在參數(shù)集進行了編碼的個體。此編碼操作，使得遺傳算法可直接對結(jié)構(gòu)對象（集合、序列、矩陣、樹、圖、鏈和表）進行操作，僅用適應度來評估個體優(yōu)劣，具有很強的魯棒性，并且具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力，穩(wěn)健性極強、可操作性和簡單性突出。此外，采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應地調(diào)整搜索方向，不需要確定的規(guī)則。我們習慣上把Holland1975年提出的GA稱為經(jīng)典的GA。它的主要步驟如下：

（1）編碼：GA在進行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合便構(gòu)成了不同的點。

（2）初始群體的生成：隨機產(chǎn)生N個初始串結(jié)構(gòu)數(shù)據(jù)，每個串結(jié)構(gòu)數(shù)據(jù)稱為一個個體，N個個體構(gòu)成了一個群體。GA以這N個串結(jié)構(gòu)數(shù)據(jù)作為初始點開始迭代。

（3）適應性值評估檢測：適應性函數(shù)表明個體或解的優(yōu)劣性。不同的問題，適應性函數(shù)的定義方式也不同。

（4）選擇：選擇的目的是為了從當前群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。遺傳算法通過選擇過程體現(xiàn)這一思想，進行選擇的原則是適應性強的個體為下一代貢獻一個或多個后代的概率大。選擇實現(xiàn)了達爾文的適者生存原則。

（5）交換：交換操作是遺傳算法中最主要的遺傳操作。通過交換操作可以得到新一代個體，新個體組合了其父輩個體的特性。交換體現(xiàn)了信息交換的思想。

（6）變異：變異首先在群體中隨機選擇一個個體，對于選中的個體以一定的概率隨機地改變串結(jié)構(gòu)數(shù)據(jù)中某個串的值。同生物界一樣，GA中變異發(fā)生的概率很低，通常取值在0.001~0.01之間。變異為新個體的產(chǎn)生提供了機會。

經(jīng)典遺傳算法(SGA)的基本流程描述如算法1所示。算法1．SGA算法1.t←0;2.initializeP(t);//初始化個體3.evaluate(P(t));//評價個體4.While(notterminatecondition)Do//進行選擇、交叉、變異,產(chǎn)生新一代種群5.P1←Select(P(t));//從上一代種群中選擇個體加入P1中6.P2←Crossover(P1);//對P1中的個體進行交叉操作生成P27.P(t+1)←Mutate(P2);//對P2中的個體進行變異操作8.Evaluate(P(t+1));Compute(Best);//評價新種群,并計算當前最優(yōu)個體Best9.t←t+1;10.EndWhile;11.Output(Best,f(Best))//輸出最優(yōu)個體Best及其對應的函數(shù)值

GA的計算過程為：選擇編碼方式，產(chǎn)生初始群體，計算初始群體的適應性值，如果不滿足條件則進行

選擇，交換，變異，進而計算新一代群體的適應性值。

遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類由很強的魯棒性，所以廣泛應用于很多學科。目前遺傳算法所涉及的主要領(lǐng)域有自動控制、規(guī)劃設(shè)計、組合優(yōu)化、函數(shù)優(yōu)化、生產(chǎn)調(diào)度問題、神經(jīng)網(wǎng)絡學習過程、機器人學習、機器學習、遺傳編程、圖象處理、信號處理、自動控制和人工生命等領(lǐng)域。其中，函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領(lǐng)域，也是對遺傳算法進行性能評價的常用算例。對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。遺傳算法對于組合優(yōu)化中的NP完全問題也非常有效，例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用?，F(xiàn)在遺傳算法已成為解決復雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務分配等方面都得到的有效的應用。在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步的應用，并顯示出良好的效果。例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經(jīng)網(wǎng)絡的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學習等，都顯示出了遺傳算法在這些領(lǐng)域中應用的可能性。除此之外，遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應用。在圖像處理中的優(yōu)化計算方面遺傳算法也找到了用武之地，目前已在模式識別、圖像恢復、圖像邊緣特征提取等方面得到了應用。人工生命與遺傳算法有著密切的關(guān)系，基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論，人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供了一個有效的工具，人工生命的研究也必將促進遺傳算法的進一步發(fā)展。而基于遺傳算法的機器學習，特別是分類器系統(tǒng)，在很多領(lǐng)域都得到了應用。例如：遺傳算法被用于學習模糊控制規(guī)則，利用遺傳算法來學習隸屬度函數(shù)，從而更好的改進模糊系統(tǒng)的性能；基于遺傳算法的機器學習可用來調(diào)整人工神經(jīng)網(wǎng)絡的連接權(quán)，也可用于人工神經(jīng)網(wǎng)絡的網(wǎng)絡結(jié)構(gòu)優(yōu)化設(shè)計；分類器系統(tǒng)也可在學習式多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應用。此外在社會科學、生物學、商業(yè)及工程等各種不同領(lǐng)域也得到了越來越廣泛的應用。由此可見，遺傳算法的應用研究已從初期的組合優(yōu)化求解拓展到了許多更新，更工程化的應用方面?？蓾M足性問題的意義可滿足性問題(SatisfiabilityProblem,SAT)是由Cook證明的第一個NPC問題，它是計算科學中的典型問題之一，也是當今計算機科學和人工智能研究的核心問題。其后的NPC問題證明都是建立在SAT問題之上，研究解決SAT問題的有效算法不僅具有重大的理論意義，而且在智能規(guī)劃、智能決策、定理證明、電路診斷和優(yōu)化計算、人工智能、機器學習、VLSI集成電路設(shè)計與檢測和數(shù)據(jù)庫檢索等諸多領(lǐng)域有著實際的意義。SAT問題的一般性描述如下：令P={p1,p2,…，pn}是n個不同命題變元的集合，P上公式的一個指派是函數(shù)t：P→{T,F}，用n元布爾向量t=<t1,t2,…,tn>表示，其中t∈{0,1}。顯然，P上存在2n個不同的指派。對于P上公式A，如果存在指派t使得t(A)=1，則稱A為可滿足的；如果對于任意指派t使得t(A)=0，則稱A為不可滿足的(或矛盾的)。形如C=ci1∨ci2∨…∨cik…∨cir的公式稱為子句，其中cij為pij或﹁pij，稱cij為P上的文字(literal)。公式A=C1∧C2∧…∧Ci∧…∧Cm稱為合取范式，其中Ci為其子句(1≤i≤m)。如果存在指派t使A滿足，則稱A是可滿足公式。易知，合取范式A在指派t下是可滿足的當且僅當其每個子句Ci均是可滿足的。于是，SAT問題是指對于給定P={p1,p2,…，pn}上的一個CNFA，判斷是否存在一個指派t使得A是可滿足的。當公式A中的每個子句Ci(1≤i≤m)都只含有k個不互補的文字時，公式A被稱為k-SAT問題。簡單地說，SAT問題就是給定一個包含n個變量m個子句的合取范式，判斷是否有使這些子句全部為真的賦值。SAT的問題被證明是NP難解的問題。目前解決該問題的方法主要有完備的方法和不完備的方法兩大類。完備的方法優(yōu)點是保證能正確地判斷SAT問題的可滿足性，但其計算效率很低，平均的計算時間為多項式階，最差的情況計算時間為指數(shù)階，不適用于求解大規(guī)模的SAT問題。不完備的方法的優(yōu)點是求解的時間比完備的方法快得多，但在很少數(shù)的情況下不能正確地判斷SAT問題的可滿足性。傳統(tǒng)的方法有：枚舉法、局部搜索法和貪婪算法等，但由于搜索空間大，問題一般難以求解。對于像SAT一類的NP難問題，采用一些現(xiàn)代啟發(fā)式方法如演化算法往往較為有效。由于現(xiàn)代科技、軍事以及經(jīng)濟管理的大量重要應用都歸結(jié)為求解完全問題，所以工程技術(shù)、軍事、工商管理、交通運輸及自然科學研究中的許多重要問題，如程控電話的自動交換、大型數(shù)據(jù)庫的維護、大規(guī)模集成電路的自動布線、軟件自動開發(fā)、機器人動作規(guī)劃等，都可轉(zhuǎn)化成SAT問題。它的快速求解不僅具有重要的理論意義,而且在軟件自動開發(fā)技術(shù)、邏輯推理機、VLSI設(shè)計、人工智能、機器學習、以及知識庫維護和檢測和數(shù)據(jù)庫檢索等許多領(lǐng)域都有重要的實際應用價值。此外，SAT問題還在集成電路設(shè)計、數(shù)據(jù)庫檢索、定理證明、數(shù)理邏輯、計算機視覺、機器人規(guī)劃和空間布線等具體研究領(lǐng)域中有著廣泛的應用。因此致力于尋找求解SAT問題的快速而有效的算法，不僅在理論研究上而且在許多應用領(lǐng)域都具有極其重要的意義。關(guān)于SAT問題求解的算法是國內(nèi)外研究的熱點之一，目前求解SAT問題存在多種算法，其中基于局部搜索或梯度下降理論的算法為完全算法，例如窮舉搜索法、Davis-Putnam算法、DPLL算法等，優(yōu)點是能保證正確地判斷SAT問題的可滿足性，但是，由于SAT問題的計算空間隨著問題規(guī)模的增大呈級數(shù)增長，當SAT問題的規(guī)模較大時，完全算法不實用。而SAT問題是一個NPC問題，該問題是否存在多項式時間算法目前還未解決，在這種情況下，人們開始尋找不完全的但快速且非常實用的隨機算法，即不完全算法。所謂不完全是指：如果范式是可滿足的，則此算法將停機并給出一個解，否則算法可能不停機。其代表性的算法有：Localsearch算法、擬人擬物算法、遺傳算法(GA)、模擬退火算(SA)法和微粒群算法(PSO)等。由于有些優(yōu)化算法所需要的計算空間難以承受，所以算法可解的問題在實踐上不一定可解。P類問題指具有多項式求解的算法的問題類。但到目前為止，許多優(yōu)化問題仍沒有找到求的最優(yōu)解的多項式時間算法，通常稱這種比P類問題更廣泛的問題為非多項式確定問題，即NP問題。其中SAT問題就是一種NP問題。NP完全問題是當代計算機科學中的核心問題之一，現(xiàn)已證明大量重要的計算機科學的理論和應用問題都歸結(jié)為求解NP完全問題，但到目前為止，這一問題還沒有得到有效解決。經(jīng)過近幾十年來的研究，人們普遍認為NP完全問題的研究可以通過對某一特殊的NP完全問題作深入具體的研究來進行。SAT問題是一典型的NP完全問題，對這一典型問題進行深入的理論分析有助于NP完全問題研究的向前發(fā)展。SAT問題與人工智能中的推理問題有著直接而密切的關(guān)系，然而由于SAT問題是NP完全的因此不大可能存在一個求解該問題的通用快速算法。但是人們沒有放棄針對特殊類型SAT問題的算法的設(shè)計與研究。對于求解SAT問題的不同的實用算法，需要有SAT問題的實例來衡量這些算法的性能。經(jīng)常使用的是隨機產(chǎn)生的SAT問題的實例。但也有不少學者研究出了一些將其他重要的組合問題有效的轉(zhuǎn)化為SAT問題的方法。這些問題包括圖著色積木世界規(guī)劃，VLSI設(shè)計，Jobshop排工問題等。這些問題本身也是難解問題，由此轉(zhuǎn)化的SAT問題實例有一定的難度，且具有一些隨機產(chǎn)生的SAT問題的實例所不具有的特性。有效的解決這類SAT問題不僅對理論與方法的發(fā)展很重要，而且也具有一定的應用前景。二.國內(nèi)外研究現(xiàn)狀以下介紹一下有關(guān)遺傳算法和SAT問題研究的一些新進展：1.求解SAT問題的改進粒子群優(yōu)化算法利用限制性公式的相關(guān)理論將可滿足性問題(SAT)等價轉(zhuǎn)換為定義在{0,1}n上的多項式函數(shù)優(yōu)化問題，并將二進制粒子群優(yōu)化算法(BPSO)與局部爬山搜索策略相結(jié)合，給出了一種求解SAT問題的新算法：基于局部爬山搜索的改進二進制粒子群優(yōu)化算法(簡稱IBPSO)。計算表明：對于隨機3-SAT問題測試實例，IBPSO算法的求解結(jié)果均優(yōu)于當前較流行的局部搜索算法SAT1-3和WARSAT算法，這說明利用IBPSO算法求解SAT問題是一種高效可行的新方法。2.利用近似解加速求解SAT問題的啟發(fā)式完全算法結(jié)合DPLL

完全算法能夠證明可滿足性(SAT)

問題的不可滿足性和局部搜索算法快速的優(yōu)點,提出利用近似解加速求解SAT

問題的啟發(fā)式完全算法。

首先利用局部搜索算法快速地得到一個近似解,并將該近似解作為完全算法的初始輸入,用于其中分支變量的相位決策。該算法引導完全算法優(yōu)先搜索近似解所在的子空間,加速解器找到可滿足解的過程,為SAT

問題的求解提供了一種新的有效途徑。實驗結(jié)果表明,該算法有效地提高了決策的精度和SAT

解決器的效率,對很多實例非常有效。3.SAT問題中局部搜索法的改進局部搜索方法在求解SAT問題的高效率使其成為一研究熱點．提出用初始概率的方法對局部搜索算法中變量的初始隨機指派進行適當?shù)募s束．使在局部搜索的開始階段，可滿足的子句數(shù)大大增加，減少了翻轉(zhuǎn)的次數(shù)，加快了求解的速度．用該方法對目前的一些重要的SAT

問題的局部搜索算法(如WSAT，TSAT，NSAT，SDF等)進行改進。通過對不同規(guī)模的隨機3-SAT問題的實例和一些不同規(guī)模的結(jié)構(gòu)性SAT問題的實例，以及利用相變現(xiàn)象構(gòu)造的難解SAT實例測試表明，改進后的這些局部搜索算法的求解效率有了很大的提高．該方法對其他局部搜索法的改進具有參考價值．4.

一種新的SAT問題預處理算法提出了一項新的正向推理技術(shù)：對稱擴展的一元子句推倒技術(shù)。與傳統(tǒng)的一元子句推導技術(shù)相比．文中的方法通過在一元子句推導過程中添加對稱的蘊涵關(guān)系從而能夠推導出更多的一元子句?；谶@項新技術(shù)實現(xiàn)了一個可滿足性問題(SAT)預處理器Snowball。實驗結(jié)果驗證了該項技術(shù)的有效性，表明該預處理器Snowball能夠有效地化簡SAT問題的規(guī)模并減少解決SAT問題的時間。5.一種求解難3-SAT問題的新方法根據(jù)Kennedy和Eberhart提出的二進制粒子群優(yōu)化算法(BinaryParticleSwarmOptimizers)，基于局部隨機搜索策略，給出一種求解難3-SAT問題的新方法：基于局部隨機搜索的改進二進制粒子群優(yōu)化算法(ModifedBinaryParticleSwarmOptimizersBasedonlocalstochasticserch,簡稱MBPSO)。數(shù)值實驗表明，對于隨機產(chǎn)生的3-SAT問題測試實例，該算法是一種高效實用的新方法。6.隨機k-SAT問題的回溯算法分析通過研究搜索樹的平均節(jié)點數(shù)，分析了回溯算法求解隨機k-SAT問題的平均復雜性，結(jié)果表明：找到實例所有的解或證明其無解所需的平均節(jié)點數(shù)隨變量數(shù)n的增加而指數(shù)增長；隨著r(子句數(shù)/變量數(shù))的增大求解將變得越來越容易，而且當r趨近于無窮大時，以n為指數(shù)，平均節(jié)點數(shù)的底數(shù)將無限地趨近于1。因此盡管回溯算法求解隨機k-SAT問題具有指數(shù)的平均復雜性，但當r充分大以后，許多實例的求解將變得非常容易。7.采用正交免疫克隆粒子群算法求解SAT問題根據(jù)Kennedy和Eberhart提出的二進制粒子群算法，基于抗體克隆選擇理論提出一種求解合取范式可滿足問題的粒子群算法―正交免疫克隆粒子群算法。該算法將合取范式可滿足問題轉(zhuǎn)換為求解目標函數(shù)最小值的優(yōu)化問題，為提高收斂速度，根據(jù)子句的先驗知識計算出個體的初始指派概率對種群進行初始化。為了避免算法早熟收斂提高粒子群個體解分布的均勻性，將離散正交交叉算子用于免疫基因操作中，并給出適應于求解合取范式可滿足問題的免疫粒子群進化算子。實驗采用標準SATLIB庫中變量個數(shù)從20-250的3700個不同規(guī)模的標準合取范式可滿足問題對正交免疫克隆粒子群算法的性能作了全面的測試，并與標準粒子群算法和免疫克隆選擇算法進行了比較。結(jié)果表明，正交免疫克隆粒子群算法的成功率在三個算法中最高，運行時間和評價次數(shù)最少。8.基于子句權(quán)重學習的求解SAT問題的遺傳算法提出了一種求解SAT問題的改進遺傳算法(SAT-WAGA)。SAT-WAGA算法有多個改進性特點：將SAT問題的結(jié)構(gòu)信息量化為子句權(quán)重，增加了學習算子和判定早熟參數(shù)，學習算子能根據(jù)求解過程中的動態(tài)信息對子句權(quán)重進行調(diào)整，以便防止遺傳進程的早熟，同時，算法還采用了最優(yōu)染色體保存策略防止進化過程的發(fā)散。實驗結(jié)果表明：與一般遺傳算法相比SAT-WAGA算法在求解速度、成功率和求解問題的規(guī)模等方面都有明顯的改善。9.求解SAT問題的分級重排搜索算法局部搜索法在SAT問題上的成功運用已引起越來越廣泛的重視，然而，它在面對不可滿足問題例時的局限性不能不被考慮。分級重排搜索算法MSRA(multi-stagesearchrearrangementalgorithm)正是為克服局部搜索法的不完備性而提出的，準確地講，它是幾種算法在思想上的集成，但為明確起見，把其最典型的分級重排過程作為名稱。分級重排搜索算法在求解SAT問題時，能表現(xiàn)出優(yōu)于單一求解策略(如局部搜索法或回溯算法)的明顯特性。由于可根據(jù)約束條件的強弱來估計SAT問題例的可滿足性，因此能夠以此來確定更有效的求解策略。10.組織進化算法求解SAT問題基于組織的概念設(shè)計了一種新的進化算法一求解SAT的組織進化算法(OrganizationalEvolutiorraryAlgorithmforSATproblem,OEASAT)。OEASAT將SAT問題分解成若干子問題，然后用每個子問題形成一個組織，并根據(jù)SAT問題的特點設(shè)計了三種組織進化算子一自學習算子、吞并算子和分裂算子以引導組織的進化。根據(jù)組織的適應度，將所有組織分成兩個種群一最優(yōu)種群和非最優(yōu)種群，然后用進化的方式來控制各算子，以協(xié)調(diào)各組織間的相互作用，OEASAT通過先解決子問題，再協(xié)調(diào)相沖突變量的方式來求解SAT問題。由于子問題的規(guī)模較小，相對于原問題來說較容易解決，這樣就達到了降低問題復雜度的目的。實驗采用標準SATLIB庫中變量個數(shù)從20-250的3700個不同規(guī)模的標準SAT問題對OEASAT的性能作了全面的測試，并與著名的WalkSAT和RFEA2D的結(jié)果作了比較。結(jié)果表明，OEASAT具有更高的成功率和更高的運算效率。對于具有250個變量、1065個子句的SAT問題，OEASAT僅用了1.524s，表現(xiàn)出了優(yōu)越的性能。11.求解SAT問題的擬人退火算法利用一個簡單的變換，將可滿足性問題轉(zhuǎn)換為一個求相應目標函數(shù)最小值的優(yōu)化問題，提出了一種用于跳出局部陷阱的擬人策略?；谀M退火算法和擬人策略，為SAT問題的高效近似求解得出了擬人退火算法(PA)，該方法不僅具有模擬退火算法的全局收斂性質(zhì)，而且具有一定的并行性、繼承性。數(shù)值實驗表明，對于隨機產(chǎn)生的測試問題例，采用擬人策略的模擬退火算法的結(jié)果優(yōu)于局部搜索算法、模擬退火算法以及近來國際上流行的WalkSAT算法，因此擬人退火算法是可行和有效的。三.個人的主要工作通過前文描述可知，SAT問題是指對于給定P={p1,p2,…，pn}上的一個CNFA，判斷是否存在一個指派t使得A是可滿足的。當公式A中的每個子句Ci(1≤i≤m)都只含有k個不互補的文字時，公式A被稱為k-SAT問題。對于一個SAT問題實例A=C1∧C2∧…∧Ci∧…∧Cm，由DeMorgen定律[7]易證：﹁A﹁C1∨﹁C2∨…∨﹁Ci∨…∨﹁Cm(﹁c11∧﹁c12∧…﹁∧c1k…﹁∧c1r)∨(﹁c21∧﹁c22∧…∧﹁c2k…﹁∧c2r)∨…∨(﹁cm1∧﹁cm2∧…∧﹁cmk…﹁∧cmr).(1)由于對任意指派t，t(A)=1t(﹁A)=0。因此，在(1)式中若﹁cij=pij(1≤i≤m，1≤j≤n)，則用xij替換掉﹁cij，若﹁cij=﹁pij(1≤i≤m，1≤j≤n)，則用(1-xij)替換掉﹁cij。同時，用“+”(普通的加法運算)替換掉“∨”，用“．”(普通的乘法運算)替換掉“∧”，則將判定SAT問題實例的可滿足問題等價地轉(zhuǎn)換為判定{0,1}n上相應多項式函數(shù)是否存在零點的問題，其中且xij∈{x1,x2,…,xn}。由此，可以得到如下結(jié)論：定理1.SAT實例A可滿足對于{0,1}n上函數(shù)，存在n元0-1向量X=(t1,t2,…,tn)使得。并且以X=(t1,t2,…,tn)為指派使得A可滿足。例如，由定理1可得SAT實例A=(﹁p1∨p2∨p3∨﹁p4)∧(p1∨p3∨p4)∧(p1∨p2∨﹁p3)在{p1,p2,p3,p4}上是可滿足的函數(shù)f(X)=x1(1-x2)(1-x3)x4+(1-x1)(1-x3)(1-x4)+(1-x1)(1-x2)x3在{0,1}4上存在零點，即存在4元0-1向量X=(t1,t2,,t3,t4)∈{0,1}4，使得f(X)=0。SAT問題中指派t=<t1,t2,…,tn>為二進制向量，與SGA算法的個體表示天然一致；同時，由定理1結(jié)論可知，利用函數(shù)，個體的適應度計算也非常方便。因此，將SGA用于求解SAT問題是非常自然的。雖然容易發(fā)現(xiàn)SGA可求解SAT問題，但是大量的實驗結(jié)果表明：直接利用SGA求解SAT問題的效果并不理想，特別是對于較大規(guī)模的SAT實例，SGA的求解成功率很低。因為遺傳算法是一種通用搜索算法，它通過模擬進化，適者生存過程，以隨機形式將最適合于特定目標函數(shù)的種群通過重組產(chǎn)生新的一代，在進化過程中通過選擇，重組和突變逐漸產(chǎn)生優(yōu)化問題的解決方案。但隨著人們對遺傳算法的深入研究，發(fā)現(xiàn)現(xiàn)行遺傳算法存在著一些缺陷，如早熟現(xiàn)象，即未成熟收斂；局部搜索能力弱，易陷于局部最優(yōu)點；隨機性大，容易在迭代過程中破壞群體中的優(yōu)秀個體，從而導致收斂速度減慢；計算參數(shù)均是根據(jù)經(jīng)驗確定，很難找到最確切的值。為了提高求解的效率，需要借鑒其他的算法或技術(shù)來改進SGA，為此我們嘗試將SGA與局部搜索算法(LocalSearchAlgorithm,LSA)相結(jié)合，在交叉運算和變異運算的基礎(chǔ)上，利用LSA來優(yōu)化所得的每個個體，然后再利用選擇運算實現(xiàn)種群的進化。由此得到一種改進的混合遺傳算法(ModifiedHybridGeneticAlgorithm，MHGA)。下面先介紹LSA算法。設(shè)待求解問題為最小優(yōu)化問題，X=(x1,x2,…,xn)為n元向量，f(X)為目標函數(shù)值，T=(t1,t2,…,tn)為X在{0,1}n上的一個賦值，Neg(T,i)表示對T的第i個分量ti取反，即若在T中ti=1，則Neg(T,i)中ti=0；若在T中ti=0，則Neg(T,i)中ti=1。于是LSA(X)算法的一般原理描述如下：算法2．LSA算法1.Random(T);//隨機產(chǎn)生X的一個賦值TCompute(f(T));//計算對應的函數(shù)值T1←T4.Fori=1tonDo5.T’←Neg(T,i)//從上一代種群中選擇個體加入P1中Iff(T’)≤f(T1)ThenT1←T’7.Return(T1,f(T1))對隨機產(chǎn)生的賦值T，LSA算法通過嘗試改變其每個分量來尋找最優(yōu)值，顯然算法的復雜性為Θ(n)。由于其線性階復雜性，實際在應用該算法求解問題時可以通過多次迭代來進行求解。下面將此方法與SGA算法相結(jié)合，給出一種用于求解3-SAT問題的改進混合遺傳算法(ModifiedHybridGeneticAlgorithm，MHGA)。算法3．MHGA算法1.t←0;2.initializeP(t)={Gi(t)=(g1(t),g2(t),…,gn(t))|gi(t)∈{0,1}∧1≤i≤m};//初始化個體evaluate(P(t));//評價個體4.While(notterminatecondition)Do//進行選擇、交叉、變異,產(chǎn)生新一代種群5.P1←Select(P(t));//從上一代種群中選擇個體加入P1中6.P2←Crossover(P1);//對P1中的個體進行交叉操作生成P27.P(t+1)←Mutate(P2);//對P2中的個體進行變異操作Fori=1tomDoG1←G(t)Forj=1tonDo11.G’←Neg(G(t),i)//從上一代種群中選擇個體加入P1中12.Iff(G’)≤f(G1)ThenG1←G’13.EndWhile;14.Output(Best,f(Best))//輸出最優(yōu)個體Best及其對應的函數(shù)值雖然MHGA算法與SGA算法相比，每次迭代增加了Θ(mn)的計算量，但由于其吸收了LSA算法的局部搜索能力，使得每次迭代所得到的個體相對更優(yōu)，不但不會增加時間開銷，相反使MHGA算法在求解質(zhì)量和速度方面均優(yōu)于SGA算法，這一點將在下一節(jié)通過實際求解大規(guī)模SAT問題實例來驗證。四.數(shù)據(jù)分析實驗環(huán)境為Pentium(R)4CPU2.19GHz,內(nèi)存256MB，硬盤80GB，MicrosoftWindowsXPProfessional版本2002ServicePack2操作系統(tǒng)，并采用MicrosoftVisualC++6.0[8]編程實現(xiàn)。SAT問題實例的規(guī)模記為(n,m)，其中n為變元個數(shù)，m為子句個數(shù)。固定n=200，對m=300,350,…,700分別隨機生成20個對不同規(guī)模的SAT問題實例，利用兩個各算法分別計算，通過統(tǒng)計的可滿足樣例求得它們的成功率和運行時間。MHGA算法與SGA算法采用的參數(shù)如下：種群體大小為為300，交叉概率為0.7，變異概率為0.02，最大運行代數(shù)為1000。兩算法的求解結(jié)果比較見圖1和圖2。由兩個圖的比較可以看出：MHGA的成功率不但比SGA高，而且所需的迭代次數(shù)也相對較少，這說明將遺傳算法與局部搜索算法相結(jié)合來求解SAT問題是可行的和有效的。五.總結(jié)本文利用GA和局部搜索算法(LocalSearchAlgorithm,LSA)相結(jié)合，在將SAT問題等價轉(zhuǎn)換{0,1}n上的多項式是否存在零點的判斷問題基礎(chǔ)上，給出一種求解3-SAT問題的改進混合遺傳算法(ModifiedHybridGeneticAlgorithm，MHGA)，并利用隨機大規(guī)模3-SAT問題實例驗證了算法的可行性與有效性，在利用GA求解SAT問題方面進行有益的探討。GA是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學的觀點，通過自然選擇、遺傳、變異等作用機制，實現(xiàn)各個個體的適應性的提高。這一點體現(xiàn)了自然界中物競天擇、適者生存的進化過程。在文章中使用遺傳算法求解SAT問題，主要是利用了遺傳算法的具體求解問題無關(guān)性以及全局優(yōu)化的優(yōu)點。用遺傳算法求解SAT問題可以作為很多實際應用領(lǐng)域中一個基礎(chǔ)，因此找出求解SAT問題的高效的遺傳算法具有很多的實際意義，而將其應用于更多領(lǐng)域，同時研究應用中存在的問題也是值得關(guān)注的熱點。致謝本次項目得到石家莊經(jīng)濟學院科技處和石家莊經(jīng)濟學院學生科技基金大力支持，在此，本課題組成員致以衷心的感謝。本論文在賀老師的指導下完成，他認真負責的工作態(tài)度、嚴謹?shù)闹螌W精神和深厚的理論水平都使我受益匪淺。他不僅在理論上給了我巨大的支持，而且在算法的實施上還給了我很大的幫助，在此我向老師表達深深的謝意。另外，我還要向幫助我支持我的各位同學表示感謝，尤其是同課題組的同學，他們在資料的查找和研究報告的校對方面給與我很大的幫助。參考文獻[1]黃拙，張健．由一階邏輯公式得到命題邏輯可滿足性問題實例[J]．軟件學報，2005，16(3)：329-335。[2]張德富，黃文奇，王厚祥．求解SAT問題的擬人退火算法[J]．計算機學報，2002,25(2)：148-152。[3]賀毅朝，王彥祺，寇應展．一種求解3-SAT問題新方法．計算機工程與應用，200642(16)：70-72。[4]徐宗本．計算智能—模擬進化計算．北京：高等教育出版社，2005。[5]賀毅朝，王熙照，寇應展．一種具有混合編碼的二進制差分演化算法．計算機研究與發(fā)展，2007，44(9)，1476-1484。[6]劉勇，康立山等．非數(shù)值并行算法(二)―遺傳算法．北京：科學出版社，2003。[7]張?。壿嫻降目蓾M足性判定―方法、工具及應用[M].北京：科學出版社，2000。[8]杜丁柱，葛可一，王潔．計算復雜性導引[M].北京：高等教育出版社，2002：35-37。[9]李未，黃雄．命題邏輯可滿足性問題的算法分析[J]．計算機科學，1999,26(3)：1-9。[10]李未，黃文奇．一種求解SAT問題的數(shù)學物理算法．中國科學，1994,24(11)：1208-1217。[11]王文杰，葉世偉．人工智能原理與應用．北京：人民郵電出版社，2004。[12]徐宗本，張講社，鄭亞林．計算智能中的仿生學：理論與方法．北京：清華大學出版社，2001。[13]楊晉吉，蘇開樂．SAT問題中局部搜索法的改進[J]．計算機研究與發(fā)展，2005,(1)：60-65。[14]吳勝．用遺傳算法求解3-SAT問題[J]．福建電腦，2005,(7)：49,51。[15]王小平，曹立明．遺傳算法-理論、應用與軟件實現(xiàn)[M].西安：西安交通大學出版社，2002。[16]耿素云，屈婉玲，王捍貧．離散數(shù)學教程．北京大學出版社，2002。[17]康博創(chuàng)作室．VisualC++6.0高級編程．清華大學出版社，2000。附錄/*****************************************************************/#include<stdio.h>#include<stdlib.h>#include<time.h>#include<math.h>/*****************************************************************/#definerdint(i)(rand()%(int)(i))#definerdft()(double)((double)rdint(30000)/(30000.0))#definePOPSIZE100#defineDIMENSION50#defineMAXITERA1000#defineN3*DIMENSION#defineM3#definePCROSS0.5#definePMUTATE0.1/*****************************************************************/structindi{ intx[DIMENSION]; intF; intH; doublefitness;}population[POPSIZE],temppop[POPSIZE],tempbest;intCNF[N][M];intgeneration;intbest,worst;FILE*fp;/*****************************************************************/voidinitialize(void);voidinitsatcnf(void);voidinitpop(void);voidinitreport(void);voidevaluate(void);voidcalculation(int);voidgennewpop(void);voidselection(void);voidgencoress(void);voidgenmutate(void);voidreplace(void);voidoutputresults(void);/*****************************************************************/voidmain(){ charch; generation=0; srand(time(NULL)); if((fp=fopen("SAT.txt","w"))==NULL) { printf("\nCannotopeninputfile\n");exit(1);} initialize(); evaluate(); outputresults(); while(generation<MAXITERA) { gennewpop(); evaluate(); //ch=getchar(); generation++; outputresults(); } fclose(fp);}/*****************************************************************/voidinitialize(void){ initsatcnf();initpop(); initreport();}/*****************************************************************/voidinitsatcnf(void){ inti,j,k; for(i=0;i<N;i++) { for(j=0;j<M;j++) { k=0; CNF[i][j]=rdint(DIMENSION); if(rand()%2==0) CNF[i][j]=-CNF[i][j]; while(j!=0&&k!=j) { for(k=0;k<j;k++) { if(abs(CNF[i][j])==abs(CNF[i][k])) break; } if(k!=j) { CNF[i][j]=rdint(DIMENSION); if(rand()%2==0) CNF[i][j]=-CNF[i][j]; } } } }}/*****************************************************************/voidinitpop(void){ inti,j; for(i=0;i<POPSIZE;i++) { for(j=0;j<DIMENSION;j++) { if(rdft()<0.5) population[i].x[j]=0; else population[i].x[j]=1; } calculation(i); }}/*****************************************************************/voidinitreport(void){ inti,j; printf("ThepolynomalofSATis:\n\n"); for(i=0;i<N;i++) { printf("["); for(j=0;j<M;j++) { if(CNF[i][j]<0) printf("x%d",-CNF[i][j]); if(CNF[i][j]>=0) printf("(1-x%d)",CNF[i][j]); } if(i<N-1)printf("]+"); elseprintf("]"); } printf("\n\n");}/*****************************************************************/voidevaluate(void){ inti,j; inttotalH=0;best=0; worst=0; for(i=1;i<POPSIZE;i++) { if(population[worst].F<population[i].F) worst=i; if(population[best].F>population[i].F) best=i; } for(i=0;i<POPSIZE;i++) { population[i].H=population[worst].F-population[i].F; totalH+=population[i].H; } for(i=0;i<POPSIZE;i++) { population[i].fitness=population[i].H/(double)totalH; for(j=0;j<DIMENSION;j++) tempbest.x[j]=population[best].x[j]; tempbest.F=population[best].F; }}/*****************************************************************/voidcalculation(intm){ inti,j; intindex; inttemp=0,tempt=1; for(i=0;i<N;i++) { tempt=1; for(j=0;j<M;j++) { index=CNF[i][j]; if(index<0) tempt*=population[m].x[-index]; else tempt*=1-population[m].x[index]; } temp+=tempt; }population[m].F=temp;}/*****************************************************************/voidselection(void){ inti,j,k; doublerand1; for(i=1;i<POPSIZE;i++) population[i].fitness+=po