摘要
TSP是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目n是成指数型增长的,所以一般很难精确地求出其最优解,因而寻找出有效的近似求解算法就具有重要的意义。现提出一种求解TSP问题比较有效的遗传算法,从其数学模型、遗传算子、评估函数、种群多样性等方面对算法进行了分析,结果表明提出的算法在求解TSP问题上是有效的。
TSP is a typical combination optimization problem,which is also a NP hard-problem. It's 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 mathematical model,algorithm operators,evaluation function,and population diversity. The experiment result has proved that this algorithm is effective to search TSP optimization result.
出处
《安阳工学院学报》
2007年第4期57-60,共4页
Journal of Anyang Institute of Technology
关键词
组合优化
NP难
TSP
遗传算法
最短路径
combination optimization
NP hard problem
TSP
Genetic algorithm
shortest path
