利用遗传算法解决TSP问题

您可以编辑WORD格式课程实验报告1.实验目的利用遗传算法获得TSP问题的近似解。2.实验要求要求学生理解用遗传算法解决问题的基本过程。您熟悉TSP问题，知道TSP问题的难点在哪里，也知道如何使用遗传算法获得更好的近似解决方案。3.实验内容知道n个城市之间的相互距离，现有的推销员必须访问n个城市，每个城市只能访问一次，最后必须返回出发城市。如何确定对这些城市的访问顺序，使其旅行的总长度最短？图表理论中的术语，假设图表g=(v，e)。其中v是一组顶点，e是一组边，集d=(dij)是一个距离矩阵，由顶点I和顶点j之间的距离组成。旅行社的问题是通过所有顶点，求出每个顶点仅通过一次的最短距离的循环。4.实验硬件和软件环境基本Windows系统基本操作环境，VS20125.实验程序(1)遗传算法是模仿达尔文生物进化论的自然选择和遗传机制的生物进化过程的计算模型，是模拟自然进化过程寻找最佳解决方案的方法遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数t，随机生成m个对象作为初始组P(0)。b)个人评估：计算组P(t)中个人的适合性。c)选择操作：将选择操作符应用于组。选择的目的是将优化的对象直接传给下一代，或通过配对将新对象传授给下一代。选择操作基于组内个人的适合性评估。d)交集运算：将交集运算子套用至群组。交集是指取代两个父物件的部分结构，重新组合以建立新物件的作业。遗传算法的核心作用是交叉运算符。e)转移运算：将转移运算子套用至群组。改变群体中特定基因座的基因值。组P(t)通过选择、交叉、变异运算得到下一代组P(t 1)。f)确定终止条件： t=T使用在进化过程中获得的最大适应性的对象作为最佳解决方案输出来终止计算。(2)用遗传算法模拟TSP问题TSP问题和旅游企业问题，假设有一个旅游企业家访问n个城市，他必须选择去的路线，路线的限制是每个城市访问一次，最后回到最初出发的城市。路径的选取目标是所需路径的最小距离(所有路径的最小距离)此问题是对称旅行社问题(dij=dji，随机I，j=1，2，3，n)和不对称旅行问题(dijdji，随机I，j=1，2，3，n)。城市v=v1，v2，v3，VN的访问顺序之一为t=(t1，T2，T3，ti、TN)，则tiv(I=1，2，3，n)和TN 1=t1时，旅行商问题的数学模型如下：Min l= d (t (I)，t (I 1) (I=1，n)旅行推销员问题是常见的组合优化问题，是具有大量可能路径的NP难题城市的数n是指数增长的，所以一般很难准确地找到最优解，本文利用遗传算法来寻找近似解。6.实验阶段：(1)初始化过程：v1、v2、v3、使用VN表示选定的n个城市。将整数pop-size定义为染色体数，并随机生成pop-size的初始染色体，随机顺序为1到18的整数。(2)拟合度f的计算：计算群体中每个染色体VI的拟合度，f=d(t(i)，t(i 1)。(3)评估函数eval(vi):用于设置对象内每个染色体vi的概率，使此染色体被选中的可能性与对象内其他染色体的适应性成正比。通过车轮挂在一起，适应性染色体在后台生成的概率更大。alpha(0，1)，本文将基于顺序的计算函数定义为eval(vi)=alph *(1-alpha)。(I-1)。(4)选择过程：选择过程基于旋转下注轮pop-size次，每次旋转为新人口选择一条染色体。赌局根据每个染色体的适应度选择染色体。步骤1，每个染色体VI的累计概率计算qi，Q0=0；Qi= eval (VJ) j=1，I；I=1，pop-size。Step2，在间隔(0，pop-size)中生成随机数r；Step3、ruqi-1重复Step4，step2，step3一次总pop-size，就可以得到pop-size狗的复制染色体。(5)交叉过程：本文采用一般单点交叉。重复以下过程(从到pop-size)以确定交叉操作的父项。如果0，1生成随机数r，r将选定的父代组合到两个组中，则随机交叉一个位置，如下所示：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 16 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1相交后：8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 16 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1(6)变异过程：本文采用均匀多点变异。在r中选择多染色体VI作为父对象，类似于在交叉操作中选择父对象的过程。对于每个选定父级，从每个位置随机选择多个位置，以便从xk的值范围为ukmin，ukmax和xk=ukmin r(ukmax-ukmin)的0，1生成随机数r。例如：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1转换后：8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1(7)周期操作：判断是否满足设定的代数xzome，否则，可变度也跳到f的计算。是的，完成遗传操作，然后跳出去。实验代码：#include#include#include#include#include#define cities 10 /城市数#define MAXX 100/重复#define PC 0.8 /交配概率#define pm 0.05 /变异概率#define num 10/总量大小Int bestsolution/最佳染色体int distancecitiescities；/城市之间的距离结构组/染色体的结构int citycities；/城市顺序Int adapt/适应性双p；/人口的生存概率groupnum，group tempnum；/cities随机生成城市之间的相互距离Void init()Int i、j；