Genetic Algorithm for Solving SAT Problems Based on Learning Clause Weights
Ling Ying · Chinese Journal of Computers · 2005
A novel genetic algorithm, SAT-WAGA, is proposed for solving SAT problems based on learning clause weights in this paper. Several new characteristics of the algorithm are innovative. The new algorithm makes use of the heuristic information from the structure of SAT problems by clause weights. A new operator of learning clause weights is designed to prevent precocity in the process of solving problems. This operator adapts the weights of clauses according to a criteria condition. A criteria parameter for detecting precocity is defined. The strategy of keeping the best chromosomes guarantees the property of convergence in the evolution iteration. To demonstrate the feasibility of the new algorithm, an experiment system of several famous algorithms is implemented. The experiment works focus on comparing the total span of all plateaus in evolution iteration, the success rates and the total time of the new algorithm to a classical genetic algorithm by solving several groups of various scales of random generated SAT problem instances. The appropriate values of the precocity criteria parameter of the new algorithm are also tested and presented. The experimental results show that the SAT-WAGA performs remarkably better than a classical genetic algorithm in the aspects of speed, the success rate and the solvable problem scales.