The Research On Estimation Of Distribution Algorithm Based On Copula Theory

Estimation of Distribution Algorithms (EDAs) combine the knowledge of Intelligence Computation and the knowledge of Statistics. EDAs are a kind of algorithm based on population. In each interation, the best individuals of current population are selected according to their fitness, and the distribution model of the selected population is estimated in order to guide the new generation. The EDAs for multivariate interaction are the hot topic of current research aera. The Bayesian network, the Gaussian network and the Markov network are used to reflect the interrelation of variables. But the study of these networks occupies many time. So, most of the time of current EDAs is consumed in estimating the distribution model. Some other algorithms suppose the distribution model of selected population is joint Gaussian distribution and estimate the eigenvalues and covariance matrix of joint Gaussian distribution. But the joint Gaussian distribution can not reflect precisely the interrelation of the optimized variables because of the characters of the Gaussian distribution such as symmetry, besides the correlative coefficient based on covariance refelects only the linear interaction of variables. So, the EDAs based on joint Gaussian distribution do not perform well.In the copula theory of statistics, the multivariate joint distribution can be diviede into two parts: one is the univariate margins of each variable, the other is a function called copula reflecting the interrelation structure of variables and neglecting the margins of variables. Copula reflects not only the linear relationship of variables but also the golobal interaction of variables. Scholars conclude and study deeply many classical copulas through the analysis of many realistic data.A new framework of EDAs based on copula theory (copula EDAs) is proposed and studied in this paper. The estimation of margins and the estimation of copula are performed independently in copula EDA. Actually, these two operators can be performed parallelly, and they are simpler and more time-economic than estimation of the complex network. The following topics are studied in this paper:(1) The framework and the process of the copula EDA are deduced from the analysis of EDAs and copula theory,and the global convergence of the copula EDAs are proved. The model estimation is divided into two parts: estimate the margins; estimate the copula. In general, one way to estimate the copula is to select a copula with parameter and then to estimate the parameter according to the selected population; the other way is to construct a copula according to the selected population, such as empirical copula. The model sampling is mainly the sampling from copula. A vector in the unit supercube is sampled from the copula and the point in the search space is calculated by it and the inverse functions of the margins. This point is one individual of the new generation.(2) In the guidance of framework of copula EDA, a two-dimensional Gaussian copula and two two-dimensional Archimedean copulas are used to refelect the relationship of optimized variables, and three copula EDAs are implemented for the two-dimensional optimization problem in continuous area. The experimental results show the feasiability and efficiency of the copula EDA.(3) We propose an empirical copula EDA for multi-variate numberic optimization problem. In this algorithm, the unit supercube is divided into some little supercubes and the number of individuals in each little supercube is counted. The empirical copula is constructed according to these numbers. The margins can be any kind of distribution. The Gaussian distribution and the empirical distribution are demonstrated in this paper. In this algorithm, the empirical copula is not explicitly expressed. The sampling way from empirical copula is deduced according to its construction way. So, the sampling operator is implemented directly according to the counted numbers. The experimental results show that empirical copula EDA optimizes efficiently the multi-variate numberic problems, and the global exploitation ability of empirical copula EDA is strong.(4) The Archimedean copula EDA is also proposed for multi-variate numberic problems. The relationship of variables in selected population is refelected by Archimedean copulas. Three algorithms (Clayton copula EDA, Gumbel copula EDA and Frank copula EDA) are discussed. They are compared with some classical EDAs within the same fitness evaluation.(5) The affect of parameter of copula and the affect of sampling way are discussed. Two ways to estimate the parameter of Archimedean copula (i.e. PMLE and Kendall?) are introduced into Archimedean copula EDA. Four situations are devised to test the influence of parameter estimation to the performance of the algorithms. The experiments show the Archimedean copula EDA with parameter estimation perform better than the classical EDAs both in convergence speed and in convergence precision. Besides, the“Kendall?”way is more efficient than the“PMLE”way. The copula can be considered as a random variable, so the density function that the copula obeys can be estimated and sample from it. This sampling method is used in Archimedean copula EDA, and the results show the method is more precise and effective.(6) The application of copula EDA in image vector quantization is studied in this paper. The training vectors are distributed into different subpopulations according to the code. The simulation experiment results on some benchmark images show that the copula EDA is super than LBG and other algorithms.