基于進化非選擇算法的可滿足性問題求解.pdf

1、進化非選擇算法是通過借鑒生物免疫進化機制與免疫非選擇機制而提出的，具有較好的全局搜索能力?？蓾M足性問題(The Satisfiability Problem，SAT)是六個基本的NP完全問題之一，其他NP完全問題均可在多項式時間內(nèi)轉(zhuǎn)換為可滿足性問題。因此，SAT問題具有重要的研究價值。
　　 本文主要分析進化非選擇算法用于可滿足性問題求解時的性能，并與傳統(tǒng)的啟發(fā)式翻轉(zhuǎn)方法(Flip Heuristic)相結(jié)合，以設計高效的可滿足

2、性問題求解算法。具體工作包括以下幾個方面。
　　 (1)從實驗角度分析了非選擇算子在求解可滿足性問題時的作用。首先，設計了用于SAT求解的ENSA-SAT算法(Evolutionary Negative SelectionAlgorithm for SAT)，通過與不含非選擇的進化算法的實驗比較，分析了非選擇算子在協(xié)助算法跳出局部最優(yōu)方面的作用。其次，將傳統(tǒng)的啟發(fā)式翻轉(zhuǎn)方法引入到進化非選擇算法中，設計了用于SAT求解的ENSA-

3、FH-SAT算法(EvolutionaryNegative Selection Algorithm combined with Flip Heuristic for SAT)，并與不含非選擇的ES-FH-SAT算法(Evolutionary Strategy combined with Flip Heuristic for SAT)在同等條件下進行實驗比較，分析了非選擇算子在協(xié)助算法跳出局部最優(yōu)方面的作用。
　　 (2)提出了用

4、于求解可滿足性問題的混合算法HENSA-SAT(Hybrid ofEvolutionary Negative Selection Algorithm，F(xiàn)lip Heuristic，BackForwardFlipHeuristic and VerticalClimbing for SAT)。HENSA-SAT將進化非選擇、啟發(fā)式翻轉(zhuǎn)、退步進步啟發(fā)式翻轉(zhuǎn)局部搜索和垂直爬山法等相結(jié)合而設計。實驗結(jié)果表明，HENSA-SAT在求解可滿足性問題，