面向SAT問(wèn)題的免疫算法的改進(jìn)研究.pdf

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

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

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

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