Research On Estimation Of Distribution Algorithm And Its Appications In Intelligent Scheduling

Intelligent scheduling is an effective way to complex production scheduling problems, which opens a novel research area of production scheduling. However, the current intelligent scheduling methods are not enough to solve a variety of practical scheduling problems. These facts ask to further expand the research ideas, so as to find new efficient methods.Estimation of distribution algorithms (EDA) is a new class of evolutionary algorithms, which becomes a current focus in the field of intelligent computation. To avoid the destruction of building blocks caused by crossover and mutation, probabilistic model is used to guide the searching process, which improves the performance of EDA. Therefore, EDA can effectively solve many complex optimization problems that traditional evolutionary algorithms haven't solved.Taking the advantages above into account, EDA is introduces to the field of intelligent scheduling in this paper. Some issues related to production scheduling and EDA are also studied. The main research works are as follows:(1)To build the models of discrete production process, a rule description method with time factor is proposed, and an improved rule matching strategy is given. The models of processing units in discrete production are built both by the rule description method and by the Petri net.(2) To overcome the limitations of EDA with no interactions in solving complex functional optimization problems, Q learning-based estimation of distribution algorithm is proposed. Each allele is associated with an agent, which selects updating rules for the corresponding probability value as its actions. Using Q learning technique, agents interact with the population in evolutionary process, so as to adaptively update the probabilistic vector and hence improve the global search ability of the algorithm.(3) According to the characteristics of the job-shop scheduling problem, a kind of adaptive integer encoding estimation of distribution algorithm is proposed. Using the idea of adaptive incremental learning, this algorithm achieves evolutionary search in the integer search space by updating the probability matrix and sampling, which shows a better performance.(4) Immune estimation of distribution algorithm is proposed and its applications in both determinate and fuzzy flow-shop scheduling problem are given. Inspired by the mechanism of artificial immune, the concentration-based selecting form is used in this algorithm, so as to maintain the variety of the population and obtain better results.(5) In order to predict the processing time, a case-based reasoning method is proposed. The historical data are used to build case base, while a clustering algorithm is selected to create indexical structure. Then similar cases are searched in two steps, which are modified to become the predictive values. The experimental results show that the predictive precision of this method is higher than multiple linear regression and neural network.