新聞內容

您當前所在位置:AG新世界_手机版 >> 技術資訊 >> 技術百科

物料退火算法的專題介紹


來源:

摘要:物料退火算法來源于固體退火原理,將固體加溫至充分高,再讓其徐徐冷卻,使用加溫時,固體內部粒子隨溫升變爲無序狀,內能增大,而徐徐冷卻時粒子漸趨有序,在每個溫度都達到平衡態,使用退火爐常溫時達到基態,內能減爲最小。

 物料退火算法來源于固體退火原理,將固體加溫至充分高,再讓其徐徐冷卻,使用加溫時,固體內部粒子隨溫升變爲無序狀,內能增大,而徐徐冷卻時粒子漸趨有序,在每個溫度都達到平衡態,使用退火爐常溫時達到基態,內能減爲最小。

根據Metropolis准則,粒子在溫度T時趨于平衡的概率爲e-ΔE/(kT),其中e爲溫度T時
的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
起源
模擬退火算法起源于物理退火。
􀂄物理退火過程:
⑴ 加温过程
⑵ 等温过程
⑶ 冷却过程
模型建立
模擬退火算法可以分解爲解空間、目標函數和初始解三部分。
模擬退火的基本思想:
⑴ 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点), 每个T值的迭代次数L
⑵ 对k=1,……,L做第⑶至第6步:
⑶ 产生新解S′
⑷ 计算增量Δt′=C(S′)-C(S),其中C(S)为评价函数
⑸ 若Δt′<0则接受S′作为新的当前解,否则以概率exp(-Δt′/T)接受S′作为新的当前解.
⑹ 如果满足终止条件则输出当前解作为最优解,结束程序。
終止條件通常取爲連續若幹個新解都沒有被接受時終止算法。
⑺ T逐渐减少,且T->0,然後轉第2步。
算法步驟
模擬退火算法新解的産生和接受可分爲如下四個步驟:
第一步是由一個産生函數從當前解産生一個位于解空間的新解;爲便于後續的計算和接受,減少算法耗時,通常選擇由當前新解經過簡單地變換即可産生新解的方法,如對構成新解的全部或部分元素進行置換、互換等,注意到産生新解的變換方法決定了當前新解的鄰域結構,因而對冷卻進度表的選取有一定的影響。
第二步是計算與新解所對應的目標函數差。因爲目標函數差僅由變換部分産生,所以目標函數差的計算最好按增量計算。事實表明,對大多數應用而言,這是計算目標函數差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropolis接受准则: 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
第四步是當新解被確定接受時,用新解代替當前解,這只需將當前解中對應于産生新解時的變換部分予以實現,同時修正目標函數值即可。此時,當前解實現了一次叠代。可在此基礎上開始下一輪試驗。而當新解被判定爲舍棄時,則在原當前解的基礎上繼續下一輪試驗。
注意事項
模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。
 
