Research On Algorithm Optimization And Application Of Maximum Satisfiability Problem

With the rapid development of information science and network technology,combinatorial optimization problem has become an important research direction in operations research,discrete mathematics and computer science.Maximum satisfiability problem is a typical combinatorial optimization problem.Many combinatorial optimization problems in real life can be transformed into maximum satisfiability problems,such as robot path planning,vehicle scheduling,resource allocation,neural network optimization and so on.Therefore,the research on Max-SAT problem solving algorithm has important theoretical significance and application value.Max-SAT is a classical NP hard problem.With the in-depth development of artificial intelligence and big data technology,the amount of data increases rapidly,and the scale of Max-SAT problem gradually expands.The original algorithm for solving Max-SAT problem is no longer applicable.Therefore,researchers begin to design new solving algorithms or optimize the original solving algorithms.Based on this,in order to optimize the alert propagation algorithm and simulated annealing algorithm,two non complete algorithms are designed to solve the Max SAT problem,thus improving the performance of solving the Max SAT problem.Specifically,the main research contents are listed as follows:(1)On the basis of warning propagation algorithm,warning values are obtained by local warning propagation,some variables are assigned by warning values,and for unassigned variables,variable weights are calculated,and a group of effective variable assignments are obtained.finally,the random walk local search algorithm is used for the assignment results.The improved algorithm improves the global search ability of the warning propagation algorithm in solving the Max-SAT problem,and can be used to solve any region.At the same time,the accuracy of the solution is also improved.The results show that the performance of this algorithm is better than that of traditional warning propagation algorithm.(2)An improved fast simulated annealing algorithm is proposed to solve the Max-SAT problem.The initial solution is calculated by variable weights,combined with probability-based random disturbance and selective disturbance,and a memory function is added to the Metropolis acceptance criterion to search the current local optimal solution.Secondly,two cooling modes of high and low temperature are introduced to greatly improve the global search ability of the algorithm,and then accelerate the convergence speed of the algorithm.Effectively reduce the solving time.Finally,simulation experiments are carried out on open data sets and randomly generated data sets to prove the effectiveness of the improved algorithm.(3)A Max-SAT solver is designed and developed,which is used to generate random SAT instances and solve Max-SAT problems...