蟻群優化演算法 (Ant Colony Optimization)
最佳化方法簡介歷史確定性搜尋基本搜尋法逐漸深入法α-β 修剪A* 搜尋法隨機搜尋單粒子隨機搜尋貪婪演算法爬山演算法模擬退火法禁忌搜尋法多粒子隨機搜尋演化策略鳥群演算法蟻群演算法蜂群演算法程式實作基本搜尋法爬山演算法基因演算法鳥群演算法訊息相關網站參考文獻最新修改簡體版English |
簡介蟻群優化演算法是模仿螞蟻覓食行為的演算法，是 1992 由 Marco Dorigo 在其博士論文中所提出來的。 螞蟻覓食的時候，若找到食物，在搬運食物回程的途中會分泌一種特殊的賀爾蒙，以告訴其他螞蟻可以循著該路徑去搬運食物。由於這些賀爾蒙會隨時間的經過而蒸發，但若有其他螞蟻也循該路徑回來則會繼續分泌賀爾蒙補強之。因此，這些賀爾蒙成為良好的食物指標，讓螞蟻得以同心協力搬回最多的食物。  蟻群演算法的特色，就是利用這些荷而蒙以達到優化的目的，其演算法如下。 演算法
位置移動公式螞蟻從位置 i 移動到位置 j 的機率公式如下所示 (1)\begin{align} p_{i,j} = \frac { (\tau_{i,j}^{\alpha}) (\eta_{i,j}^{\beta}) } { \sum (\tau_{i,j}^{\alpha}) (\eta_{i,j}^{\beta}) } \end{align}
其中的各個參數之意義如下： $\tau_{i,j}$ 是位於 $i,j$ 路徑上的費洛蒙數量 $\alpha$ 是 $\tau_{i,j}$ 的費洛蒙影響力控制系數 $\eta_{i,j}$ 是路徑 $i,j$ 上的費洛蒙初始值 (在優化前就設好的，通常為 $1/d_{i,j}$) $\beta$ 是 $\eta_{i,j}$ 的費洛蒙影響力控制系數 費洛蒙更新公式(2)\begin{align} \tau_{i,j} = (1-\rho)\tau_{i,j} + \Delta \tau_{i,j} \end{align}
其中的各個參數之意義如下： $\tau_{i,j}$ 是位於 $i,j$ 路徑上的費洛蒙數量 $\rho$ 是費洛蒙的蒸發系數 $\Delta \tau_{i,j}$ 螞蟻所釋放的費洛蒙數量，通常公式如下所示。 (3)\begin{align} \Delta \tau^{k}_{i,j} = \begin{cases} 1/L_k & \mbox{if ant }k\mbox{ travels on edge }i,j \\ 0 & \mbox{otherwise} \end{cases} \end{align}
其中的 $L_k$ 是第 k 隻螞蟻的旅途長度 本文由維基百科節錄翻譯而來，請遵守 CC 授權中的 Creative Commons Attribution-ShareAlike License 條款。 |
page revision: 8, last edited: 11 Sep 2010 00:35
Post preview:
Close preview