论文部分内容阅读
巡回旅行商问题（TSP）是一个组合优化方面的问题，已经成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法不但可以求解TSP问题，而且还可以求出该问题的最优解。但是对现有的计算机来说，使用常规穷举法在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求解TSP问题的优化算法应运而生，适用于TSP巡回旅行商路径优化的算法有很多，例如模拟退火算法、人工鱼群算法、神经网络算法、遗传算法等。 本课题主要围绕TSP问题的路径寻优问题展开研究，通过分析遗传算法的利弊，得知并行遗传算法（Parallel Genetic Algorithm）是一种有效解决带有约束条件的TSP巡回旅行商问题的算法。针对并行遗传算法解决本课题问题的缺陷，提出一种基于评价算子的TriBA并行遗传算法。基于评价算子的TriBA并行遗传算法主要在并行算法上做了三方面改进： 改变了拓扑结构。通过新的种群分配方式，有效地解决了主从式结构的负载不均衡问题。TriBA结构是可扩展的，可以根据种群大小，确定子种群的数目，有效地节约了硬件资源。 改变了数据迁徙方式。TriBA结构中数据的迁徙方式包括全局迁徙方式，快速迁徙方式，局部迁徙方式和混合迁徙方式四种方式。改变了主从式拓扑结构单一的数据迁徙方式，有助于最优个体迅速传播到每个子种群中。 提出了一种基于评价算子的迁徙操作。通过评价算子，可以反映当前种群的局部收敛程度，当局部收敛度满足设定的评价算子时，再进行迁徙操作。实现了子种群最优个体的异步迁徙，提高了遗传算法迁徙的效率，提高了算法的寻优效率。 最后使用基于改进迁徙操作的TriBA并行遗传算法求解城市规模是20?20的TSP问题，进行适应度函数计算，交叉、变异操作和迁徙操作，可以成功地寻找到TSP问题的最优路径。通过对实验数据的分析，对于相同的城市 TSP问题，基于TriBA结构的并行遗传算法模型相对于主从式并行遗传算法模型进化的效率明显提高，有较好的并行算法加速比。