贪心遗传算法求解TSP问题.doc

《贪心遗传算法求解TSP问题.doc》由会员分享，可在线阅读，更多相关《贪心遗传算法求解TSP问题.doc（53页珍藏版）》请在三一办公上搜索。

1、2009届学生毕业设计(论文)材料（一）毕 业 设 计（论 文）任 务 书课题名称贪心遗传算法求解TSP问题姓 名何熙之学 号050640307院 系信息与计算机科学系专 业计算机科学与技术指导教师贾丽媛 (副教授)2009年 1 月 12 日一、设计（论文）的教学目的通过本课题的设计，培养学生综合运用所学知识分析和解决实际问题的能力；培养学生独立思考、调查研究、查阅中英文文献和收集资料的能力；使学生提高理论分析、开发软件的能力，从而拓宽学生的知识视野，锻炼和提高学生运用可视化编程工具进行软件开发的能力。二、设计（论文）的主要内容 TSP问题是一个NP难题，采有传统的算法很难求出问题的最优解。

2、TSP搜索空间随着城市数n的增加而增加，所有的旅程路线组合数为(n-1)！/2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的困难。借助于遗传算法的搜索能力解决TSP问题，是很好的一个想法。根据问题的规模，制定用户的需求计划，再根据需要开发相应的源代码软件，具体内容包括：1、对货郎担问题进行调查，制定用户需求计划。2、学习遗传算法原理及其使用。3、学习C+等面向对象语言。4、接受各自的设计任务，开发相关源代码程序。5、总结毕业设计成果，编写有关材料。6、准备毕业答辩。三、 设计（论文）的基本要求 通过毕业设计过程，要求学生掌握遗传算法的基本知识，并能通过计算机

3、 编程解决TSP实际问题。逐步了解软件开发的基本步骤。四、进度安排序号论 文（设 计）各 阶 段 内 容起止日期1开题、准备资料、相关知识准备2009.3.1-2009.3.312对已有方法的检验、分析，并进行设计2009.4.1-2009.4.203对改进（或新的）方法的实现与测试，毕业论文初稿2009.4.21-2009.5.184整理资料、修改毕业论文，准备答辩2009.5.19-2009.5.305毕业答辩2009.5.31五、主要参考文献 1 贾丽媛,杜欣.并行遗传算法研究J.湖南城市学院院报(自然科学版),2006,15:22- 23 2 王小平,曹立明.遗传算法理论、应用与软件实

4、现M. 西安:西安交通大学出版社， 2002 3 毛盛贤,刘国瑞.遗传工程的应用与展望M.北京:北京师范大学出版社,1986. 4 刘立平遗传算法综述J 东莞理工学院学报，2005，12（3）：4852 5 李艺工程结构优化设计的混合遗传算法J 四川大学学报，2005，37（4）：16 19 6 傅清祥,王晓东. 算法与数据结构M. 北京: 电子工业出版社,1998 7 邵军力,张景,魏长华.人工智能基础M. 北京: 电子工业出版社,2000 8 李鑫,陆海东.遗传算法及其应用J.吉林化工学院院报,2005,22:45-46 9 谈家桢.基因和遗传M.北京:科学普及出版社,1981. 10 李

5、金鹏遗传算法原理及在结构优化设计中的应用J.辽宁工学院学 报,2004,24（3）:5659 11 周明,孙树栋.遗传算法原理及其应用M.北京:国防工业出版社,1999 12 张文修,梁怡.遗传算法的数学基础M.西安:西安交通大学出版社,2000 13 魏英姿，赵明扬，黄雪梅，胡玉兰A.求解TSP问题的贪心遗传算法,2004 14 贺毅朝,刘坤起,张翠军,张巍A.求解背包问题的贪心遗传算法及其应用,2007 15 张海兵,徐诚,李世永A.贪心遗传算法及其在武器目标分配问题中的应用,2007 16 魏英姿,赵明扬，张凤，胡玉兰A.贪心遗传算法求解组合优化问题,20052009届学生毕业设计(论文

6、)材料（二）学 生 毕 业 设 计（论 文）开 题 报 告 书课题名称贪心遗传算法求解TSP问题姓 名何熙之学 号050640307院 系信息与计算机科学系专 业计算机科学与技术指导教师贾丽媛 (副教授)2009 年 3 月 19 日设计（论文）题目贪心遗传算法求解TSP问题课题的根据：1）说明本课题的理论、实际意义2）综述国内外有关本课题的研究动态和自己的见解课题的理论：遗传算法（Genetic Algorithm,简称GA）是以Darwin生物进化论哲学思想为启发的搜索技术，GA的基本概念和理论框架是由美国密执安大学的John Holland教授于1975年首先提出来的。模式定理证明了GA

