Estimation Of Distribution Algorithms And Their Applications In Dynamic Optimization Problems

Estimation of distribution algorithm (EDA) is a new class of evolutionary algorithms, which combines the statistic theory with evolutionary schemes. In recent years, EDA attracts more and more attentions. Although EDA has got some progresses since it was proposed, there are many unsolved problems, such as theory analysis, algorithm designs and applications, etc. Based on characteristics and types of EDA, we mainly focus our study on the performance improvement of EDA and the applications of EDA to dynamic optimization problems. The main contributions of this dissertation are as follows:1. Study the convergence of estimation of distribution algorithm. Firstly, a model of EDAs with finite population is built up by incorporating an error into expected distribution of parent population. Secondly the convergence of EDAs is proved with finite population under three widely used selection schemes.2. Bayesian optimization algorithm (BOA) is improved from three aspects. Firstly, a Bayesian optimization algorithm incorporated with local structure learning is proposed to decrease the computation, and the complexity of the proposed algorithm is analyzed. Secondly, according to the characteristics of BOA, it is discussed on how to discovery and use prior knowledge in general optimization problems. Concretely, the information discovered in the previous generation is used as prior knowledge and is incorporated into the Bayesian networks learning. As a result, the reliability of the networks and the performance of the proposed algorithm are improved. Finally, we discuss the population diversity of BOA and design a diversity function. By using this function, the mutation operator is incorporated into BOA. The objective is to maintain the diversity of population and avoid the algorithm traping in the local optima. Simulations indicate that the above three algorithms are all effective.3. We design a class of special dynamic optimization problem and propose an algorithm to solve it. Firstly, according to the characteristic of changing environment, a class of special dynamic problem in which the change time obeys some distribution is addressed. Secondly, for this type of problems, an adaptive PBIL (Population-based incremental learning) algorithm is presented, where the probability of the random variable is used to adaptively adjust the probability model of the current population, to increase population diversity and to promptly react to the environment changing. The experimental results show that adaptive PBIL can track the optimal solution more reliably and accurately compared with PBIL. 4. For dynamic discrete optimization problems, a multi-population univariate marginal distribution algorithm (MUMDA) is proposed. The main idea of the algorithm is to divide the search space into several parts by using several probability modals corresponding to several populations. Meanwhile the algorithm explores and exploits in different regions and can make the best solutions migrate. The experimental results show that the MUMDA is effective and can react to the dynamic environments promptly.5. For dynamic simple-objective optimization problems, a self-organization scheme is proposed. This approach combines the current information and the historic information of optimal solutions to increase the population diversity. Incorporated by the scheme, a new self-organization univariate marginal distribution algorithm (SOUMDA) is proposed. The experimental study on dynamic sphere function showed that the SOUMDA is effective and can adapt to the dynamic environments rapidly.6. For dynamic multimodal optimization problems, a new Multi-population and Diffusion UMDA (MDUMDA) is presented. The multi-population approach is used to locate multiple local optima for dynamic multimodal problems. The diffusion model is used to guide increasing the diversity, which makes the neighbor individuals of previous optimal solutions move gradually and thus can enlarge the search space. The experimental studies on the multimodal dynamic moving peaks benchmark are made to evaluate the proposed algorithm.7. For dynamic multi-objective optimization problems, a regularity modal-based estimation of distribution algorithm with prediction is proposed. In algorithm design, we use the central points of Pareto optimal set and reference solutions of Pareto optimal set to describe Pareto optimal solutions. So it can be used to storage the history of the Pareto optimal solutions of dynamic multi-objective optimization problems. Then by using the inertia prediction and Gauss mutation the prediction set of central points and reference solutions is generated. After an environment changed, the predict set is incorporated in the current population to guide increasing the population diversity. Finally, the experiments on dynamic multiobjective optimization problems were carried out to evaluate the performance of our proposed algorithm.