计算机科学与技术基于遗传算法的tsp问题研究学位论文.doc

《计算机科学与技术基于遗传算法的tsp问题研究学位论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业论文题目基于遗传算法的tsp问题研究学院计算机与科学技术专业计算机科学与技术学号200213137193学生姓名张三指导教师李四日期二·〇〇八年六月摘要TSP问题又称为货郎担问题。TSP是一个典型的优化组合问题，它需要求出旅行商从某一城市出发经过所有城市所走路程的最短路径，其可能的路径数与城市个数成指数关系增长。找出有效的近似求解算法具有重要的意义。选择用遗传算法去解决TSP问题。本论文对各个算子分别选择的是基于序的评估函数、轮盘赌选择法、两点交叉法、两点区间随机排序变异法，并且通过30个城市的实际的

2、例子来验证，结果求出最短路径为421.5977，优于二叉树描述法的结果428.90，启发式搜索法的结果436.01，表明遗传算法在求解TSP问题上是有效的。关键词：组合优化；TSP问题；遗传算法；最短路径AbstractTSPproblemisalsoknownasthetravelingsalesmanproblem.TSPisatypicalportfoliooptimizationproblemandneedstocalculatetheshortestpaththatatravelingsales

3、mangoesthroughallcities.Thenumberofthepossiblepathsmaygrowwithindexofthenumberofcities.Itisofgreatsignificancetofindoutaneffectiveapproximatealgorithm.ItisusedgeneticalgorithmstosolvetheTSPproblem.Inthispaper,theoperatorsarefitnessfunctionbasedonsequencec

4、hoice,selectionwiththelawofroulettegambling,two-pointcrossover,two-pointrandomintervalmutation.Anactualexamplethrough30citiesisgot.Theresultis421.5977oftheshortestpath,whichisbetterthanbinarytreedescriptionwiththeresultof428.90,heuristicsearchwiththeresul

5、tof436.01,andshowsthatthegeneticalgorithmforTSPiseffective.Keywords:CombinatorialOptimization;TSP;GeneticAlgorithm;theShortestPath目录目录4绪论51遗传算法的设计思想82系统实现93程序的运行演示124测试运行134.1模块测试134.2整体测试134.2.1在测试过程中使用到的调试技术：134.2.2评估运行的可靠性问题：134.3测试结论14结论15参考文献16绪论一、遗传

6、算法概述和发展背景（1）遗传算法简介遗传算法（GeneticAlgorithm，简称GA）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是从代表问题可能潜在的解集的一个种

7、群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解[1]。（2）遗

8、传算法特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：（1）遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便地应用遗传操作算子。（2）遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。二、关于TSP问