7、具有全局搜索能力。GA中的交叉被认为是贡献于GA的全局搜索性能最重要的因素，变异算子在一定程度上也有这种贡献。然而，遗传算法的搜索方向在遗传操作中很少被强调。为了快速获得高性能的候选解，搜索方向应能指示出GA在一定领域中潜在的前进方向，遗传操作随机数的使用常常会引起候选解在搜索空间中处于随机的位置，如果最优解所在区域距当前搜索区域很远又不能预先识别的话，这就降低了发现最优解的速度，尤其是对于多重优化问题。课题的实际意义：遗传算法的应用广泛,在卫星路由器中的应用，硬件演化，自适应遗传算法网络资源均衡与优化等很多方面均有实现。随着其应用范围的逐渐拓展，遗传算法的研究方面也出现新的方面，如基于遗传算

8、法的机器学习，遗传算法与其他智能算法的渗透结合，并行遗传算法的研究等方面。这些对于遗传算法的研究，不仅推动着遗传算法自身的发展，同时对其他智能算法的发展有着重要作用，特别在人工生命的研究上，遗传算法发挥着其不可替代的作用。研究动态：针对遗传算法在应用过程中出现的收敛速度过慢和封闭竞争问题，可以使用贪心遗传算法，采用混合式方法，遗传算法被用于个体中的全局搜索，而贪心算法在染色体中施行局部探寻。利用贪心算法指导遗传算子操作的策略，此策略强调了GA潜在的搜索方向使得子代群体能在此方向前进，快速搜索到其他高质量的区域，通过TSP问题试验以说明贪心遗传算法的有效性。 个人见解：遗传算法是由自然界的进化论

9、模拟而来，是一种机制求解极值问题的自组织、自适应的智能算法，它在解决一些复杂问题特别是优化问题方面有其特别与独到之处，是一种值得深入研究的算法。课题的主要内容: TSP问题是一个NP难题，采有传统的算法很难求出问题的最优解。TSP搜索空间随着城市数n的增加而增加，所有的旅程路线组合数为(n-1)！/2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的困难。借助于遗传算法的搜索能力解决TSP问题，是很好的一个想法。根据问题的规模，制定用户的需求计划，再根据需要开发相应的源代码软件，具体内容包括：1、对货郎担问题进行调查，制定用户需求计划。2、学习遗传算法原理及其使

10、用。3、学习C+等面向对象语言。4、接受各自的设计任务，开发相关源代码程序。5、总结毕业设计成果，编写有关材料。6、准备毕业答辩。研究方法： 调查法：调查遗传算法的实际意义和可行性研究； 行动研究法：应用遗传算法解决TSP问题，通过编程来验证，在研究过程中，了解浮点数编码、适应度函数、交叉算子和变异算子，遗传算法的三个基本运算（选择、交叉、变异）等问题。完成期限和采取的主要措施：序号论 文（设 计）各 阶 段 内 容起止日期1开题、准备资料、相关知识准备2009.3.1-2009.3.312对已有方法的检验、分析，并进行设计2009.4.1-2009.4.203对改进（或新的）方法的实现与测试

11、，毕业论文初稿2009.4.21-2009.5.184整理资料、修改毕业论文，准备答辩2009.5.19-2009.5.305毕业答辩2009.5.31 认真完成毕业设计所要求的内容,在设计过程中通过查找资料与请教指导老师来解决所遇到的难题与疑问。主要参考资料： 1 贾丽媛,杜欣.并行遗传算法研究J.湖南城市学院院报(自然科学版),2006,15:22-23 2王小平,曹立明.遗传算法理论、应用与软件实现M. 西安:西安交通大学出版社， 2002 3 毛盛贤,刘国瑞.遗传工程的应用与展望M.北京:北京师范大学出版社,1986. 4 刘立平遗传算法综述J 东莞理工学院学报，2005，12（3）：

