文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 运用遗传算法求解TSP问题的探讨
侵权投诉

运用遗传算法求解TSP问题的探讨

运用遗传算法求解旅行商问题的探讨,数学建模中的经典问题

刘会超,刘 珂:运用遗传算法求解TSP问题的探讨 ·37·

q2=(186 | 4357 | 2910). gi=f(Pi), (2)

再计算个体的相对适应值

hi(Pi)=gi

2.4 变异算子的设计

∑

i=1

m

从遗传算法的观点来看,解的进化主要靠选择机

fi, (3)

制和杂交算子来完成,变异只是为选择、杂交过程中

可能丢失的某些遗传基因进行修复和补充[5].变异一变异算子有散播般是以概率qm∈[0.05~0.20]进行的.

变异、移位变异、插入变异、倒置变异、倒置移位变异等.本文采用的是倒置变异算子,方法如下:在个体编码串中随机选择两个城市,第一个城市的右城市与第二个城市之间的编码倒序排列,从而产生一个新个体,例如,若父个体是(18392764105),假设随机选择的城市是2和4,那么产生的新个体为

(18392467105).

3 实验与结论

最后,根据hi(pi)把一个圆盘分成n份,每份扇形的

(3)式中, P表示某条合法的中心角为2πgi.在(2)式和i路径,f(Pi)表示路径的长度,i=1,,2L,m.在进行选择时,可以假想转动一下圆盘,若某参照点落入第

i个扇形内,则选择个体i.这样,小扇区的面积越大,被选中的概率也越大,即个体适应值越大它被选择到的机会也越多,其基因结构被遗传到下一代的可能性也越大.运用此选择方式随机生成m个体(个体数一般为20~200),最终形成演化种群. 2.3 杂交算子的设计

杂交算子是模拟生物进化中染色体的交换组合来产生新的优良品种,进而搜索到空间中新的点[4].杂交一般是以概率qc∈[0.60~0.98]进行的.关于路径表示的杂交算子主要有部分匹配杂交(Partially Matched Crossover,简称PMX)、顺序杂交(Order Crossover,

设共有10个城市,各城市间的距离如表1所示.qc=0.8,qm=0.1,在相同的演化代数下,传取m=20,

统方法所求得的较优值f(P)=373.660km,较优路径210,,,,9871,,,465},而用本文去除冗余的为P={3,,

、循环杂交(Cycle Crossover,简称CX)等,简称OX)

本文采用的是PMX.

在PMX操作中,首先随机地在父体中选取两个杂交点,定义这两点之间的区域为匹配区域,一并交换相应的匹配区域;然后根据匹配区域内的城市确定部分映射关系;接着在父体上先填入无冲突的城市,以保证在路径中每个城市被且仅被访问一次;再对有冲突的城市分别执行这些部分映射,直到填入无冲突时,则获得杂交后的两后代.

例如,对下面的两父体,随机选择两个杂交点(“|”表示杂交点)

p1=(182|4357|6109), p2=(174 | 6893 | 2510),

方法所求得的较优值f(P)=355.461km,较优路径为

P={1,,,3210,,,,,,,9876541}.

表1 各城市之间的距离 km

1111111112345678910ij15.23876.47124.11754.11842.94133.35252.82477.14345.714

2222222233456789104ij57.14342.35372.94160.00064.11862.35376.19035.23884.118

3333334445678910567

ijij6 28.235 77 57.647 788910891091010ij52.94177.14366.66728.23556.19040.00034.28640.95249.524

实验结果表明,采用该演化算法能够降低种群生成时的冗余度,保持种群的多样性,提高求解的效率,而且还能有效地避免“早熟”现象,因而此算法是有效算法.

参考文献:

交换两个杂交点之间的匹配区域,得到

q1=(1** | 6893 |***), q2=(1** | 4357 |***),

[1] 王宇平,李英华.求解TSP的量子遗传算法[J].计算机

学报,2007,(5):748~755.

其中“*”为待定城市号.由匹配区域确定的部分映射为:4―6,3―8,5―9,7―3.然后,从各自的父体中填入无冲突的城市,得到

