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

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