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

第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