Genetic Algorithm And Discrete Particle Swarm Algorithm In The Application Of SAT Problem

This paper discusses the global optimization algorithm of genetic algorithm and discrete particle swarm optimization. Genetic Algorithm (Genetic Algorithm, GA) is a kind of natural evolution by Darwin and Mendel genetic theory, based on solving global optimization problems of the bionic algorithm, which is by the United States Professor of the Holland JH. GA based on the survival of the fittest, the evolution of the principle of survival of the fittest, the solution containing groups may be used repeatedly genetics basic operations, and continuously generate new groups, so that populations of constant evolution, in both the global optimization of a parallel search technology to search for the optimal group individual, in order to achieve the optimal solution to meet the requirements or quasi-optimal solution. GA can be widely used in combinatorial optimization, machine learning, adaptive control, planning and design, artificial neural network training, and image processing areas such as intelligent computing in the 21st century, practical technologies.Genetic algorithm contains the following five basic elements: (1) the encoding parameters; (2) specify the initial population; (3) fitness function design; (4) control parameter settings (primarily population size and genetic operation to set the probability of fitness); (5) The design of genetic manipulation. These five elements constitute the core of the genetic algorithm. This article focuses on the genetic operators of selection, crossover and mutation operator of genetic algorithm's influence in the implementation process. And templates crossover has been improved, while maintaining the premise of the original model of diversity, cross-operator as little as possible changes to the parent on behalf of the individual models, while discussing the operation operator, and improved technology based on niche genetic algorithm.PSO (particle swarm optimization, PSO) is based on the basic principles of the social behavior of groups of species above, initially to simulate the social behavior of the flock or fish to be established. Formation flying with the flock's direction of flight, if a sudden change, the entire flock will be in a relatively short period of time to re-formation of flying in one direction, while if there are individual bird's flight direction, if a sudden change, it will be with the entire direction of flight of the flock re-adjust the direction of flight. Based on this idea, the social behavior of this species group with description of the algorithm to do, but the formation of particle swarm optimization.The algorithm is based on principles of neighborhood design method of operation. Groups of particles in place on the optimization problem represents a possible solution, a single particle migration is in accordance with its own fitness function value and the neighboring particles within the region had experienced the best location and the overall fitness of the particles of the highest visited The best location determined. Particles in its neighboring regions to study, it would also provide its own to other particles possess the best structural information.The standard particle swarm algorithm is mainly used in the optimal value function of a continuous numerical solution, in practice proved to be a more effective method, with the design simple, easy to operate, the convergence speed and high efficiency. However, in practical applications, many discrete problem solving, such as scheduling, routing and other issues. The standard particle swarm algorithm can not do anything, because we can not guarantee must be in the discrete solution space, so the scholars of the standard ion swarm done a lot to improve in order to make particle swarm algorithm can solve the problems in discrete space, there have been more than applied to different kinds of discrete particle swarm optimization problems.This paper describes in detail the genetic algorithm and its development process based on the paper, a niche-based technology can enhance the local search ability of genetic algorithm for an improvement, the introduction of templates crossover operator to make the algorithm to avoid trapped in local solutions. Enhance the diversity of the individual, to a certain extent similar to the individual played a foreclosure effect. As the template does not take into account when crossing the exchange of its location, the probability of failure mode is relatively small. At the same time, it can search some of the previous point-based crossover model can not search a certain extent to avoid the algorithm into a local minimum. However, in applications, the crossover operator is based on a certain probability of realization, the probability called crossover probability. This avoids blind crossover operations carried out through the crossover probability to control the conduct of cross-cutting operations. And use the genetic algorithm [0,1] domain of the SAT is solved, experimental results show that fewer of the SAT for the clause, the question that the algorithm can find a better solution, when the number of iterations a sufficient number of cases, virtually always able to find all the solutions, but for the solution of large-scale SAT problems have yet to be further improved.This is also the dual discrete particle swarm algorithm has been improved, in the algorithm, the introduction of probability, the algorithm can be applied to discrete optimization problems. The resulting particles depends on whether it was changed under the guidance of the probability of particles in [0,1] between the values. If the particle's current position under the effect of the probability function can be greater than a predetermined random value, then the current state of the particles to take a contrary, if the particle's current position under the effect of the probability function of random value is less than a predetermined , then the state of the particles take 0. Shared function with the probability to carry out the adjustments in lieu of flying particles vector, taking into account when the particles move up to a certain precision, every particle of the reference method used by neighborhood will play a significant role, that is, to a certain extent, you could find the optimal solution faster.From a large number of repeated implementation of the results can be seen, for less number of clauses for solving SAT problems can receive good results, and the use of the method compared with non-implementation of the algorithm result, the method of computing time is more short. Meanwhile, the same number of iterations or a specified number of cases to migrate than the algorithm does not use this method to make more of the solution. If you do not take into account the cost of computing to give algorithms enough iterations, the algorithm can find all the solutions. But the more the number of clauses, then the implementation of the algorithm efficiency will decline.In summary, the specific work of this paper is:1. Discussed the genetic algorithm genetic operators and operation of operator. 2. Niche-based technology, an improved genetic algorithm to enhance local search ability of the algorithm will be used to improve problem-solving SAT.3. Discussed the particle swarm algorithm and discrete-ion swarm.4. Algorithm for binary discrete ion groups to do to improve and strengthen capacity of local search algorithm will be used to improve small-scale problem-solving SAT.In this paper, future research work done in planning, in-depth study of intelligent global optimization algorithm applied to large-scale SAT will improve the problem-solving, and can be used in neural networks based on mathematical mean to optimize the weight coefficients.