The Research Of The Improvement Of Immune Algorithm For SAT Problem

Satisfiability problem(SAT Problem) is the first proved NP complete problem, and itis also the "seed" of all NP complete problems. Any NP complete problem can beconverted into SAT problem to solve in polynomial time. At present, the method forsolving SAT is widely used in the automatic generation of test vectors, symbolicmodel checking and equivalence checking as well as the field of electronic autom-ation design. Therefore, it is of great significance and applied value to study the SATproblem.Currently the main method for solving SAT problem can be divided into completealgorithms and incomplete algorithms. If the problem can be solved, we are bound tofind the solution with the complete algorithms. However, with the increasing scale ofthe problem, SAT problem’s computational complexity will greatly increase likeexponent. The incomplete algorithm can not guarantee to find the solution of theproblem, but it can solve the problem with great speed and usually meet the require-ments. Therefore, incomplete algorithm has gradually become a research hotspot forsolving SAT problem.This paper mainly researched the SAT problem’s solution with incompletealgorithm method. Based on the introducation of the SAT problems, their solutions,basic knowledge of immune principles and immune algorithm, two kinds of improvedimmune algorithm are proposed and applied in SAT problem and ALLSAT problem inthis paper.Firstly, an improved immune algorithm based on Hamming distance is proposedfor solving the SAT problem. The algorithm defined the antibody concen-tration withHamming distance, which avoided the time-consuming calculation and improved theefficiency of the algorithm. According to the shortcomings of traditional mutationoperator, the algorithm used a new mutation operator, which is based on randomsearch. The mutation operator not only can accelerate the evolution speed ofpopulation, but also can prevent the “disturbed” phenomenon in the later stage ofevolution. Experimental results show that:the algorithm is better than immune algor-ithm based on information entropy in success rate, convergence rate, etc, has lessaverage evolution generation and higher success rate than Quantum Immune CloneAlgorithm. Secondly, an improved Multigroup cloning immune algorithm is proposed forsolving ALLSAT problem. This algorithm is optimized with niche method andbit-climbing algorithm. It has the advantages of keeping population diversity, fastconvergence rate,etc. Algorithm evolve kinds of population at the same time, eachgroup can be cloned, mutation, selection, the best individuals of each species wereclimbing operation. When subgroup evolve to a certain number, if the optimal solut-ion is the problem’s solution, we put this solution into the niche core set. Then wecompare each individual distance between groups and niche core set. If the distance isvery small, then it can generate a new individual, which replace the old individual toconstitute a new subgroup, and then restart the evolution of various groups. The expe-rimental results based on the solution to ALLSAT problem show that:for small-scaleproblems, the algorithm can find all solutions quickly. And for large-scale problems,which traditional methods can not solve, the algorithm can find as much solutions aspossible.