Research On Hybrid Differential Evolution Algorithms For Binary Constraint Satisfaction Problems

Our daily life is filled with all kinds of constraints, for example, one week invariably includes seven days. We have to arrange our everyday work according to the timetable. Therefore, constraint is a very broad concept and Constraint Satisfaction Problems (CSPs) belong to an important research area in Artificial Intelligence. Lots of problems can be stated as CSPs. For instance, Eight-Queen problem is the most famous one, and Sudoku, Timetable, Robot Planning are all CSPs. There are many solutions to CSPs. As a result, it is a powerful tool when used to solve many complex combinatorial problems, and has aroused great attentions as well. Most of those combinatorial problems are NP-Complete problems. Generally speaking, the key targets of CSPs are to find one possible solution or all solutions. If an assignment of values to the set X makes all the constraints satisfied simultaneously, then we call these values a solution of CSPs.Constraint satisfaction problems on finite domains are typically solvable using a form of search. The most commonly used techniques are backtracking, constraint propagation, and local search algorithm.Backtracking is a kind of recursive algorithm. It maintains partial intermediate results of the variables when a program is being executedConstraint propagation is a method used to modify constraint satisfaction problems. More precisely, it is a forced executed one, forcing the local compatibility, which matters the consistency of a group of variables or constraints.Local search algorithm is incomplete. It may find a solution to a problem, but it possibly fails even if the problem is solvable. In practice, the efficiency of local search is depended by random function. Nowadays, integration of search with incomplete local search leads the world's focus to hybrid algorithms.Differential evolution algorithm is very similar to the standard one. They are both based on the population, and have choices, intersections and mutated operations. Still, Greedy Algorithm is used in the same way. The only difference is that the differential evolution algorithm calculates the mutation rate with differential methods. So individuals may be affected by others'position and their changes and then demonstrate the social properties of swarm intelligence. There are three parameters can be used to improve the differential evolution algorithm--mutation rate F, the crossover rate CR and the size of population NP, and among them mutation rate F is the most important one. Many studies are aiming at how to improve the mutation rate F.This paper focuses on hybrid differential evolution algorithms for binary constraint satisfaction problems. That is to make Differential Evolution Algorithms combined with other methods, and then apply them to solve binary constraint satisfaction problems. This thesis has proposed four different hybrid algorithms. Specifically, and the related research work of this thesis is carried out in the following aspects:Firstly, a novel self-adaptive differential evolution algorithm, called SADE, has been proposed. SADE self-adaptively adjusts the mutation rate F and the crossover rate CR, and keeps the diversity of the population effectively. In order to balance individual's exploration ability, which is to solve the problem, and exploitation ability, which is to prevent the local optimization and find new space, in different stages, this paper sets two different self-adjusted nonlinear functions that vary dynamically, F and CR. SADE maintains the diversity of population and also improves the global convergence ability in the meantime. It improves the efficiency and success rate and avoids the premature convergence as well. Simulation and comparisons are based on the same test-sets of CSPs, and the results present the effectiveness, efficiency and robustness of the proposed algorithm.Secondly, in order to solve constraint satisfaction problems, an improved differential evolution (IMDE) algorithm is proposed. With the purpose of improving the performance, bases on the different distribution of different groups, the IMDE algorithm adjust the F and CR of every individual dynamically. IMDE maintains the diversity of population and improves the global convergence ability. Experimental results prove that IMDE is effective and efficient in solving binary constraint satisfaction problems.Thirdly, a novel hybrid elements exchange/electromagnetism meta-heuristic differential evolution algorithm (EEMDE) has been proposed. The original DE algorithm is to avoid the premature convergence effectively. The electricity charge in the electricity field is affected by the source charge'Coulombs force and that is the Coulombs Law. A individual will be like a charged particle, and a metric is defined, which is used to measure the composition of forces exerted on a point. The composition of forces is defined as to get an adaptive adjustment of the mutation rate F. EEMDE avoids the DE to the "uphill" in the wrong direction forward may produce slight disturbance on the original vector for enhancing the exploring capacity. Experiments demonstrate that the convergence of EEMDE is faster than DE and simulations based on some CSPs and it proved the effectiveness, efficiency and robustness in the same time.Finally, a self-adaptive particle swarm algorithm, called SAPSO, has been proposed. Exploration procedure and exploitation procedure have been introduced in SAPSO. The population diversity variable, which was used to represent the diversity of population, has been defined. In addition, a metric to measure a particle's activity, which is used to choose which state it would reside in, is defined. In SAPSO, each particle has two states:exploration state and exploitation state. In order to balance a particle's exploration and exploitation capability for different evolving phase, a self-adjusted inertia weight which varies dynamically with each particle's evolution degree and the current swarm evolution degree are introduced into SAPSO algorithm. It uses the self-adaptive selection to select values from domains instead of random selection. This strategy searches in the promising solution space for global solution when the particles exploit the search space. It tests the hybrid algorithm (SAPSO) with random constraint satisfaction problems. The experimental results show that the hybrid particle swarm algorithm (SAPSO) has better global search abilities than PS-CSP, and the convergence of the algorithm is also better than other.Three differential evolutions algorithms and one PSO algorithms have been proposed. We compared the performance of different differential evolution algorithms on binary CSPs proposed recent years. The experimental results indicate that the proposed algorithm can achieve pleasing results. However, more careful parameter tuning may improve the performance with different problem instances, and more comparative works for more problems should be performed to provide a full view. In the future, we will extend the proposed SADE algorithm for solving more comprehensive set of test problems, including real life problems.