资源描述：
《tsp问题的顺序插入交叉算子》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、!!!!"!#!$!%!&!’!(!)*+,*’’(,*+-*./$$0,1-&,"*2计算机工程与应用!""#!$%"!#89!"#问题的顺序插入交叉算子孙海雷!刘琼荪!胡上尉:G<23%H’"%!IEGJ%)#(H-K#!2G:+3#(HL"%重庆大学数理学院!重庆FMNNFFO)’’"(")>?3$+",3$%&-3#4:&%"#&"-!O+)#(P%#(G#%Q"*-%$R!O+)#(P%#(FNNNFF!-./01ST,3%’/-K#+3%’"%UU7VAWDX&),"$%&’()*+(!,-$.
2、(/01)230!&$"4’01)5+(6789+8!02+8:"8/22/;+8#<+8’:/8=/8!"#6$#%&’()*+,-!,))*!,-.,/0&&1!".(!#,2!3445!67)>$/?@)??ABC2:8’D://&&)*4%#($)$+"9:;&+3*3&$"*!3#"L&*)--)Q"*)="*3$)*!)*4"*%#-"*$&*)--)Q"*)="*3$)*%-4"-%(#"4!L+%&+%#$*)4K&"-$*%3#(’"4%-$3#&"4%>>"*"#&">K#&$%)#3-
3、3&*%$"*%)#3#4K-"-$+"(*""4R-"’"&$%)#-$*3$"(R%#$+"&*)--)>$+"("#"$%&3’()*%$+,29+%-)="*3$)*%-&)#4K&$"4K-%#($+"’)&3’%#>)*,3$%)#">>"&$%Q"’R3#4%#+"*%$%#("Y&"’’"#$("#">*),$+"=3*"#$-3E$+3-Z""#=*)Q"4">>"&$%Q"$+*)K(+$+")=$%,%[3$%)#&),=K$%#()>-),""Y3,=’"1E+F5/892/4*3Q
4、"’%#(53’"-,3#6*)Z’",-’"#"$%&(’()*%$+,)’($-)*4"*%#-"*$&*)--)Q"*)="*3$)*摘要!针对9:;问题的特点!在遗传算法的交叉运算过程中设计了三角距离差函数作为评价标准!运用贪婪策略思想!提出了一种新的交叉算子"顺序插入交叉#B*4"*E#-"*$O*)--)Q"*!简称BEO$算子!该算子有效地利用了局部信息!并且能很好地继承父代优秀的基因!实例仿真验证了该算子的有效性%关键词!9:;问题&遗传算法&顺序插入交叉算子文章编号!AUUCH!DDA)C
5、UU7$U!7UUW8HUC文献标识码!中图分类号!9;DUA1W&引言访这!个城市!并且每个城市只能访问一次!最后又必须返回遗传算法"’"#"$%&(’()*%$+,-!简称./$是012)’’3#4于到出发城市*如何安排他对这些城市的访问次序!可使旅行总5678受生物进化论的启发而提出来的!./是基于%自然选择!路程最短,用图论的术语来说!假设有一个图"#)$!%$!其中$适者生存&的一种高度并行’随机的优化算法!它将问题的求解是顶点集)顶点对应于某个城市$!%是边集)城市之间的连接状态!每边赋予权重
6、!即城市间的距离$!设!是由顶点&到达表示成染色体的适者生存过程!通过染色体群的一代代的不断顶点3之间的距离所组成的距离矩阵!如果任意两个城市间的进化!包括复制’交叉和变异的操作!最终收敛到%最适应环境&距离都是对称的!它对应的是图论中的无向图-若两个城市间的个体!从而求得问题的最优解或满意解(旅行商问题)9:;$是的距离是非对称的!它对应于图论中的有向图*旅行商问题就一个典型的组合优化问题!并且是一个<;难题!目前求解9:;是求出一条经过所有顶点且每个顶点只经过一次的具有最短问题的主要方法有启发式搜索法’
7、模拟退火法’遗传算法’路径的回路*2)=>%"’4神经网络算法和二叉树描述算法等*用遗传算法求解9:;)A*+问题的关键就是交叉算子的设计!部分匹配交叉);?@$D顺序插入交叉算子设计顺序交叉"B@$)C*’循环交叉"B@$)D*等算子!它们没有充分考虑假设有*个城市&!!!.!*染色体编码定义为推销员所经9:;问题所具有的特点!忽视了父代中边的邻接状况!使得运过的城市的顺序号!如染色体4/)5&!5!!.!5*$!将上述染色体算效果不理想!而插入交叉"E@$)F*和两交换启发式"2./$)8*算子看成一个
8、环!染色体中5*的下一个城市为5&*虽然对邻接状况进行了考虑!但是它们都没有考虑染色体最后定义设有三个城市-!6!1!定义三角距离差函数’)(!)!一个基因和第一个基因间的距离*因此!为克服上述算子的局*$如下/限性!作者通过研究!提出了一种能够有效利用局部信息!并且7)-!6!1$+.)-!6$8.)6!1$9:);!<$能很好地继承父代优秀的基因的顺序插入交叉算子!在交叉运其中.)5!=$表示城市5到城市=的
