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

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