12、4852 5 李艺工程结构优化设计的混合遗传算法J 四川大学学报，2005，37（4）：1619 6 傅清祥,王晓东. 算法与数据结构M. 北京: 电子工业出版社,1998 7 邵军力,张景,魏长华.人工智能基础M. 北京: 电子工业出版社,2000 8 李鑫,陆海东.遗传算法及其应用J.吉林化工学院院报,2005,22:45-46 9 谈家桢.基因和遗传M.北京:科学普及出版社,1981. 10 李金鹏遗传算法原理及在结构优化设计中的应用J.辽宁工学院学 报,2004,24（3）:5659 11 周明,孙树栋.遗传算法原理及其应用M.北京:国防工业出版社,1999 12 张文修,梁怡.遗传算

13、法的数学基础M.西安:西安交通大学出版社,2000 13 魏英姿，赵明扬，黄雪梅，胡玉兰A.求解TSP问题的贪心遗传算法,2004 14 贺毅朝,刘坤起,张翠军,张巍A.求解背包问题的贪心遗传算法及其应用,2007 15 张海兵,徐诚,李世永A.贪心遗传算法及其在武器目标分配问题中的应用,2007 16 魏英姿,赵明扬，张凤，胡玉兰A.贪心遗传算法求解组合优化问题,2005指导教师意见： 签名： 年 月 日开 题 报 告 会 纪 要时间地点与会人员姓 名职务(职称)姓 名职务(职称)姓 名职务(职称)会议纪要： 主持人：记录人： 年 月 日指导小组意见（负责人本人手写） 负责人签名： 年 月

14、日院系意见 负责人签名： 年 月 日2009届学生毕业设计(论文)材料（三）学 生 毕 业 设 计（论 文）答 辩 评 审 表 课题名称贪心遗传算法解决TSP问题姓 名何熙之学 号050640307院 系信息与计算机科学系专 业计算机科学与技术指导教师贾丽媛 (副教授)2009年 5 月 25 日毕业设计（论文）成绩评定标准及评审表专业：计算机科学与技术 课题：贪心遗传算法解决TSP问题 学生：何熙之分块 等级及得分项 目（该项满分值）评 分 等 级各 档 得 分评分ABCDABCD指导教师40%完成任务的水平和质量501资料搜集与整理论证情况（10）齐全较完全基本齐全差9-107-85-64

15、2基本概念和理论情况（10）清楚、正确基本清楚基本正确尚清楚尚正确不清楚不正确9-107-85-643计算方法和计算结果（15）正确、应用计算机较多基本正确少量应用尚正确尚应用不正确未应用13-1510-127-964独立见解和应用价值（5）有、较大有、一般有、无或无、一般无、无54325说明书、图纸（10）层次分明、正确无误、认真工整、外文提要正确基本正确、较认真、较明确尚正确、尚认真、基本正确错误很多、认真、不正确9-107-85-64独立工作能力306方案制定、选用（10）独立完成且正确基本独立完成正确尚能独立完成基本正确不能独立完成且错误很多9-107-85-647规范和手册使用（8）

16、熟练基本熟练尚可基本不会87658编程、上机结果的分析与处理、国内外文献阅读（12）熟练主动查阅消化引用基本熟练查阅、有引用尚可尚能查阅引用基本不会查阅引用11-129-107-86工作态度209遵守纪律（10）好较好一般差9-107-85-6410爱护公物、保持良好环境（5）好较好一般差543211工作责任心、主动性（5）强较好一般差5432材料评阅人30%1任务完成情况（10）全部完成基本完成主要部分完成未完成9-107-85-642基本概念和理论论证情况（20）清楚、正确基本清楚基本正确尚清楚、尚正确不正确、未应用18-2015-1712-14113计算方法和计算结果（30）正确、应用计

17、算机较多基本正确少量应用尚正确、未应用不正确、不应用26-3021-2516-20154独立见解和应用价值（10）有、较大有、一般有、无或无、一般无、无9-107-85-645说明书、图纸（20）层次分明、正确无误、认真工整，外文提要正确基本正确、较认真、较正确尚正确、尚认真、基本正确错误很多、不认真、不正确18-2015-1712-14116题目难度大小、工作量（10）难、饱满知中、较饱满较易、尚饱满易、不饱满9-107-85-65答辩委员30%1报告情况（20）简明、清晰、重点突出基本清晰重点不够尚清晰、有错概念不清错误较多18-2015-1712-14112回答问题情况（50）正确、熟练

