螞蟻算法

蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找最佳化路徑的機率型技術。它由Marco Dorigo於1992年在他的博士論文中引入，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。

概述

螞蟻算法

自然界的螞蟻種群相當廣泛,但大部分種群都有以下的能力: 螞蟻們總能找到食物源和螞蟻窩之間的最短路徑. 一旦這條最短路徑被發現, 螞蟻們就能在這條路上排成一行, 在食物源和螞蟻窩之間搬運食物. 螞蟻們是怎么做到的呢?

相關

我們知道,2點間直線距離最短. 但螞蟻們顯然不具備這樣的視力和智慧. 它們無法從遠處看到食物源, 也無法計畫一個合適的路徑來搬運食物. 螞蟻們採用的方法是全體在老窩的周圍區域進行地毯式搜尋.而他們之間的聯繫方式是通過分泌化學物質在爬過的路徑上,這種化學物質叫信息素(Pheromone).
螞蟻們習慣選擇信息素濃度高的路徑. 下面的圖解釋了螞蟻們的工作原理.
剛開始離開窩的時候, 螞蟻們有兩條路徑選擇: R1和R2. 這兩者機會相當. 螞蟻們在爬過R1和R2的時候都留下了信息素. 但是, 由於R2的距離短, 所需要的時間就少, 而信息素會揮發, 所以螞蟻們留在R2上的信息素濃度就高. 於是,越來越多的螞蟻選擇R2作為最佳路徑, 即使它們是從R1來到食物源,也將選擇R2返回螞蟻窩. 而從老巢里出發的螞蟻們也越來越傾向於R2. 在這樣的趨勢下, R1漸漸變的無人問津了
根據螞蟻們選擇路徑的方法而得到的啟發, Dr. Dorigo在1991年發表了螞蟻算法(Ant algorithm). 十多年來, 螞蟻算法,以及各種改進過的螞蟻算法,被廣泛的套用在實際生活的各個方面. 在計算機技術套用中,它可以作為網路路由控制的工具. 在交通控制中, 它也成功解決了車輛調度問題.在圖表製作中, 它被用來解決顏色填充問題. 此外, 它還可以被用來設計大規模的時刻表. 而推銷員問題,既在多個不同地點間往返的最佳路徑選擇問題, 應該算是螞蟻算法最重要的用途了.