q1=(1*2 | 6893 | *10*), q2=(1** | 4357 | 2*10).

[2] 黄雪梅,李涛,徐春林,等.一种基于免疫遗传的TSP求

四川大学学报(工程科学版),2006,(1):86~91. 解方法[J].

[3] 潘正君,康立山,陈毓屏.演经计算[M].北京:清华

大学出版社,2004.16~36.

个体q1中的第一个*处原为8,由映射关系3―8映射再由7―3映射到7无冲突,则把7填入.到3仍冲突,

类似地进行操作,最终得到的两个子个体为

q1=(172 | 6893 | 4105),

[4] 李倩,文贵华,丁月华.一种改进的求解旅行商问题的

单亲遗传算法[J].计算机工程与科学,2007,(2):89~109.

[5] 王小平,曹立明.遗传算法[M].西安:西安交通大学

出版社,2001.

〔责任编辑 张继金〕

上一页第2页

你可能喜欢

  • 遗传算法解决TSP问题
  • 人工智能导论
  • 旅行商问题算法
  • 车辆路径问题
  • 汉诺塔递归算法
  • 编译原理第二版课后答案
  • 遗传算法应用实例

热门文档

相关文档

  • 【武汉大学】运用遗传算法求解TSP问题的探讨

    【武汉大学】运用遗传算法求解TSP问题的探讨_工学_高等教育_教育专区。遗传算法求解TSP问题第24卷第5期2009年10月 天中学刊JournalofTianzhong 、,01.24 No.5 ...

  • 【浙江大学 综合】遗传算法求解TSP问题的研究进展

    4)遗传算法使用的选择、交叉、变异算子都是随机的; 3对TSP的遗传基因编码方法在遗传算法的应用中,遗传基因的编码是一个很重要的问题.对遗传基因进行编码时,要...

  • 【论文】遗传算法求解TSP问题的改进

    遗传算法求解TSP问题的改进_专业资料。针对遗传算法解决TSP问题的特点,构造出遗传算法需要的初始种群.运用相同算法对改进前后的两种种群进行实验,得出改进方法具有增强...

  • 遗传算法求解TSP问题的研究

    第 7 卷第 26 期 (2011 年 9 月 ) http://www.dnzs.net.cn E-mail: eduf@cccc.net.cn Tel:+86-551-5690963 5690964 遗传算法求解 TSP 问题的研究汪...

  • 用遗传算法求解TSP问题

    具体的适应度函数可以表示为f=i/(Td+ ●t I输山琏庖鹿值t优的十体I 图1求解TSP问题的遗传算法框图 2 TSP遗传算法表示和实现演化计算已被成功地应用于求解...

  • 遗传算法解决TSP问题。C++、MFC界面编程

    (系 学院 系): 专题业: 目: 计算机科学与技术学院 计算机科学与技术 基于遗传算法的 TSP 问题求解方法 的研究与实现 指导者: 指导者: 朱保平 (姓名) 副教授...

  • 基于Matlab的遗传算法解决TSP问题的报告

    基于Matlab的遗传算法解决TSP问题的报告_其它_总结/汇报_应用文书。使用matlab语言对遗传算法进行编程,解决TSP问题,并使用专门测试的tsp进行试验,发现和标准值比较...

  • 求解TSP问题的一种启发式遗传算法

    TSP问题是著名的NPC问题,在组合优化中有许多应用。讨论如何应用启发式遗传算法求解此问题,并设计一种启发式交叉算子和换位变异算子,主要特点是给出算子在程序中的...

  • 【论文】求解TSP问题的一种改进的遗传算法

    求解TSP问题的一种改进的遗传算法_IT/计算机_专业资料。TSP维普资讯 http://www.cqvip.com 求解 T P问题 的一种改进 的遗传算法 S谢胜利 唐敏: 董金祥 (...

  • 遗传算法及其在TSP问题中的应用研究

    遗传算法及其在TSP问题中的应用研究_自然科学_专业资料。用粒子群算法等求解TSP问题的相关论文贵州大学 硕士学位论文 遗传算法及其在TSP问题中的应用研究 姓名:李薇...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email