改进的十进制MIMIC算法：高效解决大规模TSP问题

"本文介绍了一种改进的十进制MIMIC算法，用于解决旅行商问题（TSP），这是在2012年由郝承伟和高慧敏发表的研究成果。该算法针对大规模TSP问题的缺陷进行了优化，提高了算法在处理大问题规模时的性能。" 在传统的MIMIC（模拟并行机学习）算法基础上，作者提出了一种基于十进制编码的变体，以适应旅行商问题的离散特性。TSP是一个经典的组合优化问题，目标是找到访问一系列城市并返回起点的最短路径，每个城市仅访问一次。在处理大规模问题时，原始的MIMIC算法可能会遇到效率和解决方案质量下降的问题。 为了克服这些挑战，研究者对算法进行了多方面的改进。首先，他们调整了编码方式，以更好地适应问题的结构。其次，他们修改了概率模型，这有助于算法更有效地探索搜索空间。在初始种群生成阶段，研究者采用了贪心算法，这是一种有效的局部最优策略，可以快速形成一个初始解集。在算法的进化过程中，引入了杂交算子、变异算子、映射算子和优化算子等演化算子，这些算子能促进种群的多样性，避免早熟收敛。 此外，他们还提出了一种动态调整优势群体规模的方法。这种方法可以根据算法运行时的性能自动调整，以保持种群的多样性，即使在小种群规模下也能应对大规模问题。这种动态调整策略对于维持算法的全局搜索能力和防止过早收敛至关重要。 通过这些改进，实验结果显示，改进后的MIMIC算法在解决更大规模的TSP问题时，不仅提高了解的质量，也加快了寻优速度。这表明该算法具有更好的可扩展性和优化能力，对于处理实际中的复杂TSP实例具有很高的应用价值。 关键词：MIMIC算法，旅行商问题，分布估计算法，概率矩阵。 中国图书馆分类号：TP18 文献标识码：A 这项研究提供了一个高效的解决方案，用以改进MIMIC算法在解决旅行商问题上的性能，特别适用于大规模问题，通过创新的编码策略和动态优化机制，提高了算法的寻优效率和解的精度。