节点文献
差异演化算法及其应用研究
Research on Differential Evolution Algorithm and Its Applications
【作者】 武志峰;
【导师】 黄厚宽;
【作者基本信息】 北京交通大学 , 计算机软件与理论, 2009, 博士
【摘要】 差异演化是Storn和Price在1996年提出的一种新型演化算法,近年来已经成为演化计算中的研究热点。差异演化利用种群中两个个体向量的差向量作为第三个个体向量的扰动分量形成变异向量,然后采用优胜劣汰的自然选择机制产生下一代种群。与其它演化算法相比,差异演化算法具有更好的搜索性能,适宜于求解高维、非线性和多目标优化问题。目前差异演化算法已广泛应用于各个领域。然而,差异演化算法和其它演化算法一样,也存在着早熟、后期收敛速度慢及算法控制参数难以正确选取等问题。同时,差异演化算法的机理决定了它适合于求解连续空间的最优化问题,不能直接用来求解离散空间的组合优化等问题。本论文正是从这几个方面进行了深入研究,提出了若干改进算法,并把这些改进算法应用于自适应均衡算法设计、模糊聚类分析、多Agent联盟形成等领域,取得了很好的效果。本文主要工作和创新点概述如下:(1)为加快差异演化算法的收敛,避免算法陷入局部最优解,提出一种双子代竞争差异演化算法DocDE。算法利用交叉操作生成两个子代个体,并通过改进的两次“贪心式”选择策略与父代个体一起竞争形成新一代种群。该算法可以充分利用父代个体中的有用基因信息,有效扩大算法的搜索空间,提高算法的搜索效率。标准测试函数上的实验结果显示,该算法具有较好的适应性、稳定性及较强的全局搜索能力,特别是对高维复杂函数,该算法可以较快地找到最优解。同时,把DocDE算法应用于无线通信系统中的自适应均衡算法设计,提出一种基于DocDE的自适应均衡算法,利用DocDE代替传统梯度下降方法调节均衡器中的抽头系数。实验结果表明,基于DocDE的自适应均衡算法能够获得比传统基于梯度下降的LMS算法更好的收敛速度和更高的收敛精度,具有较低的误码率,可以有效减少训练序列的长度,增加信息传输的有效时间,提高信道利用率。(2)针对差异演化演化算法的控制参数选取问题,提出一种自适应差异演化算法SelfDE,自动调整算法中的缩放因子和交叉概率。该算法对种群中每个个体都使用各自独立的缩放因子和交叉概率,并把个体适应度作为个体对应控制参数调整的决策依据,从而克服控制参数调整的盲目性。该方法不但可以减少差异演化算法中需要人工选取的控制参数,而且加快了算法的收敛速度。通过不同测试函数的仿真实验表明,与其它参数自适应算法相比,SelfDE算法在最优解质量和收敛速度上都有较好的表现。另外,针对模糊聚类问题,提出一种动态权和有效性函数DWSVF指标,改进了聚类有效性指标的效率。将SelfDE算法应用于模糊C-均值聚类,以动态权和有效性函数指标为适应度函数,提出一种基于自适应差异演化的模糊C-均值聚类算法FCBADE。在不同数据集上的实验结果表明,提出的聚类有效性指标DWSVF性能稳定,FCBADE算法能准确地找到实际聚类数、有效地避免陷入局部极值问题,比其它几种聚类算法具有更好的性能。(3)在多Agent系统中,Agent联盟形成是一个组合优化问题。将求解连续域上函数优化问题的差异演化算法应用于离散域上组合优化问题求解,结合Agent联盟形成问题提出一种二进制编码差异演化算法BinDE。算法通过引入S型函数把差异演化算法变异操作的结果变换到离散域空间,从而解决组合优化问题。与遗传算法和蚁群算法的对比实验结果表明,BinDE算法在求解Agent联盟形成问题中是可行、有效的,无论在解的质量还是运行时间上都明显优于遗传算法和蚁群算法。
【Abstract】 Differential Evolution (DE) is proposed by Storn & Price in 1996. As a novel Evolutionary Algorithm (EA), DE has attracted more attention in recent years. The crucial idea behind DE is a scheme for generating trial vectors. DE generates new vectors by adding the scaled difference of two randomly selected population vectors to a third randomly selected population vector, and mixing the target vector with the generated vector. In the selection stage, the trial vector competes against the target vector to produce the new generation Compared with other EAs, DE is capable of optimizing high dimension, nonlinear, nond ifferentiable, multimodal objective functions and multiobjective optimization problems. It has been applied to many areas successfully. However, like other EAs, DE still suffer from the problem of slow and premature convergence. In addition, the control parameters involved in DE is highly dependent on the problems under consideration and is not easy to properly set. In this dissertation, some improved DE algorithms are proposed and applied in the fields of fuzzy clustering analysis, agent coalition formation and adaptive equalization. The main contributions of this dissertation are described as follows:(1) In order to speed up the convergence of DE and to avoid the algorithm falling into a local optimal solution, a modified DE algorithm, called DocDE, is presented, in which two trial vectors are created by crossover operation as candidates of the next generation The experimental results on benchmark functions show that the proposed algorithm is good at adaptability, stability and global search ability. Especially, for high-dimensional complicated functions, DocDE can expand the search space to find the optimal solution quickly. A novel method for adaptive equalization is presented, which using DocDE instead of gradient descent to adjust the coefficients of the equalizer. The experimental results show that the novel algorithm speeds up the convergence rate and improves the convergence precision through the evolution of multi-gene ration in the situation of a short training set. Compared with the traditional LMS and original DE, the novel algorithm achieves the lower misadjustment and the less symbol error rate.(2) For solving control parameters selected problem of DE, a self-adaptive differential evolution algorithm, called SelfDE, is presented. The improved algorithm uses self-adaptive mechanisms to adjust scale factor F and crossover rate CR in DE. It not only reduces the control parameters of DE required to be selected by hand , but also speeds up the algorithm convergence rate. Experimental results on different benchmark functions show that SelfDE is superior to the other related algorithms such as jDE, FADE, DESAP and SaDE algorithms on the quality of solution for most benchmark functions. A new fuzzy clustering algorithm based on SelfDE (FCBADE) is presented, which can be used for optimizing clustering criterion function and generating appropriate partitioning of the dataset. In the algorithm, the weighted sum validity function (WSVF) is improved as a dynamic weighted sum validity function(DWSVF). Several experiments have been implemented to show the effectiveness of FCBADE. In comparison with other genetic clustering algorithms, FCBADE can consistently and efficiently converge to the best-known optimum corresponding to the given data in concurrence with the convergence result. The experiments also found that DWSVF is generally able to improve the confidence of clustering solutions and achieve more accurate and robust results.(3) In multi-agent systems, forming agent coalition is a combinatorial optimization problem. In order to apply DE which is suitable for solving optimization problems mainly in continuous spaces to solve the combined optimization problems in discrete spaces, a novel binary-encoding differential evolution (BinDE) algorithm, which combined with forming agent coalition, is presented. The experimental results show that the new algorithm is feasible and efficient. It is superior to other related methods such as GA and ACA both on the quality of solution and on the convergence rate.