标准
课程实验报告
1实验目的利用遗传算法获得TSP问题的近似解。2实验要求
要求学生了解遗传算法解决问题的基本流程。对TSP问题有所了解知道TSP问题的难点在什么地方如何使用遗传算法来获得一个较好的近似解。3实验内容已知
个城市之间的相互距离，现有一个推销员必须遍访这
个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图gve，其中v是顶点集，e是边集，设ddij是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。4实验软硬件环境
基本Wi
dows系统基本运行环境，VS2012
文案
f标准
5实验方案
（1）遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法遗传算法的基本运算过程如下：a初始化：设置进化代数计数器t0，设置最大进化代数T，随机生成M个个体作为初始群体P0。b个体评价：计算群体Pt中各个个体的适应度。c选择运算将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体Pt经过选择、交叉、变异运算之后得到下一代群体Pt1。f终止条件判断若tT则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。（2）用遗传算法模拟TSP问题TSP问题及旅行商问题假设有一个旅行商人要拜访
个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值
这个问题可分为对称旅行商问题dijdji任意ij123，…
和非对称旅行商问题dij≠dji任意ij123，…
。
若对于城市vv1v2v3…v
的一个访问顺序为tt1t2t3…ti…t
其中ti∈vi123…
，且记t
1t1，则旅行商问题的数学模型为：
mi
lσdtiti1（i1…
）旅行商问题是一个典型的组合优化问题，并且是一个
p难问题，其可能的路径数目r