遗传算法与蚁群算法在旅行商问题中的应用Word格式.doc
《遗传算法与蚁群算法在旅行商问题中的应用Word格式.doc》由会员分享，可在线阅读，更多相关《遗传算法与蚁群算法在旅行商问题中的应用Word格式.doc（68页珍藏版）》请在冰点文库上搜索。
4386570
30071970
25621756
27881491
23811676
1332695
37151678
39182179
40612370
37802212
36762578
40292838
42632931
34291908
35072367
33942643
34393201
29353240
31403550
25452357
27782826
23702975
其它相关参数根据实际情况灵活设置。
第2页
毕业设计（论文）主要内容：
1对ＴＳＰ相关概念做简单介绍。
2对两种算法的基本思想的起源背景，定义，特点，现状进展做简单阐述。
３遗传算法基本原理及求解ＴＳＰ问题的基本流程。
４蚁群算法求ＴＳＰ问题基本原理和基本流程。
５根据实际模型（中国31个省会城市的最短周游问题）编写出相应程序并求出其结果。
６两中算法对比分析。
学生应交出的设计文件（论文）：
１结束时应交出论文一篇。
２设计的求解问题的源代码。
第3页
主要参考文献（资料）：
1蔡自兴，徐光枯.人工智能及其应用.北京:
清华大学出版社，2006.
2敖友云，迟洪钦.基于遗传算法求解TSP问题的一种算法[J].计算机与数字工程，2006，34（4）:
52-55.
3唐立新，旅行商问题（TSP）的改进遗传算法[J].东北大学学报（自然科学版），1999，20（l）:
40并2.
4尚智强，郑耀林一种改进遗传算法在旅行商（TSP）问题中的应用[J].福建电脑，2002，（8）:
42-43.
5温广辉，王明旭，郭用琼一种求解TSP问题的新型遗传编码方案[J].科学技术与工程，2006，6
（2）:
206-208.
6MarcoDorigo,ThomasStutzle.蚁群优化.北京：
清华大学出版社,2003.27~34
7李士勇.蚁群优化算法及其应用.哈尔滨:
哈尔滨工业大学出版社，2005.158~164
8段海滨.蚁群算法原理及其应用.北京：
科学出版社,2004.135~139
9叶志伟，郑肇葆。
蚁群算法中参数，，设置的研究——以TSP问题为例（武汉大学遥感信息工程学院湖北武汉430079）
10JiangRui,SzetoKY,LuoYu-pin,HuDong-cheng.APathSplittingSchemeBasedDistributedParallelGeneticAlgo-rithmforLargeTravelingSalesmanProblems[C]//Proc.ConferenceonIntelligentInformationProcessing.2000:
478-485.
11FogelDB.ApplyingEvolutionaryProgrammingtoSelec-tedTravelingSalesmanProblems[J].CybemeticsandSys-tem,2001,24
（1）:
27-36.
12lgium.AntColonySystem:
ACooperativeLearningApproachtotheTravellingSalesmanProblem.TechnicalReportIRIDIA-1996-5
13arcoDorigo,G.DiCaro,andL.M.Gambardella.Antalgorithmsfordiscreteoptimization.ArtificialLife,5:
137-172,1999
专业班级信息与计算科学０５０２学生樊茂森
要求设计（论文）工作起止日期２００９.４.２０－２００９.６.２０
指导教师签字日期
教研室主任审查签字日期
系主任批准签字日期
第4页
学院:
理学院系别:
数学系
专业班级：
信计0502班姓名：
樊茂森
指导老师：
刘晓峰
摘要
旅行商问题是研究最为广泛的组合优化问题，在现实生活中，也有着广泛的应用。
由于已经证明，旅行商问题是NP完全问题，因此，不太可能发现能保证在多项式计算时间内获得问题最优解的算法。
遗传算法是一种有效的解决最优化问题的方法。
遗传算法是求解NP完全问题的一种常用方法，它在解决排列组合问题方面占有很重要的地位。
本文针对旅行商问题，分别对个体的基因编码、适应值，以及选择、交叉、变异算子进行了设计，给出了一种解决旅行商问题的遗传算法。
蚂蚁算法就是近年来出现的，搜索效果良好的一种启发式搜索方法。
蚂蚁算法的主要思想，是模拟蚂蚁寻找食物的过程。
在蚂蚁在搜索的过程中，会不断分泌外激素。
蚂蚁之间通过外激素交流信息，可以很快找到从蚁穴到食物之间的最短路线。
蚂蚁算法的核心，就是让蚂蚁以外激素为媒介，互相交流信息，不断搜索更好的旅行路线，从而取得旅行商问题的令人满意的答案。
关键词：
仿生算法，蚁群算法，遗传算法，旅行商问题。
GeneticAlgorithmandAntColonyAlgorithmforTSP
Abstract
Travelingsalesmanproblemistostudyawiderangeofmostcombinatorialoptimizationproblems,inreallife,alsohaveawiderangeofapplications.AsaresulthasbeenprovedthatthetravelingsalesmanproblemisNP-completeproblem,therefore,unlikelytobefoundtoensurethatthecalculationinpolynomialtimetoobtaintheoptimalsolutionalgorithmfortheproblem.
Geneticalgorithmisaneffectivesolutiontotheoptimizationproblem.GeneticalgorithmstosolveNP-completeproblemisacommonlyusedmethod,whichinaddressingtheproblemofpermutationandcombinationplaysanimportantrole.
Thispapertravelingsalesmanproblemusingageneticalgorithmtosolve,byusingaselection,crossoverandmutation,andotheroperatortooperator,andfinallytestresults.
AntSystem（AS）isanew,promisingheuristics.AScamefromstudyingofantsinreality.Whenantssearchfood,theydepositpheromonealthoughtheirways.Bycommunicatingthroughpheromoneandreinforcingsearching,antscanalwaysfindbestwayfromhometofood.Sameasantsinreality,coreofASisthepheromone.Artificialantscommunicatewitheachother,searchnewwaysbasedonhistoricalresults,andgivesatisfyingsolutionstoTSPfinally.
Keywords:
Bionicalgorithm,antcolonyalgorithm,geneticalgorithm,travelingsalesmanproblem.
目 录
摘要 I
Abstract II
1求解组合优化问题的仿生进化算法 1
1.1NP完全问题 1
1.2旅行商问题 1
1.2.1算法复杂性理论简介 1
1.2.2旅行商问题介绍 2
1.2.3解决旅行商问题的意义 2
1.3.遗传算法 2
1.3.1遗传算法生物学背景 2
1.3.2搜索空间（SearchSpace） 3
1.3.3遗传算法定义 3
1.3.4遗传算法特点 4
1.3.5遗传算法的应用进展 4
1.4蚁群算法 6
1.4.1蚁群算法简介 6
1.4.2蚁群算法的特点 7
1.4.3蚁群算法的应用进展 7
2遗传算法解决TSP问题 9
2.1旅行商问题描述 9
2.2构造城市位置矩阵、距离矩阵 9
2.3编码与初始群体生成 9
2.4计算适应度 10
2.5选择操作 10
2.6交叉和变异操作 11
2.7遗传算法中的一些参数分析 12
2.8算法流程 13
3蚁群算法及TSP问题 15
3.1蚁群算法的由来 15
3.2蚁群的自组织行为 15
3.3蚁群算法基本原理 17
3.4基本蚁群算法的缺陷及改进方法 20
3.5蚁群算法的模型及在TSP问题中的实现 21
3.6蚁群算法模型参数对ＴＳＰ问题影响的试验分析研究 23
3.7算法流程图 27
4遗传算法与基本蚁群算法的实验分析 29
结论 31
参考文献 32
致 谢 33
外文原文 34
中文翻译 52
59
1求解组合优化问题的仿生进化算法
1.1NP完全问题
我们知道很多问题有快速的算法（多项式算法）.但是,也有很多问题是无法用算法解决的。
事实上，已经证明很多问题不可能在多项式时间内解决出来。
但是，有很多很重要的问题他们的解虽然很难求解出来，但是他们的值却是很容易求可以算出来的。
这种事实导致了NP完全问题。
NP表示非确定的多项式（NondeterministicPolynomial），意思是这个问题的解可以用非确定性的算法“猜”出来。
如果我们有一个可以猜想的机器，我们就可以在合理的时间内找到一个比较好的解。
NP-完全问题学习的简单与否，取决于问题的难易程度。
因为有很多问题，它们的输出极其复杂，比如说人们早就提出的一类被称作NP-难题的问题。
这类问题不像NP-完全问题那样时间有限的。
因为NP-问题由上述那些特征，所以很容易想到一些简单的算法――把全部的可行解算一遍。
但是这种算法太慢了（通常时间复杂度为O（2^n））在很多情况下是不可行的.
现在,没有知道有没有那种精确的算法存在。
证明存在或者不存在那种精确的算法这个沉重的担子就留给了新的研究者了，或许你就是。
现在很多人认为那种精确的算法是不存在的，所以他们试图寻找一种替代的算法――比如说这里的遗传算法。
这里的NP-问题的例子，旅行商问题（TravellingSalesmanProblem）或背包问题（knapsackproblem），都是满意性问题。
1.2旅行商问题
1.2.1算法复杂性理论简介
一个算法的有效性可以用执行该算法所需要的各种计算资源的量来衡量，最主要的两个资源就是所需的运行时间和存储空间。
算法或问题的复杂性一般是问题规模n的函数，时间复杂性记为T（n），空间复杂性记为S（n）。
算法执行期间占用的存储单元定义为算法的空间复杂性。
但在算法分析和设计中，人们通常总是将最快的算法与最有效的算法等同起来，这是因为时间需求常是决定某一算法在实际中是否真正有效的决定性因素。
因此，在算法复杂性研究中，衡量一个算法的效果，最广泛采用的标准是在产生最终结果前所花费的时间，常称复杂性为时间复杂性。
从组合最优化问题的定义我们可以了解到，每一个组合优化问题其实都可以通过枚举的方法得到最优解。
但是枚举是以时间为代价的，有的枚举时间还可以接受，有的还能接受有的则不能接受。
算法的时间复杂性对计算机的解题能力（速度和规模）有重大的影响。
我们在此以TSP问题为例，对这个问题的直观的求解方法是穷举法，现在来考察需要的计算时间。
假设城市规模是n，旅行商在起点时，下一步的访问有n-1个城市供选择:
当访问完第二个城市后，他可以从剩下的n-2个城市中选择一个城市进行访问:
依此类推，当它访问完第i个城市后，他可以从n-1-i个城市中选择一个城市进行访问。
因此，完成一次回路需要进行（n-1）!
的计算，每次计算，需要累加n条访问路线的费用总和，所以，总的计算时间是（n!
）。
用运算能力为每秒一百万次浮点运算的计算机求解，在n=10时只需0.185。
而在n=20，需用1929年才能找到最优解。
1.2.2旅行商问题介绍
旅行商问题，即TSP问题（TravelingSalesmanProblem）是数学领域中著名问题之一。
假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。
路径的选择目标是要求得的路径路程为所有路径之中的最小值【2】。
TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。
TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题【3】。
同样的问题，在中国还有另一个描述方法：
一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？
这个描述之所以称为中国邮递员问题（ChinesePostmanProblemCPP）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。
1.2.3解决旅行商问题的意义
旅行商问题在现实世界中有许多表现形式，因而使得解决TSP问题变得很流行。
我们现在来解释一下。
一些含有路径问题能够比成旅行商问题。
这个问题是去找出最小限度地去服务于众多顾客。
现在有许多问题包含了找出最小的次数去服务于所有顾客。
我们称这类问题为TSP问题。
电脑线问题也能比做TSP问题。
我们需要连接线和盒子在不超过两次的范围内，并且需用到线的长度最小。
另一个例子就是由PLATE，LOWE和CHANDRSEKARAN提出的飞行器用油问题。
这个飞行器最少的燃料供给也能比成TSP问题。
还有在单个机器上花的时间和准备给机器花的时间也是TSP问题，我们需要用最少的时间去完成工作。
一个机器人需要演示出许多不同的操作去完成这个工作，在这个例子中虽然它不能被比成TSP问题，但是解决TSP问题的方法也许适合解决这个问题。
因此解决TSP具有及其重要的现实意义。
1.3.遗传算法
1.3.1遗传算法生物学背景
基因
所有的生物都是由细胞组成的。
在每一个细胞中都有想同序列的染色体。
染色体是一串DNA的片断，它为整个有机体提供了一种复制模式。
染色体是由基因组成的，或者说染色体就是一块块的基因。
每一个基因为一个特定的蛋白质编码。
或者更简单的说，每一个基因为生物体的某一特定特征编码，比如说眼睛的颜色。
所有可能的某一特定特征的属性（比如，蓝色，桔黄色等）被称之为等位基因。
每一个基因在染色体上都有其特定的位置，这个位置一般被称作位点（Locus）。
全部序列的基因物质（或者全部的染色体）称之为基因组（或染色体组）（Genome）。
基因组上特定序列的基因被称作基因型（Genotype）。
基因型和后天的表现型两者是有机体的显性、生理和心理特征比如说眼睛的颜色、智力的基础。
复制（Repeoduction）
在复制中，首先发生的是交叉（Crossover）。
来自于父代的基因按照一定的方式组成了新的基因。
新的子代还可能发生变异（Mutation）。
变异的意思是DNA上的某一些成分发生了一点点的变化。
这些改变可能是由于在由父代到子代的基因复制中出现的误差。
生物体的适应度由生物体自身是否能生存来度量的。
1.3.2搜索空间（SearchSpace）
在很多情况下,我们解决一个问题就是从一大堆的数据中寻找一个解，而通常这个解都是混杂在数据中的。
所有可行解（FeasibleSolution可行解就是满足了一定约束条件的解）组成的空间称之为搜索空间（也可以称之为状态空间）。
搜索空间中的每一个点都是一个可行解。
每一个可行解都可以被它的函数值或者它的适应度所标记。
记住：
问题的解就是搜索空间中的一个点，于是我们就是要从搜索空间中找到这个点。
这样，求解问题就可以转化为在搜索空间中寻找极值点（最大值或者最小值点）。
搜索空间在求解问题时可能是完全已知的，但一般来说我们只知道一些孤立的点，然后我们逐渐地生成其它点。
问题是，这个搜索过程可能很复杂，我们甚至不知道该去哪里搜索或者该从是么地方开始搜索。
事实上，有很多寻找合适解（注意：
不一定是最优解）的方法，比如说爬山法（HillClimbing）禁止接近法（TabuSearch）,模拟退火算法（SimulatedAnnealing）以及遗传算法等等.用遗传算法求解出来的解一般被认为是一个比较好的解,因为我们没有办法证明它是最优解.
1.3.3遗传算法定义
遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体（individual）组成。
每个个体实际上是染色体（chromosome）带有特征的实体。
染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。
因此，在一开始需要实现从表现型到基因型的映射即编码工作。
由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。
这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
1.3.4遗传算法特点
遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：
1、遗传算法以决策变量的编码作为运算对象。
传统的优化算法往往直接决策变量的实际值本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。
2、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。
3、遗传算法使用多个点的搜索信息，具有隐含并行性。
4、遗传算法使用概率搜索技术，而非确定性规则。
1.3.5遗传算法的应用进展
由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：
1、函数优化。
函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：
连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。
对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。
2、组合优化
随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。
对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。
实践证明，遗传算法对于组合优化中的NP问题非常有效。
例如遗传算法已经在
升级会员 