运用遗传算法求解旅行商问题的探讨,数学建模中的经典问题
刘会超,刘 珂:运用遗传算法求解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.
〔责任编辑 张继金〕
【武汉大学】运用遗传算法求解TSP问题的探讨_工学_高等教育_教育专区。遗传算法求解TSP问题第24卷第5期2009年10月 天中学刊JournalofTianzhong 、,01.24 No.5 ...
4)遗传算法使用的选择、交叉、变异算子都是随机的; 3对TSP的遗传基因编码方法在遗传算法的应用中,遗传基因的编码是一个很重要的问题.对遗传基因进行编码时,要...
遗传算法求解TSP问题的改进_专业资料。针对遗传算法解决TSP问题的特点,构造出遗传算法需要的初始种群.运用相同算法对改进前后的两种种群进行实验,得出改进方法具有增强...
第 7 卷第 26 期 (2011 年 9 月 ) http://www.dnzs.net.cn E-mail: eduf@cccc.net.cn Tel:+86-551-5690963 5690964 遗传算法求解 TSP 问题的研究汪...
具体的适应度函数可以表示为f=i/(Td+ ●t I输山琏庖鹿值t优的十体I 图1求解TSP问题的遗传算法框图 2 TSP遗传算法表示和实现演化计算已被成功地应用于求解...
(系 学院 系): 专题业: 目: 计算机科学与技术学院 计算机科学与技术 基于遗传算法的 TSP 问题求解方法 的研究与实现 指导者: 指导者: 朱保平 (姓名) 副教授...
基于Matlab的遗传算法解决TSP问题的报告_其它_总结/汇报_应用文书。使用matlab语言对遗传算法进行编程,解决TSP问题,并使用专门测试的tsp进行试验,发现和标准值比较...
TSP问题是著名的NPC问题,在组合优化中有许多应用。讨论如何应用启发式遗传算法求解此问题,并设计一种启发式交叉算子和换位变异算子,主要特点是给出算子在程序中的...
求解TSP问题的一种改进的遗传算法_IT/计算机_专业资料。TSP维普资讯 http://www.cqvip.com 求解 T P问题 的一种改进 的遗传算法 S谢胜利 唐敏: 董金祥 (...
遗传算法及其在TSP问题中的应用研究_自然科学_专业资料。用粒子群算法等求解TSP问题的相关论文贵州大学 硕士学位论文 遗传算法及其在TSP问题中的应用研究 姓名:李薇...
热门文档