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