动态随机最短路径算法研究

张水舰; 刘学军; 杨洋

doi:10.7498/aps.61.160201

摘要

静态最短路径问题已经得到很好解决, 然而现实中的网络大多具有动态性和随机性. 网络弧和节点的状态及耗费不仅具有不确定性且相互关联, 弧和节点的耗费都服从一定的概率分布, 因此把最短路径问题看作是一个动态随机优化问题更具有一般性. 文中分析了网络弧和节点的动态随机特性及其相互关系, 定义了动态随机最短路径; 给出了动态随机最短路径优化数学模型, 提出了一种动态随机最短路径遗传算法; 针对网络的拓扑特性设计了高效合理的遗传算子. 实验结果表明, 文中提出的模型和算法能有效地解决动态随机最短路径问题, 可以运用到交通、通信等网络的网络流随机优化问题中.

关键词:

Abstract

The static shortest path problem has been solved well. However, in reality, more networks are dynamic and stochastic. The states and costs of network arcs and nodes are not only uncertain but also correlated with each other, and the costs of the arcs and nodes are subject to a certain probability distribution. Therefore, it is more general to model the shortest path problem as a dynamic and stochastic optimization problem. In this paper, the dynamic and stochastic characteristics of network nodes and arcs and the correlation between the nodes and arcs are analyzed. The dynamic stochastic shortest path is determined. The dynamic stochastic optimization model of shortest path is provided, and a shortest path genetic algorithm is proposed to solve dynamic and stochastic shortest path problem. The effective and reasonable genetic operators are designed according to the topological characteristics of the network. The experimental results show that this algorithm can be used to effectively solve the dynamic stochastic shortest path problem. The proposed model and algorithm can be applied to the network flow optimization problem in transportation, communication networks, etc.

Keywords:

作者及机构信息

1.
南京师范大学虚拟地理环境教育部重点实验室, 南京 210046

基金项目: 国家高技术研究发展计划(批准号: 2007AA12Z238)和江苏省博士后基金(批准号: 1101016B)资助的课题.

Authors and contacts

1.
Key Laboratory of Virtual Geographic Environment of Ministry of Education, Nanjing Normal University, Nanjing 210046, China

Funds: Project supported by the National High Technology Research and Development Program of China (Grant No. 2007AA12Z238) and the Postdoctoral Science Foundation of Jiangsu Province, China (Grant No. 1101016B).

参考文献

[1]	Peer S K, Dinesh K S 2007 Comput. Math. Appl. 53 729
[2]	Li S B, Wu J J, Gao Z Y, Lin Y, Fu B B 2011 Acta Phys. Sin. 60 050701 (in Chinese) [李树彬, 吴建军, 高自友, 林勇, 傅白白 2011 物理学报 60 050701]
[3]	Wang K, Zhou S Y, Zhang Y F, Pei W J, Liu Q 2011 Acta Phys. Sin. 60 118903 (in Chinese) [王开, 周思源, 张毅锋, 裴文江, 刘茜 2011 物理学报 60 118903]
[4]	Bellman E 1958 Quart. Appl. Math. 16 87
[5]	Dijkstra E W 1959 Numer. Math. 1 269
[6]	Dreyfus S 1969 Operat. Res. 17 395
[7]	Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[8]	Frank H 1969 Operat. Res. 17 583
[9]	Hall R W 1986 Transport. Sci. 20 182
[10]	Fu L, Rilett L R 1998 Transport. Res. B 32 499
[11]	Miller-Hooks E D, Mahmassani H S 1998 Comput. Operat. Res 25 1107
[12]	Miller-Hooks E D, Mahmassani H S 2000 Transport. Sci. 34 198
[13]	Sigal C E, Pritsker A A B, Solberg J J 1980 Operat. Res. 28 1122
[14]	Kamburowski J 1985 Operat. Res. 22 696
[15]	Wellman M P 1995 Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence Montreal, Quebec, Canada, August 18-20, 1995 p18
[16]	Jaillet P 1992 Networks 22 589
[17]	Fan Y Y, Kalaba R E, Moore J E 2005 Comput. Math. Appl. 49 1549
[18]	Dong J Y, Zhang J Y, Chen Z 2007 Acta Phys. Sin. 56 5013 (in Chinese) [董继扬, 张军英, 陈忠 2007 物理学报 56 5013]
[19]	Alberto D V, Roberto M, Norman C, Andrea E R, Gambardella L M 2008 Eur. J. Operat. Res. 185 1174
[20]	Thangiah S R, Nygard K, Juell P 1991 Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications Miami, USA, February 24-28, 1991 p422
[21]	Inagaki J, Haseyama M, Kitajima H 1999 Proc. IEEE Int. Symp. Circuits and Systems Orlando, USA, May 30-June 2, 1999 p137
[22]	Chang W A, Ramakrishna R S 2002 IEEE Trans. Evol. Comput. 6 566
[23]	Nanayakkara S, Srinivasan D, Lup L, Xavier G, Elizabeth T, Ong S H 2007 IEEE Congress on Evolutionary Computation Singapore, September 25-28, 2007 p4469
[24]	Davies C, Lingras P 2003 Eur. J. Operat. Res. 144 27
[25]	Yang S, Cheng H, Wang F 2010 IEEE Trans. Syst. Man Cybernet. C 40 52
[26]	Charles J S 1996 A Course in Probability and Statistics (California: Duxbury Press) p81
[27]	Holland J H 1975 Adaptation in Natural and Artificial Systems (Michigan: University of Michigan Press) p22
[28]	Thomas B W, White C C 2007 Eur. J. Operat. Res. 176 836
[29]	Bell M G H, Iida Y 1997 Transportation Network Analysis (Chichester: John Willey and Sons) p17

