摘要
根据TSP问题的特征信息并借鉴邻域搜索算法的有关思想,提出了一种基于近邻策略的TSP问题求解算法,该算法首先依据TSP问题的特殊性求出相应的近邻模式,再将近邻模式用于初始种群的生成,而后在进化过程中随机引入这类模式。该算法可以大大缩短遗传进程,提高进化效率。通过仿真实验,验证了该算法的有效性,并且随着城市数目的增加其优越性更为明显。
According to the specific properties of TSP and the spirit of neighborhood search,the paper presents a new genetic algorithm based on the nearest neighbor strategy to solve TSP.First,calculate the nearest neighbor schemas according to the TSP and use the schemas to generate the initial population.Then introduce one of the schemas randomly into every generation. Simulation tests show that the new algorithm increases the convergence speed heavily and has better effect on the process of GAs.As the city number increases,its superiority appears more obviously.
出处
《计算机工程与应用》
CSCD
北大核心
2009年第28期67-68,71,共3页
Computer Engineering and Applications
关键词
近邻策略
遗传算法
旅行商问题
nearest neighbor strategy
Genetic Algorithm（GA）
Travelling Salesman Problem（TSP）
