SAT Problem Solving based on Hybrid Grey Wolf Genetic Algorithm

A hybrid algorithm based on grey wolf optimization algorithm, genetic algorithm, and heuristic information is proposed for solving SAT problems. The algorithm is an incomplete algorithm. To solve the problem that the retention of dominant individuals in the standard genetic algorithm depends on selection probability, the grey wolf optimization algorithm is introduced into the crossover operator to increase the probability of inheriting dominant individuals to new generation. At the same time, there is also a significant randomness in mutation operation, which makes the entire algorithm prone to falling into local optima and the convergence speed is too slow. Therefore, in mutation operator, select those variables whose values can satisfy more clauses, to jump out of local optima while accelerating the convergence speed of the algorithm. Through comparative experiments, it was found that the algorithm proposed in this paper can quickly solve satisfying problems, and the algorithm is efficient and stable.