求解TSP问题的一种改进的十进制MIMIC算法

摘要

Modified decimal MIMIC algorithm is a kind of discrete estimation of distribution algorithm, which is based on binary MIMIC algorithm and convenient to solve traveling salesman problem. Considering the drawbacks of the MIMIC algorithm while solving larger-scale TSP, this paper improved the encoding mode and probability model, proposed new individual strategy, introduced greedy algorithm at the initial phase of the probability matrix, and adopted crossover operator,mutation operator,etc. during the process of evolution, employed dynamic adjusted method to determine the population size. These modifications gurantee the population diversity even in small population and for larger-scale TSP. Experiment results show that problem scale, solution quality and speed of the optimization are improved significantly.%十进制MIMIC算法是基于MIMIC二进制编码算法思想的可用来求解TSP的离散分布估计算法.着重考虑该算法在较大规模TSP问题上的算法缺陷,对其编码方式和概率模型进行了改进,提出了新的个体生成策略,在初始化种群阶段使用了贪心算法,在进化过程中引入了杂交算子、变异算子、映射算子、优化算子等演化算子,采用了动态调整方法来确定优势群体的规模.以上改进使得算法在小种群解大规模TSP问题的情况下仍可保持种群的多样性.实验结果表明,改进算法在求解规模、求解质量和寻优速度上都有明显提高.