Estimation of Distribution Algorithms for Single- and Multi-Objective Optimization
Bo Gao · 2014
This dissertation reviews the literature on estimation of distribution algorithms (EDAs). It also develops new EDAs for solving both Single-Objective Optimization (SOO) and Multi-Objective Optimization (MOO) problems. The EDA is an outgrowth of the Genetic Algorithm (GA). It replaces the crossover and mutation operations of the GA with learning and sampling from a probability distribution built on selected solutions. The model fitting is typically carried out using maximum likelihood estimation. This thesis focuses on developments of EDAs for SOO and MOO as follows: - Investigating the effectiveness of different statistical models within EDAs, including the multivariate t distribution and mixtures of multivariate t distributions. Solving MOO problems requires optimization algorithms to find a set of solutions. EDAs generate a population of potential solutions to the optimization problem at each step. The solution to an MOO problem is a Pareto-optimal set, rather than a single value, and so EDAs are well-suited to approximating this. The mixture model uses multiple single distribution components to construct more complex distributions. This allows the modelling of multiple important but disconnected regions of the decision space, which can be particularly useful for MOO problems. - Introducing novel mutation operations for EDAs. Two novel mutation operations, the Decomposition and T Distribution-Based Mutation (DMO) and the Annealing Schedule and T Distribution-Based Mutation (ASTMO), are proposed in this thesis. - Implementing and examining the outcomes of using different techniques in single- and multi-objective EDAs, including an archive population, ranking and fitness sharing. - A Novel EDA is developed, namely the Multivariate T Distribution, Archive And Mutation-Based EDA (TAM-EDA), for solving SOO problems. Experiments were conducted for comparing the performance of SOO algorithms, including TAM-EDA, Nelder-Mead Simplex Algorithm, Genetic Algorithm (GA), Univariate Marginal Distribution Algorithm (UMDA) and Estimation of Multivariate Normal Algorithm (EMNA). The SOO problems used in the comparison were: the Black-Box-Optimization-Benchmarking 2009 Test Problems (BBOB2009), Parameter Estimation for Differential Equations, Fourier series curve fitting and a Transistor Modeling Problem.- Two novel EDAs, Multivariate T Distribution and Mutation-Based Multi-objective EDA (TM-MOEDA), and Mixture Of Multivariate T Distributions and Mutation-Based Multi-objective EDA (MTM-MOEDA), are proposed for solving MOO problems. Experiments were conducted for comparing the proposed EDAs with other MOO algorithms, including Multi-objective GA (MOGA), Multi-objective UMDA (MOUMDA), and Multi-objective EMNA (MOEMNA). The MOO problems used in the comparison were: Van Veldhuizen's Test Problems (MOP), Zitzler-Deb-Thiele Test Problems (ZDT), variants on the ZDT problems, Deb-Thiele-Laumanns-Zitzler Test Problems (DTLZ) and the CEC'09 MOEA test problems. The performance of TAM-EDA on the BBOB 2009 competition test problems would have ranked amongst the top 3 algorithms for 10-dimensional problems and the top 5 algorithms for 40-dimensional problems. The proposed algorithms achieved good results on all ZDT and DTLZ test problems.n