贪心遗传算法求解TSP问题

毕 业 设 计（论 文）任 务 书 课题名称 贪心遗传算法求解 TSP 问题 姓 名 何熙之 学 号 050640307 院 系 信息与计算机科学系 专 业 计算机科学与技术 指导教师 贾丽 媛 (副教授 ) 2009 年 1 月 12 日 2009 届学生 毕业设计 (论文 )材料 （一） 一、设计（论文）的教学目的 通过本课题的设计，培养学生综合运用所学知识分析和解决实际问题的能力；培养学生独立思考、调查研究、查阅中英文文献和收集资料的能力；使学生提高理论分析、开发软件的能力，从而拓宽学生的知识视野，锻炼和提高学生运用可视化编程工具进行软件开发的能力。 二、设计（论文）的主要内容 TSP 问题是一个 NP 难题，采有传统的算法很难求出问题的最优解。 TSP 搜索空间随着城市数 n 的增加而增加，所有的旅程路线组合数为 (n-1)！ /2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的困难。借助于遗传算法的搜索能力解决 TSP 问题，是很好的一个想法。根据问题的规模，制定用户的需求计划，再根据需要开发相应的源代码软件，具体内容包括： 1、对货郎担问题进行调查，制定用户需求计划。 2、学习遗传算法原理及其使用。 3、学习 C+等面向对象语言。 4、接受各自的设计任务，开发相关源代码程序。 5、总结毕业设计成果，编写有关材料。 6、准备毕业答辩。 三、 设计（论文）的基本要求 通过毕业设计过程，要求学生掌握遗传算法的 基本知识，并能通过计算机 编程解决 TSP 实际问题。逐步了解软件开发的基本步骤。 四、进度安排 序号 论 文（设 计）各 阶 段 内 容 起止日期 1 开题、准备资料、相关知识准备 2009.3.1-2009.3.31 2 对已有方法的检验、分析，并进行设计 2009.4.1-2009.4.20 3 对改进（或新的）方法的实现与测试，毕业论文初稿 2009.4.21-2009.5.18 4 整理资料、修改毕业论文，准备答辩 2009.5.19-2009.5.30 5 毕业答辩 2009.5.31 五、主要参考文献 1 贾丽媛 ,杜欣 .并行遗传算法研究 J.湖南城市学院院报 (自然科学版 ),2006,15:22- 23 2 王小平 ,曹立明 .遗传算法 理论、应用与软件实现 M. 西安 :西安交通大学出版社， 2002 3 毛盛贤 ,刘国瑞 .遗传工程的应用与展望 M.北京 :北京师范大学出版社 ,1986. 4 刘立平遗传算法综述 J 东莞理工学院学报， 2005， 12（ 3）： 48 52 5 李艺 工程结构优化设计的混合遗传算法 J 四川大学学报， 2005， 37（ 4）： 16 19 6 傅清祥 ,王晓东 . 算法与数据结构 M. 北京 : 电子工业出版社 ,1998 7 邵军力 ,张景 ,魏长华 .人工智能基础 M. 北京 : 电子工业出版社 ,2000 8 李鑫 ,陆海东 .遗传算法及其应用 J.吉林化工学院院报 ,2005,22:45-46 9 谈家桢 .基因和遗传 M.北京 :科学普及出版社 ,1981. 10 李金鹏遗传算法原理及在结构优化设计中的应用 J.辽宁工学院学 报 ,2004,24（ 3） :56 59 11 周明 ,孙树栋 .遗传算法原理及其应用 M.北京 :国防工业出版社 ,1999 12 张文修 ,梁怡 .遗传算法的数学基础 M.西安 :西安交通大学出版社 ,2000 13 魏英姿，赵明扬，黄雪梅，胡玉兰 A.求解 TSP 问题的贪心遗传算法 ,2004 14 贺毅朝 ,刘坤起 ,张翠军 ,张巍 A.求解背包问题的贪心遗传算法及其应用 ,2007 15 张海兵 ,徐诚 ,李世永 A.贪心遗传算法及其在武器目标分配问题中的应 用 ,2007 16 魏英姿 ,赵明扬，张凤，胡玉兰 A.贪心遗传算法求解组合优化问题 ,2005 学 生 毕 业 设 计（论 文） 开 题 报 告 书 课题名称 贪心遗传算法求解 TSP 问题 姓 名 何熙之 学 号 050640307 院 系 信息与计算机科学系 专 业 计算机科学与技术 指导教师 贾丽媛 (副教授 ) 2009 年 3 月 19 日 2009 届学生 毕业设计 (论文 )材料 （二） 设计（论文）题目 贪心遗传算法求解 TSP 问题 课题的根据： 1）说明本课题的理论、实际意义 2）综述国内外有关本课题的研究动态和自己的见解 课题的理论：遗传算法（ Genetic Algorithm,简称 GA）是以 Darwin 生物进化论哲学思想为启发的搜索技术， GA 的基本概念和理论框架是由美国密执 安大学的 John Holland 教授于 1975 年首先提出来的。模式定理证明了 GA 具有全局搜索能力。 GA 中的交叉被认为是贡献于 GA 的全局搜索性能最重要的因素，变异算子在一定程度上也有这种贡献。然而，遗传算法的搜索方向在遗传操作中很少被强调。为了快速获得高性能的候选解，搜索方向应能指示出 GA 在一定领域中潜在的前进方向，遗传操作随机数的使用常常会引起候选解在搜索空间中处于随机的位置，如果最优解所在区域距当前搜索区域很远又不能预先识别的话，这就降低了发现最优解的速度，尤其是对于多重优化问题。 课题的实际意义： 遗传 算法 的应用广泛 ,在卫星路由器中的应用，硬件演化，自适应遗传算法网络资源均衡与优化等很多方面均有实现。随着其应用范围的逐渐拓展，遗传算法的研究方面也出现新的方面，如 基于遗传算法的机器学习 ，遗传算法与其他智能算法的渗透结合，并行遗传算法的研究等方面。这些对于遗传算法的研究，不仅推动着遗传算法自身的发展，同时对其他智能算法的发展有着重要作用，特别在人工生命的研究上，遗传算法发挥着其不可替代的作用。 研究动态：针对遗传算法在应用过程中出现的收敛速度过慢和封闭竞争问题，可以使用贪心遗传算法，采用混合式方法，遗传算法 被用于个体中的全局搜索，而贪心算法在染色体中施行局部探寻。利用贪心算法指导遗传算子操作的策略，此策略强调了 GA潜在的搜索方向使得子代群体能在此方向前进，快速搜索到其他高质量的区域，通过 TSP问题试验以说明贪心遗传算法的有效性。 个人见解：遗传算法是由自然界的进化论模拟而来，是一种机制求解极值问题的自组织、自适应的智能算法，它在解决一些复杂问题特别是优化问题方面有其特别与独到之处，是一种值得深入研究的算法。 课题的主要内容 : TSP 问题是一个 NP 难题，采有传统的算法很难求出问题的最优解。 TSP 搜索空间随着城市数 n 的增加而增加，所有的旅程路线组合数为 (n-1)！ /2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的困难。借助于遗传算法的搜索能力解决 TSP 问题，是很好的一个想法。根据问题的规模，制定用户的需求计划，再根据需要开发相应的源代码软件，具体内容包括： 1、对货郎担问题进行调查，制定用户需求计划。 2、学习遗传算法原理及其使用。 3、学习 C+等面向对象语言。 4、接受各自的设计任务，开发相关源代码程序。 5、总结毕业设计成果，编写有关材料。 6、准备毕业 答辩。 研究方法： 调查法 ：调查遗传算法的实际意义和可行性研究； 行动研究法 ：应用遗传算法解决 TSP 问题，通过编程来验证，在研究过程中，了解浮点数编码、适应度函数、交叉算子和变异算子，遗传算法的三个基本运算（ 选择 、交叉 、 变异 ）等问题。 完成期限和采取的主要措施： 序号 论 文（设 计）各 阶 段 内 容 起止日期 1 开题、准备资料、相关知识准备 2009.3.1-2009.3.31 2 对已有方法的检验、分析，并进行设计 2009.4.1-2009.4.20 3 对改进（或新的）方法的实现与测试，毕业论文初稿 2009.4.21-2009.5.18 4 整理资料、修改毕业论文，准备答辩 2009.5.19-2009.5.30 5 毕业答辩 2009.5.31 认真完成毕业设计所要求的内容 ,在设计过程中通过查找资料与请教指导老师来解决所遇到的难题与疑问。 主要参考资料： 1 贾丽媛 ,杜欣 .并行遗传算法研究 J.湖南城市学院院报 (自然 科学版 ),2006,15:22-23 2王小平 ,曹立明 .遗传算法 理论、应用与软件实现 M. 西安 :西安交通大学出版社， 2002 3 毛盛贤 ,刘国瑞 .遗传工程的应用与展望 M.北京 :北京师范大学出版社 ,1986. 4 刘立平遗传算法综述 J 东莞理工学院学报， 2005， 12（ 3）： 48 52 5 李艺工程结构优化设计的混合遗传算法 J 四川大学学报， 2005， 37（ 4）： 16 19 6 傅清祥 ,王晓东 . 算法与数据结构 M. 北京 : 电子工业出版社 ,1998 7 邵军力 ,张景 ,魏长华 .人工智能基础 M. 北京 : 电子工业出版社 ,2000 8 李鑫 ,陆海东 .遗传算法及其应用 J.吉林化工学院院报 ,2005,22:45-46 9 谈家桢 .基因和遗传 M.北京 :科学普及出版社 ,1981. 10 李金鹏遗传算法原理及在结构优化设计中的应用 J.辽宁工学院学 报 ,2004,24（ 3） :56 59 11 周明 ,孙树栋 .遗传算法原理及其应用 M.北京 :国防工业出版社 ,1999 12 张文修 ,梁怡 .遗传算法的数学基础 M.西安 :西安交通大学出版社 ,2000 13 魏英姿，赵明扬，黄雪梅，胡玉兰 A.求解 TSP 问题的贪心遗传算法 ,2004 14 贺毅朝 ,刘坤起 ,张翠军 ,张巍 A.求解背包问题的贪心遗传算法及其应用 ,2007 15 张海兵 ,徐诚 ,李世永 A.贪心遗传算法及其在武器目标分配问题中的应用 ,2007 16 魏英姿 ,赵明扬，张凤，胡玉 兰 A.贪心遗传算法求解组合优化问题 ,2005 指导教师意见 ： 签名： 年 月 日 开 题 报 告 会 纪 要 时间 地点 与 会 人 员 姓 名 职务 (职称 ) 姓 名 职务 (职称 ) 姓 名 职务 (职称 ) 会议纪要： 主持人： 记录人： 年 月 日 指 导 小 组 意 见 （负责人本人手写） 负责人签名： 年 月 日 院系 意 见 负责人签名： 年 月 日 学 生 毕 业 设 计（论 文） 答 辩 评 审 表 课题名称 贪心遗传算法解决 TSP 问题 姓 名 何熙之 学 号 050640307 院 系 信息与计算机科学系 专 业 计算机科学与技术 指导教师 贾丽媛 (副教授 ) 2009 年 5 月 25 日 2009 届学生 毕业设计 (论文 )材料 （三） 毕业设计（论文）成绩评定标准 及评审表 专业： 计算机科学与技术 课题： 贪心遗传算法解决 TSP 问题 学生： 何熙之 分 块 等级及得分 项 目 （该项满分值） 评 分 等 级 各 档 得 分 评分 A B C D A B C D 指 导 教 师 40% 完成任务的水平和质量50 1资料搜集与整理论证情况（ 10） 齐全 较完全 基本齐全 差 9-10 7-8 5-6 4 2基本概念和理论情况（ 10） 清楚、正确 基本清楚 基本正确 尚清楚 尚正确 不清楚 不正确 9-10 7-8 5-6 4 3计算方法和计算结果（ 15） 正确、应用计算机较多 基本正确 少量应用 尚正确 尚应用 不正确 未应用 13-15 10-12 7-9 6 4独立见解和应用价值（ 5） 有、较大 有、一般 有、无或无、一般 无、无 5 4 3 2 5说明书、图纸（ 10） 层次分明、正确无误、认真工整、外文提要正确 基本正确、较认真、较明确 尚正确、尚认真、基本正确 错误很多、认真、不正确 9-10 7-8 5-6 4 独立工作能力30 6方案制定、选用（ 10） 独立完成 且正确 基本独立 完成正确 尚能独立完成基本正确 不能独立完成且错误很多 9-10 7-8 5-6 4 7规范和手册使用（ 8） 熟练 基本熟练 尚可 基本不会 8 7 6 5 8编程、上机结果的分析与处理、国内外文献阅读（ 12） 熟练主动查阅消化引用 基本熟练查阅、有引用 尚可尚能 查阅引用 基本不会 查阅引用 11-12 9-10 7-8 6 工作态度20 9遵守纪律（ 10） 好 较好 一般 差 9-10 7-8 5-6 4 10爱护公物、保持良好环境（ 5） 好 较好 一般 差 5 4 3 2 11工作责任心、主动性（ 5） 强 较好 一般 差 5 4 3 2 材 料 评 阅 人 30% 1任务完成情况（ 10） 全部完成 基本完成 主要部分完成 未完成 9-10 7-8 5-6 4 2基本概念和理论论证情况（ 20） 清楚、正确 基本清楚 基本正确 尚清楚、尚正确 不正确、未应用 18-20 15-17 12-14 11 3计算方法和计算结果（ 30） 正确、应用计算机较多 基本正确 少量应用 尚正确、未应用 不正确、不应用 26-30 21-25 16-20 15 4独立见解和应用价值（ 10） 有、较大 有、一般 有、无或 无、一般 无、无 9-10 7-8 5-6 4 5说明书、图纸（ 20） 层次分明、正确无误、认真工整，外文提要正确 基本正确、较认真、较正确 尚正确、尚认真、基本正确 错误很多、不认真、不正确 18-20 15-17 12-14 11 6题目难度大小、工作量（ 10） 难、饱满 知中、较饱满 较易、尚饱满 易、不饱满 9-10 7-8 5-6 5 答 辩 委 员 30% 1报告情况（ 20） 简明、清晰、重 点突出 基本清晰 重点不够 尚清晰、有错 概念不清 错误较多 18-20 15-17 12-14 11 2回答问题情况（ 50） 正确、熟练 基本正确 尚正确、有错 基本不正确 43-50 35-42 27-34 26 3说明书、图纸（ 20） 总体印象认真、工整、正确 较认真 尚认真 不认真 18-20 15-17 12-14 11 4独立见解和应用价值（ 10） 有、较大 有、一般 有、无或无、一般 无、无 9-10 7-8 5-6 4 说 明： 1本方案供院系部参考，评分方案和比例均可根据实际情况进行调整。 2学生的答辩成绩取诸答辩委员会的平均成绩。 3答辩委员会除给出答辩成绩外，还应汇总和审查指导教师、材料评阅人给出的成绩，然后分档（优 90；良 80-89 分；中 70-79 分；及格 60-69 分；不及格 59 分）给出学生毕业设计（论文）成绩。 指 导 教 师 评 审 意 见 (40%) 评语： 评分 指导教师（签名）： 年 月 日 评 阅 教 师 评 审 意 见 （ 30%） 评语： 评分 评阅教师（签名）： 年 月 日 答 辩 小 组 意 见 （ 30%） 评语： 评分 负责人（签名）： 年 月 日 院 系 意 见 评语： 论文最终评分 负责人（签名）： 评定等级 院系（公章） 年 月 日 注：评语包括设计（论文）优点、缺点、数据、材料、论证、结论是否正确，有无新的见解等。 等级标准：优 90；良 80；中 70；及格 60；不及格 60； 答 辩 会 纪 要 时间 2009 年 5 月 31 日 地点 1 教 102 答 辩 小 组 成 员 姓 名 职 称 所 学 专 业 所 从 事 专 业 答辩中提出的主要问题及回答的简要情况记录： 会议主持人： 记 录 人： 年 月 日 毕业设计（论文）答辩申请表 学 号 050640307 姓 名 何熙之 院 系 信息与计算机科学系 专 业 计算机科学与技术 指导教师 贾丽媛 设计（论文）课题名称 贪心遗传算法解决 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 毕业答辩 毕业设计（论文）特色简介（数量、质量、创新）： 针对遗传算法在应用过程出现的收敛过慢和封闭竞争问题，利用贪心算法指导遗传算子操作的策略，保证算法每步运行的有效性。而算法出事种群的生成、交叉、变异等环节节都依据贪心选择原则指导操作，避免了传统遗传算法随机性操作的弊端，算法相对较稳定，减少了 GA计算工作量，大大提高了算法的效率。 是否同意参加 答辩意见： 主指导教师（签名） 年 月 日 学 生 毕 业 设 计（论 文） 课题名称 贪心遗传算法求解 TSP 问题 姓 名 何熙之 学 号 050640307 院 系 信息与计算机科学系 专 业 计算机科学与技术 指导教师 贾丽媛 （ 副教授 ） 2009 年 5 月 25 日 2009 届学生 毕业设计 (论文 )材料 （四） 湖南城市学院本科毕业设计（论文）诚信声明 本人郑重声明：所呈交的本科毕业设计（论文），是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本设计（论文）不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由 本人承担。 本科毕业设计（论文）作者签名： 二九 年 五 月 三十一 日 目 录 摘 要 . I 关键词 . I Abstract.II Key Words .II 1. 遗传算法与 TSP 问题 . 1 1.1 遗传算法 . 1 1.1.1 遗传算法概念 . 1 1.1.2 遗传算法的特点 . 2 1.1.3 遗传算法的应用 . 2 1.1.4 遗传算法原理 . 3 1.1.5 遗传算法应用步骤 . 3 1.1.6 遗传算法执行代码 . 4 1.1.7 基本遗传算法 . 4 1.2 TSP 问题 . 5 1.2.1 TSP 问题描述 . 5 1.2.2 遗传算法解决 TSP 问题 . 6 1.3 遗传算法的局限性 . 6 2. 贪心算法 . 6 2.1 贪心算法概述 . 6 2.2 贪心算法的基本思路 . 7 2.3 贪心算法存在的问题 . 7 3. 贪心遗传算法 . 7 4. 算法的实现 . 7 4.1 算法流程 . 7 4.2 具体设计 . 8 4.2.1 种群初始化 . 8 4.2.2 贪心交叉算 子 . 9 4.2.3 贪心变异算子 . 11 4.2.4 移民操作 . 11 5. 程序的调试 . 11 5.1 程序的运行 . 11 5.2 运行环境与相关介绍 . 13 5.2.1 运行环境 . 13 5.2.2 Visual C+版本介绍 . 13 参考文献 . 15 致 谢 . 16 附 录（程序源代码） . 17 I 贪心遗传算法求解 TSP 问题 何熙之 （ 湖南城市学院计算机科学系 2009 届计算机科学与技术专业，湖南 益阳 413000） 摘 要 ： 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说 来，遗传算法是按不依赖于问题本身的方式去求解问题。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值的点。基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群，最终可得到问题的最优解和近似最优解。提出贪心遗传算法。通过构建 “基因库 ”形成好的 “基因片断 ”，从而生成高性能的初始种群；依据贪心选择的原则指导遗传操作，实施贪心交叉操作和贪心变异操作；移民操作向种群引进新的遗传物质，克服了封闭竞争缺点，并且可以避免早熟收敛。贪心遗传算法可以大大加快搜 索的速度，仿真结果表明算法是十分有效和实用的。 关键词 ： 基本遗传算法；贪心遗传算法；贪心交叉算子；贪心变异算子；旅行商；建筑块 II Greedy Genetic Algorithm for TSP problem HE Xi-zhi (2009 Year computer science and technology major， Department of computer and science， Hunan City University， Hunan YiYang 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 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 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 population 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 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 operator; Greedy mutation operator; Traveling salesman problem; Building blocks 1 1 遗传算法与 TSP 问题 1.1 遗传算法 1.1.1 遗传算法概念 遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的 J.Holland 教授 1975 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生 物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有 “生存检测 ”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择 、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。早在本世纪 40 年代，就有学者开始研究如何利用计算机进行生 2 物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入 60 年代后，美国密歇根大学的 Holland 教授及其学生 们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术 遗传算法。 1.1.2 遗传算法的特点 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点： 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。 遗 传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 遗传算法使用多个点的搜索信息，具有隐含并行性。 遗传算法使用概率搜索技术，而非确定性规则。 1.1.3 遗传算法的应用 由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面 是 遗传算法的一些主要应用领域： 1、 函数优化 函数 优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。 2、 组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要 3 精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之 一。实践证明，遗传算法对于组合优化中的 NP 问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。此外，GA 也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用 。 1.1.4 遗传算法原理 步骤： 初始化 t0 进化代数计数器； T 是最大进化代数；随机生成 M 个个体作为初始群体 P（ t）； 个体评价 计算 P（ t）中各个个体的适应度； 选择运算 将选择算子作用于群体； 交叉运算 将交叉算子作用于群体； 变异运算 将变异算子作用于群体，并通过以上运算得到下一代群体 P（ t + 1） ; 终止条件判断 t T： t t+1 转到步骤 2； tT：终止 输出解。 遗传算法原理图如下： 图 1.1 遗传算法原理 1.1.5 遗传算法应用步骤 确定决策变量及各种约束条件，即个体的表现型 X 和问题的解空间； 建立优化模型 （目标函数最大 OR 最小） 数学描述形式 量化方法； 群体 P（ t） 选择运算 交叉运算 变异运算 群体 P（ t+1） 解码 解集和 个体评价 4 染色体编码方法； 解码方法； 个体适应度的量化评价方法 F(x)； 设计 遗传算子； 确定有关运行参数。 1.1.6 遗传算法执行代码 遗传算法的执行代码 m_Tsp.Initpop()； /种群的初始化 for(int i=0； idecen|variancedecvar)/m_Tsp.m_gen=MG是否成立，若是，进化终止，输出结果；否则，转 (4)。 具体算法流程图如下： N Y N Y 图 4.1 贪心遗传算法流程图 4.2 详细 设计 4.2.1 种群初始化 编码 旅行商问题是个排序问题，按照城市被访问的次序表示旅行路径。城市编为一串整型值。例，假设有 5个城市 1， 2， 3， 4， 5，如果旅行商从 3城市开始经过了 5城市、 1城市、 4城市、 2城市、再回到 3城市，则染色体为 35142， 为表示的确定 GA 控制参数 i=0 生成初始种群（贪心选择） 贪心交叉、变异 i=i+1 i G？ i =G? 移民操作 开始 输出 9 一个路径。对有 N个城市的 TSP问题，在初始化种群时，随机取 1到 N之间的整型数，形成长度为 N的染色体，保证每一城市的整型基因能且只能出现一次。按这种方式构建的染色体即表示了一个可行解。在利用 GA解决 TSP问题时，城市在染色体中的相对位置比绝对位置更重要。例：对 3城市的对称旅行商问题，（ 1 2 3）（ 3 1 2）都指的是相同的旅行。这样，有局部优势的城市对就很重要。 贪心初始化种群 遗传算法涉及的基因，大多来源于个体本身，从而个体质量的高低决定了算法的效率，如果群体中的所有个体的适应值都较差， 势必影响算法的全局性能，对于 TSP问题尤其明显。为了克服上述弱点，首先将 TSP问题中的 N个点按每点进行排序，根据 “基因库 ”来构造 “基因片断 ”，从而组建染色体串。 构建 “基因库 ” 对于有 N个城市 TSP问题，距离 i城市最近的 C个城市按距离由小到大排序进行编码，组成 NC (c #include #include #include #include void init(FILE *fp); int fab(int n); /能产生的路径总数 void ga(