P?[1?(1?h)?E/T]1/(1?h) (2-6)
上述式子中还存在着如下的关系式:?E?E(m)?E(m0),而(2-6)中的h表示的是实数参量。倘若h?1时,那么又有如下的函数式:
P?exp(??E/T) (2-7)
上述式子(2-7)是常规性的模拟退火算法有关接受概率的函数式,是函数式(2-6)的特殊情况。
2.1.3退火计划
有关退火计划的函数式如下所示:
T(k)?T0exp(?ck1/N) (2-8)
上述式子中的T0所表示的是最初温度的参量;k所表示的是迭代次数参量;
c所表示的是已知的常量;N所表示的是等待反演参量的数量。同时我们还能够将上述式子(2-8)写为如下的式子:
T(k)?T0?k1/N (2-9)
上述式子中的,a所表示的是温度的衰减率参量,且一般其数值界定的范围在[0.7,1.0]在具体运用时,一般选择0.5抑或是1.0的数值来取代上述式子(2-9)中的参量1/N。
在VFSA环境下,最后的式子(2-4)以及(2-5)会对时下的模型产生扰动之后出现新的模型,其接收的式子依照上述的式子(2-6)来开展,且依据式子(2-9)来进行缓慢地减温环节。
2.2 VFSA机理分析
因为VFSA本身拥有其他方法不曾具有的优势,因此,在很多学者的分析中,都采用了该方法来展开研究。因而,借助于VFSA工具的目的是在原先的基础上加以改观。在大多数情况下,SA本身具有鲜明的优越性能,是一类全局范围内的优化方式,其内在的原因在于退火计划以及模型扰动模式等诸多元素有机地整合。VFS A也属于这种类型。
VFSA的迅捷特点在于该退火方法应和快速降温有内在的关联性。我们从以
上(2-8)以及(2-9)的例子中能够发现,温度参量T和迭代次数参量k之间存在着一定的关联性。根据分析可知,二者之间存在着负相关的关系。下图2-2便是这二者变量之间内在对应的变化示意图。其中,图2a所表示的是式子(2-9)中的参量N的变化情况(N所表示的是等待反演参数的数量),其他的参量维持原状。下图2b则代表的是上述式子(2-9)中的参量?的改变情况,其涵义指的是温度的衰减率,其他的参量也维持原状。就实际的检测结果可知,无论哪类情况,VFSA在降低温度方面都是很明显的。该方法的优势如下:在温度偏大的情况下,能够获取偏大的能量值,并挣脱局部化的极值,进而使得目下的状况符合含纳最优解数值的最好的空间范围内。如若温度不高,那么可以获取的几率则马上递减,因为所受掌控的退火温度偏低,那么达到相应的时期之后,算法所匹配的能量状况应该小于当下的能量数值。因而,能够接纳状态的能量数值,就其所处的低温度的环境而言,大多数情况下呈现出递减的趋势,一直延迟到最少能量的出现——此时,有关函数的最优解便出现了。而温度等于零的环境下,基本上无法接纳,最多只可以接纳极少的能量,此时,算法便变成局部性的搜索。VFSA的退火偏快时,为了使得该模拟退火方法名副其实,倘若所处的环境温度偏大,那么应该使得扰动环境下大致遍历全部解的空间,从而找出含纳能量数值最小的最优解空间。因而,在温度偏大时,就要关注模型扰动情况下的分布现象,而这一点在诸多的算法体系中显得更为关键,在本论文中要使得模拟退火挣脱出局部性的极值,其所处的环境应该是高温状态之中。
图2-2 VFSA的温度衰减示关系意图
我们通过举例来加以分析。引入2个不同的状况,依次用x、y参量来加以表示,且定义域的范畴在[-3.3],它在高温度环境下的模型情况的次数为15,且用+来加以表示。为了达到方便对比的目的,截取基于随机数发生器环境下的相同定义域内的状况,其次数也一致,用·来加以表示。具体情况可参见下图2-3所示。
图2-3 高温环境下VFSA结构模型的布局图示
从上述图2-3可知,在高温环境下,“+”事实上并未游遍全部的定义空间,而是局限于图中偏于左下方的较小的范围之中,而借助于随机数发生器所产生的相同次数的“·”布局状态则相对均匀化些,大多数在定义域空间中均匀地分布着。需要留意的是,上述图内所标示的2种模式的初始情况是相一致的。该情况亦能够借助于相关的理论来展开相关的研究。借助于函数式(2-4)以及(2-5)可知,该扰动方式实质性而言,具有鲜明的局部化特点,即高温时范畴拓展,而低温环境下则日趋减少,而新模型中的参量mi?出现的情况是基于当下已有模型mi的四周经由扰动之后出现的;上述函数式中的yi则等同于1个系数,其数值大小界定了模型扰动所对应的范畴。很明显地,yi表示的是比较特别的随机数,其具体的数值和温度参量T以及迭代参量k之间存在着紧密的关联性;更为关键的是扰动现象和mi的具体方面有内在的关联性,该扰动方式界定了处于高温环境下有
限性次数的扰动无法促使状态可以游遍全部的概念范围。因而,就游遍空间的性能角度而言,高温环境状态要比随机数发生器弱一些。此时,也会对模拟退火的演算功效产生一定的退化后果。主要的棘手之处在于:演算前高温的具体界定并不容易。因为,温度的偏高抑或是偏低均会对演算的方法及其效率产生干扰。
接下来我们研究处于低温环境中该退火算法的扰动特点对定位最优解精确度所产生的作用。因为模型扰动所依据的方式为上述式子(2-4),因而扰动特点和该函数式的系数yi存在着紧密的关联性,同时该参量亦和而mi、T与k等参量之间存在着紧密的关联性。为了更好地研究内在关联性,我们借助于下图2-4来加以说明。
图2-4 VFSA内的参量k以及参量yi的内在关联性
从上图2-4可知,该案例有效地勾画了参量k和参量yi内在的关联性,也描述了在温度递增情况下相关的模拟退火示意图。将这二者的示意图对比之后会发现,该模拟退火模式下yi的改变并不明显,当处于低温情况下,yi才貌似出现振荡幅度趋于变小的态势。偶尔亦会出现明显的振幅情况。表明低温下扰动后的模型并非都在当前模型周围,实际上与当前模型有一定的差距。该低温环境下的模型扰动特点在一定程度上有利于求得最优解。说明低温环境下扰动的范围比较地大,而经由扰动之后该模型可以被接纳的概率势必出现减少的后果,进而对寻优效率产生一定的影响,最后影响最终解的精确度数值。
2.3改进的模拟退火算法
从上面的分析可知,我们可以发现,VFSA算法主要有如下的2个关键特征:其一,高温环境下,因为模型扰动模式比较地特别,游遍解空间的功能要弱于随机发生器,也即模型扰动的幅度有关的因素很多,同时整体上而言也并不大;其二,低温环境下,通过扰动方式之后,相关的模型并不是全部处于当下模型的四周,也就是出现了扰动幅度偏大的情况。上述2点影响该算法的效率不怎么高,也会在一定程度上影响解的精度。
可喜的是,上述的探讨过程也含纳了改进VFSA算法的路径:当处于高温环境时,采用全局扰动模式替换当下的扰动模式扰动方式;当处于低温环境时,只须针对函数式(2-5)的参量yi做好相应的制约条件改变即可。
其改进的大致做法是把该VFSA分为2个步骤:在第一个步骤中,使用的方法是较高的初始温度和VFSA 的退火计划,模型作全局随机扰动,以搜索并锁定最优解区间;过程二,采用较低的初始温度和新的退火计划,模型作局部随机扰动(在当前模型周围),以在锁定最优解空间后,由于搜索空间变小,能提高模型接受效率.新的退火计划将作适当的回火升温,这样如果当前模型没有跳出局部极小值区间,适当的升温可以使之再一次跳出,使最终解更可靠.退火温度与模型扰动方式的改进,二者密切相关.由于改进是基于VFSA的,故称之为改进的VFSA,简称MVFSA.需要指出的是,上述的改进是对退火及模型扰动方式的改变,而SA 的广义Boltzmann—Gibbs分布接受概率及Metropolis准则并没有改变.SA之所以为全局搜索算法,其接受概率方式及Metropolis准则是其精髓,MVFSA并没有影响其精髓,而是使得该二者更具效率,寻优精度更高,算法更接近实际应用.笔者目前已经对一些诸如应用MVFSA 最短路径分析、地球物理中的反演问题等用SA作一些具体的研究,并且取得一定的进展.
算法操作是算法实施优化进程的关键步骤,设计优良的操作对改善算法性能和提高算法效率具有重大作用。从搜索结构上考虑,邻域函数结构(状态产生方式)、状态更新方式和收敛(或稳定)判据最重要,关健参数的控制可归入参数选择的研究内容。邻域大小和结构的选择应从计算效率考虑,保证侯选解在一定程度上遍布全部的解空间。状态更新方一式的选择可使算法具有避免局部极小的能力。