Research On Constraint Solving Algorithms Based On Differential Evolution

Constraint Satisfaction problem(CSPs) is a significant branch in the field of operations research and artificial intelligence. In real life, many problems can be converted into the CSPs to solve. Constraint satisfaction problem research is mainly divided into language and algorithms, which respectively correspond to the two fields of constraint satisfaction problem, namely representation and reasoning. Representation can be divided into general and special. and reasoning can be divided into constraint propagation and search again.CSPs are usually NP- hard problems, which is composed of a set of variables and a set of constraints. Solving the CSPs is looking for a group assignment for its variable set to make it meet the constraint set. Such a group assignment is called a solution of CSPs. And solving method of CSPs can be generally divided into completeness solving algorithm and non-completeness solving algorithm. Completeness algorithm is based on the backtracking algorithm(BT), which adopts depth-first strategy when it chooses instantiated variables. If not found solution then start back mechanism, until we find a set of solution, or prove that the problem is no solution; Non-completeness algorithm generally refers to the swarm intelligence algorithm,finally wich can find the optimal solution by iterative,through the simulation of the some biological group(such as forage, agglomeration, evolution, etc.). This paper is mainly related to the differential evolution(DE).In the DE, every possible solution is called parameter vectors or genes. Steps of the differential evolution is approximately the same to the standard Evolutionary Algorithm(EA), but different from the traditional EA. DE mainly depends on the differential vector to disturb the current test vector, by using the differences of the parameter vector to explore the target area. Since the late 1990 s, in the field of science and engineering, DE has gradually increasing influences and an important position in the optimization problem. First of all, compared with other evolution algorithm, the obvious advantages of DE is that direct implementation is easier. No matter what kind of programming language, the body of the algorithm is only four or five lines of codes; Secondly, in solving the unimodal, multimodal, discrete and continuous problems, the DE showes good performance advantages, beyond many algorithms; Again, the control parameters of DE is less, which mainly includes three control parameters such as the crossover probability( CR), the scalar factor( F) and the population size( NP). The performance of the algorithm also mainly depend on the three control parameters. Finally, compared to some of the most competitive argument optimizer(such as adaptive evolutionary strategy of covariance matrix CMA- ES), DE has a low space complexity.Proposed the adaptive DE based on GAC in arc consitency technology in this paper, AC- FSADE algorithm, compared with SADE algorithm, has a three part of improvements. First of all, the scalar factor F of controlling the variation is updated based on individual fitness, F is larger in primary evolution stage, and the search step is long, which help to open the exploring space up. F is lesser, the search step is short, which help fast convergence of the algorithm in late evolution; Secondly, The crossover probability(CR) of controlling crossover operation can be updated based on the individual fitness. CR is lesser and it can prevent premature convergence,which help to keep population diversity at the start of evolution. CR is bigger, which help individuals retain good genes in late evolution.Finally, blending the GAC of arc consitency technology in SADE, eliminates invalid values in variable domain, and reduces the scope of variable domain, which simplify the problem to solve and improves the success rate of the algorithm.The experimental results show that the proposed AC- FSADE algorithm effectively improves the success rate of the algorithm.Compared with SADE, the solving success rate is increased by 22% approximately. So, when solving the CSPs, AC- FSADE algorithm is a kind of potential DE, which has broad prospects for development.