18、基本正确尚正确、有错基本不正确43-5035-4227-34263说明书、图纸（20）总体印象认真、工整、正确较认真尚认真不认真18-2015-1712-14114独立见解和应用价值（10）有、较大有、一般有、无或无、一般无、无9-107-85-64说明：1本方案供院系部参考，评分方案和比例均可根据实际情况进行调整。 2学生的答辩成绩取诸答辩委员会的平均成绩。 3答辩委员会除给出答辩成绩外，还应汇总和审查指导教师、材料评阅人给出的成绩，然后分档（优90；良80-89分；中70-79分；及格60-69分；不及格59分）给出学生毕业设计（论文）成绩。指导教师评审意见(40%)评语：评分 指导教师（

19、签名）： 年 月 日评阅教师评审意见（30%）评语： 评分 评阅教师（签名）：年 月 日答辩小组意见（30%）评语：评分 负责人（签名）： 年 月 日院系意见评语：论文最终评分 负责人（签名）： 评定等级 院系（公章） 年 月 日注：评语包括设计（论文）优点、缺点、数据、材料、论证、结论是否正确，有无新的见解等。等级标准：优90；良80；中70；及格60；不及格60； 答 辩 会 纪 要时间2009年5月31日地点1教102答辩小组成员姓 名职 称所 学 专 业所 从 事 专 业答辩中提出的主要问题及回答的简要情况记录： 会议主持人：记 录 人： 年 月 日毕业设计（论文）答辩申请表学 号05

20、0640307姓 名何熙之院 系信息与计算机科学系专 业计算机科学与技术指导教师贾丽媛设计（论文）课题名称贪心遗传算法解决TSP问题设计（论文）要求及进程计划起 止 时 间任 务 要 求完成情况指 导 教 师签 名2009.3.1-2009.3.31开题、准备资料、相关知识准备2009.4.1-2009.4.20检验分析已有方法并进行设计2009.4.21-2009.5.18实现与测试，毕业论文初稿2009.5.19-2009.5.30整理资料和毕业论文，准备答辩2009.5.31毕业答辩毕业设计（论文）特色简介（数量、质量、创新）： 针对遗传算法在应用过程出现的收敛过慢和封闭竞争问题，利用贪

21、心算法指导遗传算子操作的策略，保证算法每步运行的有效性。而算法出事种群的生成、交叉、变异等环节节都依据贪心选择原则指导操作，避免了传统遗传算法随机性操作的弊端，算法相对较稳定，减少了GA计算工作量，大大提高了算法的效率。是否同意参加答辩意见： 主指导教师（签名）年 月 日2009届学生毕业设计(论文)材料（四）学 生 毕 业 设 计（论 文） 课题名称贪心遗传算法求解TSP问题姓 名何熙之学 号050640307院 系信息与计算机科学系专 业计算机科学与技术指导教师贾丽媛 （副教授）2009 年 5 月 25 日湖南城市学院本科毕业设计（论文）诚信声明 本人郑重声明：所呈交的本科毕业设计（论文

22、），是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本设计（论文）不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 本科毕业设计（论文）作者签名： 二九 年 五 月 三十一 日目 录 摘要I 关键词I AbstractII Key WordsII1. 遗传算法与TSP问题11.1 遗传算法11.1.1 遗传算法概念11.1.2 遗传算法的特点21.1.3 遗传算法的应用21.1.4 遗传算法原理31.1.5 遗传算法应用步骤31.

23、1.6 遗传算法执行代码41.1.7 基本遗传算法41.2 TSP问题51.2.1 TSP问题描述51.2.2 遗传算法解决TSP问题61.3 遗传算法的局限性62. 贪心算法62.1 贪心算法概述62.2 贪心算法的基本思路72.3 贪心算法存在的问题73. 贪心遗传算法74. 算法的实现74.1 算法流程74.2 具体设计84.2.1 种群初始化84.2.2 贪心交叉算子94.2.3 贪心变异算子114.2.4 移民操作115. 程序的调试115.1 程序的运行115.2 运行环境与相关介绍135.2.1 运行环境135.2.2 Visual C+版本介绍13参考文献15致 谢16附 录（

