基于遗传算法组合优化问题研究-毕业设计中期

《基于遗传算法组合优化问题研究-毕业设计中期》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、毕业设计中期答辩基于遗传算法的组合优化问题研究——TSP问题求解研究内容遗传算法的基本原理TSP问题的定义遗传算法求解TSP问题的算法及其编程实现和仿真实验解TSP问题算法的分析和评估研究目标及方法目标：通过模仿生物遗传学和自然选择的机理，借助生物遗传学的观点，通过编码，选择，交叉，变异等算子构造一类优化搜索算法（遗传算法），在给定一组N个城市和他们两两之间的直达距离的前提下，在合理的时间内，找出一个闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短（TSP问题）。并且算法要达到要求的精度，同时对选择的算法做出适当的分析和评估。研究目标及方法方法：采用Visualc++6.0作为软件开

2、发工具，用STL编程方式，在屏幕上点击n个点作为城市，然后对这些城市进行编号，每个城市分别用1到n之间不同的整数表示，n个整数的一个排列就代表了旅程的一个可能解，然后对其进行选择，交叉，变异等一系列遗传操作，最后求出最优解，并在屏幕上仿真输出结果。遗传算法的基本原理遗传算法是仿照人类社会的进化过程提出的，它首先利用随机方式产生一初始群体，群体中的每个个体称为染色体，它对应着优化问题的一个可能解，染色体的最小组成元素称为基因，它对应可能解的某一特征，即设计变量。染色体的评价函数值反映可能解的优劣，按照优胜劣汰原则对染色体进行选择，相对“好”的个体得以繁殖，相对“差”的个体将死亡，因此群体整体

3、的性能，通过选择，交叉，变异等过程将趋于改善，经过若干代繁衍进化就可使群体性能趋于最佳。遗传算法的基本流程TSP问题的定义巡回旅行商问题（TSP），也称为货郎担问题是一个较古老的问题，最早可以追溯到1759年Euler提出的骑士旅题。1948年，由美国兰德公司推动，TSP问题成为近代组合优化领域的一个典型难题，应该说，TSP问题是一个具有广泛的应用背景和重要理论价值的组合优化问题。用图语言来描述TSP问题，给出一个图G=(V,E),每条边e都属于边集E上有非负权值的w(e),寻找G的Hamilton圈C，使得C的总权值w(c)=∑w(e)最小,其中e属于E(C).算法分析步骤1：在屏幕上画

4、一个10*6的栅格，大小为700*420象素，作为遗传算法解TSP问题的演示地图，然后，在地图上点击鼠标左键设置点作为城市，点击鼠标右键清空点，当点击菜单开始或按ENTER键时即进行寻路。步骤2：当设置了城市点之后，程序先初始化，用vector>drawpoint储存点的位置并标号，用vector>pointmatrix储存任意两个点的距离，用pair,int>resultpoint储存点的位置和距离，其中，距离是屏幕上象素点的距离，两个点之间的距离用公式sqrt(pow(vecpoint[n].x-vec

5、point[m].x,2)+pow(vecpoint[n].y-vecpoint[m].y,2))来计算。算法分析步骤3：城市点的信息已经设置完毕，现在进行遗传算法的初始化设置，n个城市用0到n-1的n个数表示染色体的n个基因。这n个数的一种组合（即一条染色体）表示一条TSP问题的路径。然后随机初始化种群，随机初始化染色体，并且对每条染色体计算其个体适应度，根据适应度选出最佳染色体。步骤4：交叉操作，在此，应用多种交叉方法，用户根据自己的需要可选择不同的交叉方法，从而使旅程最佳。应用的交叉方法有：顺序交叉法，部分匹配交叉法，类顺序交叉法，循环贪心交叉法等。算法分析步骤5：变异操作，求解TS

6、P问题时，变异算子的设计比交叉算子的设计灵活，任何具有局部搜索能力的算子都可以作为它的变异算子。●倒位：首先在父个体中随机地选择两个截断点，然后将这两点所夹的子串中的城市进行反序。●插入：选择一个城市并随机地插入某一位置。●移位：选择一个子路径并随机地插入某一位置。●互换：随机地选择两个城市，并交换其所处的位置。●基于位置的变异：随机地选择两个城市，将第二个城市放在第一个之前。算法分析步骤6：在交叉和变异的过程中，可以进行遗传算法的各种参数设置，具体设置图表如下：算法分析步骤7：经过不断的选择，交叉，变异，最终找到一条最优的染色体，即找到一条最优路径。步骤8：计算路径的长度，并且根据路径的

7、顺序，在图上用有色直线连接各个点。结果分析测试结束语遗传算法是一种求解组合优化问题的模拟人类进化的有效算法，而TSP问题是最经典的组合优化问题，可推广应用于VLSI芯片设计、电路版布局、机器人控制、车辆选路等领域。本文就是从研究最经典的TSP问题入手，设计了一个用遗传算法解决TSP问题的方法，并通过地图来进行仿真。而且，遗传算法实现起来不是很复杂，比起其他的研究在应用于该领域时有较高的效率。Thankyou!