面向SAT問題的免疫算法的改進研究.pdf

1、命題可滿足性問題(SAT問題)是第一個被證明的NP完全問題，是一切NP完全問題的“種子”，任何NP完全問題都可在多項式時間內(nèi)轉(zhuǎn)化為SAT問題進行求解。當前SAT求解方法在測試向量自動生成、符號模型檢查及組合等價性檢查等電子設計自動化領域中得到了廣泛的應用?？梢姡瑢AT問題的研究有著重要的理論意義和應用價值。
　　 目前求解SAT問題的主要方法大致可以分為完全算法和不完全算法。如果問題存在解，完全算法保證一定能找到問題的解。但隨

2、問題規(guī)模增大，SAT問題的計算復雜度呈指數(shù)增長；不完全算法雖然不能保證一定能找出問題的解，但是求解速度快且通常能滿足需求。故此，不完全算法逐漸成為求解SAT問題的研究熱點。
　　 本文主要針對不完全算法對SAT問題的求解進行研究。首先介紹了SAT問題及其求解方法、免疫原理與免疫算法的基本知識，其次通過對SAT問題求解和SAT問題全部解問題(ALLSAT問題)求解的研究，提出了兩種分別適用于SAT問題和ALLSAT問題求解的改進免

3、疫算法。
　　 首先，針對SAT問題的求解，本文提出了一種基于海明距的改進免疫算法。該算法基于海明距對抗體濃度進行定義，避免了耗時的對數(shù)計算，提高了算法效率；鑒于傳統(tǒng)變異算子存在的不足，算法引入了一種基于隨機搜索思想的新變異算子，該變異算子既可以加快種群進化速度，又可以防止進化后期產(chǎn)生“擾動”現(xiàn)象。實驗結(jié)果表明：該算法在成功率、收斂速度等方面都比基于信息熵的免疫算法有顯著提高；與量子克隆免疫算法相比，該算法平均進化代數(shù)少、成功率

4、高。
　　 其次，針對ALLSAT問題的求解，本文提出了一種改進的多種群克隆免疫算法。該算法采用小生境方法與位爬山算法進行優(yōu)化，因而具有能保持種群多樣性、收斂速度快等優(yōu)點。算法首先同時進化多個種群，每個種群進行克隆、變異、選擇操作，對每個種群的最優(yōu)個體進行位爬山操作。當子群進化一定代數(shù)之后，如該子群的最優(yōu)解是問題的解，則將該解放入小生境核集。然后比較種群中的個體與小生境集合中個體的距離，如與小生境集合中某個個體距離很小則產(chǎn)生新個