A Decimal Mimic Algorithm Improvement And Application

In this thesis, an introduction about the development of Estimation ofDistribution Algorithm (EDA) is given, including the historical background,theoretical basis of EDA and decimal Mutual Information Maximization forInput Clustering (MIMIC) algorithm. A literature review of the current progressin the Traveling Salesman Problem (TSP) and Permutation Flow-shopScheduling Problem (PFSP) is provided. Based on the analysis of theadvantages and disadvantages while using decimal MIMIC algorithm to solveTSP, the encoding model and probability model of the decimal MIMICalgorithm are improved, new individual strategy is proposed, some evolutionoperators are introduced. With these modifications, a new improved decimalMIMIC algorithm is proposed. We compare the performance of our algorithmwith the original decimal MIMIC algorithm for TSP, and try to implement thevalidity tests for the ATSP and the PFSP problem.The main contributions of this work are as follows:1, Propose a new improved algorithm based on the decimal MIMICalgorithm. The decimal MIMIC algorithm is a kind of discrete estimation ofdistribution algorithms and can be used to solve TSP. In order to overcome thedefects of the original algorithm for larger-scale TSP, the encoding model andprobability model are improved, new individual strategy is proposed, andcrossover operator, mutation operator, etc. are adopted during the process ofevolution. These modifications can guarantee the population diversity even insmall population for larger-scale TSP. Experiment results show that comparedwith the original decimal MIMIC algorithm, the performance of our algorithmhas improved significantly.2, In order to solve ATSP and PFSP with the improved decimal MIMICalgorithm, non-symmetric matrix is used as new probabilistic model to replacethe symmetric matrix for TSP. The modified algorithm has some features; on theone hand, it has the advantages of EDA algorithm, powerful global searchability. On the other hand, the evolution operator in the algorithm reduces the demand of the population size. Experiment results show that the modifieddecimal MIMIC algorithm is effective and stable for ATSP and PFSP.