基于模拟退火算法的曲面最短路径求解

时间：2025-04-23

　第46卷　第3期　　　　　　　　　　　　武汉大学学报(自然科学版)　　　　　　　　　2000年6月　　　　　　　　　　　　J.WuhanUniv.(Nat.Sci.Ed.)　　　　　

Vol.46　No.3　June,2000,273～276

文章编号:0253-9888(2000)03-0273-04

基于模拟退火算法的曲面最短路径求解

黄樟灿1,陈思多2,康立山3,陈毓屏3

(1.武汉汽车工业大学基础课部,武汉430070;2.武汉汽车工业大学电信学院,武汉430070;

3.武汉大学软件工程国家重点实验室,武汉430072)

　　摘　要:通过对路径的节点序列内在关联性的分析,提出了适合曲面最短路径问题的邻域结构,使整段路径的优化问题能够通过局部调整得以实现.将模拟退火算法的框架引入路径寻优中,提出了解决曲面最短路径的随机搜索算法.最后给出了数值仿真实例.

关　键　词:曲面最短路径;邻域结构;启发式概率搜索;模拟退火算法中图分类号:TP301.6　　　文献标识码:A

0　引　言

在给定曲面上的两定点间求沿曲面的最短路径,是理论与实际领域都十分关注的问题.在公路、铁路的布局,电力、通信线路,输水、输油管道的架设等大规模的工程规划问题中,能否求得良好的路径,将对整个工程的成本以及投入运营后的开支产生重要影响.由于曲面最短路径问题表述简单而意义重大,数学史上对其有过长期的研究,其一般的思想是用变分方法求得解析解.这些算法往往极度依赖于描述曲面的函数形式,鲁棒性一般极不理想,而且往往难于处理约束.然而,现实的问题,特别是地形之类的曲面极为复杂,且由观测数据拟合而成,远非经典数学研究的那些性态优良的曲面可比.由于没有通用的、鲁棒的数值算法,工程实际中往往是凭借经验,或者在平面上用直线连接形成路径的投影线[1].近年来,各种新兴的启发式概率搜索算法层出不穷,并且在函数优化、参数估计、组合优化等方面取得了可喜的成功[2].然而,在曲线优化方面,目前国内外还很少有人尝试用概率搜索方法加以求解.鉴于此,本文首次将先进的启发式概率搜索思想引入路径寻优问题中.

本文通过对节点序列内在关联性的分析,提出

了适合邻域搜索类算法实施的邻域结构,使得曲面最短路径的求解在本质上可以应用演化思想优化.本文以度量的观点分析了优化指标,提出了路径的邻域结构,结合典型的邻域类搜索算法——模拟退火算法的框架,提出了曲面最短路径一般的算法.最后给出了一个数值仿真的实例.结果证明,这种算法的效果非常令人满意,具有重大的现实意义.

1　曲面最短路径问题的最优化模型

约定曲面2:

z=z(x,y)　(x,y)∈D　D为凸集

(1)

　　求曲面上两定点(x0,y0,z0)与(xf,yf,zf)间沿曲面2的最短路径#.#在XOY平面上的投影曲线为L.即有:

minJ(#)=

ds∫

(2)

　　由于等式(1)中,z为x及y的单值函数,故x

与y张成状态空间,本文将状态空间作为搜索空间.所要优化的对象是XOY空间上的一条投影曲线L.

x=U(t)

　t∈[0,1]