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

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

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

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