基于遺傳算法的SAT問(wèn)題求解研究.pdf

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

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

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