施引文献

[1]	Peer S K, Dinesh K S 2007 Comput. Math. Appl. 53 729
[2]	Li S B, Wu J J, Gao Z Y, Lin Y, Fu B B 2011 Acta Phys. Sin. 60 050701 (in Chinese) [李树彬, 吴建军, 高自友, 林勇, 傅白白 2011 物理学报 60 050701]
[3]	Wang K, Zhou S Y, Zhang Y F, Pei W J, Liu Q 2011 Acta Phys. Sin. 60 118903 (in Chinese) [王开, 周思源, 张毅锋, 裴文江, 刘茜 2011 物理学报 60 118903]
[4]	Bellman E 1958 Quart. Appl. Math. 16 87
[5]	Dijkstra E W 1959 Numer. Math. 1 269
[6]	Dreyfus S 1969 Operat. Res. 17 395
[7]	Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[8]	Frank H 1969 Operat. Res. 17 583
[9]	Hall R W 1986 Transport. Sci. 20 182
[10]	Fu L, Rilett L R 1998 Transport. Res. B 32 499
[11]	Miller-Hooks E D, Mahmassani H S 1998 Comput. Operat. Res 25 1107
[12]	Miller-Hooks E D, Mahmassani H S 2000 Transport. Sci. 34 198
[13]	Sigal C E, Pritsker A A B, Solberg J J 1980 Operat. Res. 28 1122
[14]	Kamburowski J 1985 Operat. Res. 22 696
[15]	Wellman M P 1995 Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence Montreal, Quebec, Canada, August 18-20, 1995 p18
[16]	Jaillet P 1992 Networks 22 589
[17]	Fan Y Y, Kalaba R E, Moore J E 2005 Comput. Math. Appl. 49 1549
[18]	Dong J Y, Zhang J Y, Chen Z 2007 Acta Phys. Sin. 56 5013 (in Chinese) [董继扬, 张军英, 陈忠 2007 物理学报 56 5013]
[19]	Alberto D V, Roberto M, Norman C, Andrea E R, Gambardella L M 2008 Eur. J. Operat. Res. 185 1174
[20]	Thangiah S R, Nygard K, Juell P 1991 Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications Miami, USA, February 24-28, 1991 p422
[21]	Inagaki J, Haseyama M, Kitajima H 1999 Proc. IEEE Int. Symp. Circuits and Systems Orlando, USA, May 30-June 2, 1999 p137
[22]	Chang W A, Ramakrishna R S 2002 IEEE Trans. Evol. Comput. 6 566
[23]	Nanayakkara S, Srinivasan D, Lup L, Xavier G, Elizabeth T, Ong S H 2007 IEEE Congress on Evolutionary Computation Singapore, September 25-28, 2007 p4469
[24]	Davies C, Lingras P 2003 Eur. J. Operat. Res. 144 27
[25]	Yang S, Cheng H, Wang F 2010 IEEE Trans. Syst. Man Cybernet. C 40 52
[26]	Charles J S 1996 A Course in Probability and Statistics (California: Duxbury Press) p81
[27]	Holland J H 1975 Adaptation in Natural and Artificial Systems (Michigan: University of Michigan Press) p22
[28]	Thomas B W, White C C 2007 Eur. J. Operat. Res. 176 836
[29]	Bell M G H, Iida Y 1997 Transportation Network Analysis (Chichester: John Willey and Sons) p17

