推 wmn:寫得很好呀～～ 218.171.9.36 07/16
※ 引述《bingoabingo (狗強者)》之銘言：
: 演算法中有一個步驟是
: 把值帶入一個式子exp{(Ei-Ej)/t}
: 然後產生一個U(0,1)來比大小
: 我想請問這樣做的原理是啥
你說的是在
Simulated Annealing
中提到的Metropolis Monte Carlo procedure吧
SA的精神就是為了避免 讓找到的解卡在local minima cost
所以設計了一套機制 來逃離這個local minima。
當你用某種方法找的的組態 cost 比本來的小時，就接受這個組態
但萬一找到的組態cost比原本的高，也不一定會放棄這個組態
Metropolis Monte Carlo procedure 就是提供一個簡單的程序
來求出接受這個組態的機率。
簡單的說，他讓你在系統溫度高(式子裡面的t)時，較易接受大的cost增加量
而當溫度低的時候(代表SA程序已經進入尾聲)高的cost就很難再爬上去
cost就是你的Ei-Ej
當Ei-Ej > 0 的時候 演算法就直接接受這個組態，進入下一個iteration
當Ei-Ej < 0 (代表後面的組態cost比較大)時 演算法決定採用Ej這個組態的機率
就是根據exp{(Ei-Ej)/t}這個式子(此值介於0和1之間)來決定
若|Ei-Ej|的值越大，接受的機率就越小
而在相同的|Ei-Ej|情況之下，t越小 接受的機率也越小
這代表在高溫的狀態下 往上爬比較容易
等到冷掉了(t很小)就不容易往上爬了
覺得自己解釋的很差
直接去看
http://www.internetcad.com/thesis/annealing.pdf
的2.1後半段 或許會比較清楚
在google找到的
--
生物多樣性之所以重要，就在於我們不知道為什麼重要。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.166.66