【作者】 付宏杰；

【导师】 孙吉贵；

【作者基本信息】 吉林大学 ， 计算机软件与理论， 2011， 博士

【摘要】 随着新技术、新方法的不断涌现,人们对于传统问题的求解提出了更高的要求,将经典的求解算法与新兴优化技术相结合,越来越成为一种解决问题的新思路,很多实践证明,混合算法能够更加灵活、更加高效的解决实际问题。本文将差分进化算法与其它传统算法相结合,提出了求解二元约束满足问题的混合差分进化算法。提出了SADE算法,将构造的自适应函数运用于差分进化算法的变异因子和交叉因子的自适应调整,算法的实验结果与近年来提出的一些算法进行了求解性能的比较和分析,分析结果显示SADE算法收敛性很好,求解成功率(SR)远远高于其他算法;提出了IMDE算法,分析在CSPs问题的求解过程中种群的不同状态,使用分段函数来针对不同的种群分布,分别进行不同的变异策略,采用公测数据集进行测试,与其他算法的测试结果进行对比后的结果显示,算法有效的预防了早熟收敛,保持了种群的多样性；提出了EEMDE算法,将类电磁机制算法(EM)的吸引-排斥机制与差分进化算法相结合,种群中每个个体看作是一个点电荷,每个点电荷根据带电量不同的比较,而受到其他点电荷的吸引或者排斥的库仑力的作用,根据点电荷所受的合力的方向来获得加速度,改变点电荷的位置,算法在不需要外在干预的情况下,就能够很好的解决局部收敛的问题,实验结果显示,算法的收敛速度接近达到其他算法的二倍,算法的物理模拟具有可行性；提出了一种SAPSO算法,将自适应思想应用于粒子群算法用于求解二元约束满足问题,将该算法应用于求解随机约束满足问题,实验结果表明,改进后的算法比原算法(PS-CSP)能以更快的速度收敛到全局解。对于本文提出的以上算法,均采用了其他作者公开的公用测试数据集进行了测试,测试结果表明,本文提出的以上算法运行结果良好。关于将差分进化算法与其它技术相结合的研究工作还处于刚起步的阶段,有很多关于解决不同问题的尝试和探索工作需要研究,本文所完成的工作对该领域的深入研究具有很好的促进作用。同时也为求解类似的问题提供了新的思路和求解手段。因此,具有一定的理论研究意义和实际应用价值。更多还原

【Abstract】 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.更多还原