[1]	王超, 李绣峰, 张生俊, 王如志. 基于遗传算法的宽带渐变电阻膜超材料吸波器设计. 物理学报, 2024, 73(7): 074101. doi: 10.7498/aps.73.20231781
[2]	栾迦淇, 张亚杰, 陈羽, 郜定山, 李培丽, 李嘉琦, 李佳琪. 基于遗传算法的太赫兹多功能可重构狄拉克半金属编码超表面. 物理学报, 2024, 73(14): 144204. doi: 10.7498/aps.73.20240225
[3]	李铁军, 孙跃, 郑骥文, 邵桂芳, 刘暾东. 基于遗传算法的Au-Cu-Pt三元合金纳米粒子的稳定结构研究. 物理学报, 2015, 64(15): 153601. doi: 10.7498/aps.64.153601
[4]	常红伟, 马华, 张介秋, 张志远, 徐卓, 王甲富, 屈绍波. 基于加权实数编码遗传算法的超材料优化设计. 物理学报, 2014, 63(8): 087804. doi: 10.7498/aps.63.087804
[5]	何然, 黄思训, 周晨腾, 姜祝辉. 遗传算法结合正则化方法反演海洋大气波导. 物理学报, 2012, 61(4): 049201. doi: 10.7498/aps.61.049201
[6]	胡晓琴, 谢国锋. 遗传算法优化BaTiO3壳模型势参数. 物理学报, 2011, 60(1): 013401. doi: 10.7498/aps.60.013401
[7]	俎云霄, 周杰. 基于组合混沌遗传算法的认知无线电资源分配. 物理学报, 2011, 60(7): 079501. doi: 10.7498/aps.60.079501
[8]	汪剑波, 卢俊. 双屏频率选择表面结构的遗传算法优化. 物理学报, 2011, 60(5): 057304. doi: 10.7498/aps.60.057304
[9]	宋丹, 张晓林. 基于不动点理论的多系统兼容接收机频点选择问题的研究与遗传算法实现. 物理学报, 2010, 59(9): 6697-6705. doi: 10.7498/aps.59.6697
[10]	程兴华, 唐龙谷, 陈志涛, 龚敏, 于彤军, 张国义, 石瑞英. GaMnN材料红外光谱中洛伦兹振子模型的遗传算法研究. 物理学报, 2008, 57(9): 5875-5880. doi: 10.7498/aps.57.5875
[11]	俞阿龙. 基于遗传小波神经网络的机器人腕力传感器动态建模研究. 物理学报, 2008, 57(6): 3385-3390. doi: 10.7498/aps.57.3385
[12]	牛培峰, 张君, 关新平. 基于遗传算法的混沌系统二自由度比例-积分-微分控制研究. 物理学报, 2007, 56(7): 3759-3765. doi: 10.7498/aps.56.3759
[13]	龚春娟, 胡雄伟. 遗传算法优化设计三角晶格光子晶体. 物理学报, 2007, 56(2): 927-932. doi: 10.7498/aps.56.927
[14]	牛培峰, 张君, 关新平. 基于遗传算法的统一混沌系统比例-积分-微分神经网络解耦控制研究. 物理学报, 2007, 56(5): 2493-2497. doi: 10.7498/aps.56.2493
[15]	林海, 吴晨旭. 基于遗传算法的重复囚徒困境博弈策略在复杂网络中的演化. 物理学报, 2007, 56(8): 4313-4318. doi: 10.7498/aps.56.4313
[16]	钟会林, 吴福根, 姚立宁. 遗传算法在二维声子晶体带隙优化中的应用. 物理学报, 2006, 55(1): 275-280. doi: 10.7498/aps.55.275
[17]	保文星, 朱长纯, 崔万照. 基于克隆选择的混合遗传算法在碳纳米管结构优化中的研究. 物理学报, 2005, 54(11): 5281-5287. doi: 10.7498/aps.54.5281
[18]	王东风. 基于遗传算法的统一混沌系统比例-积分-微分控制. 物理学报, 2005, 54(4): 1495-1499. doi: 10.7498/aps.54.1495
[19]	吴忠强, 奥顿, 刘坤. 基于遗传算法的混沌系统模糊控制. 物理学报, 2004, 53(1): 21-24. doi: 10.7498/aps.53.21
[20]	王耀南, 谭文. 混沌系统的遗传神经网络控制. 物理学报, 2003, 52(11): 2723-2728. doi: 10.7498/aps.52.2723

计量

文章访问数: 9174
PDF下载量: 2646
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

搜索

留言板