The Research On Estimation Of Distribution Algorithm Based On Hierarchy Copula

Estimation of Distribution Algorithms (EDA) are stochastic optimization techniques that explore the space of potential solutions by building and sampling explicit probabilistic models of promising candidate solutions. The important step that differentiates EDA from Genetic algorithms(GA) is the construction and sampling of the model that attempts to capture the probability distribution of the promising solutions, without crossover and mutation. At present, the multivariate interaction has been a hotspot of research in EDA. The Bayesian network, the Gaussian network and the Markov network are used to reflect the interrelation of variables, Some other algorithms suppose the distribution model of selected population is joint Gaussian distribution, but the joint Gaussian distribution can not reflect precisely the interrelation of the optimized variables.The copula theory indicates the use of copula is a way to deal with multivariate distributions, the multivariate joint distribution can be divided into two parts:the first one starts by modeling each marginal distribution, and the second one consists of estimating a copula which summarizes all the dependence structure. Therefore, this dissertation can study the marginal distribution and dependence structure seperately. By using lower-dimensional copulas as building blocks, EDA based on hierarchical copula theory can construct flexible probabilistic model, and overcome the limitations of multivariate normal distribution.In order to solve high-dimensional optimal problems, this dissertation studied the copula selection problem, EDA based on different hierarchical copula structure (including nested copula, C-vine and D-vine based on pair-copula) and high-dimensional model reducing problem in V-EDA based on copula entropy. At last, the application of switched copula-EDA in coverage problem of wireless sensor network is conducted. The main efforts in this dissertation are as follows:1. EDA based on two different copula selection methods. With the extension of copula’s application to EDA, the need for a simple and reliable method to choose the right copula emerged rapidly. In order to solve the copula selection problem, an innovative method, called switched copula selection method is introduced, which is inspired by the mixed copula selection method, and being applied to Copula-EDA, called Switched Copula-EDA. The new method can ignore how to determine a fixed copula beforehand, whereas it organizes different kinds of copulas through a copula selection pool, and copula is randomly chosen from the copula selection pool according to the corresponding probability. An adaptive adjustment strategy of the corresponding probability is proposed in the thesis, which can be evolved adaptively in line with the performance of copula function. The experiments illustrate that the time consuming of Mixed copula-EDA dramatically increase, while the so-called Switched copula-EDA is almost the similar as the fixed method, but the performance is much better.2. Nested Archimedean copula-EDA. This dissertation introduce a new paradigm, called Nested Archimedean copula-EDA, which integrates EDA with nested Archimedean copulas, and indicates an innovative way to solve the multivariate and multiple dependences optimization problem. Based on the sampling method of the exchangeable Archimedean copula and d-dimensional nested Archimedean copula, the sampling step of three-dimensional nested Archimedean copula is discussed in detail. Then the framework of Nested Archimedean copula-EDA is described, and the procedure of three-dimensional Gumbel copula-EDA is put forward. The experiment results indicate the convergence rate of almost all functions is more than80%, the convergence generation is reasonable as well, which validate the feasibility and efficiency of our algorithm.3. V-EDA. Multivariate distributions can be decomposed into the appropriate pair-copula times a conditional marginal density, this method provide a powerful and flexible tool to deal with complex dependences. The class of vines embraces a large number of possible pair-copula decompositions. This dissertation concentrates on two special cases of regular vines; the canonical vine(C-vine) and the D-vine. Each model gives a specific way of decomposing the density. In this dissertation, by discussing the construction graph, hierarchy graph and the density function of C-vines and D-vines, a new algorithm is proposed, called Estimation Distribution Algorithms based on Vine(V-EDA). The architecture of V-EDA is provided, the sampling method and parameter estimation method of the probability model is discussed, the simulation results based on two different vines, namely C-vine and D-vine, show that the proposed algorithm is not only feasible to high dimensional optimization problem, but also perform well in global exploitation.4. Multi-dimensional V-EDA based on copula entropy. In order to reduce the considerably computation burden, the vine model should be simplified. Based on the concepts of information theory and copula entropy, some relationship among copula entropy, mutual information and Kullback-Leibler Divergence are introduced. By minimizing the information lost, the criterion of truncated simplification of C-vine and D-vine are listed. In light of the truncation methodology, the truncated C-vine and D-vine models are studied. Experimental results show the potential application ability of the algorithm.5. Applying Copula-EDA to the coverage problem in wireless sensor network. The optimal model is developed for the coverage problem of wireless sensor network. By considering the continous variable which belong to interval [0,1], as the chosen probability of corresponding sensor node, the discrete optimization model of coverage problem in wireless sensor network is solved. A large number of simulation experiments are carried on in the circumstances of different deployment of wireless sensor network nodes, different perceptual model, and experimental results has validated the algorithm.