已知 n 个城市之间的相互距离，现有一个推销员必须遍访这 n 个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图 g=(v,e)，其中 v 是顶点集，e 是边集，设 d=(dij)是由顶点 i 和顶点 j 之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题(dij=dji,,任意 i,j=1,2,3，…,n)和非对称旅行商问题(dij≠dji,,任意 i,j=1,2,3，…,n)。若对于城市 v={v1,v2,v3,…,vn}的一个访问顺序为 t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且记 tn+1= t1，则旅行商问题的数学模型为：min l=σd(t(i),t(i+1)) （i=1,…,n）旅行商问题是一个典型的组合优化问题，并且是一个 np 难问题，其可能的路径数目与城市数目 n 是成指数型增长的，所以一般很难精确地求出其最优解，本文采纳遗传算法求其近似解。遗传算法：初始化过程：用 v1,v2,v3,…,vn 代表所选 n 个城市。定义整数 pop-size 作为染色体的个数，并且随机产生 pop-size 个初始染色体，每个染色体为 1 到 18 的整数组成的随机序列。适应度 f 的计算：对种群中的每个染色体 vi，计算其适应度，f=σd(t(i),t(i+1)).评价函数 eval(vi)：用来对种群中的每个染色体 vi 设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选 择 产 生 后 台 的 机 会 要 大 ， 设 alpha∈(0,1) ， 本 文 定 义 基 于 序 的 评 价 函 数 为eval(vi)=alpha*(1-alpha).^(i-1) 。[随机规划与模糊规划]选择过程：选择过程是以旋转赌轮 pop-size 次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1 、对每个染色体 vi,计算累计概率 qi，q0=0;qi=σeval(vj) j=1,…,i;i=1,…pop-size.step2、从区间(0,pop-size)中产生一个随机数 r；step3、若 qi-1 step4、重复 step2 和 step3 共 pop-size 次，这样可以得到 pop-size 个复制的染色体。grefenstette 编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采纳 grefenstette 编码《遗传算法原理及应用》可以避开这种情况的出现。所谓的 grefenstette...
