Research On Max-SAT Solving Algorithm Based On Population Evolution

As a classic NP difficulty problem,the maximum satisfiability problem(Max-SAT)is one of the core issues of theoretical computer science.Many combinatorial optimization problems in real life can be transformed into Max-SAT problems such as circuit planning,vehicle scheduling,and neural network optimization.The research on Max-SAT problem solving algorithm has important theoretical significance and practical application value.The algorithm for solving Max-SAT problems is divided into exact algorithms and heuristic algorithms.The exact algorithm can search the whole solution space to give the global optimal solution,but the theoretical time complexity of the algorithm is exponential,so it is not suitable for solving large-scale examples in a short time.The heuristic algorithm can give an approximate global optimal solution in a short time,which is very advantageous for solving problems that require fast response.Based on the research of Max-SAT problem,this paper proposes a new Max-SAT algorithm based on population evolution.The framework of the population evolution algorithm based on opposite learning for solving the Max-SAT problem is designed.In opposition-based population evolution algorithm,population diversity is expanded by considering candidate individuals and opposing individuals simultaneously.Two local search algorithms combining taboos and path-relinking are proposed.In the tabu search algorithm,the double tabu strategy is adopted,which not only avoids the flipping selection of arguments in the search process,but also limits the choice of search solutions.In the path-relinking algorithm,the dual opposite search is used,which not only from the initial solution search to the target solution,simultaneous search from target solution to initial solution.The 454 examples of the random group and the 402 examples of the crafted group in the 2016 Max-SAT International Competition were calculated.The experiment compared the influence of the optimization strategy proposed by the paper on the algorithm.The optimized algorithm is compared with the state-of-the-art algorithms in the current literature.The experimental results show that the optimal solution number of the proposed algorithm is similar to the current optimal algorithm,and the speed of proposed algorithm is faster than the current optimal algorithm.