A New Maximum Entropy Estimation of Distribution Algorithm to Solve Uncertain Information Job-shop Scheduling Problem

Published Online October 2009 in MECS

In the field of science, engineering and economy, many of latest the advances rely on computing corresponding optimization problems of the global optimal solution of the numerical technique.

EDA ( Estimation of Distribution Algorithm) is a new algorithm based on the population evolution , it constructs the probability distribution model by statisticing the information of optimal individuals in a present group, then samples the model to produce the next generation, thus, the offspring can be distributed in good space with large probability, which can promote the group’s evolution. Compared with the traditional evolutionary algorithm, crossover and mutation operator is replaced by distribution estimation, what else the new population produced by distribution estimation. EDA makes use of the distribution of random vectors to characterize its internal probability of dependence, therefore how to find an n-dimensional probability model which can fully reflect the interaction between random variables is the key of EDA. Probability distribution model directly determines the performance of EDA. Precise probability distribution model ensures a good outcome, and vice versa. Currently, the more common practice is the application of probability map model (Reference [1] shows that discrete EDA uses bayes network to express the relationship between variables, continuous EDA uses gauss network). However, how to determine the network parameters which in turn determine the optimal network structure is proved to be a NP-Hard problem, and the complicated calculation has greatly reduced the computing performance of EDA and limited the application of EDA. This paper presents a new algorithm named Maximum Entropy Estimation of Distribution Algorithm (MEEDA), this algorithm is based on Jaynes principle, using the random variables’ maximum entropy estimates its minimum bias probability distribution, and as the algorithm’s evolution model, and efficiently reduce the computational complexity of the algorithm. The simulation experiments of the two kinds of problems prove the effectiveness of the proposed algorithm, with higher global search ability and more stable convergence.

Manuscript received Febuary 21, 2009; revised July 13, 2009; accepted July 25, 2009.

II. Maximum entropy estimation of distribution ALGORITHM

A． The principle of EDA

EDA is generated from genetic algorithm (GA). GA performs selection, producing a mating pool; a new population is then produced from the mating pool by crossover and mutation operations. This process is then iterated until a termination criterion is met. Although GA can be applied to many combinatorial optimization problems, yet they all need some prior knowledge to determine the evolution operator, therefore, it is difficult to find an appropriate set of parameters in coding and combined with the operation for a particular problem, which is the inherent defect of GA. Furthermore, in evolutionary terms, the crossover and mutation operator are used to the realization of and the exchange of individual information in group, and select operator is used to the guidance of the evolutionary process, both of them did not consider the relevant information of the same generation individuals, so they did not fully make use of the existing information and reduced the operating efficiency of GA; furthermore, crossover and mutation operator can not guarantee the establishment of building blocks assumptions in theory, as a result, GA demonstrates very poor performance for some of the issues (such as misleading).

To improve these deficiencies, H. Muhlenbein and G. Paa p in reference [2] proposed the estimation of distribution algorithm in 1996, which quickly aroused the concern of extensive research. And it has been a hotspot of evolutionary computation at present. EDA does not use crossover and mutation operator, but uses probability distribution of higher degree individuals in the group as the evolutionary model, and then produces the next generation of subgroups; with the use of tracking advanced method to replace the recombination of the GA modes, and it has expanded the applied space of EDA.

As an evolution model is derived from the statistical probability distribution of information, thus it shows the main characteristics of groups in making the best use of existing information and reflecting more accurately the relationship between variables. The theoretical study in reference [3] shows that in the iterative process, EDA may get interaction information of individuals between group and different bit of individuals, identify and manipulate the model of important blocks, therefore it can effectively solve the optimization problems in which the decision-making variables are interactive.