基于遗传算法的tsp问题研究

目录

基于遗传算法的tsp问题研究 1

一、论文观点来源 1

二、论文基本观点 1

三、论文主要内容结构 1

1、算法设计 1

2、遗传编码 1

3   程序的运行演示 4

4   测试运行 5

4.1   模块测试 5

4.2   整体测试 5

4.3   测试结论 5

四、参考文献 5

基于遗传算法的tsp问题研究

一、论文观点来源

TSP问题又称为货郎担问题。TSP是一个典型的优化组合问题，它需要求出旅行商从某一城市出发经过所有城市所走路程的最短路径，其可能的路径数与城市个数成指数关系增长。找出有效的近似求解算法具有重要的意义。

选择用遗传算法去解决TSP问题。本论文对各个算子分别选择的是基于序的评估函数、轮盘赌选择法、两点交叉法、两点区间随机排序变异法，并且通过30个城市的实际的例子来验证，结果求出最短路径为421.5977，优于二叉树描述法的结果428.90，启发式搜索法的结果436.01，表明遗传算法在求解TSP问题上是有效的。