模拟退火策略（共8篇）
模拟退火策略 篇1
细菌觅食优化算法(Bacterial Foraging Optimization algorithm,BFOA)是一种源于微生物世界的新型仿生类智能优化算法[1]。它是由Kevin M.Passino在对人类肠道中真实大肠杆菌的觅食行为研究的基础上提出的一种全局启发式算法。目前已在电器工程与控制、滤波器问题、人工神经网络训练、模式识别、调度问题等方面得到成功应用。但也存在一些缺点,如算法在趋向性操作中容易陷入局部极值、求解精度不高、稳定性较差。
为了提高BFOA的性能,人们对算法的改进进行了研究,主要集中在算法参数和算法融合两个方面。梁艳春等人对趋向性操作进行改进提出了两种新的搜索策略:基于个体信息和基于群体信息的搜索策略;陈瀚宁等人分析步长C对BFOA局部开采和全局探索能力的影响提出自适应趋向性步长,并利用步长C的特点提出了协同细菌觅食算法[2];储颖等人针对细菌觅食优化收敛速度慢的特点,提出一种快速细菌群游算法[3],加强了算法在优化初期的全局搜索能力以及优化后期的局部搜索能力;Dasgupta和Das等人理论分析了使用自适应机制的步长对算法收敛性和稳定性的影响[4],但是他们的理论分析是基于一定的条件假设,只考虑在一维的连续空间中一个单独粒子进行的趋向性操作;Mishra提出用Takagi-Sugeno型模糊推理机制选取最优步长,该算法被称为模糊细菌觅食算法,但是,模糊细菌觅食算法的性能完全依赖于隶属函数和模糊规则参数的选择[5]。Biswas等人结合BFOA和PSO形成了混合算法—细菌种群优化(BSO)[6],有效地平衡了局部开采能力和全局探索能力,但是该算法在细菌的趋化算子内嵌入粒子群方法,赋予细菌对全局极值的感知能力,所有细菌通过与全局极值的对比,根据粒子群迭代公式更新细菌位置,此时算法中的趋化算子并没有起到作用;Dasgupta等人将差分进化算法中的交叉与变异操作引入到BFOA,提出了一种混合全局优化算法[7],虽然增加了种群的多样性,但同时也容易导致群体中优秀个体的缺失。
本文将模拟退火策略引入到基本的BFOA,提出了一种基于模拟退火策略的细菌觅食优化算法。该算法在趋向操作完成后,采用模拟退火策略对全局最优个体进行优化,提高算法的优化精度和稳定性,利用模拟退火算法的概率突跳性来避免陷入局部极值。
1 基本细菌觅食优化算法
1.1 BFOA的基本原理
BFOA模拟的是大肠杆菌在人体肠道内吞噬食物的行为,该算法主要有三大基本操作:趋化操作、复制操作、迁移操作。一个优化周期主要由3个部分组成,它们分别是趋化过程(Chemotaxis),繁殖过程(Reproduction),迁徙过程(Elimination and Dispersal)。
1)趋化过程
趋化行为是指细菌向含有丰富营养的区域聚集的行为,包括翻转(Tumble)和前进(Swim)两种模式。趋化行为使得算法中的细菌具有连续局部搜索的能力。细菌的趋化行为如图1所示,其中(1)为细菌的前进行为,(2)为细菌的翻转行为。
BFOA算法的趋化过程,可以描述如下,设(j,k,l)表示细菌i的位置,则在细菌趋化过程中细菌的运动可以表示为:
公式(1)中,j表示第j代趋向性操作循环,k表示第k代繁殖循环,l表示第l代迁徙循环,C(i)>0为细菌的趋向性行为步长,公式(2)中表示随机方向上的向量,是随机的翻转角度。
2)繁殖过程
趋化过程结束后,为了提高搜索的精度和缩短搜索时间,细菌进入繁殖过程,这一过程是参考了某一时间区域内细菌的整体表现后,执行的“优胜劣汰”行为,是以趋化周期内的细菌能量(适应值累加和)为标准,选择繁殖能量高的半数细菌来代替较差的另一半。
单个细菌的健壮函数表示为:
公式(3)中Jhealth表示细菌i在第j次趋向操作,第k次复制操作,第l次迁徙操作的健康值,Jhealth的值越大,细菌的健壮性就越差。淘汰的细菌个数表示为:
公式(4)中S表示细菌种群数,Sr表示淘汰的细菌数。
3)迁徙过程
在复制操作完成之后,细菌按照一定的概率p被随即分配到解空间中去,该操作就是迁徙操作。迁徙操作避免了细菌陷入局部极值,从而提高了算法的全局寻优能力。
1.2 BFOA流程
BFOA的流程图如图2所示。
2 模拟退火算法
模拟退火算法的思想最早是由Metropolis等提出的,1983年Kirkpatrick等将其用于解决组合优化问题[8]。该算法的出发点来源于工程中固体物质的退火原理,模拟了高温金属降温的热力学过程。从某一较高温度出发,伴随温度参数的不断下降,逐渐产生新的状态,结合概率突跳性在解空间中随机寻找目标函数的全局最优值,最终固体内粒子逐渐有序,达到平衡态。模拟退火算法在搜索过程中的概率突跳能力可以有效避免算法陷入局部极值,从而高效快速的找到全局最优解[9]。算法优化流程如下:
1)随机产生初始状态s=s0,确定初始温度t=t0,令k=0;
2)若算法终止条件未满足,则重复以下步骤:
(1)若抽样稳定准则未满足,则重复如下步骤:
(a)由当前状态s产生新的状态sj;
(b)若min{l,exp[-(Jsj-Js)/tk]}≧rand[0,1],则s=sj;否则保持当前状态不变,其中Js为状态s的目标值;
(2)退温操作tk+1=f(tk),令k=k+1;
3)输出算法搜索结果。
3 改进的细菌觅食优化算法
3.1 对优化变量进行越界处理
在优化过程中,当优化变量超过搜索区间时,对其采用撞壁法进行处理,以保证变量满足边界约束条件。
3.2 基于模拟退火策略的细菌觅食优化算法(SA-BFO)
3.2.1 SA-BFO的主要思想
BFO算法容易陷入局部极值,收敛精度低。SA算法是通过控制初温和温降过程来控制算法的搜索过程,在高温时,算法具有较高的突跳性,可以避免陷入局部极值;在低温时,有较好的保优性能,增强了算法的搜索能力。将细菌觅食优化算法和模拟退火算法有效的结合起来,用模拟退火算法来处理细菌觅食优化算法的早熟收敛和精度不高的问题。首先对每个个体进行趋向性操作,然后用趋向操作搜索到的全局最优个体进行模拟退火搜索,根据Metropolis准则接收新个体,并用搜索到的最优个体作为全局最优个体位置,最后执行复制操作和迁移操作。从而引导细菌快速跳出局部最优,加快收敛速度,提高算法的精度。
3.2.2 SA-BFO流程
SA-BFO的流程如图3所示:
4 仿真实验
4.1 测试函数
为了测试SA-BFO的性能,选取以下典型函数进行仿真实验,并且与标准的BFOA进行比较。
其中函数f1、f2、f3为单峰函数,f4、f5、f6为复杂的多峰函数,容易陷入局部极值,很难找到全局最优。为了测试SA-BFOA的性能,对上述六个函数分别采用基本的BFOA和SA-BFOA求解其最小值,进行30次实验,测试指标包括平均优化值、标准差和平均运行时间。其中平均优化值是指30次优化搜索结果的平均最优值,反映了在给定迭代次数下算法所能达到的精度;标准差反映了算法的鲁棒性和稳定性,标准差越小,算法越稳定;平均运行时间是指算法运行1次的平均时间,反映了算法的求解速度,平均运行时间越小,算法的求解速度越快。
4.2 参数设置
为了保证算法的可比性,对基本细菌觅食优化算法设置相同的参数,种群数为100,维度为100,趋化次数Nc=10,趋化步长c=0.2,最大前进步数Ns=4,复制次数Nre=10,迁移次数Ned=2,迁移概率Ped=0.25。模拟退火算法中的参数设置为:链长MarkovLength=50,温度衰减参数Decay Scale=0.95,步长因子Step Factor=0.02,初始温度Temperature=100。
4.3 实验结果
表1为BFO和SA-BFO优化6个测试函数的实验结果。从表1可以看出,不管是单峰函数还是多峰函数,SA-BFOA在平均最优值和标准差方面都优于基本BFOA,其中对于单峰函数f1、f2、f3,SA-BFOA的优化效果明显优于基本BFOA,对于多峰函数f4、f5、f6,SA-BFOA的优化效果略优于基本BFOA,表明SA-BFOA的求解精度和稳定性都优于基本BFOA,但是,由于在SA-BFO算法中加入了模拟退火搜索,所以,SA-BFOA的平均运行时间明显大于基本BFOA,运行速度较慢。
5 结束语
将退火策略引入基本细菌觅食优化算法中,提出了一种基于退火策略的细菌觅食优化算法。该算法利用模拟退火算法的概率突跳性来避免陷入局部极值,采用模拟退火策略对全局最优个体进行优化,提高算法的优化精度和稳定性。实验结果表明,改进算法具有更好的求解精度和鲁棒性,但是运行速度较慢,有待在后续研究中改进并将其应用于实际工程优化问题中。
摘要：针对标准细菌觅食优化算法(BFOA)求解精度不高、稳定性较差、容易陷入局部极值的问题,提出了一种基于模拟退火策略的细菌觅食优化算法(SA-BFO)。该算法在趋向操作完成后,采用模拟退火策略对全局最优个体进行优化,提高算法的优化精度和稳定性,利用模拟退火算法的概率突跳性来避免陷入局部极值。仿真实验结果表明,改进算法比标准细菌觅食优化算法具有较高的优化性能。
关键词：细菌觅食优化算法,模拟退火,概率突跳性,精度,稳定性
参考文献
[1]麦雄发,李玲.混合PSO的快速细菌觅食算法[J].广西师范学院学报,2010,4(27):91-95.
[2]Chen H,Zhu Y,Hu K.Cooperative bacterial foraging optimization[J].Discrete Dynamicsin Natureand Society,2009,3(5):635-656.
[3]储颖,靡华,纪震,等.基于粒子群优化的快速细菌群游算法[J].数据采集与处理,2010,25(4):442-448.
[4]Das S,Dasgupta S,Biswas A,et al.Onstability of the chemotactic dynamicsin bacterial foraging optimization algorithm[J].IEEETransac tionson Systems,Man,and Cybernetics-PartA:Systems and Humans,2009,39(3):670-679.
[5]Mishra S.Hybridleast-square adaptive bacterial foraging strategy forharm onicestimation[J].IEEEProceedings-Generation,Transmission,Distribution,2005,152(3):379-389.
[6]Biswas A,Dasgupta S,Das S,et al.Synergy of PSO and bacterial foraging optimization-Acomparative study on Merical benchmarks[J].In novationsin Hybrid Intelligent Systems,2007,26(13):44(3):255-263.
[7]Dasgupta S,Biswas A,Das S,et al.Automatic circled etectiononimages with an adaptive bacterial foraging algorithm[C],2008Genetic andEvolutionary ComputationConference(GECCO 2008),2008,13(5):1695-1696.
[8]魏延,谢开贵.模拟退火算法[J].蒙古师范高等专科学校学报,1999,1(4):8-11.
[9]王联国,洪毅,赵付青,等.一种模拟退火和粒子群混合优化算法[J].计算机仿真,2008,25(11).
模拟退火策略 篇2
线性最小二乘估计在对非线性函数进行线性近似的.过程中会产生模型误差,而一些非线性参数估计方法可能因为函数复杂而难以求导,法方程系数矩阵秩亏或呈病态矩阵时难以求解,非线性迭代解法有时对初始值的选择存在依赖性,不恰当的初始值会导致迭代无法收敛.针对这些问题,引入了模拟退火算法,介绍了该算法的基本原理、计算步骤和收敛性,并以3个控制网平差应用为例,说明该算法具有无需求导求逆,简洁实用,易于编程等优势,并能实现全局优化,获得高精度的平差结果.
作 者：邓兴升 王新洲 DENG Xing-sheng WANG Xin-zhou 作者单位：邓兴升,DENG Xing-sheng(武汉大学,测绘学院,湖北,武汉,430079;武汉大学,灾害监测与防治研究中心,湖北,武汉,430079)
王新洲,WANG Xin-zhou(武汉大学,测绘学院,湖北,武汉,430079;武汉大学,灾害监测与防治研究中心,湖北,武汉,430079;山东科技大学,地球信息科学与工程学院,山东,青岛,266510)
模拟退火算法及改进研究 篇3
模拟退火算法是一种适合解决大规模组合优化问题的算法,特别是在现代的计算机科学、图像处理、超大规模集成电路设计、生物学等科学领域中的组合优化问题,如传统方法难处理的NP完全问题(Nondeterministic polynomial Complete problem)和TSP货郎担问题(Traveling Salesman Problem)。模拟退火算法(Simulated Annealing,SA)最早的思想是由Metropolis在1953年提出,并由Kirkpatrick、Gelett等引入组合优化领域。SA算法特别适合并行计算,描述简单、初始条件限制少、使用灵活且运行效率高,所以被广泛地运用。
1 模拟退火算法基本原理
模拟退火算法源于对固体退火降温过程的模拟,采用Metropolis准则,是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性,是局部搜索算法的扩展,是基于迭代求解策略的一种随机寻优算法,从理论上来说,它是一个全局最优算法。
模拟退火算法其物理退火过程分为三个阶段:
(1)加温阶段。加热时,随着温度升高,固体粒子运动增强,其偏离平衡位置会越来越大。当温度达到一定高度,有序固体熔解为无序液体,从而消除系统中原来可能存在的非均匀状态。
(2)平衡阶段。退火过程中系统的每一温度要达到平衡状态,系统状态的自发变化遵循热力学定律,总是朝着自由能减少的方向进行,当系统自由能最小时,系统达到平衡。
(3)冷却阶段。随温度降低,粒子运动减弱且渐趋于有序,系统能量下降。
加温阶段即对应算法的设定初温,平衡阶段对应算法的采样过程,该过程须遵循Metropolis准则,冷却阶段对应算法控制参数下降。
2 模拟退火算法的实现过程
模拟退火算法用冷却进度表来控制算法的进程,使算法在控制参数T徐徐降温并趋于零时最终求得组合优化问题的相对全局最优解。其中优化问题的一个解i及其目标函数f(i)分别与固体的一个微观状态i及其能量Ei相对应。SA算法具体步骤如下:
(1)初始化。初始温度为T0,初始解X及目标函数f(X0),给定每个T的条迭代次数即Metropolis链长LN。
(2)对当前解X随机扰动产生新解Xn及其目标函数f(Xn)。
(3)df=f(Xn)-f(X0)。
(4)如果df≤0,则新解Xn转移为当前解。
(5)如果df>0,则根据Metropolis准则计算接受新解概率p,其中Ej,Ei分别对应f(Xn)和f(X0)产生一个在(0,1)区间上均匀分布的随机数m,如p>m,则新解Xn作为新的当前解,否则保留当前解X0。
(6)对当前温度T降温,步骤(2)至(5)迭代N次,即一个马尔可夫链LN。
(7)如果迭代终止条件满足,算法结束,则当前解为全局最优,算法结术;否则根据给定的温度衰减函数Tk产生新的温度控制参数T及链长度LN,转入步骤(2),进入下一温度点的平衡点寻优。
3 模拟退火算法的要素
(1)状态空间:即解空间,也称为搜索空间,是经过编码的可能解组成的集合。
(2)状态产生函数:应尽可能保证产生的候选解遍布整个状态空间,可采用附加扰动、随机产生、移位、平滑、边界取值等多种算子作为模拟退火的状态产生函数。状态产生函数通常产生的候选解的方式和候选解产生的概率分布两部分组成。
(3)初始温度:实验表明,初始温度越高,得到高质量解的概率越大,但算法计算的时间越长。兼顾算法求解的质量和执行效率,选择初温的方法常有:随机产生一组状态,确定最大值和最小值间的差值d,利用函数得到初温,如T0=dp,其中p为初始接受概率;或均匀抽样一组状态,以各状态的目标值的方差为初温。
(4)冷却进度表:是指从某一高温状态向低温状态冷却时的降温管理表,也即温度衰减函数,也可称为退火策略。最简单的控制参数衰减函数为:
其中,a是常取值0.5~0.9,这种退火策略是很常用。
经典的模拟退火衰减函数为:
其中,Tk为第k步时的温度值,T0为初始温度。也可以选择其它的衰减函数如等等。衰减函数应选择小的比较合适,可避免过长的马尔可夫链和迭代次数增加。
(5)Metropolis准则:Metropolis准则是Metropolis等人在1953年提出的重要性采样法,其基本思想是采样是着重选择那些具有重要贡献的状态,则可以较快地达到较好的结果。该准则是SA算法收敛于全局最优解的关键。
粒子初始状态i为当前状态,Ei是该状态的能量,即目标函数在状态i的值,某个粒子位移随机产生一微小变化,得一新状态j,其能量为Ej。如果Ej<Ei,则j状态是重要状态,如果Ej>Ei,则要根据概率p来判定,p计算公式如下:
式中,T为温度,κ为玻耳兹曼常数,exp表示自然指数。温度越小,则降温概率p就越小,温度越高,与出现一次能量差为d E的降温概率p就越大。p越大则j状态是重要状态的概率就越大。若j是重要状态,则取代i成为当前状态,否则舍弃新状态。再重复以上新状态产生过程。这种接受新状态转移的准则即为Metropolis准则。
(6)内循环终止的准则:也称为Metropolis抽样稳定准则,用于决定各温度下产生候选解的个数,该准则包括有:目标函数的平均值是否稳定;连续若干步目标函数值变化较;按一定的步数抽样。
(7)外循环终止的准则:即决定算法何时结束,主要包括:循环迭代的次数设置;终止温度的阈值设置;检验系统熵值是否稳定;检验算法收敛到最优值连续若干步保持不变。其中终止温度的设置常用的是Kirkpatrick等提出准则:在若干个马尔可夫链中解无任何变化(恶化或优化)就终止算法。迭代次数Lk的选取了冷却进度表密切相关,一般Tk小衰减,则Lk值就适当大。
4 模拟退火算法改进策略
模拟退火改进策略主要分为两大类:一是模拟退火算法自身要素的改进;二是与其它搜索算法相结合。
4.1 模拟退火算法自身要素的改进
主要包括以下几个方面的改进:(1)提升初温。算法初始化,增加升温或重升温过程,将温度适当提高,以激活各状态的接受概率,可以避免算法在局部极小解处停滞不前。(2)增加记忆功能。增加存储环节,将当前最好状态记录下来,避免搜索过程由于因根据Metropolis准则接受当前解时,可能丢掉当前遇到的最优解。(3)增加补充搜索过程。在退火结束后,把当前最优解设置为初始状态,再次执行模拟退火过程或局部性的搜索。(4)多次搜索策略。即对每一当前状态,采用多次搜索策略,取代标准SA算法的单次比较方式。
特别值得关注的是2006年陈华根,李丽华等提出基于Ingber提出的非常快速的模拟退火算法(简称VFSA)改进的MVFSA算法。该算法针对VFSA算法的两个基本特点,主要作两点改动:(1)在高温下,以模型的全局扰动方式代替目前的扰动方式;(2)是在低温下,对模型扰动进行某种约束,边扰动边逐步减小模型扰动空间,以提高新模型被接受的机率。
4.2 混合模拟退火算法
模拟退火算法与其他搜索算法相结合,是计算智能领域中的研究热点之一。80年代末,人们开始将注意力投向模拟退火与遗传算法结合。1997年王雪梅、王义和提出模拟退火与遗传算法相结合,主要思想是在传统GA的生存策略中引入Bloztman生存机制,将模拟退火算法融入遗传算法的新个体产生中,以求得最优解作为遗传的父本。
2003年李红军提出模拟退火与遗传算法相结合,此混合算法是以遗传算法为主体流程,侧重全局搜索,将模拟退火机制融入其中,侧重局部搜索,是在对每个基因个体实施一定演变而产生恶化解的设计引用了遗传算法中的变异和倒位的思想。此算法策略是从对全局最优解的搜索角度和算法的进化速度上来提高模拟退火遗传算法的性能。此混合算法比基本遗传算法在进化速度上有很大提高,且在局部搜索能力方面也有非常明显的改进,此算法还在从当前局部最优状态向其它未被搜索空间转移的能力上有了较大的实质性突破。
2007年刘敏等提出自适应的模拟遗传算法,提出自适应变异概率的概念与理论改善遗传算法的收敛速度,以解决遗传算法中变异概率取值较小且在整个搜索过程中固定不变,易陷入局部最小值的不足,杂交母体选择是以整体退火选择的方式,可克服种群早熟化,避免过早收敛。
2004年余建军,孙树栋提出将模拟退火与免疫算法混合。该混合算法是从一组随机初始解开始,先通过选择、交叉、变异等免疫操作来产生一组的新抗体,然后再对各新抗体进行模拟退火求最优解。免疫算法的全局搜索能力好,可以快速在解空间的全体解搜索出来,不会陷入局部最优级解,其局部搜索能力较差。模拟退火算法的Metropolis准则可以有限度地接受恶化解,并可以使其接受概率趋向于零,使得算法局部搜索能力强。两种算法合理融合,使算法的在全局和局部搜索能力均有提高。
2005年高尚,杨静宇等提出基于模拟退火的粒子群优化算法。粒子群优化算法(PSO)是是由kennedy与Eberhart于1995年提出的。源于对岛群捕食的行为研究,同遗传算法类似,是一种基于迭代的优化工具。基本粒子群优化算法中,粒子位置更新时未作限制,导致可能因新的位置变坏,引起收敛速度缓慢,所以对位置更新也作限制。限制的思路的主要方法是在粒子位置更新时引入模拟退火思想,限制粒子更新位置的范围,将其变坏限制在一定范围内,提高算法寻优能力。
5 结束语
模拟退火算法是一种高效、通用、易实现的优化算法,适合于解决大规模组合优化问题的通用而有效的近似算法,它有较强的局部搜索能力,但并不一定能找到全局的最优解,对参数依赖性较强。通过对模拟退火算法的要素的改进或与其它算法相结合可提高模拟退火算法的性能。近年来,模拟退火算法与遗传算法的融合在计划调度、机器人研究、软硬划分等方向均有应用。因此,今后要进一步深入研究SA与GA算法的给合,充分利用双方的优势,使其在相应的科学领域发挥更大的作用。
摘要：模拟退火算法(SA)是一种适合解决大规模组合优化问题的算法。模拟退火算法源于对固体退火降温过程的模拟,采用Metropolis准则,包括状态空间、状态产生函数、冷却进度表和Metropolis准则及内外循环终止的准则等几要素。模拟退火改进策略主要有自身要素的改进和与其它搜索算法相结合。SA与GA(遗传算法)相结合,可使算法在全局和局部的搜索能力均有提高,是近几年研究的热点。
关键词：模拟退火算法,Metropolis准则,冷却进度表,遗传算法
参考文献
[1]Dimitris Bertsimas,John Tsitsiklis.Simulated Annealing[J].Statis-tical Science,1993,1(8):10-15.
[2]许国根,贾瑛.模式识别与智能计算[M].北京,北京航空航天大学出版社,2012.
[3]李红军.模拟退火遗传算法的性能评价[J].湖南城市学院学报:自然科学版,2003,24(3):111-113.
[4]高尚,模拟退火算法中的退火策略研究[J].航空计算技术,2002,32(4):20-26.
[5]余建军,孙树栋.模拟退火免疫混合算法[C].全国第16届计算机科学与技术应用(CACIS)学术会议论文集,2004,8:823-827.
[6]高尚,杨静宇,吴小俊,等.基于模拟退火算法思想的粒子群优化算法[J].计算机应用与软件,2005,22(1):103-104.
[7]陈华根,李丽华,等.改进的非常快速模拟退火算法[J].同济大学学报:自然科学版,2006,34(8):1121-1125.
[8]王雪梅,王义和.模拟退火算法与遗传算法的结合[J].计算机学报,1997(4):381-384.
模拟退火策略 篇4
模拟退火法是一种有别于常规最优化方法的算法。该方法可以克服目标函数局部极小的限制, 从而使反演获得全局最优解, 提高反演精度和效率。本文将研究区域进行网格化划分, 并结合模拟退火法对研究区域进行三维密度界面的数值模拟。通过分析, 取得了较好的反演结果。
1 方法原理及模型构建
1. 1 方法原理
模拟退火法源于统计热力物理学, 它模拟熔融状态下物体缓慢冷却达到结晶状态的物理过程. 模拟退火反演算法的基本思想是: 生成一系列参数向量模拟粒子的热运动, 通过缓慢地减小一个模拟温度的控制参数, 使模拟的系统最终冷却结晶达到系统能量最小值的过程。模拟退火法与传统寻优方法在迭代过程中对模型的接收上有所不同。模拟退火法不但接收误差能量减小的模型, 同时也以某种概率接收误差能量增加的模型。正是这种接收模式避免了迭代搜索过程陷入局部最优解的局面。这一突破点使该方法能够收敛到全局最优解。提高反演的精度和效率, 使反演结果更理想。
1. 1. 1 模拟退火算法
据王山山等［4］, 任义庆等［5］对算法的研究: 设反演的目标函数为E ( ml) , m ∈ Ω, m为模型, Ω 为反演的解空间 ( 模型空间) 。
假定有待反演的N个模型参数表示为:m=m1, m2, …, mN, 其中每一个mi有一个对应的模型空间[mimin, mimax]。其算法步骤为:
1) 随机产生一个初始模型m0, 设定系统的初始温度T0, 模型反演空间, 最大迭代次数, 拟合误差阀值 ε 等参数。令l = 0;
2) 对第l次迭代的模型参数值ml, 计算其目标函数E ( ml) , 计算温度Tl, 在模型空间里随机地修改模型参数值为ml +1。按下式计算修改的接收概率:
式 ( 1) 中: ΔE = E ( ml +1) - E ( ml) 为目标函数的差值。
若 ΔE < 0, 表明系统朝着能量减小的方向移动, 新模型ml +1可以概率1 接收。若 ΔE > 0, 计算概率p ( ΔE) 。显然, 0 < p ( ΔE) < 1。然后在[0, 1]中产生一个随机数R。若p ( ΔE) < R。则接收新模型ml +1。否则拒绝修改模型。
3) 计算目标函数E ( ml) , 若E ( ml +1) < ε 则退出, 否则l = l + 1, 转到第二步。
对于退火过程, 要求温度T随着迭代次数的增加而缓慢降低。本文采用双曲线下降型。
式 ( 2) 中: Tl为第l次迭代的温度, T0为初始温度, l为迭代次数。
初始温度T0不能太高, 否则增加计算时间, T0也不能太低, 否则模型选取不能覆盖整个模型空间, 只是在初始模型附近选取, 不能进行全局寻优。T0只能通过实验计算得到。
对于从模型参数值ml到ml +1的修改, 我们才有对ml的每个元素进行随机扰动从而得到ml +1。即
1. 2 模型构建
设定的研究区域为400 km × 60 km × 60 km。如图1 所示, 将研究区域划分为长方体。为了减小边界条件的影响, 我们在研究区域内的最外层将单元格的大小设定为: 10 km ×10 km ×10 km。将次外层设置为5 km ×5 km ×5 km。剩下的设置为2 km ×2 km × 2 km。相同大小的单元体的密度值相同, 如图1 所示。据明圆圆［6］等对模型构造的划分: 将图1 中的任意一个单元体置于图2 中。据陈胜早［7］对单元块重力异常的计算: 设其长宽高分别为a, b, c。取每个单元体的几何中心 ( ε, η, ζ) 为该单元的坐标。ρ为该单元体的剩余密度。则该单元体对其外一点p ( x, y, z) 产生的重力异常为
式 ( 4) 中:
由重力的可加性可得所有长方体在p ( x, y, z) 处产生的总的重力异常为
2 数值模拟
设置单元体大小为10 km × 10 km × 10 km的密度为: 2 600 kg/m3, 5 km ×5 km ×5 km的密度为:2 700 kg / m3, 2 km × 2 km × 2 km的密度为: 2 800kg / m3。为了编写程序的方便, 我们将这些密度按从左上角的单元格为起点, 顺时针旋转存储为一维的数组。并且先存储10 km × 10 km × 10 km, 继而是5 km ×5 km ×5 km, 最后存储2 km ×2 km ×2 km的密度。在平行于x方向, z = 0 分别布设三条测线, 即: y = 10, y = 30, y = 50。每条测线上设置100个观测点, 观测点之间的间距为4 km。这样, 把以上这些参数带入到编写的模拟退火法程序中。可以得出以下结果。
由于反演出来的密度数值的个数较多。我们在三种不同规模的单元格中各选取一定比例的密度数值对比。如图3 ~ 图5。图3 中: 红色表示反演的密度, 上层的绿色表示的是原始模型的密度。从数值上分析, 可知: 他们的误差很小。从图4 可以更进一步地分析, 他们差值的最大值不到0. 2 g/cm3。其反演精度很高。从图5 可以更进一步地看出, 其误差百分比最大不超过6%。以此说明, MSA方法的反演精度较高。
从图6 可以看出, 此图6 中包含了三条侧线的异常曲线对比。其中, 横坐标 ( 0 ~100) 表示第一条侧线, 后面依次为第二, 三条测线。反演出的重力异常与理论异常曲线吻合得非常好。从图7 中的反演异常与理论异常的相对误差来看, 其中最大的误差为2. 4%, 其他大部分误差都在0. 2% ~1. 4% 之间, 说明反演的精度很高。
从以上的对比可以看出:
1) 从这次选用的迭代算法模拟退火法 ( MSA) 可以看出。其精度和误差精度都很高, 这主要是MSA具有一定的概率跳出局部极小值的特性。尽可能搜索全区的极小值。
2) 从设置的模型可以看出, 这次的模型考虑到边界效应。特意设置了为了减小边界效应的边界模型。其反演的精度和误差都有很大的提高。
3 结论
通过重力异常反演地球内部横向的密度结构, 对于了解地球内部的精细的地质结构有着重要的意义。对于进一步对地下资源的勘察也有着重要的意义。本文通过构建一种利于减小边界效应的网格化的地质模型, 并结合模拟退火法。通过以上数值模拟可以看出该模型的构建对减少边界效应有很好的效果。为密度反演提供了一种高效率的密度反演方法。
参考文献
[1] 肖鹏飞, 陈生昌, 杨长福, 等.油气藏潮汐重力的初步研究.石油物探, 2007;46 (2) :202—206
[2] 柯小平, 王勇, 许厚泽, 等.青藏东缘三维Moho界面的位场遗传算法反演.大地测量与地球动力学, 2006;26 (1) :100—104
[3] 张凤旭, 孟令顺, 张凤琴, 等.重力位谱分析及重力异常导数换算新方法—余弦变换.地球物理学报, 2006;49 (1) :244—248
[4] 王山山, 聂勋碧.基于波场计算的最优化速度反演.石油物探, 1994;33 (1) :81—95
[5] 任义庆, 徐仲达, 马在田.应用模拟退火法反演横波速度.石油地球物理勘探, 1996;31 (5) :677—684
[6] 明圆圆, 范美宁.鱼群算法的重力密度异常反演方法.物探化探计算技术, 2012;34 (6) :666—671
模拟退火策略 篇5
相比于传统的统计模型,基于多径电磁计算的射线跟踪(Ray Tracing,RT)信道模型作为一种最常见的确定性模型,能够较准确地预测城市微小区以及室内场景的场强覆盖[1,2]。然而,射线跟踪算法精度严重依赖于算法所需的预设参数。参数校正方法旨在求取适用于特定场景的最佳参数集,从而提高RT预测精度。
在地球物理学和遥感领域,有一类利用雷达回波求取介质电磁参数的方法称作反演。由于雷达回波无法显示地表示为参数的函数,故常采用智能搜索算法来反演参数。反演方法有很多种,包括梯度法、牛顿法、蒙特卡洛法、遗传算法、模拟退火(Simulated Annealing,SA)算法等。文献[3]提出了一种搜索步长自适应的模拟退火反演方法,相较于传统模拟退火具有较高的搜索效率;文献[4]提出一种模拟退火与遗传算法相结合的混合算法,能够在保证全局搜索能力的前提下进一步提高局部搜索能力。
RT参数校正与地球物理学的参数反演问题在数学上具有一致性,归根结底都是一种对多元目标函数的迭代最优化方法,其正向映射关系f一般多为隐式的或较复杂,难以用解析方法直接求解。因此借助较成熟的反演及其改进方法解决RT参数校正问题是可行的。文献[5,6]虽然给出了利用模拟退火算法对室内射线跟踪算法进行参数校正的实例,但并未对搜索算法本身做出改进。此处采用了一种改进的模拟退火方法作为RT参数校正方法,既能够有效避免陷入局部最小值点,又能尽量减少正演算法y=f(X)的迭代次数,提高了算法效率。
1 射线跟踪预测模型概述
作为确定性信道模型的一种,RT模型需要对特定场景进行建模,并利用射线的发射与接收对收发天线进行仿真,以及利用追踪几何路径的方法来模拟电磁波在空间的传播。关于电磁场的计算,主要是根据自由空间传播损耗公式、反射定律、一致绕射理论(UTD)等计算得出接收点的场强或时延、到达角等多径信息[1,2,7]。RT需事先设定材料电磁参数、天线参数或其他一些待定参数。确定参数后,要利用设定好的精度准则对参数进行校正以得到最适用于当前场景的RT参数[8]。
2 模拟退火算法概述
作为最优化方法,模拟退火算法具备较好的全局寻优能力,在组合优化问题和连续空间优化问题上应用广泛。设目标函数为y=f(X),X={x1,x2,x3,…}为参数集,令目标函数表示样本接收点上的实测值与RT预测值的均方误差,则目标函数表达式为:
Ci和Mi分别表示在第i个接收点处的场强计算值和场强实测值。若Xopt表示待求解的最优参数,则Xopt满足f(Xopt)=minf(X)。理想状态下,以Mi表示的实测值可以认为是在真实的参数集Xreal作用下的第i个接收点的真实场强,则有Xopt→Xreal;但实际情况要考虑到设备精度、场景模型精度、噪声等因素,真实参数集Xreal不可测,因此所求的Xopt是对Xreal的似然估计,有时称Xopt为“等效参数”。用模拟退火实现的反演过程实际上是迭代过程,总体上看,迭代总是朝着使目标函数减小的方向进行,但也允许以一定概率接受“较差”的参数集,从而具备一定的跳脱局部极值点的能力。跳变点接收概率用Metroplise准则描述:
算法通过内部最大迭代次数n和外部温度T控制迭代的进行,通过Metroplise准则判断决定迭代是否被接受,文献[5]给出了较为详尽的算法流程。
3 参数校正算法实例
为了验证参数校正算法的可行性,本节将以某室内场景为例,根据该场景实测数据[9],利用改进的模拟退火算法进行参数校正。天线发射2.5GHz窄带信号,采用软件无线电USRP设备在室内一条接收路径上(y=1.8m;x=2.8~10.3m;z=1.5m)进行了实测[9]。场景模型示意图如图1所示。
3.1 参数集的选取
校正参数前,首先需确定参数集,即找出对场强预测结果影响较大的参数。此处采用的RT算法为自主编写射线管射线跟踪方法(C#语言实现),接收球半径作为一个重要参数,用来调整接收点接收路径数量。在电磁参数方面,相关文献通过详实地研究,发现介电常数的影响远高于另外两个———磁导率和电导率[10,11,12]。因此,此处用于校正的参数为:接收球半径R、墙面介电常数ε1、地面介电常数ε2。
3.2 搜索策略
模拟退火算法针对不同的参数应设定不同的搜索范围,搜索范围又称“扰动区间”。若区间过小,则可能忽略全局最优点,导致结果不是最优;若区间过大,则由于迭代次数过多导致收敛速度变慢或降低优化精度。因此这里采用自适应调整搜索步长[3],当“跳跃”没有被接受的次数较多时,扩大“扰动区间”以方便全局搜索。对第i个参数,扰动区间用ξi表示,则采用以下方式设定区间大小:
式中,δi表示扰动区间初始范围阈值,n为内部循环总次数,na为内部循环“跳变”没有被接受的总次数,5.0为多次试验得到的经验常数。对于本例的三个参数,初始搜索区间分别为R:0.01m~0.1m;ε1、ε2:1~15。
3.3 参数校正结果及分析
针对室内场景,初始解根据经验值设定。完整的参数校正过程较耗时,共用时4h22min(调用420次射线跟踪计算,降温28次,内部循环15次)。与固定步长相比,采用自适应搜索步长的策略,在初始区间足够宽裕时,可以有效缩小搜索区间,从而在一定程度上提高搜索精度。若采用枚举法令参数+/-固定常数以遍历参数,例如R以+0.0025从0.01递增至0.1,ε1、ε2以+1从3递增至15,则共需调用18×13×13=3042次RT计算模块,运算过于耗时且搜索精度不及SA算法。参数校正结果如表1所示。
4 结束语
本文借鉴了地球物理学中较为成熟的参数反演思想,采用了自适应搜索步长的模拟退火算法作为射线跟踪的参数校正方法。通过一个室内场景实例,对2.5GHz窄带信号进行实测和仿真,根据某一路径上的少量实测数值反推出3D射线跟踪的最优参数,成功地实现了参数校正过程,且校正后的预测结果能较好地与测量值吻合。
参考文献
[1]Iskander M F,Yun Z.Propagation Prediction Models for Wireless Communication Systems[J].IEEE Transactions on Microwave Theory and Techniques,2002,50(3):662-673.
[2]Phillips C,Sicker D,Grunwald D.A Survey of Wireless Path Loss Prediction and Coverage Mapping Methods[J].IEEE Commnications Serveys&Tutorials,2013,15(1):255-270.
[3]张宇,张晓娟,方广有.大尺度分层介质电特性参数的反演方法研究[J].物理学报,2013,62(4):1-5.
[4]宋欢,胡耀垓,赵正予,等.基于混合遗传算法的斜测电离图参数反演[J].地球物理学报,2014,57(3):703-714.
[5]Priebe S,Jacob M,Kürner T.Calibrated Broadband Ray Tracing for the Simulation of Wave Propagation in mm and Sub-mm Wave Indoor Communication Channels[C].European Wireless 2012,Poznan,Poland,2012:1-10.
[6]Priebe S,Kannicht M,Jacob M,et al.Ultra Broadband Indoor Channel Measurements and Calibrated Ray Tracing Propagation Modeling at THz Frequencies[J].Journal of Communications and Networks,2013,15(6):547-558.
[7]Yun Z,Zhang Z,Iskander M F.A Ray-Tracing Method Based on the Triangular Grid Approach and Application to Propagation Prediction in Urban Environments[J].IEEE Transactions on Antennas and Propagation,2002,50(5):750-758.
[8]Seidel S Y,Rappaport T S.Site-Specific Propagation Prediction for Wireless In-Building Personal Communication System Design[J].IEEE Transactions on Vehicular Technology,1994,43(4):879-891.
[9]武博强,杨晋生,刘敬浩,等.基于USRP平台的无线信道测量设计与实现[J].电子测量技术,2014,37(2):120-123.
[10]Athanasiadou G E,Nix A R.Investigation into the Sensitivity of the Power Predictions of a Microcellular Ray Tracing Propagation Model[J].IEEE Transactions on Vehicular Technology,2000,49(4):1140-1151.
[11]Rizk K,Wagen F,Gardiol F.Influence of Database Accuracy on Two-Dimensional Ray-Tracing-Based Predictions in Urban Microcells[J].IEEE Transactions on Vehicular Technology,2000,49(2):631-642.
基于模拟退火算法的网络优化设计 篇6
近年来,模拟退火算法不仅因为其自身的稳健性、隐并行性和全局特性而得到了广泛的应用,而且,其中的杂交思想作为一种方法论也给从事科学研究的人们以许多启迪,并导致许多边缘学科的产生。本文利用正交设计能快速找出最优解的特点,把正交设计嵌入到遗传算法的交叉算子中,研究了一种采用多点正交交换的遗传算法。算法通过正交表安排遗传算法的交叉运算,并在所产生的多个子代中选择适应度大的进入下一次进化。随后,利用这种改进的算法来优化计算机网络设计中的路由选择与容量分配问题,与拉格朗日松弛法、传统遗传算法进行了比较。结果表明该算法较之传统方法结果更优,与传统遗传算法相比,获得同样解的情况下,收敛速度明显加快。
一、模拟退火算法
模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热的时候,粒子间的布朗运动增强,到达一定强度后,固体物质转化为液态,这个时候再进行退火,粒子热运动减弱,并逐渐趋于有序,最后达到稳定。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,值得注意的是,当T为0时,模拟退火就成为局部搜索的一个特例。算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
模拟退火的典型特征是除了接受目标函数的改进外,还接受一个衰减极限,当T较大时,接受较大的衰减,当T逐渐变小时,接受较小的衰减,当T为0时,就不再接受衰-减。这一特征意味着模拟退火与局部搜索相反,它能避开局部极小,并且还保持了局部搜索的通用性和简单性。
模拟退火的基本思想:
(1)初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点),每个T值的迭代次数L
(2)对k=1,……,L做第(3)至第6步:
(3)产生新解S′
(4)计算增量Δt'=C(S′)-C(S),其中C(S)为评价函数
(5)若Δt′<0则接受S′作为新的当前解,否则以概率exp(-Δt′/T)接受S′作为新的当前解.
(6)如果满足终止条件则输出当前解作为最优解,结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。
(7)T逐渐减少,且T>0,然后转第2步。
模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法。
二、在网络优化设计中的应用
1. 问题描述
在设计计算机通信网,特别是干线网时,各条链路的容量分配和报文的路由选择是需要考虑的两个重要问题。在网络拓扑结构已定的情况下,怎样确定各条链路的容量分配和报文的路由选择,使得整个网络的建设、运转费用最低?因此,最佳的结果应当是考虑线路选择和容量这两个问题。本文采用模拟退火算法给出了优化该问题的数学模型。
2. 模拟退火算法设计
拓扑结构用图1描述如下,在图G(V,A)中,V表示网络的节点(即容量或路由互通立交)集合,V={v1,v2,...,vn},对G中的某一条边(vi,vj)之间连通则为路段长度,如(vi,vj)之间不连通为∞,在实际计算中以一个足够大的值代替。我们把矩阵w={d(vi,vj)|vi,vj∈V}称为网络拓扑权矩阵。
在模拟退火算法中加入倒置思想:随机在路径中选出两个节点vi与vj,然后将两个节点之间的节点顺序完全倒置得出新的路径。如两相异点k和m,则将原路径(w1,w2,...wk-
变为新路径:(w1,w2,...wk-1,wm,wm-1,...,wk+1,wkwm+1,...,wn)。
得出解空间,通过权w{i,j}>0,且节点x的标号为D(x),那么D(z)是从节点a到z的最短路径的长度,所以最短路径可以表示为:
其中
2.2.1.适应度函数
由解空间计算出权值向量W,由此计算出网络的输出,以训练集样本作为网络的输入和期望输出。设节点规模为N,每节点相应的实际输出yk(k=1,2,…n,n是网络输入输出样本对数)。第i(i=1,2,…N,N是节点群体规模)个节点的误差平方和表示为,其倒数作为群体的适应度值。
2.2.2最优路径模式
设优化问题的系统参数(变量)有x1个,x1表示分配第x1类容量给第l条链路,构成可供优化选的参数(变量)集X:
X即为优化问题的解空间。其中的一组参数如下式所示:
,称为该参数优化问题的一个解。
网络矩阵有如下递归方程和第k步的邻接矩阵:
设评价优化问题的性能指标有m个,构成性能指标集Q:
对于某一个参数解x(j),对应的性能指标值为:
其中,qk(j)是每一个性能指标qk关于参数解x(j)的取值。
sk反映了指标qk的满意程度;利用sk构成满意度函数向量:s=[s1,s2,...,sm],
,以向量函数g(·)表示性能指标向
量q的满意度函数,得到:
定义综合满意度函数:
其中,
综合满意度函数为标量函数,反映出了网络对性能指标的综合评价。根据以上各式,可以定义优化问题的计算模型如下:
三、程序设计
节点越多,循环次数越多,计算时间将成倍增长,因此机器的运行速度、计算时间和占用的计算机内存也会大幅度的提高。考虑到每个路由器周期性地发送数据,提供其邻接点的信息或当其状态改变时通知其它路由器。通过对已建立的邻接关系和链接状态进行比较,失效的路由器可以很快被检测出来,网络拓扑相应地更动,建立一个邻接矩阵和一个动态数组来存储网络的拓扑关系。从生成的拓扑数据库中,每个路由器计算最短路径树,以自己为根。进行动态最短路径优化。模拟退火算法的网络优化设计程序设计如图2所示。
四、实验结果
为准确证明算法的效率,由于算法要求初始温度必须充分大,所以在算法中我们设置初始温度都为300000,降温速率都为0.92,迭代次数均为2000次。设在网中,节点有72个并且每个节点都与网络其它节点进行通信,设每队通信结点的通信量为每秒4个报文,采用Matlab编制了算法程序,为了消除随机干扰,不同分组长度下的实验都运行多次。在所有参数相同的情况下,算法得到的结果为:总路线长度为8868.2,运算时间为13.11秒。算法优化的最终结果如图3所示。
摘要：网络是个随机性很强系统,为了获得良好的通行效率,提出了一种基于模拟退火算法优化方法,同时给出了程序设计流程。在算法中加入倒置思想,选择合适的适应度函数值,然后构造模型,给出了优化函数。仿真结果表明:这种算法不仅收敛性和稳定性都很好,而且模型是可行的、有效的。
关键词：网络优化,模拟退火算法,拓扑权矩阵
参考文献
[1]王伟,殷志祥.基于模拟退火算法的可逃逸粒子群算法[J].计算机应用研究,2008,(05):1326-1327,1339
[2]徐潘萍.浅谈模拟退火算法在自动排课系统中的应用[J].井冈山学院学报,2008,(06):35-37
[3]李薰春,史虹湘,杨明,李栋.基于模拟退火算法的地面电视频率指配方法研究[J].广播与电视技术,2008,(06):27-30
[4]李香平,张红阳.模拟退火算法原理及改进[J].软件导刊,2008,(04):47-48
[5]王伟.模拟退火算法的并行化策略研究[J].电脑知识与技术,2008,(25):1523-1524
[6]冯剑,岳琪.模拟退火算法求解TSP问题[J].森林工程,2008,(01):94-96
[7]潘海琳,张松涛,张福利.并行模拟退火算法在拱坝体形优化中的应用[J].黑龙江水专学报,2008,(02):29-31
[8]李爽,张瑾.改进模拟退火算法在数据挖掘中的应用[J].计算机与数字工程,2008,(02):17-19,168
[9]叶子伟,韩红超.基于退火BP神经网络的GPS高程转换[J].测绘工程,2008,(04):4-7
模拟退火策略 篇7
TSP的求解算法包括两大类:精确解法和启发式算法[2]。由于精确解法受到求解规模的限制, 而近年来问题规模越来越大, 因此国内外学者的研究主要倾向于启发式算法:遗传算法 (genetic algorithm, GA) 、蚁群算法 (ant colony algorithm, ACO) 、模拟退火 (simulated annealing, SA) 算法、禁忌搜索 (tabu search, TS) 算法等[3—7]。
针对TSP的改进SA算法研究, 国内外学者已经做了很多工作[8—10];提出了许多改进算法, 其中有一部分改进效果比较明显, 但以往学者提出的改进大多都是基于自己的经验, 缺乏细致科学的性能筛选分析实验, 所以主观性太强。本文则针对传统SA算法的不足, 从三个方面提出了改进的SA算法的想法, 然后以TSP标准测试库TSPLIB[11]中的数据对每一种改进想法进行仿真实验, 对其改进性能进行对比分析, 最终筛选出相对理想的改进SA算法。最后的数据验证也表明改进SA算法在性能上比GA和传统SA算法都有较大提高。
1 传统模拟退火算法
1.1 模拟退火算法基本原理
模拟退火算法原理来源于固体退火:将固体加温至充分高, 再让其徐徐冷却, 加温时, 固体内部粒子随温升变为无序状, 内能增大, 而徐徐冷却时粒子渐趋有序, 在每个温度都达到平衡态, 最后在常温时达到基态, 内能减为最小。根据Metropolis准则, 粒子在温度T时趋于平衡的概率为e-ΔE/ (k T) , 其中E为温度T时的内能, ΔE为其改变量, k为Boltzmann常数。
用固体退火模拟组合优化问题, 将内能E模拟为目标函数值f, 温度T演化成控制参数t, 即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始, 对当前解重复“产生新解—计算目标函数差—接受或舍弃”的迭代, 并逐步衰减t值 (由冷却进度表 (cooling schedule) 控制) , 算法终止时的当前解即为所得近似最优解, 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。
1.2 模拟退火算法模型流程
模拟退火算法模型包括编码方式、目标函数、冷却进度表、扰动机制、内循环机制、外循环机制等, 其中最基础的是编码方式、目标函数和冷却进度表。
1.2.1 编码方式
求解TSP问题的各种编码中, 多数以遍历城市的次序排列进行编码, 即整数编码。这种方法简单、自然、容易理解。如城市编号为[3, 2, 5, 4, 7, 1, 6, 9, 8]表示从3号城市出发, 经过2、5、4、7、1、6、9、8后, 最终又回到了城市3。
1.2.2 目标函数
TSP问题的一个个体为C={C (1) , C (2) , …, C (N) }, 其目标函数定义为个体所代表路径确切距离的长度, 即
式中C (i) 为路径C的第i个城市, d[C (i) , C (j) ]为两城市间的距离, 而且d[C (i) , C (j) ]=d[C (j) , C (i) ]。在后面的运行过程中, 算法试图使适应度函数f (C) 最小化并认为使得该函数取得较小值的解为较优解。
1.2.3 冷却进度表
传统冷却进度表包括初始温度T0、衰减函数g (T0) , 以及当前温度T下内循环迭代次数L。
初始温度T0针对不同的问题可以有不同的取值方法, 一般TSP常用的方法为:随机产生N个个体, 分别计算其目标函数值f (Ck) , k=1, 2…N, T0有如下两种取值方式:
温度衰减函数g (T0) 根据不同问题的需要, 可以设置不同的衰减速度, 常见的有三种:
当前温度T下内循环迭代次数L通常取常数定值。
1.2.4 模型流程
模拟退火算法可以分解为解空间、目标函数和初始解三部分。其模型的具体流程如下:
(1) 初始化:初始温度T0 (充分大) , 初始解C (C表示城市序列, 是算法迭代的起点) , 每个t值的迭代次数L。
(2) 对k=1, …, L做第 (3) 至第 (5) 步。
(3) 随机产生扰动, 得到新解C'。
(4) 计算增量Δf=f (C') -f (C) , 其中f (C) 为目标函数。
(5) 若Δf≤0, 则接受新解, 否则以概率p (Δf) =exp (-Δf/T) 接受新解, 以概率1-p (Δf) 接受原解, 并以接受的解作为下一次模拟的初始解。
(6) 温度T按一定的规律逐渐减少。
(7) 如果满足终止条件则输出当前解作为最优解, 结束程序;如果不满足则转第 (2) 步。
2 改进模拟退火算法
分析SA退火算法可以发现, 虽然SA算法存在有限度地接受劣解、可以跳出局部最优解原理简单、使用灵活、适合求解出优化问题的全局最优或近似全局最优解等优点;但它存在以下三点主要问题: (1) 退火速度问题。同一温度下的充分搜索是相当必要的, 在变量多、目标函数复杂时, 为了得到一个好的近似解, 温度T需要从一个较大的值开始, 并在每一个温度值T执行多次Metropolis算法, 迭代运算速度慢。 (2) 扰动机制种类繁多, 灵活性大, 每一种的收敛速度和寻优能力不易估计, 选择时难以抉择。 (3) 搜索过程中由于执行概率接受环节而遗失当前遇到的最优解。针对以上三个问题, 提出以下三点改进。
2.1 内循环改进
虽然传统的SA方法设置了内循环, 在同一温度值T执行多次Metropolis算法, 保证全局搜索能力。但是实践表明, 将温度T下执行Metropolis算法的次数设置为定值往往不够灵活, 次数过多造成时间的浪费, 次数过少则损失解的质量。改进之处即设置采样稳定条件, 使得采样次数可以根据当前所得解的情况灵活处理, 在保证解质量的前提下, 尽量避免时间的浪费。
采样稳定条件定义为:同一温度T下局部解未被提高的次数L。具体操作是在每个温度T开始时设置一个局部解未被提高次数计数器num=0, 然后每执行一次Metropolis算法之后进行判断, 如果局部解被提高了就将num重新置于0, 否则就将num加1;这样直到num达到上限L时跳出当前温度T的内循环。
2.2 扰动机制改进
传统的SA算法选用单一的扰动机制, 而且没有证明这种单一的扰动机制就是最优的, 因此造成解被改进的可能性不大。改进之处在于提供了6种扰动机制, 给它们以同等机会被采用, 这样就增大了解被改进的可能性。扰动机制如图1所示。
其中M5还有一个变种, 即城市子排列双向反序, 如图2所示:
2.3 记忆功能改进
传统SA算法“依概率接受”思想, 使得当前状态可能要比搜索过程中某些中间状态差, 在仿真实验中已经发现最终得到的近似最优解有时候比中间经历的最好解差, 这样就浪费了搜索时间, 影响了搜索效果。为了不损失搜索过程中遇到的当前最优解, 并提高搜索效果, 加快搜索速度, 文章的改进之处在于增加了记忆功能。
记忆功能是指在搜索过程中记住当前最优解, 并及时更新使之能记住搜索过程中遇到的最好解, 避免了由于执行概率接受环节而遗失当前遇到的最优解, 增加了这种记忆能力的模拟退火算法已成为一种智能化的算法。
2.4 改进后的模型流程
在传统SA算法的基础上, 加入以上三种改进, 实现后的模型流程为如下:
(1) 运用公式W1或W2产生初始温度T0, 随机产生初始解C, 定义记忆器best=C, 定义局部最大无更优解产生次数L、全局最大无更优解产生次数M、局部最优解未更新次数num=0、全局最优解未更新次数aim=0、退火代数k=0。
(2) k=k+1, 运用公式G1、G2或G3更新温度Tk。
(3) 对个体C以同等概率执行3.3中的6种扰动机制, 产生新解C'。
(4) 按公式O计算增量Δf=f (C') -f (C) , 如果Δf<0, 则C=C', num=0, 转第 (7) 步。
(5) 计算概率值p (Δf) =exp (-Δf/Tk) , 产生伪随机数r, 如果r
(6) num=num+1, 转第 (7) 步。
(7) 如果num≤L, 则转第 (3) 步, 否则转第 (8) 步。
(8) 如果f (C)
(9) 如果aim≤M, 则转第 (2) 步, 否则以best为最终解输出, 算法结束。
3 仿真实验及结果分析
为了验证SA算法改进思想的效果, 分别选用att48、eil51、eil76进行实验。仿真硬件为普通PC机, 微处理器为Core2 Duo (2.00 Hz) , 内存1.00GB, 仿真软件为MATLAB (R2008a) 。以上3个问题的数据集均来自国际通用的TSP标准测试库:http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/tsp/。
仿真实验分3次进行, 前两个实验均以eil51为数据集, 分别测试内循环改进和扰动机制改进的效果 (记忆功能改进比较直观, 无需测试) , 并从中选择最佳的参数配置, 组合成比较理想的改进SA算法。第三个实验是综合运用att48、eil51、eil76三个测试集, 将改进SA算法与标准GA以及传统SA算法进行对比实验, 进一步验证改进效果。
3.1 内循环改进仿真实验
为了仿真检测内循环改进的效果, 设计了一组对比SA算法实验:
确定量:有记忆功能;以公式W2确定初始温度T0;温度衰减函数选择公式G1;扰动机制以同概率采用M5 (城市子排列反序) 和M5’ (城市子排列双向反序) ;全局最大无更优解产生次数M=300。
变量:温度T下局部最大无更优解产生次数L, 分别取0、50、100、200、500、1 000次。
每个不同的参数L运算10次, 然后取平均值, 得到结果如表1所示。
由表1的结果可知, 采取内循环比不采取内循环效果要好很多, 而且内循环迭代次数越多, 结果越好, 但是运算时间也就越高。综合分析认为局部最大无更优解产生次数L设为500比较合适。
3.2 扰动机制改进仿真实验
为了仿真检测扰动机制改进的效果, 文章设计了一组对比SA算法实验:
确定量:有记忆功能;以公式W2确定初始温度T0;温度衰减函数选择公式G1;全局最大无更优解产生次数M=300;局部最大无更优解产生次数L=500。
变量:单一扰动机制M1、M2、M3、M4、M5、M6和同等概率采用6种扰动机制M7。每种扰动机制运算10次, 然后取平均值, 得到结果见表2。
由表2的结果可知, 扰动机制M1、M2和M3单独使用的效果不是很好, 应该避免单独使用这样一种扰动机制;单独使用时, M5效果最好;总体来说, 综合使用时M7结果好、方差小, 效果最佳。
3.3 综合对比仿真实验
由以上两个仿真实验, 可得一种比较理想的改进SA算法:采用记忆功能;以公式W2确定初始温度T0;温度衰减函数选择公式G1;全局最大无更优解产生次数M=300;局部最大无更优解产生次数L=500;扰动机制为M7。
为了仿真检测改进SA算法的效果, 文章设计了一组改进SA算法与标准GA以及传统SA算法进行对比实验:
每种算法的终止条件都设为相同, 即全局最优解没有被改进的次数达到300次时终止程序。每种算法针对各个问题均运算10次, 然后取平均值。具体结果见表3。
由表可以看出改进的SA算法与标准GA和传统SA算法相比, 运算结果不仅平均值有很大改进, 而且每10次计算都能够算到最优解, 同时结果的方差也相对较小, 结果比较稳定, 可以说明改进是成功的。图3给出了三种算法计算eil51问题, 均迭代1 000次之后的收敛曲线图。
TSP标准测试库给出三个问题att48、eil51和eil76的最优解为33 522、426和538, 本文的改进SA算法均能够达到, 图4、图5和图6分别展示了三个最优解。
4 结束语
通过分析传统SA算法原理和存在的不足, 提出了三种改进SA算法的思想。运用TSP标准测试集对三种改进思想进行仿真对比实验, 最终找到合理的改进参数配置, 得到一种较优的改进SA算法。将改进算法与GA和传统的SA算法进行对比实验, 结果表明该算法在性能上有较大提高。文中改进SA算法计算时间仍然相对偏长, 这将是下一步继续改进的目标。
参考文献
[1] 韩丽霞, 王宇平.解旅行商问题的一个新的遗传算法.系统工程理论与实践, 2007;12:145—150
[2] Steinbrunn M, Moerkotte G, Kemper A.Heuristic and randomized optimization for the join ordering problem.The VLDB Journal, 1997;6 (3) :8—17
[3] 林志毅.改进的遗传算法求解TSP问题.湖北:武汉理工大学, 2006
[4] Kirkpatrick S, Gelartt C D, Vecchi M P.Optimization by simulated annealing.Science, 1983;220 (11) :650—671
[5] 苏晋荣.基于智能优化算法的TSP问题研究及应用.山西:山西大学, 2007
[6] 于海平, 杨艳霞.基于信息素变异的蚁群算法的应用研究.计算机与数字工程, 2011;39 (9) :10—12
[7] 文永军.旅行商问题的两种智能算法.西安:西安电子科技大学, 2010
[8] 田澎, 王浣尘, 张冬茉.旅行商问题 (TSP) 的模拟退火求解.上海交通大学学报, 1995;30 (S1) :111—116
[9] 杨卫波, 赵燕伟.求解TSP问题的改进模拟退火算法.计算机工程与应用, 2010;46 (15) :34—36
[10] 杜宗宗, 刘国栋.基于混合遗传模拟退火算法求解TSP问题.计算机工程与应用, 2010;46 (29) :40—46
模拟退火策略 篇8
遗传算法(GA)与模拟退火法(SAA)是近年来优化领域的研究热点,与传统的优化方法相比,具有算法简单、使用灵活、寻优效高、算法“健壮”、适合并行计算、不需要梯度信息等优点,目前已在组合优化、管理决策、工程领域得到一些应用。鉴于这两种算法在寻优方面的优越性,特将其算法思想以及寻优特点作一归纳,使之在工程优化设计领域中能得到广泛应用。
1 两种算法的基本思想
1.1 遗传算法
遗传算法是根据达尔文的生物进化中的“优胜劣汰”原则建立的一种优化算法。20世纪60年代首先由美国Michigan大学的J. Holland教授提出。该算法模拟了自然界中生物自然选择、适者生存的进化过程,从而达到搜索最优解的目的,标准遗传算法主要由以下基本步骤组成:
a) 对设计向量编码:遗传算法不直接处理解空间数据,需通过编码将解空间中的设计向量转化为遗传空间中的基因串,通过遗传算法改变基因串的结构以达到搜索解空间最优解的目的,常用的编码形式为二进制编码、浮点编码等。
b) 生成初始母体群:遗传算法是群体操作算法,随机生成n个基因串(每个基因串对应解空间的一个设计向量),以此作为迭代搜索的初始点。
c) 适应度计算:适应度是反应基因串对环境的适应能力,遗传算法一般不需要其他信息,仅通过适应度来评价群体中的两个体的优劣,适应度越大,个体的遗传基因越优,反之遣传基因较劣。
d) 对群体基因串进行遗传算子操作,产生新一代群体基因串遗传算法,主要有选择、交叉、变异三种算子组成,选择的目的是从群体基因串中选择遗传基因优良的基因串作为遗传父代,交叉运算的目的是产生子代基因串,变异的目的是为产生新的基因串提供机会。
通过上述三种遗传运算操作形成新一代(子代)群体基因串,如此反复迭代遗传直到搜索到最优解。
1.2 模拟退火法
模拟退火法是模拟固体退火过程而设计的一种寻优算法。20世纪80年代首先由Kirkpatrilk等人提出,在模拟退火法中,解向量X和目标函数F(X)分别对应退火过程一个固体微观状态i和相应的能量E,随着算法进程递减其值的控制参数C对应于退火过程的温度T,在某一控制参数C值下,算法所进行的“产生新解→判断→接受或放弃”的迭代过程,相对应固体在某一恒温下趋于热平衡的过程。通过若干次迭代变换后算法求出的最优解x*和目标函数F(X*)分别对应固体的基态和最小能量。
模拟退火法的求解步骤如下:1) 设定初始解X=X0和初始控制参数C=Co;2) 随机产生新X′;3) 计算转移概率p;
P(X′=>X)=
undefined
4) 判断接受或放弃新解X′,当p(X′=>X)>r,接受X′为新解,否则,放弃为X′新解;5) 判断终止条件,满足条件则停止迭代,否则转向2)。
2 两种算法的寻优能力比较
2.1 测试函数算例
为了考察两种算法的寻优能力,曾经测试了几个具有典型“欺骗”性质的函数的优化,这种具有“欺骗”性的函数全局最优点往往是孤立的并被全局最优点包围,或是多峰值函数。
f1=100(x2-xundefined)2+(x2-1)2,Ω=(-200,200)2;
f2=undefined100(x1+1-xundefined)2+(x1-1)2,Ω=(-200,200)1;
f3=xundefined+2xundefined-0.3cos3πx1-0.4cos4πx2+0.7,Ω=(-100,200)2。
f1为二维Rosenbrock函数,最小值为0,全局最优点(1,1),是一个具有曲型“狭长深谷”的函数;f2为四维Rosenbrock函数,最小值为0,全局最优点为(1,1,1,1);f3为一个多峰值函数。上述函数用传统方法很难搜索到全局最优点,具体测试结果见表1:
遗传算法与模拟退火法均为随机搜索算法,与传统优化方法相比,两种算法在寻优方面各有特点。
2.2 遗传算法的寻优特点
a) 寻优过程不需梯梯信息,特别适用复杂目标函数的优化;
b) 不是从一个单点而是从多点(群体)开始搜索;
c) 利用概率转移规则,而非确定规则;
d) 由于引入了交叉与变异算子,使遗传算法搜索到全局最优解的能力增强,理论上遗传算法搜索到全局最优的概率为1;
e) 遗传算法对初始解没有苛刻要求是一种“健壮”的算法;
f) 由于遗传算法是在遗传空间中通过操作n个基因编码串进行寻优,而n个基因串能反映O(n3)阶个基因串模式,因而遗传算法隐含并行性,这一优点特别适用于并行计算机处理,除上述优点外,遗传算法也有其缺陷,其中最突出的是“早熟现象”特别是对多峰值目标函数的优化中表现的较明显,所谓“早熟现象”是过早收剑到某一局部最优解,目前国内外学者也提出了一些解决方法,如引入共享函数、学编码等。
2.3 遗传算法的寻优算例
例:已知20t/25m门座起重机变幅齿条最大切向力F1=344kN
常规计算过程如下:
a) 初选小齿轮模数m=25,Z=14,材料40Cr,变位系数ξ=0.177,根据齿变典强度条件,求得齿宽b=200mm。
选取齿轮轴材料45号钢,根据结构和齿宽b定轮轴支承情况和支承距离L,进行齿轮轴弯曲疲劳强度校核得到轴直径d=168mm。
b) 校核齿体强度:根据齿轮计算得齿根圆直径df=296.3mm,而齿体强度要求齿根圆直径不小于302.4mm。上述计算结果不满足要求,这时必须凭经验调整有关几何尺寸参数再进行齿轮、齿轮轴和齿体的强度校核直到满足为止。而通过遗传算法可得到下面一组解(见表2),其中第一组解为全局最优解,其他若干组次优解,设计人员可以根据实际情况从中任选一组解。必定优于常规计算所得的结果。
2.4 模拟退火算法的特点
a) 寻优过程不需要梯度信息,适合复杂目标函数优化;
b) 算法简单,易程序化;
c) 与局部搜索法相比,模拟退火法能以一定概率接受恶化解从而扩大了搜索空间,使迭代过程易跳出局部最优“陷井”,增大了搜索到全局最优解的机会;
d) 最终优化解的质量不依赖初始解,因而模拟退火法是一种“健壮”的算法;
e) 理论上模拟退火法搜索到全局最优解的概率为1;
f) 如冷却进度表选取合理,模拟退火法能在较短的CPU时间内获得者高质量的全局最优解。
由于模拟退火法是对固体退火过程的简单模拟,因而不可避免的存在一些不足,主要表现为合理选取初始温度T较为困难:1) 随着控制参数T的逐渐衰减,接受恶化解的概率逐渐减小,从而使算法停留在局部最优的“陷井”中无法跳出;2) 目前,已有学者提出了一些改进的模拟退火法来解决上述问题,如加温退火法、记忆退火法、回火退火法等,均取得了较好的效果。
2.5 模拟退火算法的寻优算例
算例:16t带载变幅直臂架起重机。有关技术性能参数如表3:起重质量16t,最大幅度Rmax=16m,最小幅度Rmin=7m,臂架端点至臂架铰点的垂直距离Hmin=14m。臂架自重Gb=5×104kN,臂架重心位置l1=8m。
计算结果列于表3:
根据计算结果绘制了落差曲线图(图1)和不平衡力矩曲线图(图2)。
3 总结
遗传算法与模拟退火法在优化领域有着非常广泛的应用前景,目前对这两种算法的数学理论、性能分析、并行性计算,在神经网络中的应用等方面均是国内外学者的研究热点,本文的目的就是希望通过对这两种算法的寻优特点进行一些归纳,使之能更好的用于工程优化设计领域,以提供有价值的帮助。
摘要：介绍了遗传算法与模拟退火算法的基本思想,综述归纳了两种算法的寻优特点,使之在工程优化设计领域得到更广泛的应用。
关键词：遗传算法,模拟退火法,优化设计
参考文献
[1]刘勇.非数值并行算法——遗传算法[M].北京:科学出版社,1994.
[2]康立山.非数值并行算法——模拟退火法[M].北京:科技出版社,1995.
[3]柳卫东,等.遗传算法优能力研究[J].武汉交通科技大学学报,1998.
[4]孙艳丰,王众托.遗传算法在优化问题中的应用进展[J].控制与决策,1996(4).
[5]vas Lasrhovon P J M,Asrts E H L.Simulated annealing[M].Theory and Applications.D Reidel,1997.
[6]胡琉达.实用多目标最优化[M].上海:上海科学技术出版社,1990.
[7]刘惟信.机械最优化设计[M].北京:清华大学出版社,1994.
[8]van laarhoven P J M,Aarts E H L:Simulated annealing[M].Theory Applitions D Reidel,1947.