【作者】 郭鹏；

【导师】 罗文坚；

【作者基本信息】 中国科学技术大学 ， 计算机应用技术， 2009， 硕士

【摘要】 进化非选择算法是通过借鉴生物免疫进化机制与免疫非选择机制而提出的,具有较好的全局搜索能力。可满足性问题是六个基本的NP完全问题之一,其他NP完全问题均可在多项式时间内转换为可满足性问题。因此,SAT问题具有重要的研究价值。本文旨在分析进化非选择算法用于可满足性问题求解时的性能,并与传统的启发式翻转方法相结合,以设计高效的可满足性问题求解算法。具体工作包括以下几个方面:(1)从实验角度分析了非选择在求解可满足性问题时的作用。大量的实验结果表明,非选择在求解可满足性问题时具有协助算法跳出局部最优的作用。同时,实验结果也表明,仅仅依靠非选择并不能取得理想的结果,需要考虑其他启发式技术的加入,以增强局部搜索能力,从而进一步提高算法的求解性能。(2)提出了用于求解可满足性问题的混合算法HENSA-SAT。HENSA-SAT在进化非选择算法的基础上结合了传统的启发式翻转方法,一方面通过非选择协助算法跳出局部最优,另一方面通过启发式翻转方法提高算法的局部寻优能力。实验结果表明,HENSA-SAT在求解可满足性问题,尤其是在求解大规模可满足性问题时,与当前代表性算法GASAT相比具有较好的性能。同时,通过实验对HENSA-SAT算法的参数设置及非选择在协助算法跳出局部最优方面的作用进行了分析。总的来说,本文对非选择在求解可满足性问题时的作用作了具体分析,提出了用于求解可满足性问题的混合算法HENSA-SAT,不仅对可满足性问题本身的求解有参考价值,而且在设计用于其他约束满足及组合优化问题的进化非选择算法时有一定的指导意义。更多还原

【Abstract】 The Evolutionary Negative Selection Algorithm (ENSA) is proposed by drawing the mechanisms of evolution and negative selection in biological immune system. The ENSA has good global search ability. The Satisfiability problem (SAT) is one of the six basic NP-complete problems. Other NP-complete problems could be transformed into the Satisfiability problem in polynomial time. Therefor, the Satisfiability has important research value.This thesis aims at evaluating the performance of the Evolutionary Negative Selection Algorithm for solving the Satisfiability problem. In order to design efficient algorithms for solving the Satisfiability problem, the ENSA is combined with the classical Flip Heuristic. The main works in this thesis include the following aspects.(1) The effect of Negative Selection (NS) is analyzed in the ENSA for solving the Satisfiability problem by experiments. Experiments are conducted and the experimental results show that the NS has good ability of helping the ENSA escape from local optima for solving the Satisfiability problem. At the same time, the introduction of the NS could not reach the desired results. In order to improve the performance of the ENSA used for solving the Satisfiability problem, other heuristic techniques should be considered to enhance the ability of local search.(2) A hybrid algorithm for solving the Satisfiability problems called HENSA-SAT is proposed in this thesis. The HENSA-SAT is based on the ENSA and the Flip Heuristic. On the one hand, the ability of escaping from local optima is improved by the NS. On the other hand, the ability of local search is improved by the Flip Heuristic. Experimental results show that the HENSA-SAT has much competitive performance comparing to the classical Evolutionary Algorithms used for solving the Satisfiability problems. For the large-scale Satisfiability problems, the proposed algorithm has dominant advantages on most test instances comparing to the GASAT which is the state-of-the-art algorithm for solving the large-scale Satisfiability problems. Also, the effect of parameter settings and that of the NS which could help to escape from local optima are analyzed.Generally speaking, the hybrid algorithm for solving the Satisfiability problems called HENSA-SAT is proposed in this thesis. A concrete research is made on the effect of NS in the HENSA-SAT. The works in this thesis is not only important for solving the Satisfiability problems, but also has some guiding significance for the ENSAs used for solving other constraint satisfaction problems and combinatorial optimization problems.更多还原