1.3.1 基本思想

自然界中，蟻群尋找食物時(shí)，它們總能找到一條最優(yōu)的路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)釋放出一種特殊的信息素。開(kāi)始時(shí)，環(huán)境中沒(méi)有信息素，螞蟻完全隨機(jī)地尋找路徑。但隨后的螞蟻會(huì)根據(jù)先前螞蟻遺留下來(lái)的信息素來(lái)選擇路徑，路徑上信息素的強(qiáng)度越高，該路徑被選擇的概率越大。同時(shí)，信息素是一種揮發(fā)性物質(zhì)，如果每只螞蟻在單位距離上遺留的信息素相同，那么較短路徑上的信息素濃度就會(huì)更高，最終蟻群會(huì)找出最優(yōu)路徑。

首先將m只螞蟻隨機(jī)地放到n座城市，并將每只螞蟻的禁忌表tabu中的第一個(gè)元素設(shè)置為它此時(shí)所在的城市，讓各城市之間路徑上的信息素量相同，設(shè)τ_ij（0）=c，c為較小的常數(shù)。讓每只螞蟻根據(jù)路徑上的信息素量和啟發(fā)式信息獨(dú)立地選擇將要去的下一個(gè)城市，在時(shí)刻t，螞蟻k從城市i轉(zhuǎn)移到城市j的概率為

其中，J_k（i）表示可供螞蟻k下一次選擇的城市的集合，J_k（i）={1，2，…，n}-tabu_k。

tabu_k表中記錄了螞蟻k走過(guò)的城市，當(dāng)所有的城市都進(jìn)入tabu_k表，表明螞蟻k完成了一次周游。此時(shí)，螞蟻k走過(guò)的路徑便是TSP問(wèn)題的一個(gè)可行解。η_ij是一個(gè)啟發(fā)因子，表示螞蟻從城市i轉(zhuǎn)移到城市j的期望大小。η_ij通常為城市i到城市j距離的倒數(shù)。α和β表示信息素和期望啟發(fā)因子的相對(duì)重要程度。當(dāng)所有的螞蟻完成一次周游，各條路徑上的信息素根據(jù)式（1-4）更新：

其中，ρ（0＜ρ＜1）為信息素的蒸發(fā)系數(shù)，1-ρ表示信息素的持久性系數(shù)，Δτ_ij表示此次迭代中路徑（i，j）上的信息素增量，Δτ_ij為第k只螞蟻在本次迭代中留在路徑（i，j）上的信息素量。如果螞蟻k沒(méi)有經(jīng)過(guò)路徑（i，j），則Δτ_ij的值設(shè)為0。Δτ_ij的表達(dá)式為

其中，Q為正常數(shù)，L_k表示第k只螞蟻在此次周游中所走過(guò)路徑的長(zhǎng)度。