摘要
TSP是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目n是成指数型增长的,所以一般很难精确地求出其最优解,因而寻找出有效的近似求解算法就具有重要的意义。现就提出的一种求解TSP问题比较有效的改进的遗传算法进行了研究,从遗传算子、评估函数、种群多样性等方面对算法进行了分析,并对实例CHN144进行了测试,实验结果表明文中提出的算法在求解TSP问题上是有效的。
TSP is a typical combination optimization problem, which is also a NP hard problem. Its size is increased by exponential n. So, it is hard to find a precision result, and it is very important to search for the near result. This paper proposed an effective method based on improved genetic algorithm, analyzed the algorithm operators, evaluation function, population diversity. The experiment result about CHN144 has proved that this algorithm is effective to search TSP optimization result.
出处
《信息技术》
2006年第7期110-112,共3页
Information Technology
关键词
组合优化
NP难
旅行商问题
遗传算子
combination optimization
NP hard problem
TSP
genetic operator
