An Improved Adaptive Genetic Algorithm for Solving 3-SAT Problems Based on Effective Restart and Greedy Strategy

Abstract

An improved adaptive genetic algorithm is proposed for solving 3-SAT problems based on effective restart and greedy strategy in this paper. Several new characteristics of the algorithm are developed. According to the shortcomings of the adaptive genetic algorithm, it is easy to fall into the premature convergence and destroy optimal individual and make genetic performance decline. An improved adaptive genetic algorithm is proposed to adjust the crossover operator and mutation operator in different stages of evolution dynamically, and make use of the restart strategy to overcome the prematureness. At the same time, the algorithm adopts greedy strategy to make the maximum fitness value of each generation unabated, so as to accelerate the search for the optimal speed. In the experiment, several benchmark SAT problems in SATLIB are used to test the performance of the improved algorithm and the results are compared with those of other similar algorithms. The results show that the improved adaptive algorithm has a higher success ratio and faster solution speed.

Keywords

• genetic algorithm(GA)
• adaptive genetic algorithm(AGA)
• restart
• greedy strategy
• 3-SAT problems