Re: [問題] 機率的實用
※ 引述《lakb (Jerry)》之銘言：
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: Dev c++
: 問題(Question)：
: 我目前在寫ACO(蟻群演算法)，裡面有一個部份我不知該如何實作。隨著螞蟻的經過，
: 該路徑的費洛蒙濃度會提高，當下一隻螞蟻來的時候，費洛蒙濃度高的路經被選擇的機率
: 將會較高。
: 正題: 我不知道該如何寫出高濃度的路徑將有較高的機率會被選上(低濃度路徑仍有
: 被選上的可能)，不知道有無函式可使用? 先謝謝大家的回答!
: 補充說明(Supplement)：
不知道你是不是參考 Dorigo 的 paper?
他寫的 Ant System 跟 ACO 這兩篇 paper 應該是必讀的文章,
雖然後面實驗數據很多, 但那邊可先略過, 重點還是放在
AS/ACO 的精神與演算法上.
關於你問的路徑選擇方式, 怎麼用程式表達出來.
我可以推薦分成幾個步驟來實作:
1. 每一條edge(兩個點之間的link)都有一個費洛蒙值.
2. 每一條edge都有一個距離值.
上面這兩點的資訊要怎麼儲存? 會了之後再往下看.
3. 先看路徑的初始費洛蒙怎麼設定 (Paper有公式)
原作者是用uniform dist.的方式.
4. 已經會設定初始費洛蒙值, 接下來就是螞蟻們一開始的位置要在哪裡?
怎麼決定各個螞蟻一開始在哪個城市?
螞蟻身上背的資訊, 就是它走過哪些城市的順序.
第4點會了之後, 再繼續第5點.
5. 這裡才是你在問的問題 XD.
你的問題所參考的公式, 應該是狀態轉換公式吧
(ACS state transition rule).
這公式包含了兩個部份: exploitation 與 biased exploration.
先不要管 exploitation 這個選擇最佳下一步的方式.
biased exploration 基本精神就是取自GA的輪盤法則, 有些東西容易被挑中.
該怎麼設定挑中的機率呢? 也請看公式.
基本上, 就是用到
a. 某一隻螞蟻現在在哪一個城市 (city i),
b. 以及這隻螞蟻還有哪些未拜訪的城市們 (cities Jk),
c. i 到 Jk 所有 edges 的費洛蒙資訊 (想像是一維陣列 C)
d. i 到 Jk 所有 edges 的路徑距離的倒數 (想像是一維陣列 D)
e. C 與 D 裡面同編號的元素進行以下運算:
c * (d )^Beta =>cd , Beta的值看paper怎麼給定的.
k k k
加總所有的 cd , 這個就是輪盤法裡面輪盤的總面積大小.
k
而各個 cd / 總面積, 這個就是各個候選路徑被挑中的機率值.
k
基本上, 從 (c) 與 (d) 的資訊看來, 我們可以這樣解讀:
費洛蒙較高的edge, 比較容易被挑上.
路徑較短的edge, 比較容易被挑上.
好了, 等這個東西會寫之後, 再來看怎麼更新費洛蒙資訊.
6. 這邊不在問題範圍之內, 我就不多寫了.
反正, 它有分 Gloal updating and Local updating, 且作用的時機不同.
→
06/10 12:54, , 1F
06/10 12:54, 1F
→
06/10 13:15, , 2F
06/10 13:15, 2F
推
06/11 00:35, , 3F
06/11 00:35, 3F
※ 編輯: ericinttu 來自: 59.117.140.88 (06/11 01:44)
推
06/11 10:04, , 4F
06/11 10:04, 4F
→
06/15 02:33, , 5F
06/15 02:33, 5F
討論串 (同標題文章)