资源描述:
《基于遗传算法的组合优化问题研究毕业设计答辩课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、TSP问题的遗传算法求解方案计算机科学与技术二班要点陈述遗传算法简介及其优点2设计的基本流程3TSP问题的定义及其实用价值31设计的具体模块4要点陈述具体实践所达到的效果7结束语8各个模块的具体实现35设计中所做的改进36TSP问题的定义TSP(travelingsalesmanproblem,即旅行商问题)的文字描述可以如下表达:给定一组N个城市和他们两两之间的直达距离,找出一个闭合的旅程,使得每个城市刚好经过一次且总的旅行距离最短。TSP问题的实用价值很多实际应用问题,经过简化处理后,均可建模为TSP问题,因而
2、对TSP问题求解方法的研究具有重要实际价值。应用一:TSP问题最直接的应用是车辆选路应用推广:校车的选路;公路,铁路的铺设,输油管道的铺设;灌溉水道的选取,调水工程(例如,南水北调工程)路线的选择;行军路线的选择等。TSP问题的实用价值应用二:印制电路板的钻空路线方案应用推广:城市水管,电缆,电话线的铺设;网络布线等等。TSP问题的实用价值应用三:连锁店的货物配送路线。应用推广:货运公司上门取货,送货上门的路线;邮局取运邮件的路线等等。其实,TSP问题的应用还很多,像DNA基因序列长度的计算,机器人控制等。在此就不
3、一一介绍遗传算法简介遗传算法是仿照人类社会的进化过程提出的,它首先利用随机方式产生一初始群体,群体中的每个个体称为染色体,它对应着优化问题的一个可能解,染色体的最小组成元素称为基因,它对应可能解的某一特征,即设计变量。染色体的评价函数值反映可能解的优劣,按照优胜劣汰原则对染色体进行选择,相对“好”的个体得以繁殖,相对“差”的个体将死亡,因此群体整体的性能,通过选择,交叉,变异等过程将趋于改善,经过若干代繁衍进化就可使群体性能趋于最佳。即能找到最优解。遗传算法的优点遗传算法作为一种模拟生物进化的一种算法,提供了一种求
4、解复杂系统优化问题的通用框架。它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,具有自组织、自适应和自学习性。这种自组织、自适应特性不需要事先描述问题的全部特点,所以可解决那些复杂的非结构化问题。设计的基本流程设计的具体模块毕业设计遗传算法参数设置模块城市生成模块交叉算子选择模块变异算子选择模块地图选择模块具体输出信息显示模块各个模块的具体实现圆形地图:当用户选择圆形地图时,程序接收一个圆形地图菜单响应消息,调用圆形坐标地图类,然后调用函数在屏幕上画一个圆形地图。直角坐标地图:当用户选择直角坐标地图时,程序接收
5、一个菜单响应消息,调用直角坐标地图类,然后调用函数在屏幕上画一个700*420像素的直角坐标地图,默认地图为直角坐标地图。选择地图步骤一直角坐标地图圆形地图各个模块的具体实现用户可以点击鼠标左键产生城市,也可以选择菜单栏的设置城市选项,通过输入城市数目来随机生成城市。还可以按指定的城市坐标,设置指定的城市。当然,如果用户选择错了城市,可以在该城市上点击鼠标右键来清除城市。如果用户要清除所有的城市,可以双击鼠标右键或选择菜单栏的结束选项,都可以清除所有的城市。步骤二城市生成随机生成城市各个模块的具体实现近邻表示顺序矩
6、阵表示整数编码TSP问题编码各个模块的具体实现自然,简单和符合逻辑满足TSP问题的约束条件保证了每个城市经过且只经过一次,并且保证任何一个城市子集中不形成回路。整数编码:n个城市分别用0到n-1之间不同的整数表示,n个数的一个排列就代表旅行商问题的一个可能解,同时亦是染色体的一种构成。步骤三城市编码各个模块的具体实现步骤四遗传算法的相关参数的设置各个模块的具体实现部分匹配交叉算法顺序交叉算法交叉算子改进循环交叉算法改进循环贪心交叉算法步骤五各个模块的具体实现基于次序的变异算法基于位置的变异算法倒位变异算法变异算子步
7、骤六各个模块的具体实现当点击菜单开始后,程序开始进行寻路算法。经过不断的选择,交叉,变异,淘汰适应度比较差的解,保留好的解,经过一代代的循环,最终找到一条最优的染色体,即找到一条最优路径。步骤七计算模块各个模块的具体实现当找到一条最优路径以后,程序即停止运行。最终会用有色线条将图上的城市点连接起来,并且标出旅行城市的起点以及各个城市的访问顺序和编号。同时会将旅行路线的长度,以及算法所消耗的时间显示出来。步骤八结果显示模块程序结果设计中所做的改进一般情况下,对于求解TSP问题,均定义图状数据结构,这样,就必须定义一系
8、列的操作函数。本设计基于STL(标准模板库)中包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法,因此在VC++中应用STL进行编程。这样,既避免了定义复杂数据结构所带来时间上的开销,又提供了更好的代码重用机会。一数据结构的改进设计中所做的改进通过认真分析循环交叉算法的原理,根据具体的编程实现,对原循环交叉算法作了改进。对原循环交叉中子代初始位设为定