Research On Hybrid Differential Evolution-Estimation Of Distribution Algorithm And Its Application In Shop Scheduling

With the development of Computer Integrated Manufacturing System (CIMS), the intelligent shop scheduling has become an important way to improve the enterprise productivity. Shop scheduling problems is a class of NP-hard combinatorial optimization problems. With the expansion of the workshop, the complexity of problems will increase. Compared to deterministic algorithms and heuristic algorithms, intelligent optimization algorithms (IOA) are widely used in shop scheduling due to their high searching efficiency, strong robustness and strong portability in recent years. Estimation of distribution algorithm (EDA) is a kind of optimization algorithm based on statistical theory which can describe the relationship between each variable with its probabilistic model, so it has good global searching ability. Differential evolution (DE) algorithm is a stochastic heuristic optimization algorithm which exchanges the direction and distance information between individuals to generate offspring. Hybrid algorithms can take advantage of different searching features, so they have better optimization performance. Therefore, the researches of this paper include a hybrid differential evolution and estimation of distribution algorithm and its application in shop scheduling, the main content include:(1) Based on the characteristics of DE and EDA, a factor of the excellent population based on adaptive incremental learning is introduced to improve the searching mechanism of DE and EDA, and then a hybrid DE-EDA based on adaptive incremental learning (AILHDE-EDA) is proposed in this paper, which combines the two searching mechanisms and accelerates the convergence speed. Meantime, the Markov chain is used to prove the global convergence of this algorithm and computational simulations and comparisons demonstrate the effectiveness of the proposed AILHDE-EDA.(2) The rule of LOV (Larger-Order-Value) which can convert the continuous values to job sequence is introduced to AILHDE-EDA to solve the permutation flow shop scheduling problem (PFSP), meanwhile a local search algorithm is designed to enhance local exploitation ability. The rule of SOV (Small-Order-Value) is used to solve the job shop scheduling problem (JSP). Moreover, computational simulations with benchmark shop scheduling problems demonstrate the effectiveness of the proposed AILHDE-EDA in solving shop scheduling problems.(3) On account of the shortcomings of IOAs solving combinatorial optimization problems and the characteristic of DE and EDA, a hybrid discrete differential evolution and estimation of distribution algorithm (HDDE-EDA) is presented for the PFSP. The probability model may not be applied to sample as EDAs, but a guided agent is produced to guide the crossover and mutation of DE to generate the offspring. Meanwhile, a variety of mutation and crossover operator are developed to merge into the algorithm to balance global exploration and local exploitation. The variable neighborhood search (VNS) is utilized to further improve the search ability. Computational simulations and comparisons with some existing algorithms demonstrate the superiority of the proposed HDDE-EDA in solving the PFSP.