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

时间：2025-04-23

274

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

　　minJ(L)=

∫

{U(t)+W(t)+

f(t)dt∫

从定义可见,一阶邻域结构可以遍历一个与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=(

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ø

søs

nn-1

n-1n