24、程序源代码）17贪心遗传算法求解TSP问题何熙之（湖南城市学院计算机科学系2009届计算机科学与技术专业，湖南 益阳413000）摘要：遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不依赖于问题本身的方式去求解问题。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值的点。基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群，最终可得到问题的最优解和近似最优解。提出贪心遗传算法。通过构建“基因库”形成好的“基因片断”，从而生成高性能的初始种群；依据贪心选择的原则指导遗

25、传操作，实施贪心交叉操作和贪心变异操作；移民操作向种群引进新的遗传物质，克服了封闭竞争缺点，并且可以避免早熟收敛。贪心遗传算法可以大大加快搜索的速度，仿真结果表明算法是十分有效和实用的。关键词：基本遗传算法；贪心遗传算法；贪心交叉算子；贪心变异算子；旅行商；建筑块Greedy Genetic Algorithm for TSP problemHE Xi-zhi(2009 Year computer science and technology major，Department of computer and science，Hunan City University， Hunan YiYang

26、 413000)Abstract：Genetic algorithm is simulated in the natural environment of biological genetic and evolutionary processes and the formation of an adaptive search algorithm for global optimization probability. Overall, the genetic algorithm is based on the problem itself is not dependent on the way

27、 to solve the problem. Its goal is to search the multi-dimensional, highly non-linear space to find the best fitness value point.Basic genetic algorithm is an iterative process, which mimic the natural environment in the bio-genetic and evolutionary mechanism repeatedly to select operator, crossover

28、 operator and mutation operator act on the population, and ultimately receive the optimal solution of the problem and approximate the most optimal solution.Following the principle of greedy selection, the greedy genetic algorithm is proposed in this paper. A gene bank is constituted. The initial pop

29、ulation is formed based on the gene bank. Greedy crossover is adopted to produce a new child for its sufficiently utilizing the local information of individuals. The two exchange local search of greedy mutation is also employed to improve the individual performance. In the process of evolution, new

30、individuals immigrate to the population every a few generations.This procedure prevents premature convergence of the population and leads to an open competition.The simulation results of TSP show its excellent efficiency.Key Words: Basic genetic algorithm;Greedy genetic algorithm; Greedy crossover o

31、perator; Greedy mutation operator; Traveling salesman problem; Building blocks1 遗传算法与TSP问题1.1 遗传算法1.1.1 遗传算法概念 遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地

32、应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之

33、所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心

34、内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。早在本世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入60年代后，美国密歇根大学的Holland教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术遗传算法。1.1.2 遗传算法的特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主

35、要有以下特点： 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 遗传算法使用多个点的搜索信息，具有隐含并行性。 遗传算法使用概率搜索技术，而非确定性规则。1.1.3 遗传算法的应用由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问

36、题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面是遗传算法的一些主要应用领域：1、函数优化函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。2、组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意

37、解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。1.1.4 遗传算法原理步骤：初始化 t0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体P（t）；个体评价 计算P（t）中各个个体的适应度；选择运算 将选择算子作用于群体；交叉运算 将交叉算子作用于群体；变异运算 将变异算子作用于群体，并通过以上运算得到下一代群体 P（t + 1）;

38、终止条件判断 tT：t t+1 转到步骤2；tT：终止 输出解。群体P（t）遗传算法原理图如下：选择运算个体评价交叉运算变异运算解码解集和群体P（t+1）图1.1 遗传算法原理1.1.5 遗传算法应用步骤确定决策变量及各种约束条件，即个体的表现型X和问题的解空间；建立优化模型 （目标函数最大OR 最小） 数学描述形式 量化方法；染色体编码方法；解码方法；个体适应度的量化评价方法 F(x)；设计遗传算子；确定有关运行参数。 1.1.6 遗传算法执行代码 遗传算法的执行代码 m_Tsp.Initpop()； /种群的初始化 for(int i=0；idecen|variancedecvar)/m_Tsp.m_gen100) /将新种群更迭为旧种群，并进行遗传操作 m_Tsp.alternate()； /将新种群付给旧种群 m_Tsp.generation()； /对旧种群进行遗传操作，产生新种群 m_Tsp.