基于遺傳算法的SAT問題求解研究.pdf

1、SAT問題是計算科學(xué)中最基礎(chǔ)的問題之一，大部分組合邏輯問題都可以歸約求解SAT問題上面來，是非常具有理論研究價值和實際應(yīng)用潛力的問題。對于一個布爾公式，如果存在一組變量賦值使得該公式是可以滿足的，那么可以將公式的求解轉(zhuǎn)化為等效的可滿足性問題(Satisfibility)，自從遺傳算法誕生以來，由于其盲搜索特性，被廣泛地運用到組合優(yōu)化等領(lǐng)域。但是傳統(tǒng)的遺傳算法求解SAT問題存在容易陷入早熟、搜索效率不高等不足。本文將家族譜系樹的概念引入遺

2、傳算法中，提出了三種改進的遺傳算子—greedy交叉操作、隨機游走交叉操作以及子句變量懲罰交叉操作算子求解SAT問題，有效提高了求解成功率和收斂速度。遺傳算法同其他局部搜索算法一樣，不能判定 SAT問題是否存在解。
　　遺傳算法中，種群過早收斂的主要原因是遺傳算子的成熟化效應(yīng)。在一個封閉的種群中，個體只能與種群內(nèi)的個體交流信息，種群內(nèi)部個體之間充分共享信息的同時，也會帶來趨同化的問題。通過對全局搜索求解器zChaff、局部搜索求解

3、算法 WalkSAT等的研究，本文首先提出了在交叉算子中結(jié)合局部搜索算法及基于子句變量的懲罰策略。通過引導(dǎo)基因的交流，使得種群既能保持多樣性，又能提高遺傳算法的效率。其次，基于種群的獨島模型，模擬生物演化過程中家族譜系樹的概念，把種群劃分成更具社會學(xué)意義的家族，提出一種基于譜系樹的改進遺傳算法。其主要思想是，把種群細分為較小的家族，每個家族都有各自的演化算子，在每一次迭代后，家族之間的個體成員通過聯(lián)姻的方式進行結(jié)合，從而產(chǎn)生出比傳統(tǒng)的交