every blog every motto: You can do more than you think.

0. 前言

蟻群算法記錄

1. 簡介

蟻群算法（Ant Clony Optimization， ACO）是一種群智能算法，它是由一群無智能或有輕微智能的個(gè)體（Agent）通過相互協(xié)作而表現(xiàn)出智能行為，從而為求解復(fù)雜問題提供了一個(gè)新的可能性。蟻群算法最早是由意大利學(xué)者Colorni A., Dorigo M. 等于1991年提出。經(jīng)過20多年的發(fā)展，蟻群算法在理論以及應(yīng)用研究上已經(jīng)得到巨大的進(jìn)步。

螞蟻在尋找食物的過程中往往是隨機(jī)選擇路徑的，但它們能感知當(dāng)前地面上的信息素濃度，并傾向于往信息素濃度高的方向行進(jìn)。信息素由螞蟻?zhàn)陨磲尫?，是?shí)現(xiàn)蟻群內(nèi)間接通信的物質(zhì)。由于較短路徑上螞蟻的往返時(shí)間比較短，單位時(shí)間內(nèi)經(jīng)過該路徑的螞蟻多，所以信息素的積累速度比較長路徑快。因此，當(dāng)后續(xù)螞蟻在路口時(shí)，就能感知先前螞蟻留下的信息，并傾向于選擇一條較短的路徑前行。這種正反饋機(jī)制使得越來越多的螞蟻在巢穴與食物之間的最短路徑上行進(jìn)。由于其他路徑上的信息素會(huì)隨著時(shí)間蒸發(fā)，最終所有的螞蟻都在最優(yōu)路徑上行進(jìn)。

2. TSP問題

蟻群算法最早用來求解TSP問題，并且表現(xiàn)出了很大的優(yōu)越性，因?yàn)樗植际教匦?，魯棒性?qiáng)并且容易與其它算法結(jié)合，但是同時(shí)也存在這收斂速度慢，容易陷入局部最優(yōu)（local optimal）等缺點(diǎn)。

TSP問題（Travel Salesperson Problem，即旅行商問題或者稱為中國郵遞員問題），是一種NP-hard問題，此類問題用一般的算法是很難得到最優(yōu)解的，所以一般需要借助一些啟發(fā)式算法求解，例如遺傳算法（GA），蟻群算法（ACO），微粒群算法（PSO）等等。

TSP問題（旅行商問題）是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次 然后回到出發(fā)城市，并要求所走的路程最短。

由上述螞蟻找食物模式演變來的算法，即是蟻群算法。這種算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征，本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法。

蟻群算法應(yīng)用廣泛，如旅行商問題(traveling salesman problem,簡稱TSP)、指派問題、Job-shop調(diào)度問題、車輛路徑問題（vehicle routing problem）、圖著色問題(graph coloring problem)和網(wǎng)絡(luò)路由問題（network routing problem）等等。

3. 原理

設(shè)整個(gè)螞蟻群體數(shù)量為m，城市數(shù)量為n，城市i和j之間的相互距離為$d_{ij}$，t時(shí)刻城市i與城市j路徑上的信息濃度為${\tau }_{ij}(t)$，初始時(shí)刻，各城市間連接路徑上的信息濃度相同，不妨設(shè)$\tau (0)={\tau }_0$

3.1 轉(zhuǎn)移概率

螞蟻k根據(jù)各城市間連接路徑上的信息素濃度決定其下一個(gè)訪問的城市，設(shè)$P_{ij}^k(t)$表示t時(shí)刻螞蟻k從城市i到城市j的概率，計(jì)算公式如下：

$$P_{ij}^k=?$$