数学建模旅行商问题的一解法
维普资讯 doc.guandang.net
曲晓丽等:行商问题的一种模拟退火算法求解旅
旅行商问题的一种模拟退火算法求解 曲晓丽 .潘昊,向斌 .,柳 (.汉理工大学计算机科学与技术学院湖北武汉 1武 4 0 7;.南科技大学电子信息工程学院河南洛阳 3002河 410) 70 3
摘要:行商问题 (T P旅 S )是组合优化领域里的一个典型的,于描述却难以处理的 NP难题,可能的路径数目与城易其市数目是呈指数型增长的,解非常困难 .首先介绍了旅行商问题,拟退火算法原理及其算法实现 .应用模拟退火算法求模
对 T P进行研究,出解决 T P的一种比较精确的算法并用 Mal S给 S t b实现了算法 .最后用该算法对 T P进行了仿真,证 a S验 了该算法的有效性 .
关键词:行商问题;拟退火算法;合优化;短路径旅模组最中图分类号: P 0, T 326文献标识码: B文章编号: 0 4 7 X( 0 7 1 0 8 2 1 0—3 3 2 0 ) 8— 7—0
S l to fTr v li g S ls a o lm y a K i d o i u a e n a i g Al o ih o u i n o a eln a e m n Pr b e b n f S m l t d An e ln g rt m QU a l, Xioi PAN a, U a g i H o II Xin bn ( .S ho f Compu e cinc nd Te hn o 1 c olo t r S e e a c ol gy, uh n U n v r iy o c ol gy, uh n, 0 0, na; W a i e s t f Te hn o W a 43 07 Chi
2 Elcr ncI f r to n i e r gColg He a ie st fS i c . e to i n o ma in E gn ei l e, n n Unv ri o c n e& Te h oo y l y n 4 1 0 Chn ) n e y e c n l g,mo a g,7 0 3, i a
Absr ctT r v ln l s a Pr e ( SP) i e oft t pia P— ha d ta: a el g Sa e m n i oblm T s on he y c lN r pr blm s n c m bna o il tm ia i o e i o i t ra op i z ton, w h c se s o bede c i d b r o b ol d. t os i l m ou sofp h i c e s x ih i a yt s rbe utha d t e s ve I sp sb ea nt at n r a ee pon ntal t hea o t i— e ily wih t m un sofc t Y, O i i e y d fi u tt ole i.TSP s fr ti t o c d i hi a r t e heprn i lo i u a e nn ai g ag ih a S t s v r ifc l o s v t i is n r du e n t s p pe, h n t i cpa fsm l t d a e ln l ort m nd is agort t l ihm e lz i a e ntod e t o r a iaton r i r uc d o .T SP s t id y i u a e nn a ig l rt i s ude b sm l t d a e ln ago ihm d an a r i a e a g ih an pp ox m t l ort m w h c e ho or s l i g TSP s be t rt n t r, nd usng M a lb, ec m p ee t r gr m ors l i ih m t d f o v n i t e ha o he s a i ta w o l t he p o a f o vng TSP. The sm ua— i l ton ofa g ih f r velng s ls a oblm s gien, d t e r s t ov t fiinc i l ort m orta li ae m n pr e i v an h e ulspr e is e fce y. Ke ywor ds:r veln s ls a r e; i ul t d a e lng agort ta lig ae m n p oblm sm a e nn a i l ihm; o b n t ilo i
ia i c m i a ora ptm z ton; h h t s t e s ore tway
l引言
火,忌搜索,禁神经网络,子群优化算法,疫算法等,粒免通过模拟或解释某些自然现象或过程而得以发展,解决复为杂组合优化问题提供了新的思路和方法] .
旅行商问题 ( rvl gS l ma rbe T P代表 T ae n ae nP o l i s m, S ) 一
类组合优化问题,物流配送,算机网络,在计电子地图,
模拟退火算法在迭代搜索过程以 B l man分布概 ot n z 率接受目标函数的"劣化解"具有突出的具有脱离局域最,
交通诱导,气布线, I元布局等方面都有重要的工电 VI单 S
程和理论价值,起了许多学者的关注 .T P简单描述引 S为:名商人欲到个不同的城市去推销商品, 2个城一每市i和之间的距离为 d如何选择一条路径使得商人每 个城市走一遍后回到起点,走的路径最短 .用数学符所号表示为:设维向量 S ( C,,示一条路经, 一 C,… C)表目标函数为: +l
优陷阱的能力,时具有较强的局部搜索能力,而可以同从 获取目标函数的全局最优解 .模拟退火算法具有高效,鲁 棒,用,活的优点 .将模拟退火算法引入 TS通灵 P求解, 可以避免在求解过程中陷入 TS P的局部最优解 . 本文首先介绍了模拟退火算法,此基础上结合 TS 在 P的具体问题,模拟退火的思想引入 T P求解,计出将 S设 TS的一种模拟退火算法并用 Malb语言编程予以 P t a 实现.
mi c c,2…, )一>: c, 1+ f, ) ( ) n (1f, c ( f ) (1c 1 f 1=
TS P是典型的组合优化问题,且是一个 NP~h r并 ad
问题 .T P描述起来很简单,期的研究者使用精确算法 S早 求解该问题,用的方法包括:枝定界法,性规划法和常分线
2模拟退火算法 (i ltdAn e l gA g r h Smuae n ai loi m) n t 2 1模拟退火算法介绍 . 模拟退火算法是 1 8 9 3年 Ki p ti r ar k将 Merp l k c to oi s的
动态规划法等,可能的路径总数随城市数目是成指数但 型增长的,以当城市数目在 1 0个以上一般很难精确的所 0求出其全局最优解 .随着人工智能的发展,现了许多独出立于问题的智能优化算法,如蚁群算法,传算法,拟退遗模
模拟退火思想引入组合优化领域而形成的一种随机性组
合优化方法 .由于该算法模拟固体退火的过程,因此经常称之为"拟
退火算法"模 .模拟退火算法是模拟高温金 属降温的热力学过程 .模拟退火在进行优化时先确定初
收稿日期:0 7 4—1 2 0—0 1
7 8

旅行商问题的一种模拟退火算法求解_理学_高等教育_教育专区。算法软件技术 曲晓丽等 : 旅行商问题的一种模拟退火算法求解 旅行商问题的一种模拟退火算法求解曲...
用模拟退火算法对求解旅行商组合优化问题作了一定的研究,提出了多种不同的随机...003 摘 要:用模拟退火算 法对 求解旅行商 组合 优化问 题作 了一 定 的...
基于遗传算法的旅行商问... 13人阅读 3页 2.00 求解旅行商问题的模拟... 模拟退火算法是一种重要的...
用模拟退火算法解旅行商问题_社会学_人文社科_专业资料。建模第16 卷第 1 ...初始解可选为 ( 1, 2, …, n ) Ζ 且是一个 N P 2 a rd 问题[ ...
基于模拟退火算法的旅行商问题求解_工学_高等教育_教育专区。首先介绍了旅行商问题,给出了其数学描述以及实际应用,进而给出解决TSP的一种比较精确的算法——模拟退火...
。。 平 南京大学计 算机科 学系 摘要关挂 词 本文基于模拟退火思想提出一种 解旅行 商问题的并行算法 , 。 , 并在。 多处 理机 系统 上 实现 , 该...
求解旅行商问题的模拟退火算法高 尚 ( 华东船舶工业学院 电子与信息系 ,江苏 镇江 212003) 摘 : 旅行商问题 TSP 是一个典型的 N P 完全问题 , 模拟退火算法...
基于模拟退火算法的旅行商问题的实现摘 要: 主要介绍了模拟退火算法的原理以及...Carlo迭代求解策略的一种 随机寻优算法 [1 ] (l)以一定的概率接受恶化解 ...
由于该问题的解是一种特殊的序列.所以遗传算法在求解该问题时的性能也并不理想。模拟退火/ 基 于模拟退火算法 的旅行 商 问题 的实现 郭乐新 (门大 学信 息...
(2007)11-3-0241-02 软件时空 旅行商问题( TSP) 的改进模拟退火算法An...旅行商问题是一种典型的求解多局部最优的最优化问题:有n个城市,一个旅行者从...
热门文档