基于遗传算法的组合优化问题研究毕业设计答辩.ppt

上传人:仙人指路1688 文档编号:2282396 上传时间:2023-02-09 格式:PPT 页数:32 大小:1.92MB
返回 下载 相关 举报
基于遗传算法的组合优化问题研究毕业设计答辩.ppt_第1页
第1页 / 共32页
基于遗传算法的组合优化问题研究毕业设计答辩.ppt_第2页
第2页 / 共32页
基于遗传算法的组合优化问题研究毕业设计答辩.ppt_第3页
第3页 / 共32页
基于遗传算法的组合优化问题研究毕业设计答辩.ppt_第4页
第4页 / 共32页
基于遗传算法的组合优化问题研究毕业设计答辩.ppt_第5页
第5页 / 共32页
点击查看更多>>
资源描述

《基于遗传算法的组合优化问题研究毕业设计答辩.ppt》由会员分享,可在线阅读,更多相关《基于遗传算法的组合优化问题研究毕业设计答辩.ppt(32页珍藏版)》请在三一办公上搜索。

1、TSP问题的遗传算法求解方案,计算机科学与技术二班,要点陈述,要点陈述,TSP问题的定义,TSP(traveling salesman problem,即旅行商问题)的文字描述可以如下表达:给定一组N个城市和他们两两之间的直达距离,找出一个闭合的旅程,使得每个城市刚好经过一次且总的旅行距离最短。,TSP问题的实用价值,很多实际应用问题,经过简化处理后,均可建模为TSP问题,因而对TSP问题求解方法的研究具有重要实际价值。应用一:TSP问题最直接的应用是车辆选路,应用推广:校车的选路;公路,铁路的铺设,输油管道的铺设;灌溉水道的选取,调水工程(例如,南水北调工程)路线的选择;行军路线的选择等。,

2、TSP问题的实用价值,应用二:印制电路板的钻空路线方案 应用推广:城市水管,电缆,电话线的铺设;网络布线等等。,TSP问题的实用价值,应用三:连锁店的货物配送路线。应用推广:货运公司上门取货,送货上门的路线;邮局取运邮件的路线等等。,其实,TSP问题的应用还很多,像DNA基因序列长度的计算,机器人控制等。在此就不一一介绍,遗传算法简介,遗传算法是仿照人类社会的进化过程提出的,它首先利用随机方式产生一初始群体,群体中的每个个体称为染色体,它对应着优化问题的一个可能解,染色体的最小组成元素称为基因,它对应可能解的某一特征,即设计变量。染色体的评价函数值反映可能解的优劣,按照优胜劣汰原则对染色体进行

3、选择,相对“好”的个体得以繁殖,相对“差”的个体将死亡,因此群体整体的性能,通过选择,交叉,变异等过程将趋于改善,经过若干代繁衍进化就可使群体性能趋于最佳。即能找到最优解。,遗传算法的优点,遗传算法作为一种模拟生物进化的一种算法,提供了一种求解复杂系统优化问题的通用框架。它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,具有自组织、自适应和自学习性。这种自组织、自适应特性不需要事先描述问题的全部特点,所以可解决那些复杂的非结构化问题。,设计的基本流程,设计的具体模块,毕业设计,遗传算法参数设置模块,城市生成模块,交叉算子选择模块,变异算子选择模块,地图选择模块,具体输出信息显示模块,各个模

4、块的具体实现,圆形地图:当用户选择圆形地图时,程序接收一个圆形地图菜单响应消息,调用圆形坐标地图类,然后调用函数在屏幕上画一个圆形地图。,直角坐标地图:当用户选择直角坐标地图时,程序接收一个菜单响应消息,调用直角坐标地图类,然后调用函数在屏幕上画一个700*420像素的直角坐标地图,默认地图为直角坐标地图。,选择地图,步骤一,直角坐标地图,圆形地图,各个模块的具体实现,用户可以点击鼠标左键产生城市,也可以选择菜单栏的设置城市选项,通过输入城市数目来随机生成城市。还可以按指定的城市坐标,设置指定的城市。当然,如果用户选择错了城市,可以在该城市上点击鼠标右键来清除城市。如果用户要清除所有的城市,可

