| In this thesis, an introduction about the development of Estimation of Distribution Algorithm (EDA) was given, including the historical background and theoretical basis of EDA. Then, a literature review of the current progress in EDA and permutation permutation flow-shop scheduling problem(PFSP) was provided. Next, based on the analysis of the problems while using EDA to sovle complex continuous optimization problems, an improved EDA was proposed. Finally, the PFSP was discussed with EDA and a two-stage scheduling algorithm for PFSP was proposed. The main contributions of this work are the following two points.1. Multivariate continious optimization problems usually featured by the complex interdepence between different variates. Now, nested Archimedean copula provides convinent and flexible way to model the joint probability distribution. In order to reduce the complexity and computation cost when using EDA to solve these problems, nested Archimedean copula was employed in EDA. Firstly, a class of partially nested Archimedean copulas was constructed with Lévy subordinators, and the hard-to-check nesting condition is conveniently circumvented. And then, an improved EDA which is based on the nested Archimedean copula constructed with Lévy subordinators was proposed. Finally, the proposed method is implemented and compared with other EDAs that based on copula, the exprimental results demonstrated the effectiveness of the proposed algorithm.2. As to PFSP, a two-stage scheduling algorithm based on EDA was putforward. On the one hand, it fully takes the advantages that global searching capability and high convergence rate of EDA. On the other hand, in the second stage of the algorithm, there is a mechanism of stochastic and re-combination search in the proposed hybride neighbourhood search algorithm, which is a supplement to the weak local search capability of EDA. At last, the simulation results and comparisons based on benchmarks validate the efficiency of the two-stage algorithm. |
PDF Full Text Request