全局优化作为计算机科学和数值分析的分支，可简单归结为在某种判据准则下进行函数优化。全局优化的目标，就是对于给定的问题找到全局意义上的最优解。而对于典型的全局优化问题，目标函数通常为非线性，且存在很多局部极优。对于这类问题，传统优化算法往往容易陷入局部极优而难以对问题进行有效求解。同时，许多现实世界的问题都可归结为全局优化问题，如蛋白质结构预测、电路设计、任务调度、有限元分析等。因此对全局优化问题的研究始终是科研领域中的热点难点问题。 为了有效求解全局优化问题，人们设计了许多算法，其中演化算法作为一类重要的启发式算法，在全局优化领域得到了成功应用。演化算法是一大类借鉴达尔文进化论思想，模拟自然界物种进化过程，以种群演化的方式对问题空间进行搜索的方法的统称。在已有的各种演化算法中，历史最悠久、最为人所熟知的当属遗传算法。而随着演化计算领域的发展，一类新的演化算法――分布估计算法（Estimation of Distribution Algorithms）逐渐得到人们的重视，并且像其它诸多演化算法一样，在全局优化领域也得到了长足发展与成功应用。分布估计算法是从经典遗传算法衍生发展而来的一类新型算法，但与其他典型演化算法相比，分布估计算法最大的特点在于其不使用传统的交叉和变异算子，而采用对优质解进行建模的方式，来显式地描述潜在最优解在搜索空间内的概率分布，并通过这个估计得到的概率模型来指导后续搜索。由于引入了概率分布估计这一需求，许多传统机器学习方法在分布估计算法中得以应用。因此，分布估计算法也被视为机器学习与演化计算的交叉领域。 本文系统地介绍了用于求解全局优化问题的分布估计算法，回顾了分布估计算法的起源及发展，重点分析了分布估计算法在连续量优化问题上的性能，并针对现有方法的局限，提出了多项改进。本文的主要贡献有： 1. 分析了数值计算精度对基于高斯模型的分布估计算法的影响，指出当前算法的缺陷，提出了协方差矩阵修复（Covariance Matrix Repairing）方法，在提高算法对计算误差的鲁棒性的同时，最大限度地保证了算法的真实性能。一些原本被认为性能不佳的算法，可以在该方法的帮助下得以性能上质的提升。 2. 使用特征分析的方法， 提出了一个统一框架ED-EDA（Eigen Decomposition EDA），用于描述任意基于多元高斯模型的分布估计算法。基于此框架，研究对比了已有的各种基于多元高斯模型但使用不同搜索策略的分布估计算法的性能。 实验表明了种群规模与问题维数（搜索空间的大小）对于算法性能的影响，同时，不同搜索策略也可通过此框架得以公平对比，其各自的优缺点也同时得以充分展示。 3. 在目标函数形状不规则的优化问题上，传统的基于单高斯模型的分布估计算法往往性能不佳。针对这一问题，提出了一种基于集群（ensemble）方法思想的混杂分布估计算法NichingEDA，探讨了启发式方法在分布估计算法这一范式中的作用。实验表明，即使不使用复杂模型，引入合适的启发式策略与简单模型相配合，同样可以大幅提升分布估计算法的性能。 4. 分析了传统分布估计算法在问题维数持续增长时所面...
英文摘要
As a branch of computer science and numerical analysis, global optimization can be regarded as performing function optimization according to some criterions. The objective of global optimization is to find the globally best optimal solution of a given problem. For typical global optimization problems, the objective function is usually non-linear, and contains multiple local optima. When facing such kind of problems, traditional optimization approaches are often easily trapped by local optima and fail to find the global optimum. On the other hand, many real-world problems can be reduced to global optimization problems, such as protein structure prediction, circuit design, job scheduling, finite element analysis, etc. Therefore, global optimization is always a hot research topic and a challenging issue. To solve global optimization problems effectively, people have designed many algorithms. As an important branch of heuristic approaches, evolutionary algorithms (EA) have been successfully applied in many areas. EA is inspired by Darwinian evolutionary ideas. Through mimicking the evolutionary process of species, EA solves a global optimization problem by population-based search. Among all the EAs, genetic algorithms (GA) are the most well-known and with the longest history. As the evolutionary computation (EC) field continuously develops, estimation of distribution algorithms (EDA) have attract much attention of researchers and become a new branch of EA. Remarkable progress has been made since EDA is proposed. Like other EAs, also many successful applications of EDA have been made. EDA is derived from classical GA. But unlike other typical EAs, there is neither crossover nor mutation operators in EDA. Instead, EDA builds a probabilistic model based on promising solutions to explicitly describe the distribution of potential globally best solution. The global search is then guided by the probabilistic model. Because of the demand of estimation of distributions, many traditional machine learning methods can be introduced into EDA. As a result, EDA is also regarded as a cross subject of machine learning and evolutionary computation. This thesis firstly gives an introduction to EDA for global optimization, including a detailed review of the origin of EDA and its development. Then we primarily focus on analyzing the performance of EDAs on continuous optimization problems, and propose several improvements to remedy the drawbacks of existing approaches. The maj...
修改评论