如何安排访问次序。
问题:
已知 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)=al
pha*(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 重复以下过