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

　第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.

L:

x=U(t)

　t∈[0,1]

y=W(t)

(3)

转化之后的目标泛函如下:

a收稿日期:1999-12-27

(;(:(),,,.

274

武汉大学学报(自然科学版)第46卷

minJ(L)=

∫

L

{U(t)+W(t)+

f(t)dt∫

L

22

从定义可见,一阶邻域结构可以遍历一个与sn-1sn+1正交的直线,正态分布P满足在8上的

(4)

Markov各态遍历性,而均值在起止状态的连线上.

21/2

　[U′(t)+W′(t)]}dt=

L可用节点序列分段线性近似表示,以动态规划的观点来看,路径的搜索是多级决策的过程,由于相邻节点间的线性转移具有Markov无后效性,因而各个节点形成了状态Si=(xi,yi).x与y形成2维Euclidean状态空间.含N个元素的节点序列形成状态序列,它到解空间即路径集合是单射,即长度为N的有序状态序列对应#在状态空间上的投影折线L.

3　模拟退火算法

前面所定的邻域结构已经具有邻域搜索类算法的特性.本文将以目前最成功的启发式邻域搜索算法——模拟退火算法为基本框架,应用于对曲面最短路径的求解.关于模拟退火算法本身的说明以及理论分析,可以参见文献[3～5].

模拟退火算法的基本步骤是:产生新解—→计算目标函数差—→判断是否接受新解—→接受/放弃新解,形成迭代过程.

3.1　初始解的产生

采用线性生成方式,即在起止状态间线性地插入若干等距状态.对于曲面最短路径这种数据可视性与经验性较强的问题而言,也可以考虑人工粗略确定一条看似最优的积分路径作为初始解,让算法再作细致的调整工作.

状态序列的个数N由实际问题确定.如电力线路架设问题中,N的选取要使相邻状态间的Euclidean距离在100m左右的数量级.3.2　新解的产生机制

在当前解的N个状态中以相等概率选取一个sn,以公式(5)的方式确定其邻域结构{sn,R},并由此产生一个新的søn,形成新的状态序列.

计算目标函数差:sn与søn同属于邻域结构{sn,R},计算优化指标中的被积函数沿两条由不同状态序列sn-1→sn→sn+1与sn-1→søn→sn+1确定的路径积分所形成的差值d:d=(

s

2　邻域结构

本文所指的邻域结构,采用了模拟退火算法中的术语[3～5].将演化计算中的各种变异算子也视作邻域结构,因而可以统一模拟退火算法与演化计算中共同的思想——摄动.

从本文提出的泛函优化模型可见,初始状态与终止状态是确定的.从动态规划的观点来看,这是一个从正反两个方向都可以进行搜索的问题.对状态序列某个子列的局部优化,是在整体关联性不受破坏的前提下对整个状态序列的优化.有了局部优化的思想,便可以引入邻域结构的概念,将局部优化视做某个邻域结构中寻优的过程.这样一来,在不破坏状态列整体关联性的前提下,使之得到局部优化.更进一步,本文所定义的邻域结构是随机并具有Markov各态遍历性的,因而可发展为真正有效(全局搜索、局部收敛)的邻域搜索类算法.

在公式(4)中,被积函数f(t)半正定,在确定的积分曲线上,泛函指标会随弧长增长.显然,在更短的弧长更可能得到较小的泛函指标.当曲面复杂时,不可能对最优路径有一个整体的了解,那么线性地连接相邻状态得到的路径正好是最优或者接近最优的可能性较大.用概率分布来描述这一个事实如下.

定义　若

n+1n-1

+NE={AûPs=sn-1+2

′

n[2]

∫+∫)f(t)dt-(∫+∫)f(t)dt

n-1

sø

n

søs

nn-1

s

n-1n

sss

nn-1

(6)

由于新状态的产生只改变了由sn-1→sn+1这一子列确定的积分路径,而对其它积分段没有影响,因而d就是新解与旧解之间的目标泛函差值.3.3　退火温度的确定

初始温度的选取对模拟退火算法的多样性有重要影响.在曲面最短路径问题中,可预先目测曲面起伏程度(当然也可以求高度的方差).对于平坦的曲面,初始的线性生成解已经很接近全局最优了,为了使其只作局部微调,对恶化解的接受概率应相应减,.,

sn+1+

n-1n+1

+NE,sn′∈A}(5)2

则称二元集{sn,R}为状态转移sn-1→sn+1的一阶邻域结构.

(5)式中E为单位向量,E的方向与sn-1sn+1正交,1+

第3期　　　　　　　黄樟灿等:基于模拟退火算法的曲面最短路径求解

275

全局最优路径可能是难以想象的,为了使其跳出线性生成初始解的局部最优,对恶化解的接受概率应相应增加,即采用相对较高的初始温度.

图1中,实点表示新产生的优化解,圆圈表示被接受的恶化解.

用龙贝格(Roumberg)法计算积分值运算的结果如图2与图3,它绕过了崎岖不平的地带,从而得到了比直线更优化的路径.常用的在两点间直接连线的方式确定的路径的长度为L1=197.43,而求解出的最优路径长度为L2=171.43,优化率K为:

K=

12

×100%=13.2%L1

4　应用实例

本文研究与求解的实例采用的搜索空间D为100×100单位的正方形区域,用易于表述的解析函数模拟实际地形,以便分析引用.曲面也就是地形由如下函数构造.

h

z(x,y)=

∑hiõ-i=1

ci

ui

p

i

-(7)

ci

vi

上式的各参数如表1.

q

i

表1　模拟地形的参数

nxcycpquvh

125871.5

264282

33453322113-32

477922262538

59455331114

665241.51.5139

71511321113

89314331311

图2　运算结果的等高线示意图

1.53.5302057

651219

24-22-14-17

给定的起止点为s0=(x0,y0)=(5,

92),sf=(xf,yf)=(95,9).

本文的实验参数为:内插点N=6,初始温度t0

=300,迭代次数k=300次,变异方向由单位向量E控制,变异程度由纯量N确定.

模拟退火过程的收敛曲线如图1.

图3　运算结果的三维示意图

运算所得的最优解函数的节点序列如表2.

表2　运算所得的最优解函数的节点序列SKS0S1S2S3S4S5S6

1X5.000014.220532.420051.064564.768073.455185.3029Y92.000074.932469.615867.983755.236438.912223.5622　　Z29.186627.954116.16935.07840.37088.00396.3100

276

武汉大学学报(自然科学版)第46卷

5　结　论

从上面的数值仿真实例可见,本文提出的算法能够求出比直接连线方法更好路径.更重要的是,由于算法的良好收敛性,在计算过程的后期,其微调能力是人工方法所无法比拟,如果将其用于公路、铁路建设,电力、通信线路,输水、输油管道的架设等实际问题中,可以起到立杆见影的效果,将节省大笔开支.不仅如此,当这些工程完工之后,由于路径缩短,车辆的耗油、耗时,电力传输的损耗都将相应减少,因而对将来还会产生深远的影响.

本文提出的方法可以有效地解决形式各异的曲线优化问题,其应用远非局限于实例中的问题,作为求解曲线优化问题的一般方法,具有广泛的应用前景.本文虽未细致地研究约束的处理,但对邻域结构给出的一般定义,已经为约束的处理提供了一条可行之路.

参考文献:

[1]　CHENSi-duo,HUANGZhang-can.Algorithmofthe

ShortestPathConstraints.

onCurvedSurfaceJournal

of

Wuhan

under

SlopeAutomotive

PolytechnicUniversity,2000,22(1):84-87(Ch).[2]　PANZheng-jun,KANGLi-shan,CHENYu-ping.

Evolutionary

Computation.

Beijing:

Tsinghua

UniversityPress,1998(Ch).

[3]　KANGLi-shan,XIEYun,YOUShi-yong,etal.

SimulatedAnnealingAlgorithm.Beijing:SciencePress,1994(Ch).

[4]　AartsEHL,KorstJHM.SimulatedAnnealingand

BoltzmannMachines:A

StochasticApproach

to

CombinatorialOptimizationandNeuralComputing.NewYork:JohnWileyandSons,1989.

[5]　VanLaarhovenPJM,AartsEHL,Simulated

Annealing:TheoryandApplications.Holland:D

ReidelPaslishingCompany,1987.

SolvingtheShortestPathonCurvedSurfaceBasedonSimulated

AnnealingAlgorithm

HUANGZhang-can,CHENSi-duo,KANGLi-shan,CHENYu-ping

1

2

3

3

(1.DivisionofBasicScience,WuhanAutomotivePolytechnicUniversity,Wuhan430070,China;2.SchoolofElectronicsandInformation,WuhanAutomotivePolytechnicUniversity,Wuhan430070,China;

3.StateKeyLaboratoryofSoftwareEngineering,WuhanUniversity,Wuhan430072)

Abstract:Byanalyzingtheintrinsicrelationshipofthenodalpointseriesofthepath,theneighborhoodstructurecorrespondingtotheShortestPathonCurvedSurfaceProblemispresented,soastomaketheproblembesetfledbylocaltuning.WiththeframeworkofSimulatedAnnealingAlgorithm,thestochasticalgorithmisproposed.Thenumericalsimulationisgivenattheend.

Keywords:shortestpathoncurvedsurface;neighborhoodstructure;heuristicprobabilitysearch;simulatedannealingalgorithm

本文来源：https://www.bwwdw.com/article/c39m.html