摘要
TSP问题是一个典型的组合优化问题,并且也是一个NP难题,其可能的路径总数与城市数目n成指数型增长,一般很难精确地求出其最优解。这里对TSP问题提出了一种改进的遗传算法,通过对遗传算法的评估函数、交叉和变异方法以及参数选择等方面的分析和修改,构造了一种自适应函数以及交叉、变异方法。通过对CHN144的测试,实验结果证明此处提出的方法能更有效的求解TSP问题。
TSP is a typical combination optimization issue, which is also a NP-Hard Problem. The length of paths is exponentially increased according to the amount of the cities-n. It is hard to find an accurate result. This paper gives an improved genetic algorithm on the TSP problem. It analyzes the evaluation function, the method of crossover and mutation, the selection of parameter and so on. Then, construct a kind of self-adapt function and method of crossover and mutation. Based on the experiment of CHN144, the result has proved that this algorithm is more effective to search TSP optimization result.
出处
《电脑与信息技术》
2009年第4期32-35,共4页
Computer and Information Technology