作为模拟退火算法应用,讨论旅行商问题(Travelling Salesman Problem,简记为TSP):设有n个城市,用数码1,…,n代表。城市i和城市j之间的距离为d(i,j) i,j=1,…,n.TSP问题是要找遍访每个域市恰好一次的一条回路,且其路径总长度为最短.。
TSP的模擬退火算法模型可描述如下:
解空间 解空间S是遍访每个城市恰好一次的所有回路,是{1,……,n}的所有循环排列的集合,S中的成员记为(w1,w2,……,wn),并记wn+1= w1。初始解可选为(1,……,n)
目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数:
AG新世界要求此代價函數的最小值。
新解的产生 随机产生1和n之间的两相异数k和m,
若k
(w1,w2,…,wk,wk+1,…,wm,…,wn)
變爲:
(w1,w2,…,wm,wm-1,…,wk+1,wk,…,wn).
如果是k>m,則將
(w1,w2,…,wm,wm+1,…,wk,…,wn)
變爲:
(wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk).
上述變換方法可簡單說成是“逆轉中間或者逆轉兩端”。
也可以采用其他的變換方法,有些變換有獨特的優越性,有時也將它們交替使用,得到一種更好方法。
代价函数差 设将(w1,w2,……,wn)变换为(u1,u2,……,un),则代价函数差为:
根據上述分析,可寫出用模擬退火算法求解TSP問題的僞程序:
Procedure TSPSA:
begin
init-of-T; { T为初始温度}
S={1,……,n}; {S为初始值}
termination=false;
while termination=false
begin
for i=1 to L do
begin
generate(S′form S); { 从当前回路S产生新回路S′}
Δt:=f(S′))-f(S);{f(S)爲路徑總長}
IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])
S=S′;
IF the-halt-condition-is-TRUE THEN
termination=true;
End;
T_lower;
End;
End
模拟退火算法的应用很广泛,可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。
參數控制
模擬退火算法的應用很廣泛,可以求解NP完全問題,但其參數難以控制,其主要問題有以下三點:
⑴ 温度T的初始值设置问题。
溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高,則搜索到全局最優解的可能性大,但因此要花費大量的計算時間;反之,則可節約計算時間,但全局搜索性能可能受到影響。實際應用過程中,初始溫度一般需要依據實驗結果進行若幹次調整。
⑵ 退火速度问题。
模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說,同一溫度下的“充分”搜索(退火)是相當必要的,但這需要計算時間。實際應用中,要針對具體問題的性質和特征設置合理的退火平衡條件。
⑶ 温度管理问题。
溫度管理問題也是模擬退火算法難以處理的問題之一。實際應用中,由于必須考慮計算複雜度的切實可行性等問題,常采用如下所示的降溫方式:
T(t+1)=k×T(t)
式中k爲正的略小于1.00的常數,t爲降溫的次數
優缺點及改良方式
優點:計算過程簡單,通用,魯棒性強,適用于並行處理,可用于求解複雜的非線性優化問題。
缺點:收斂速度慢,執行時間長,算法性能與初始值有關及參數敏感等缺點。
經典模擬退火算法的缺點:
⑴如果降溫過程足夠緩慢,多得到的解的性能會比較好,但與此相對的是收斂速度太慢;
⑵如果降溫過程過快,很可能得不到全局最優解。
􀂄 模拟退火算法的改进
⑴ 设计合适的状态产生函数,使其根据搜索进程的需要
表現出狀態的全空間分散性或局部區域性。
⑵ 设计高效的退火策略。
⑶ 避免状态的迂回搜索。
⑷ 采用并行搜索结构。
⑸ 为避免陷入局部极小,改进对温度的控制方式
⑹ 选择合适的初始状态。
⑺ 设计合适的算法终止准则。
也可通過增加某些環節而實現對模擬退火算法的改進。
主要的改進方式包括:
⑴ 增加升温或重升温过程。在算法进程的适当时机,将電子散熱器的溫度適當提高,從而可激活各狀態的接受概率,以調整搜索進程中的當前狀態,避免算法在局部極小解處停滯不前。
⑵ 增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解,可通过增加存储环节,将一些在这之前好的态记忆下来。
⑶ 增加补充搜索过程。即在退火过程结束后,以搜索到的最优解为初始状态,再次执行模拟退火过程或局部性搜索。
⑷ 对每一当前状态,采用多次搜索策略,以概率接受区域内的最优状态,而非标准SA的单次比较方式。
⑸ 结合其他搜索机制的算法,如遗传算法、混沌搜索等。
⑹上述各方法的綜合應用。

上一篇:退火爐的水需要环保处理吗?
下一篇:燃氣加熱爐選用的六大優勢


相關新聞



相關産品


技術資訊


關閉
15262952939 聯系人:蔡先生
郵箱:15262952939@163.com
固話:0511-86671808
地址:江蘇省丹陽市珥陵工業開發區護國路
進入産品中心