文档介绍：中央广播电视大学开放教育
计算机专业毕业论文
基于遗传算法的tsp问题研究
姓名: 王霞
学校: 河南广播电视大学
学号: 1541001211388
指导教师: 李老师
定稿日期: 2016年12月5日
摘要
TSP问题又称为货郎担问题。TSP是一个典型的优化组合问题,它需要求出旅行商从某一城市出发经过所有城市所走路程的最短路径,其可能的路径数与城市个数成指数关系增长。找出有效的近似求解算法具有重要的意义。
选择用遗传算法去解决TSP问题。本论文对各个算子分别选择的是基于序的评估函数、***赌选择法、两点交叉法、两点区间随机排序变异法,并且通过30个城市的实际的例子来验证,,,,表明遗传算法在求解TSP问题上是有效的。
关键词:组合优化;TSP问题;遗传算法;最短路径
Abstract
TSP problem is also known as the traveling salesman problem. TSP is a typical portfolio optimization problem and needs to calculate the shortest path that a traveling salesman goes through all cities. The number of the possible paths may grow with index of the number of cities. It is of great significance to find out an effective approximate algorithm.
It is used ic algorithms to solve the TSP problem. In this paper, the operators are fitness function based on sequence choice, selection with the law of roulette gambling, two- point crossover, two- point random interval mutation. An actual example through 30 cities is got. The result is of the shortest path, which is better than binary tree description with the result of , heuristic search with the result of , and shows that the ic algorithm for TSP is effective.
Key words: Combinatorial Optimization ; TSP ; ic Algorithm ; the Shortest Path
目录
目录 4
绪论 5
1 遗传算法的设计思想 8
2 系统实现 9
3 程序的运行演示 12
4 测试运行 13
模块测试 13
整体测试 13
在测试过程中使用到的调试技术: 13
评估运行的可靠性问题: 13
测试结论 14
结论 15
参考文献 16
绪论
一、遗传算法概述和发展背景
(1)遗传算法简介
遗传算法(ic Algorithm,简称GA)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,,并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》,GA这个名称才逐渐为人所知,(SGA)。遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组