Estimation Of Distribution Algorithms For Mutivariable Coupled Problem In Continous Domain

Estimation of distribution algorithm in continuous domain is generally basedon the assumption that variables obey Gaussian distribution. The establishmentof stochastic model and the sampling process are simpli?ed by parameterizing theprocess of distribution estimation. However, this assumption can not be applied toevery case, so it is usually abandoned by general approaches. In addition, most ofthe existing algorithms in continuous domain use a single-peaked probability model.For some complex optimization problems, the single-peaked probability model cannot describe the distribution e?ectively.In this thesis, for the multivariable coupled optimization problem in continuousdomain, the empirical distribution function, the sequential importance samplingparticle ?lters and the Cholesky decomposition are applied to the study on theestimation of probability distribution and the sampling methods. The theoreticalanalysis of algorithms has carried on, and the algorithm is applied to the calculationand the consistency check of AHP judgement matrix. Main works of this thesis areas follows:(1) Estimation of distribution algorithm based on empirical distribution func-tion. The probability model is constructed using the empirical distribution functionand the assumption that the variables obey any one particular distribution is notrequired. The inverse transform method is adopted to calculate the range of eachitem in the sample vector which is regarded as the correlated constraints of variables.Experimental results show the feasibility and e?ectiveness of this algorithm.(2) The features of the sequential importance sampling particle ?lters are an-alyzed and the feasibility of applying it to construct the probability model of es-timation distribution algorithms is presented. Then, an estimation of distributionalgorithm based on sequential importance sampling particle ?lters is proposed. Inalgorithm, the probability distribution that the optimized set obeys is representedby the weighted particles, and the population of next generation is sampled fromthis probability distribution. The samples are not required to obey Gaussian distri-bution, and the probability model is multipeaked. For the multipeaked probabilitydistribution represented by weighted particles, we use the roulette gambling method to choose a particle ?rst and then sample in the neighborhood of this particle to geta sample of this distribution. According to whether the correlation among variablesis accounted in neighborhood sampling, there are two sampling methods: 1) select-ing a particle using roulette gambling method then constructing a one-dimensionalnormal distribution in the neighborhood of selected particle and sampling from it; 2)selecting a particle using roulette gambling method then using the Cholesky decom-position method to decompose the covariance matrix and sampling neighborhoodaccordingly. The correlation among the variables is considered explicitly in thecovariance matrix of optimized set when the latter method is adopted.The initial value of the control parameterλof algorithm and its changing curvesare studied. According to the change curves ofλ, the global optimization and thelocal search performance of algorithm can be controlled ?exibly. The method thatcontrols the balance between the global optimization and the local search perfor-mance during the evolutionary process can be apply to other evolutionary optimiza-tion algorithms.Experimental results show that the algorithm can solve the multivariable cou-pling optimization problem in continuous domain e?ectively.(3) According to the convergence analysis of the estimation of distribution al-gorithm based on sequential importance sampling particle ?lters, we got the conclu-sion: the algorithm will converge to the global optimum in case of in?nite populationand at least it can converge to the neighborhood of a local optimum for a limitedpopulation.The time complexity of evolutionary algorithms should be considered from twoaspects: the expected ?rst hitting time and the time of an iteration of the evolution.These two indicators can be used to characterize the time complexity of algorithm.The method used to estimate the expected ?rst hitting time of estimation distri-bution algorithms is given, and then the expected ?rst hitting time of the estimationof distribution algorithm based on sequential importance sampling particle ?lters isanalyzed. The time complexity of an iteration of the evolution is analyzed. Com-bining these two indicators, a description of the time complexity can be made.(4) Application of estimation of distribution algorithms to the calculationand the consistency check of AHP judgement matrix. An algorithm is present to calculate the weight and to check the consistency of judgement matrix. Ex-perimental results showthat the algorithmis of high precision and excellent stability.