用简单遗传算法求解TSP问题的参数组合研究

The analysis about parameters in solving TSP with genetic algorithms

首先介绍用遗传算法求解CTSP问题的实验方法 ,描述了实验中群体规模、联赛规模参数对TSP问题计算时间复杂性及求解质量的影响 .根据实验数据总结出两条规律 :(1)对N =34的TSP问题 ,群体规模在 30 0 0与 4 0 0 0之间 ,易获得最优解 ;(2 )联赛规模在群体规模的 2‰附近时 ,易获得最优解 .通过对不同规模 (15～ 34)TSP问题的试验 ,发现两条规律对TSP问题求解具有普遍有效性 .从理论上分析了群体规模和联赛规模对TSP问题求解质量和时间复杂性的影响 ,通过时间复杂性分析 。

This paper firstly illustrated the experiment methods and results in GeneticTSP. In order to find a good parameter combination, researchers have tried a great number of combinations, and explosed two rules about parameters combination, which are that good solution is easily available both in the case when population size is between 3 000 and 4 000, and the league matches size is about 2‰. It then analyes the time complexity about the league matches size in theory. Finally, it carries out several experiments to verify these rules, which show the efficiency of our approach in solving different scale TSP.