Estimation Of Distribution Algorithm And It's Application In Scheduling Problems Solving

Estimation of distribution algorithms is a class of novel evolutionary algorithm based on the probability models in the field of evolutionary computation which combines with intelligence computing theory and the knowledge of statistical studies. According to the information of some better individuals in the current population, the model of probability is built to describe the distribution of all the solutions. Then a new population can be obtained by sampling from this model of probability. This process improves the solution iteratively. The algorithm relies on the construction and maintenance of a probability model that characterizes the correlation between variables involved. So the building block is mixed and recombined effectively. It is shown a good performance on such problems that traditional GA is difficult to solve, especially on nonlinear and high-dimensional complex ones. The key of EDAs for solving problems is to construct a probability model which can characterize the promising solution accurately. However, it is very difficult to construct a proper model because the model can't reflect the problem's essential properties if its structure is too simple while the complexity of algorithm will be increased rapidly if the structure is too complex. Especially, for combinatorial optimization problems, which have strong correlation among variables of the feasible solution because of the complexity of the problem itself. So it is a bottleneck problem to build an accurate probability distribution model to represent distribution of the feasible solutions of the problem when using the estimation of distribution algorithm to solve the complex combinatorial optimization problems.In this paper, the ideas such as superior pattern connection,Bayesian Statistical Inference and Discrete Quasi-Copula theory, are introduced. The ability of solving the complex combinatorial optimization problem is improved by improving the way of building the probability model. Synchronously, the algorithm is used to solve the production scheduling problem and traveling salesman problem. The main achievement is as follows:1. Based on the scheme theorem and the hypothesis of building blocks of genetic algorithm, the similar characteristics of some individuals are considered and explored together. The idea of superior pattern connection is proposed. Information of the similarities of individuals in superior population is considered when solving problems. Based on information of probability, multi-neighboring variables are connected into a whole block when their frequency appearing in superior population is higher. In addition, it is taken as the connection block of superior pattern and it appears as a whole part in iterative process. This enhances the probability of those patterns appearing in the next generation whose fitness values are higher than the average fitness value of population. At the same time, the probability of those schemes with lower fitness values than the average fitness of population in the next generation are decreased. This algorithm can effectively avoid the problem of building blocks destroyed and has better performances of chain learning. Besides, local adjustment to the variables within each sub-block is introduced under some conditions to avoid trapping in the local optimal, which can improve the the performance of algorithm effectively.2. The estimation of distribution algorithm based on the superior pattern connection is used to solve job shop scheduling problem, flexible job shop scheduling problem and traveling salesman problem. For job shop scheduling problem and flexible job shop scheduling problem, the probability model is constructed using frequency information of pair-wise operations neighboring in superior population. These multi-neighboring operations are connected into a whole block based on information of probability. For the frequency appearing in superior population is higher, it makes the model of probability constructed well to reflect the characteristic of sequence of operations. For the traveling salesman problem, frequency information of pair-wise cities neighboring in superior population is used to build the probability model. These multi-neighboring cities are connected into a whole block according to the size of probability. So the model of probability constructed can well represent the structure of individual. The simulation results show that the proposed algorithm has a better performance for solving the problems mentioned above.3. The theory of Bayesian statistical inference is different from the Bayesian network optimization method. It does not require the process of optimization for the complex network structure when solving the problems while the information of samples provided is directly used to construct the probability distribution. The samples are inferred through the establishment of a posterior distribution. Based on Bayesian statistical inference theory, a new estimation of distribution algorithm for discrete optimization problems is proposed by using the information of individuals in superior population. At first, according to each position of individual's structure, the model of priori distribution probability is built by extracting the information of superior solutions updating. Then the model of conditional probability is also built by computing the vector of conditional probability on each position of individual and using the frequencies of neighboring variables appearing in superior population. After that, the model of posterior probability is given by combining the above two models with Bayesian formula. This model combines with information of priori distribution and conditional distribution. It has good results of statistical inference, and is used to guide new populations generation. The evolutionary process is achieved by updating iterately the model of posterior probability.4. The estimation of distribution algorithm based on Bayesian statistical inference theory is used to solve job shop scheduling problem, flexible job shop scheduling problem and traveling salesman problem. According to the characteristics of job shop scheduling problem and flexible job shop scheduling problem, the model of priori distribution probability is built for each position of operations sequence. Making the best use of information of the sequence of operations on each machine, the posterior probability model that can well reflect the characteristics of problems is constructed by using Bayesian formula. The next population is generated by sampling from this model of posterior probability. For the traveling salesman problem, information of permutation between cities is used to build the models of priori probability and posterior probability. The model of posterior probability is constructed by Bayesian formula and the next population is generated by sampling from this model. The simulation results for typical instances show that the proposed algorithm has the preferable search ability and robustness and the model of probability constructed has better stability.5. Based on discrete quasi-copula theory, an estimation of distribution algorithm based on the empirical copula function is proposed to solve discrete optimization problems.The individual is encoded with integer. The empirical distribution function is used to solve the marginal distribution function of each variable. When estimating the empirical copula function, firstly, the individuals of superior population are mapped into the interval (0,1). Then, the unit hypercube is equally partitioned into some sub-hypercubes and a multi-dimensional empirical copula function is constructed by counting the number of individuals in each sub-hypercube. A probability model of multivariate correlation for discrete variables is obtained and the next population is generated by sampling from the model. Because the proposed algorithm considers the multivariate correlation during constructing the model of probability, the probability models can well reflect the characteristics of problems'structure. Moreover, the time complexity of algorithm is analyzed.6. The estimation of distribution algorithm based on empirical copula is used to solve traveling salesman problem and flexible job shop scheduling problem. A model of multivariate correlation for these two problems is constructed by estimating the empirical copula and sampling from them. The simulation results show that the proposed algorithm has a better search ability.