如何安排访问次序
问题：已知
个城市之间的相互距离，推销员必须遍访这
个城市，且每个城市只能访问一次，最后又必须返回出发城市。如何安排访问次序，可使其旅行路线的总长度最短？
用图论的术语来说，假设有一个图gve，其中v是顶点集，e是边集，设ddij是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题dijdji任意ij123，…
和非对称旅行商问题dij≠dji任意ij123，…
。若对于城市vv1v2v3…v
的一个访问顺序为tt1t2t3…ti…t
其中ti∈vi123…
，且记t
1t1，则旅行商问题的数学模型为：mi
lσdtiti1（i1…
）旅行商问题是一个典型的组合优化问题，并且是一个
p难问题，其可能的路径数目与城市数目
是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。遗传算法：初始化过程：用v1v2v3…v
代表所选
个城市。定义整数popsize作为染色体的个数，并且随机产生popsize个初始染色体，每个染色体为1到18的整数组成的随机序列。适应度f的计算：对种群中的每个染色体vi，计算其适应度，fσdtiti1评价函数evalvi：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈01，本文定义基于序的评价函数为evalvialpha1alphai1。随机规划与模糊规划选择过程：选择过程是以旋转赌轮popsize次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1、对每个染色体vi计算累计概率qi，q00qiσevalvjj1…ii1…popsizestep2、从区间0popsize中产生一个随机数r；step3、若qi1step4、重复step2和step3共popsize次，这样可以得到popsize个复制的染色体。grefe
stette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefe
stette编码《遗传算法原理及应用》可以避免这种情况的出现。所谓的grefe
stette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：815216107431114612951813171对应：81421386325734324221。交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到popsize重复以下过
f程：从0，1中产生一个随机数r，如果r将所选r