摘要
针对求解3-SAT问题,提出了一种改进的混合遗传算法。该算法是基于局部搜索算法策略与SGA算法的基础上将三路划分快速排序算法与其相结合的一种改进。首先通过适应度函数对基准的调节,运用改进的三路划分快速排序,重新生成新的种群,这在算法延迟收敛的可能性及可满足范式无解的可能性方面能起到很好的抑制作用;其次通过实验证明,与同类算法比较,该算法加快了寻找最优解的速度。最后,验证了算法的有效性与可行性。
In this paper,an improved hybrid genetic algorithm for solving 3- SAT problem. The algorithm is an improvement which is based on the local search algorithm and SGA algorithm witch combination of three- route quick sort algorithm. Firstly,by the adjusting for the fitness function of pivot benchmark and using improved three- route quick sort to generate new population,the probability of the algorithms to delay convergence and the probability of the on solution of the SAT can play a very good inhibitory effect. Secondly,compared with the similar algorithms,it is proved by experiments that the speed of finding the optimal solution is accelerated. Finally,the validity and feasibility of the algorithm are verified.
出处
《青海大学学报（自然科学版）》
2015年第6期41-47,共7页
Journal of Qinghai University(Natural Science)
基金
青海省自然科学基金项目(2013-Z-930Q)
青海省应用基础研究基金项目(2014-ZJ-718)
国家自然基金(No.61363019)
关键词
遗传算法
局部搜索算法
三路快速排序算法
可满足性问题
genetic algorithm
local search algorithm
three-route quick sort algorithm
satisfiability problem
