【作者】 李龙；

【导师】 肖晓明；

【作者基本信息】 中南大学 ， 计算机科学与技术， 2011， 硕士

【摘要】 差异进化算法是一种高效稳健的进化算法,是近年来进化计算研究领域的热点。针对差异进化算法对变量相关问题的求解困难,本文提出一种基于协方差学习机制的差异进化算法LYDE。LYDE通过对当前解集的协方差矩阵进行特征值分解以选取合适的轴向进行交叉,消除差异进化算法对原坐标系的依赖性,并降低了优化问题变量间的相关性,提高了差异进化算法在旋转问题上的求解性能。LYDE采用双峰参数设置,即交叉概率和变异因子分别服从不同类型的双峰概率分布。交叉概率服从的双峰概率分布由两个不同均值的正态分布构成,使得交叉操作产生的子代高概率的分布在父体附近。变异因子服从的双峰概率分布由两个不同位置参数的柯西分布构成,用以平衡LYDE的全局搜索能力和局部寻优能力。通过对CEC2005中25个标准测试函数的数值试验,验证了LYDE在全局优化尤其是变量相关问题上的有效性以及在噪声问题上的鲁棒性。与现有算法(jDE, SaDE, JADE, EPSDE, CoDE)的对比结果表明LYDE在收敛速率和鲁棒性上优于现有算法。同时,实验也表明LYDE的两项机制对算法的性能有重要影响,对LYDE性能有协同作用。参数实验表明设置采样率为0.4,学习率为0.65的LYDE在测试集上有稳健的性能。为扩展LYDE的应用范围,本文通过空间映射方案将LYDE的应用领域由连续问题拓展到一类经典的离散组合优化问题——平面图上的集合覆盖问题,此类集合覆盖问题是应急设施选址的抽象问题。空间映射方案基于最小欧氏距离原则将LYDE的连续向量空间映射到离散解空间,从而保持DE的原有结构对离散问题进行求解。空间映射方案利用了平面图顶点间的距离关系,有效的提升了算法的求解性能。实验结果表明LYDE在集合覆盖问题上有优良的求解效果,并且求解性能优于遗传算法,展现了LYDE在离散问题上的应用潜力。更多还原

【Abstract】 Differential evolution which is an efficient and robust evolutionary algorithm is a hotspot of the evolutionary computation research in recent years. In order to improve the performance in multivariate correlation problems such as rotated problems, a covariance matrix learning based differential evolution (LYDE) is presented.In LYDE, Eigen decomposition is applied to covariance matrix of current solution set to achieve an Eigen coordinate system for crossover operator. The covariance matrix learning eliminates the coordinate system dependence from differential evolution and improves the performance in multivariate correlation problems. Moreover, we embed bimodal distribution parameter setting in our algorithm. Bimodal distribution for crossover probability is composed of two normal distributions with different mean values, and makes offspring produced by crossover operator distribute around the parents with high probability. Bimodal distribution for mutation factor is composed of two Cauchy distributions with different medians, and balances global exploration and local exploitation. LYDE has been tested on 25 benchmark functions of CEC2005 test suite. The experimental results suggest that LYDE is efficient for global optimization, especially rotated problems and is robust to noise. LYDE has a faster convergence rate and a higher precision than five recent algorithms (i.e. jDE, SaDE, JADE, EPSDE, CoDE) on 25 benchmark functions. The experiment also suggests both covariance matrix learning approach and bimodal parameter setting are critical to LYDE and the two components have a cooperative effect. The parameter sensitivity experiment shows LYDE with sample rate 0.4 and learning rate 0.65 has a robust performance on test suite.In addition, we propose an approach that mapping the continuous vector space to the discrete solution space based on the minimum Euclidean distance principle. By the above method, keeping the original structure of DE, the application field of LYDE is extended from the continuous problems to a classical discrete combinatorial optimization problem—set cover problem on ichnography, which is an abstraction of emergency facility location. The experiment result shows LYDE has an excellent performance and has a faster convergence rate and a higher precision than genetic algorithm. The application of LYDE for discrete problem is promising.更多还原