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

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

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

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

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

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

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

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

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

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

選擇，交換，變異，進(jìn)而計(jì)算新一代群體的適應(yīng)性值。

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

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

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

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

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

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

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

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

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