我在走向开源的不归路上!
FREE~开源的意思就是大家要相互交流经验,既然要开源,那就开源吧~我把放假参
加数模选拔时的完成的一个重要程序(我自己是觉得很重要)公布出来,和同道中人分享,随便
请教下谁知道有更好的编译方法没?
问题:已知 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 编码就是用所选队员在未选（不含淘汰）队员中的位置，如：
8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1
对应：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。
交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到 pop-size 重复
以下过程：从[0，1]中产生一个随机数 r，如果 r 将所选的父代两两组队，随机产生一个位
置进行交叉，如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
评论0