5、以双击鼠标右键或选择菜单栏的结束选项,都可以清除所有的城市。,步骤二,城市生成,随机生成城市,各个模块的具体实现,?,TSP问题编码,各个模块的具体实现,自然,简单和符合逻辑,满足TSP问题的约束条件,保证了每个城市经过且只经过一次,并 且保证任何一个城市子集中不形成回路。,整数编码:n个城市分别用0到n-1之间不同的整数表示,n个数的一个排列就代表旅行商问题的一个可能解,同时亦是染色体的一种构成。,步骤三,城市编码,各个模块的具体实现,步骤四,遗传算法的相关参数的设置,各个模块的具体实现,部分匹配交叉算法,顺序交叉算法,交叉算子,改进循环交叉算法,改进循环贪心交叉算法,步骤五,各个模块的具体

6、实现,基于次序的变异算法,基于位置的变异算法,倒位变异算法,变异算子,步骤六,各个模块的具体实现,当点击菜单开始后,程序开始进行寻路算法。经过不断的选择,交叉,变异,淘汰适应度比较差的解,保留好的解,经过一代代的循环,最终找到一条最优的染色体,即找到一条最优路径。,步骤七,计算模块,各个模块的具体实现,当找到一条最优路径以后,程序即停止运行。最终会用有色线条将图上的城市点连接起来,并且标出旅行城市的起点以及各个城市的访问顺序和编号。同时会将旅行路线的长度,以及算法所消耗的时间显示出来。,步骤八,结果显示模块,程序结果,设计中所做的改进,一般情况下,对于求解TSP问题,均定义图状数据结构,这样,

7、就必须定义一系列的操作函数。本设计基于STL(标准模板库)中包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法,因此在VC+中应用STL进行编程。这样,既避免了定义复杂数据结构所带来时间上的开销,又提供了更好的代码重用机会。,一,数据结构的改进,设计中所做的改进,通过认真分析循环交叉算法的原理,根据具体的编程实现,对原循环交叉算法作了改进。对原循环交叉中子代初始位设为定值的情况,在本设计中我改为了随机值。这样,种群的结果会多样化,从而避免了“早熟收敛”现象。最后,对两种算法进行了仿真实验,并且对实验结果进行了比较,详细情况见论文5.4节。,二,改进循环交叉算法,设计中所做的改进,在原循

8、环贪心交叉算法理论中,当所有的城市都被扩展时,算法会随机选取一个城市进行扩展,但由于随机数的产生没有规律,当城市数目较大时,会消耗大量的时间。本设计经过改进,通过循环在城市队列中来选取城市,这样会节省大量时间。最后,对两种算法进行了仿真实验,并且对实验结果进行了比较,详细情况见论文5.4节。,三,改进循环贪心交叉算法,具体实践所达到的效果,当将一系列诸于车辆选路问题,印制电路板问题,连锁店的货物配送路线问题建模为TSP问题后,将其中的目标点看作城市,将路费开销等看作是本设计中的路径,经过程序的一系列操作,最后可以求出一条最优路径。,具体实践所达到的效果,具体实践所达到的效果,结束语,遗传算法是一种求解组合优化问题的模拟人类进化的有效算法,而TSP问题是最经典的组合优化问题,可推广应用于VLSI芯片设计、电路版布局、机器人控制、车辆选路等领域。本文就是从研究最经典的TSP问题入手,设计了一个用遗传算法解决TSP问题的方法,并通过地图来进行仿真。并且对其中的某些算法进行了改进,并且对结果进行了比较。另外,遗传算法是新发展起来的一门学科,各种理论,方法尚未成熟,需要进一步地发展和完善,这需要你,需要我,来不断的推动它向前发展。,Thank You!,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 建筑/施工/环境 > 项目建议


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号