改进遗传算法初始种群策略：基于最小生成树的TSP研究

该篇论文主要探讨了遗传算法在解决旅行商问题（Traveling Salesman Problem, TSP）中的初始种群改进方法。作者贾海鹏、郑丽英、何天斌和徐顼来自兰州交通大学电子与信息工程学院，他们注意到遗传算法在实际应用中受限于计算能力和种群规模，因此初始种群的选择对于算法性能至关重要。当前，常见的初始种群构造策略包括均匀取种法和随机取种法，这两种方法虽然简单，但往往导致种群的搜索效率和适应度不高。 均匀取种法将解空间划分为n个等大的子空间，每个子空间等概率选择一个个体作为种群成员。然而，这种方法可能使种群过于随机，缺乏多样性，从而影响算法的全局搜索能力。 论文提出了一种创新的思路，即结合图论中的最小生成树原理来改进初始种群。具体而言，作者考虑了普里姆算法（Prim's Algorithm）和奇偶点图上作业法（Odd-Even Job Scheduling）等理论，通过构建更结构化的种群，期望提高搜索的导向性和收敛速度。这种改进旨在降低种群的随机性，增强种群的适应性，从而提升遗传算法在TSP问题上的寻优效率和结果质量。 由于TSP本身是NP-Hard问题，找到精确的最优解通常不切实际，因此启发式算法，特别是遗传算法，成为了研究热点。尽管已有许多针对编码方式和遗传算子的优化，但论文着重强调了对初始种群优化的必要性和挑战，指出这直接影响了算法的整体性能。 这篇论文提供了一个新的视角，即通过最小生成树理论改进遗传算法的初始种群，以期望在计算资源有限的情况下，提高算法在TSP问题上的解决方案的质量和效率。这对于理解和改进遗传算法在实际应用中的表现具有重要意义。