The Study Of The Satisfiability Problem Algorithm

Satisfiability problem(SAT)is a famous decision problem,NP-complete problem has been identified in 1971.As the basic problem of logic,the SAT is still the key point of theories and application of calculator,It is widely used in many important fields.However,the genetic algorithm is used to solve the SAT problem which is one of the much more effective intelligence algorithm.In this paper,according to the characteristics of the SAT problem,in the analysis of the weakness of the traditional ant colony algorithm and genetic algorithm in solving the SAT problem,we put forward a new kind solving method of SAT problem based on hybrid ant colony and genetic algorithm(HAG).Improvements are given in the following aspect.Firstly a new method for generating initial solutions is proposed.Then an evolution operator is presented depending on the accumulated information of the suboptimal solutions in the process of iteration.Meanwhile a mutation operator is increased by changing literal value in the unsatisfied clause under the condition of current optimal solution.The experimental results showed that in most cases our algorithm has better global searching performance and is able to find the optimal solution through only a few iterations,which can effectively avoid the premature convergence of ant colony algorithm and genetic algorithm.but,it's worth noticing the initial solutions which greatly influenced the optimizing result,a low-quality initial solutions means more iterations,even which was trapped into the part of the local optimal solution.In order to avoid appearing this case,the paper later came up with varies multi-population.namely,producing more population to take place of the original single population,different kinds of single genetic algorithm connected with each other,when the some of the population search for the real population,the iteration was finished.According to the great number of example verifications to prove the ability of the genetic algorithm of multi-population and solve efficiency is better than general ant colony optimization and genetic algorithm.Two advanced solutions were complished,which was based on MATLAB.Moreover,using many different groups difficult example verifications to test,the result of experiments verified the feasibility of my algorithm.