Research On The Hybrid Algorithm Based On DE And EDA For Solving Combinatorial Optimization Problems

Differential evolution algorithm(DE) and estimation of distribution algorithm(EDA) are two optimization techniques proposed recently in the field of evolutionary computation. Although they both demonstrate the advantages in continuous optimization problems, the researches about applying DE or EDA to solve combinatorial optimization are still lacking. Thus, the applications of these two algorithms in combinatorial optimization problems have been studied in this dissertation, and two new hybrid algorithms have been proposed. Also, some practical problems, such as traveling salesman problem(TSP) and scheduling optimization problem, are used to verify the effect of those algorithms.First, considering the characteristic of the DE's framework, a new permutation-based discrete differential evolution algorithm(pDDE) has been proposed. The definition of distance between two permutations is introduced, and new addition, subtraction and multiplication operators are quite literally defined, respectively. Based-on those new definitions, a novel modified mutation operation has been presented. Meanwhile, a permutation-based crossover operation has been adopted, and a local search algorithm involved with 2-opt operator is embedded into pDDE. The experiment results show that the proposed pDDE can find the highquality solution fast, and its performance is better than those classical algorithms, such as GA, ACO and PSO, etc.Moreover, for the permutation flowshop scheduling problem(PFSP), a hybrid algorithm called compact discrete differential evolution(cDDE) is proposed, which combines DE with EDA. In cDDE, the probability distribution is introduced and used to replace the whole population, and the sampling and update methods are designed properly. In the mutation operation of cDDE, two individuals are sampled, and then applied to generate a new individual with the best one through a new perturbation method, named destruction and construction. Also, in order to overcome the premature convergence, the Metropolis rule and an insert-based local search algorithm are introduced. Comparisons between cDDE and DE, or cDDE and EDA indicate that cDDE is an effective and sophisticated algorithm, and can solve the PFSP efficiently.Then, with the above researches, the distributed permutation flowshop scheduling problem(DPFSP) is studied. An encoding and decoding method is adopted, and some modifications of cDDE have been made, then a problem-specific well-designed local search is introduced. Thus, a new hybrid algorithm, called EDA/DDE, is proposed to solve DPFSP. The experiment results show that EDA/DDE can improve the local search ability of EDA, and thus be used to solve more complex problems.At last, the thesis is summarized, and the future research is prospected.