蟻群算法（密恐勿入）
1. 算法簡(jiǎn)介
1.1 基本原理
蟻群算法是一種模擬螞蟻覓食行為的啟發(fā)式算法，被廣泛應(yīng)用于優(yōu)化問(wèn)題的求解。蟻群算法的基本思想是，將一群螞蟻放在問(wèn)題的解空間上，讓它們通過(guò)信息素的傳遞和揮發(fā)，逐漸找到最優(yōu)解。
1.1.1 模擬螞蟻在簡(jiǎn)單地形，尋找食物
階段一：在蟻群算法的初始階段，我們?cè)诘貓D上不放置任何食物，因?yàn)槲浵佇枰跊](méi)有任何信息素的情況下開(kāi)始摸索前進(jìn)。一開(kāi)始，螞蟻們?cè)诙赐怆S機(jī)移動(dòng)，試圖找到食物的位置。每只螞蟻的速度相同，它們會(huì)按照隨機(jī)的方向前進(jìn)，直到遇到障礙物或者到達(dá)了邊界。此時(shí)，它們會(huì)再次隨機(jī)選擇一個(gè)方向，并繼續(xù)前進(jìn)。這個(gè)過(guò)程會(huì)持續(xù)進(jìn)行，
階段二：當(dāng)螞蟻們找到了食物后，它們會(huì)將一些信息素沿著它們的路徑釋放出來(lái)，并且在回到蟻巢的路上也會(huì)釋放信息素。
蟻群之間的規(guī)則：
- 螞蟻發(fā)現(xiàn)食物并將其帶回巢穴時(shí)，通常會(huì)遵循已經(jīng)標(biāo)記的路徑返回，即原路返回。在返回過(guò)程中，螞蟻會(huì)釋放歸巢素和信息素，這些化學(xué)物質(zhì)可以吸引其他螞蟻跟隨它的路徑前往食物源。如果路徑上有較多的歸巢素或信息素，則越來(lái)越多的螞蟻將會(huì)選擇這條路徑前往食物。
階段三：當(dāng)螞蟻們回到巢穴時(shí)，它們會(huì)在原來(lái)的路徑上釋放更多信息素，增強(qiáng)這條路徑的吸引力，并且嘗試著尋找更短的路徑。螞蟻們會(huì)在路徑上選擇合適的地方停下來(lái)，釋放信息素，然后返回巢穴。這個(gè)過(guò)程將持續(xù)進(jìn)行，直到螞蟻們找到了最優(yōu)路徑。
根據(jù)以上規(guī)則，隨著時(shí)間的推移，螞蟻們終會(huì)（可能）找到的最優(yōu)路徑。
1.1.2 模擬螞蟻在復(fù)雜地形，找到食物
1.2 算法應(yīng)用
蟻群算法已經(jīng)應(yīng)用于多種優(yōu)化問(wèn)題的求解，比如：
- 旅行商問(wèn)題
- 圖著色問(wèn)題
- 網(wǎng)絡(luò)路由問(wèn)題
- 調(diào)度問(wèn)題
- 生產(chǎn)計(jì)劃問(wèn)題
在這些問(wèn)題中，蟻群算法通常能夠找到較優(yōu)的解。此外，蟻群算法還可以用于機(jī)器學(xué)習(xí)領(lǐng)域中的聚類(lèi)和分類(lèi)等問(wèn)題。
2. 算法解析
想要理解算法？需要去理解以下內(nèi)容：
-
蟻群是如何找到解的？解的步驟是什么？
- 螞蟻在初始時(shí)隨機(jī)選擇一個(gè)起點(diǎn)，并向前行走。
- 當(dāng)螞蟻?zhàn)叩揭粋€(gè)節(jié)點(diǎn)時(shí)，它會(huì)選擇一個(gè)下一個(gè)節(jié)點(diǎn)進(jìn)行移動(dòng)。螞蟻選擇下一個(gè)節(jié)點(diǎn)的概率與該節(jié)點(diǎn)上的信息素濃度成正比。信息素濃度越高的節(jié)點(diǎn)，被選擇的概率也越高。
- 當(dāng)螞蟻移動(dòng)到一個(gè)節(jié)點(diǎn)時(shí)，它會(huì)在該節(jié)點(diǎn)上釋放一定量的信息素。
- 當(dāng)螞蟻找到解后，它會(huì)回到起點(diǎn)，并在路徑上釋放更多的信息素，增強(qiáng)這條路徑的吸引力。
- 當(dāng)其他螞蟻在尋找解的過(guò)程中遇到已經(jīng)被標(biāo)記的路徑時(shí)，它們會(huì)更有可能選擇這條路徑。
- 隨著時(shí)間的推移，信息素會(huì)揮發(fā)，路徑上信息素的濃度會(huì)逐漸降低。這樣，路徑上的信息素濃度會(huì)經(jīng)歷一個(gè)上升和下降的過(guò)程。
- 螞蟻們會(huì)根據(jù)路徑上的信息素濃度來(lái)選擇下一個(gè)節(jié)點(diǎn)。當(dāng)信息素濃度很高時(shí)，它們更有可能選擇這條路徑。
- 螞蟻們持續(xù)尋找解，直到找到最優(yōu)解或者達(dá)到預(yù)設(shè)的迭代次數(shù)。
螞蟻個(gè)體之間就是通過(guò)這種間接的通信機(jī)制實(shí)現(xiàn)協(xié)同搜索最短路徑的目標(biāo)的。我們舉例簡(jiǎn)單說(shuō)明螞蟻覓食行為：
現(xiàn)階段 螞蟻有A→B→C 和 A→D→C兩種較優(yōu)路徑， A→D→C的距離要大于A→B→C
因?yàn)榇罅课浵伒倪x擇概率會(huì)不一樣，會(huì)將螞蟻大致分為兩批，一批走A→B→C ，另一批走A→D→C，單位時(shí)間內(nèi)A→B→C通過(guò)螞蟻也要大于 A→D→C，隨著時(shí)間的推移，A→B→C的信息素越來(lái)越多，正反饋調(diào)節(jié)下，走此條路徑的螞蟻也越來(lái)越多。所以越短路徑的濃度會(huì)越來(lái)越大，經(jīng)過(guò)此短路徑達(dá)到目的地的螞蟻也會(huì)比其他路徑多。這樣大量的螞蟻實(shí)踐之后就找到了最短路徑。所以這個(gè)過(guò)程本質(zhì)可以概括為以下幾點(diǎn)：
- 路徑概率選擇機(jī)制信息素蹤跡越濃的路徑,被選中的概率越大
- 信息素更新機(jī)制路徑越短,路徑上的信息素蹤跡增長(zhǎng)得越快
- 協(xié)同工作機(jī)制螞蟻個(gè)體通過(guò)信息素進(jìn)行信息交流。
螞蟻在蟻群算法中通過(guò)信息素的傳遞和揮發(fā)來(lái)進(jìn)行交流。通過(guò)信息素的傳遞和揮發(fā)，整個(gè)蟻群就會(huì)產(chǎn)生信息正反饋現(xiàn)象、種群分化等。
-
正反饋現(xiàn)象
由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象。某一路徑上走過(guò)的螞蟻越多,則后來(lái)者選擇該路徑的可能性就越大。
?? 在一個(gè)人流量比較大的商場(chǎng)，人們往往會(huì)選擇人流量比較大的走廊或者通道來(lái)走，因?yàn)槿肆髁吭酱螅侥軌蛘f(shuō)明這個(gè)通道是正確的，這樣就會(huì)產(chǎn)生一種信息正反饋現(xiàn)象，后來(lái)的人也會(huì)選擇這條路線(xiàn)，進(jìn)一步增加這條路線(xiàn)的人流量。與蟻群算法類(lèi)似，人們會(huì)根據(jù)前人的經(jīng)驗(yàn)來(lái)選擇路線(xiàn)，從而產(chǎn)生類(lèi)似的正反饋現(xiàn)象。
-
種群分化
種群分化是蟻群算法中的一個(gè)現(xiàn)象，當(dāng)螞蟻在搜索過(guò)程中遇到了局部最優(yōu)解時(shí)，會(huì)一直圍繞這個(gè)局部最優(yōu)解尋找，并且釋放信息素。這會(huì)導(dǎo)致其他螞蟻也會(huì)被吸引過(guò)來(lái)，導(dǎo)致整個(gè)蟻群陷入局部最優(yōu)解，而無(wú)法找到全局最優(yōu)解的情況。這種現(xiàn)象在蟻群算法中是非常常見(jiàn)的，需要特別注意。為了避免種群分化，螞蟻需要具有一定的隨機(jī)性，同時(shí)需要及時(shí)更新信息素，以便發(fā)現(xiàn)全局最優(yōu)解。
??一個(gè)人在某個(gè)領(lǐng)域上有很高的專(zhuān)業(yè)技能，但是如果他過(guò)于專(zhuān)注于這個(gè)領(lǐng)域，就可能會(huì)失去對(duì)其他領(lǐng)域的了解和認(rèn)識(shí)，進(jìn)而導(dǎo)致對(duì)問(wèn)題的認(rèn)識(shí)出現(xiàn)偏差，甚至無(wú)法解決某些問(wèn)題。
就比如圖1. 我如果此刻將原有阻礙去掉一部分，此時(shí)只靠信息素交流的蟻群會(huì)產(chǎn)生種群分化現(xiàn)象。陷入了局部最有解。
當(dāng)蟻群算法陷入局部最優(yōu)解時(shí)，可以使用以下方法進(jìn)行優(yōu)化：
- 增加螞蟻的數(shù)量。增加螞蟻的數(shù)量可以增加搜索的廣度，從而有更大的可能性找到全局最優(yōu)解。
- 調(diào)整信息素?fù)]發(fā)速度。通過(guò)適當(dāng)降低信息素?fù)]發(fā)速度，可以增加信息素在路徑上的積累，從而增加螞蟻選擇該路徑的概率。
- 引入隨機(jī)因素。在蟻群算法中引入隨機(jī)因素，可以使螞蟻更具有探索性，從而有可能跳出局部最優(yōu)解，進(jìn)而找到全局最優(yōu)解。
- 改變參數(shù)。通過(guò)改變蟻群算法中的參數(shù)，如信息素濃度、信息素?fù)]發(fā)速度、啟發(fā)式因子等，可以使算法更加靈活，從而更容易找到全局最優(yōu)解。
- 使用局部搜索算法。在蟻群算法的基礎(chǔ)上，可以結(jié)合局部搜索算法，如模擬退火算法、遺傳算法等，來(lái)尋找全局最優(yōu)解。
上述的情況，可以利用第三條和第四條解決。
3.算法應(yīng)用——TSP問(wèn)題
3.1 TSP旅行商介紹
首先，我們先回顧一下，什么是TSP旅行商問(wèn)題：
假設(shè)有一位郵遞員，他從初始城市（任意一城市）出發(fā)，途徑所有城市并回到初始城市，那么他一共會(huì)有
( n ? 1 ) ! (n-1)! (n?1)!
條路徑。從中找出那條最短路徑，這就是TSP旅行商問(wèn)題。
如果我們遍歷的去找那個(gè)最短路徑，那么隨著城市的增加，計(jì)算量大大增加。
3.2 利用蟻群算法解決TSP問(wèn)題
在這里，螞蟻僅有信息素這一項(xiàng)能力是不夠的。所以我們給與螞蟻一些其他的能力
- 螞蟻在一次旅行中不會(huì)重復(fù)訪(fǎng)問(wèn)相同的城市
- 螞蟻可以知曉城市之間的距離。
- 螞蟻在路上會(huì)釋放信息素
- 螞蟻在選擇下一個(gè)城市的概率依靠以下公式：
p i j k = ( τ i j α ) ( η i j β ) ∑ allowed k ( τ i j α ) ( η i j β ) p_{i j}^{k}=\frac{\left(\tau_{i j}^{\alpha}\right)\left(\eta_{i j}^{\beta}\right)}{\sum_{\text {allowed}_k}\left(\tau_{i j}^{\alpha}\right)\left(\eta_{i j}^{\beta}\right)} pijk?=∑allowedk??(τijα?)(ηijβ?)(τijα?)(ηijβ?)?
| 參數(shù)名稱(chēng) | 參數(shù)意義 | 參數(shù)設(shè)置過(guò)大 | 參數(shù)設(shè)置過(guò)小 |
|---|---|---|---|
| 信息素因子ɑ | 反映了螞蟻運(yùn)動(dòng)過(guò)程中路徑上積累的信息素的量在指導(dǎo)蟻群搜索中的相對(duì)重要程度。取值范圍通常在[1, 4]之間。 | 螞蟻選擇以前已經(jīng)走過(guò)的路可能性較大，容易使隨機(jī)搜索性減弱 | 蟻群易陷入純粹的隨機(jī)搜索，使種群陷入局部最優(yōu) |
| 啟發(fā)函數(shù)因子?? | 反映了啟發(fā)式信息在指導(dǎo)蟻群搜索中的相對(duì)重要程度，蟻群尋優(yōu)過(guò)程中先驗(yàn)性、確定性因素作用的強(qiáng)度取值范圍在[0, 5]之間 | 雖然收斂速度加快，但是易陷入局部最優(yōu) | 蟻群易陷入純粹的隨機(jī)搜索，很難找到最優(yōu)解 |
其實(shí)這個(gè)公式也很好理解，螞蟻選擇城市的概率主要由 τ i j ( t ) \tau_{ij}(t) τij?(t)和 η i j ( ?? ) \eta_{ij}(??) ηij?(t)有關(guān)，分母為螞蟻k可能訪(fǎng)問(wèn)的城市之和（為常數(shù)），這樣才能使螞蟻選擇各個(gè)城市的概率之后為1，符合概率的定義。 τ i j ( t ) \tau_{ij}(t) τij?(t)和$\eta_{ij}(??)上的指數(shù)信息素因子ɑ和啟發(fā)函數(shù)因子??只決定了信息素濃度以及啟發(fā)函數(shù)對(duì)螞蟻k從i到j(luò)的可能性的貢獻(xiàn)程度。
例：下圖為計(jì)算螞蟻從起點(diǎn)城市2到可達(dá)城市的概率（套公式，很好理解）:
圖2. 此圖和此節(jié)部分內(nèi)容借鑒于禿頭小蘇：蟻群算法(實(shí)例幫助理解)
OK,螞蟻有了這些能力后，我們只需要控制一下流程，就可以解決TSP問(wèn)題了，下面是給出了此問(wèn)題的一種常用的解決流程
蟻群算法解決TSP問(wèn)題的算法流程
- 初始化信息素濃度矩陣 τ i j ( t ) \tau_{ij}(t) τij?(t)，啟發(fā)式函數(shù) η i j \eta_{ij} ηij?，以及螞蟻的位置。
- 每只螞蟻按照信息素和啟發(fā)式函數(shù)的概率選擇下一個(gè)城市。
- 記錄螞蟻的路徑和距離。
- 在所有螞蟻?zhàn)咄晁谐鞘兄?，根?jù)螞蟻?zhàn)哌^(guò)的路徑和距離更新信息素濃度矩陣 η i j ( t ) \eta_{ij}(t) ηij?(t)。
- 如果未達(dá)到停止條件，則返回步驟2。
其中，停止條件可以是迭代次數(shù)達(dá)到預(yù)設(shè)值或者最佳解不再改變。
起點(diǎn)的選擇對(duì)最短路徑是有影響的。不同的起點(diǎn)可能會(huì)導(dǎo)致不同的最短路徑。在蟻群算法中，通過(guò)隨機(jī)選擇起始點(diǎn)，可以增加搜索的廣度，從而有更大的可能性找到全局最優(yōu)解。
信息素更新的時(shí)機(jī)一般有兩種方式：
- 在每個(gè)迭代周期結(jié)束后進(jìn)行更新，即在所有螞蟻完成當(dāng)前迭代周期后，根據(jù)其路徑長(zhǎng)度和信息素更新信息素濃度。
- 在每只螞蟻?zhàn)弑樗谐鞘兄?，立即更新信息素濃度?/li>
信息素更新公式:
τ i j ( t + 1 ) = ( 1 ? ρ ) τ i j ( t ) + ∑ k = 1 m Δ τ i j k ( t ) \tau_{i j}(t+1)=(1-\rho) \tau_{i j}(t)+\sum_{k=1}^{m} \Delta \tau_{i j}^{k}(t) τij?(t+1)=(1?ρ)τij?(t)+k=1∑m?Δτijk?(t)
其中， ρ \rho ρ 是信息素?fù)]發(fā)速度， Δ τ i j k ( t ) \Delta \tau_{i j}^{k}(t) Δτijk?(t) 是螞蟻 k 在迭代 t 中走過(guò)路徑 i 到 j 所留下的信息素，m 是螞蟻的數(shù)量。
在每個(gè)迭代周期結(jié)束后進(jìn)行更新或在每只螞蟻?zhàn)弑樗谐鞘兄罅⒓锤滦畔⑺貪舛染伞?/p>
Delta tau 是螞蟻 k 在迭代 t 中走過(guò)路徑 i 到 j 所留下的信息素，不同的 Delta tau 規(guī)則有以下幾種：
- 靜態(tài)規(guī)則：所有螞蟻在搜索過(guò)程中釋放的信息素量是相等的，即 Δ τ i j k ( t ) = Q / L k ( t ) \Delta \tau_{i j}^{k}(t)=Q/L_{k}(t) Δτijk?(t)=Q/Lk?(t)，其中 Q 是常量，L_k(t) 是螞蟻 k 在迭代 t 中走過(guò)的路徑長(zhǎng)度。
- 動(dòng)態(tài)規(guī)則：螞蟻在搜索過(guò)程中釋放的信息素量是動(dòng)態(tài)變化的，即 Δ τ i j k ( t ) = Q / L k ( t ) + ∑ k = 1 m w k ? L k ( t ) \Delta \tau_{i j}^{k}(t)=Q/L_{k}(t)+\sum_{k=1}^{m} w_{k} \cdot L_{k}(t) Δτijk?(t)=Q/Lk?(t)+∑k=1m?wk??Lk?(t)，其中 ∑ k = 1 m w k = 1 \sum_{k=1}^{m} w_{k}=1 ∑k=1m?wk?=1，w_k 是螞蟻 k 對(duì)信息素的貢獻(xiàn)系數(shù)，L_k(t) 是螞蟻 k 在迭代 t 中走過(guò)的路徑長(zhǎng)度。
- 最大值規(guī)則：每只螞蟻在搜索過(guò)程中釋放的信息素量最多為 Δ τ i j k ( t ) = Q L b e s t \Delta \tau_{i j}^{k}(t)=\frac{Q}{L_{best}} Δτijk?(t)=Lbest?Q?，其中 L_best 是迄今為止找到的最短路徑長(zhǎng)度。
以上規(guī)則中，靜態(tài)規(guī)則是最簡(jiǎn)單的，但是可能會(huì)導(dǎo)致信息素的濃度過(guò)高或過(guò)低，從而影響搜索效果。動(dòng)態(tài)規(guī)則可以根據(jù)搜索的進(jìn)展情況動(dòng)態(tài)調(diào)整信息素的濃度，適應(yīng)性更強(qiáng)。最大值規(guī)則可以防止信息素濃度過(guò)高，但可能會(huì)導(dǎo)致搜索無(wú)法跳出局部最優(yōu)解。
例(靜態(tài)規(guī)則)：下圖為信息素的更新過(guò)程，假設(shè)初始時(shí)各路徑信息素濃度為10。
總結(jié)一下：
蟻群算法流程：
- 初始化信息素濃度矩陣??_{ij}(t)，啟發(fā)式函數(shù)??_{ij}，以及螞蟻的位置。
- 每只螞蟻按照信息素和啟發(fā)式函數(shù)的概率選擇下一個(gè)城市。
- 記錄螞蟻的路徑和距離。
- 在所有螞蟻?zhàn)咄晁谐鞘兄螅鶕?jù)螞蟻?zhàn)哌^(guò)的路徑和距離更新信息素濃度矩陣??_{ij}(t)。
- 如果未達(dá)到停止條件，則返回步驟2。
其中，停止條件可以是迭代次數(shù)達(dá)到預(yù)設(shè)值或者最佳解不再改變。
起點(diǎn)的選擇對(duì)最短路徑是有影響的。不同的起點(diǎn)可能會(huì)導(dǎo)致不同的最短路徑。在蟻群算法中，通過(guò)隨機(jī)選擇起始點(diǎn)，可以增加搜索的廣度，從而有更大的可能性找到全局最優(yōu)解。
信息素更新的時(shí)機(jī)一般有兩種方式：
- 在每個(gè)迭代周期結(jié)束后進(jìn)行更新，即在所有螞蟻完成當(dāng)前迭代周期后，根據(jù)其路徑長(zhǎng)度和信息素更新信息素濃度。
- 在每只螞蟻?zhàn)弑樗谐鞘兄?，立即更新信息素濃度?/li>
信息素更新公式:
τ i j ( t + 1 ) = ( 1 ? ρ ) τ i j ( t ) + ∑ k = 1 m Δ τ i j k ( t ) \tau_{i j}(t+1)=(1-\rho) \tau_{i j}(t)+\sum_{k=1}^{m} \Delta \tau_{i j}^{k}(t) τij?(t+1)=(1?ρ)τij?(t)+k=1∑m?Δτijk?(t)
其中， ρ \rho ρ 是信息素?fù)]發(fā)速度， Δ τ i j k ( t ) \Delta \tau_{i j}^{k}(t) Δτijk?(t) 是螞蟻 k 在迭代 t 中走過(guò)路徑 i 到 j 所留下的信息素，m 是螞蟻的數(shù)量。
在每個(gè)迭代周期結(jié)束后進(jìn)行更新或在每只螞蟻?zhàn)弑樗谐鞘兄罅⒓锤滦畔⑺貪舛染伞?/p>
Delta tau 是螞蟻 k 在迭代 t 中走過(guò)路徑 i 到 j 所留下的信息素，不同的 Delta tau 規(guī)則有以下幾種：
- 靜態(tài)規(guī)則：所有螞蟻在搜索過(guò)程中釋放的信息素量是相等的，即 Δ τ i j k ( t ) = Q / L k ( t ) \Delta \tau_{i j}^{k}(t)=Q/L_{k}(t) Δτijk?(t)=Q/Lk?(t)，其中 Q 是常量，L_k(t) 是螞蟻 k 在迭代 t 中走過(guò)的路徑長(zhǎng)度。
- 動(dòng)態(tài)規(guī)則：螞蟻在搜索過(guò)程中釋放的信息素量是動(dòng)態(tài)變化的，即 Δ τ i j k ( t ) = Q / L k ( t ) + ∑ k = 1 m w k ? L k ( t ) \Delta \tau_{i j}^{k}(t)=Q/L_{k}(t)+\sum_{k=1}^{m} w_{k} \cdot L_{k}(t) Δτijk?(t)=Q/Lk?(t)+∑k=1m?wk??Lk?(t)，其中 ∑ k = 1 m w k = 1 \sum_{k=1}^{m} w_{k}=1 ∑k=1m?wk?=1，w_k 是螞蟻 k 對(duì)信息素的貢獻(xiàn)系數(shù)，L_k(t) 是螞蟻 k 在迭代 t 中走過(guò)的路徑長(zhǎng)度。
- 最大值規(guī)則：每只螞蟻在搜索過(guò)程中釋放的信息素量最多為 Δ τ i j k ( t ) = Q L b e s t \Delta \tau_{i j}^{k}(t)=\frac{Q}{L_{best}} Δτijk?(t)=Lbest?Q?，其中 L_best 是迄今為止找到的最短路徑長(zhǎng)度。
4. TSP問(wèn)題—蟻群算法實(shí)現(xiàn)（python版本）
問(wèn)題背景：
假設(shè)有一位郵遞員，他從初始城市（任意一城市）出發(fā)，途徑所有城市并回到初始城市，利用蟻群算法求得最短路徑
數(shù)據(jù)：
以下是10個(gè)城市的坐標(biāo)數(shù)據(jù)：
| 城市 | X坐標(biāo) | Y坐標(biāo) |
|---|---|---|
| A | 5 | 10 |
| B | 6 | 15 |
| C | 10 | 15 |
| D | 14 | 14 |
| E | 20 | 10 |
| F | 16 | 5 |
| G | 8 | 5 |
| H | 4 | 8 |
| I | 8 | 12 |
| J | 12 | 12 |
準(zhǔn)備階段
- 首先，將數(shù)據(jù)存儲(chǔ)在Graph中，并且計(jì)算各個(gè)城市之間的距離distances。
class Graph(object):
def __init__(self, city_location, pheromone=1.0, alpha=1.0, beta=1.0):
self.city_location = city_location
self.n = len(city_location)
# phernmone矩陣
self.pheromone = [[pheromone for _ in range(self.n)] for _ in range(self.n)]
self.alpha = alpha
self.beta = beta
# 城市之間的距離矩陣
self.distances = self._generate_distances()
# 歐式距離作為圖的權(quán)重
def _generate_distances(self):
distances = []
# 遍歷行
# 遍歷列
# 如果行值=列，比如（1,1）(2,2)，這樣就是相同的城市，則距離為零
# 如果行值<列,比如（1，2）（2，3）,這樣就是不同的城市，距離按歐拉距離公式來(lái)算
# 否則，將矩陣的斜對(duì)稱(chēng)位置上的距離來(lái)補(bǔ)（原因：城市之間距離矩陣是一個(gè)distances[i][j] = distances[j][i]特點(diǎn)的矩陣,這樣的目的就是減少至少一半的計(jì)算）
for index_i, _i in enumerate(self.city_location):
row = []
for index_j, _j in enumerate(self.city_location):
if _i == _j:
row.append(0)
elif _i < _j:
x1, y1 = self.city_location[str(_i)]
x2, y2 = self.city_location[str(_j)]
row.append(np.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2))
else:
row.append(distances[index_j][index_i])
distances.append(row)
return distances
- 屬性
-
city_location: 城市位置的字典 -
n: 城市的數(shù)量 -
pheromone: 螞蟻留下的信息素的矩陣 -
alpha: 信息素強(qiáng)度的影響因子 -
beta: 啟發(fā)式因子的影響因子 -
distances: 城市之間距離的矩陣
-
- 方法
-
__init__(self, city_location, pheromone=1.0, alpha=1.0, beta=1.0): 對(duì)象初始化，計(jì)算出城市之間的距離矩陣 -
_generate_distances(self): 計(jì)算城市之間的距離矩陣
-
-
那么，我們將各項(xiàng)能力賦予螞蟻
class Ant(object): def __init__(self, graph, start_city): self.graph = graph self.start_city = start_city self.curr_city = start_city self.visited = [False for _ in range(graph.n)] self.visited[start_city] = True self.tour_length = 0 self.tour = [start_city] def choose_next_city(self): # calculate probabilities of all cities probs = [] total_prob = 0 for i in range(self.graph.n): if not self.visited[i]: prob = self.graph.pheromone[self.curr_city][i] ** self.graph.alpha * \\ (1.0 / self.graph.distances[self.curr_city][i]) ** self.graph.beta probs.append((i, prob)) total_prob += prob # select the next city randomly based on the probabilities r = random.uniform(0, total_prob) upto = 0 for i, prob in probs: if upto + prob >= r: self.curr_city = i self.visited[i] = True self.tour.append(i) self.tour_length += self.graph.distances[self.tour[-2]][i] return upto += prob def tour_complete(self): return len(self.tour) == self.graph.n- 屬性：
-
graph: 圖對(duì)象，表示要在其上運(yùn)行蟻群算法的圖 -
start_city: 整數(shù)，表示螞蟻的起始城市 -
curr_city: 整數(shù)，表示螞蟻當(dāng)前所在城市 -
visited: 布爾列表，表示城市是否已被訪(fǎng)問(wèn) -
tour_length: 浮點(diǎn)數(shù)，表示螞蟻的路徑長(zhǎng)度 -
tour: 整數(shù)列表，表示螞蟻的路徑
-
- 方法：
-
choose_next_city(): 計(jì)算所有城市的概率，根據(jù)概率隨機(jī)選擇下一個(gè)城市 -
tour_complete(): 檢查螞蟻是否已經(jīng)遍歷完所有城市
-
- 屬性：
算法構(gòu)造
通過(guò)上面的準(zhǔn)備，我們現(xiàn)階段有了螞蟻和城市圖，那么，我們來(lái)規(guī)劃一下算法的流程。把：
- 初始化螞蟻和信息素矩陣。
- 螞蟻根據(jù)信息素濃度和啟發(fā)函數(shù)選擇下一個(gè)節(jié)點(diǎn)。
- 螞蟻在路徑上釋放信息素。
- 重復(fù)步驟2和3，直到所有螞蟻都找到了解。
- 評(píng)估每條路徑的適應(yīng)度，并更新信息素矩陣。
- 重復(fù)步驟2到5，直到達(dá)到預(yù)設(shè)的迭代次數(shù)或者找到最優(yōu)解。
這里要考慮選擇哪一種更新策略、更新時(shí)機(jī)：
- 靜態(tài)規(guī)則（這里我選的這個(gè)）
- 在每個(gè)迭代周期結(jié)束后進(jìn)行更新，即在所有螞蟻完成當(dāng)前迭代周期后，根據(jù)其路徑長(zhǎng)度和信息素更新信息素濃度。
def ant_colony(graph, num_ants, num_iterations, evaporation_rate=0.5, q=500):
shortest_tour = None # 最短路徑
shortest_tour_length = float('inf') # 最短路徑長(zhǎng)度
for i in range(num_iterations):
ants = [Ant(graph, random.randint(0, graph.n - 1)) for _ in range(num_ants)] # 隨機(jī)生成螞蟻
for ant in ants:
while not ant.tour_complete():
ant.choose_next_city() # 選擇下一個(gè)城市
ant.tour_length += graph.distances[ant.tour[-1]][ant.start_city] # 計(jì)算路徑長(zhǎng)度
if ant.tour_length < shortest_tour_length:
shortest_tour_length = ant.tour_length
shortest_tour = ant.tour[:]
for i in range(graph.n):
for j in range(graph.n):
if i != j:
graph.pheromone[i][j] *= (1 - evaporation_rate) # 更新?lián)]發(fā)信息素
for ant in ants:
if (i, j) in zip(ant.tour, ant.tour[1:]):
graph.pheromone[i][j] += q / ant.tour_length # 更新釋放信息素
return shortest_tour, shortest_tour_length
- 注釋?zhuān)?
- shortest_tour：最短路徑，初始化為 None。
- shortest_tour_length：最短路徑長(zhǎng)度，初始化為正無(wú)窮。
- ants：螞蟻集合，隨機(jī)生成。
- ant：螞蟻，從 graph 中隨機(jī)選擇一個(gè)起始城市開(kāi)始走。
- choose_next_city：選擇下一個(gè)城市。
- tour_length：路徑長(zhǎng)度，初始化為 0。
- pheromone：信息素。
- evaporation_rate：信息素?fù)]發(fā)率。
- q：信息素強(qiáng)度。
- zip(ant.tour, ant.tour[1:])：將 ant.tour 中的相鄰兩個(gè)元素組成一個(gè)二元組 (i, j)，便于后續(xù)計(jì)算。
- 更新信息素時(shí)，需要更新?lián)]發(fā)信息素和釋放信息素。揮發(fā)信息素是指信息素隨時(shí)間的推移而逐漸消失；釋放信息素是指螞蟻在路徑上釋放信息素，增強(qiáng)這條路徑的吸引力。
- 返回最短路徑和最短路徑長(zhǎng)度。
測(cè)試：
將數(shù)據(jù)和流程帶入：
city_location = {
'A': (5, 10),
'B': (6, 15),
'C': (10, 15),
'D': (14, 14),
'E': (20, 10),
'F': (16, 5),
'G': (8, 5),
'H': (4, 8),
'I': (8, 12),
'J': (12, 12)
}
# 創(chuàng)建Graph對(duì)象
g = Graph(city_location)
shortest_tour, shortest_tour_length = ant_colony(graph=g, num_ants=500, num_iterations=1000)
print(shortest_tour,shortest_tour_length)
# 城市索引
city_index = {city: i for i, city in enumerate(sorted(city_location))}
# 城市索引
city_index = {city: i for i, city in enumerate(sorted(city_location))}
# 城市名稱(chēng)列表
shortest_tour = [list(city_index.keys())[i] for i in shortest_tour]
# 打印結(jié)果
print(shortest_tour)
g.plot_path(shortest_tour)
參考代碼：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-449616.html
import math
import random
class Graph(object):
def __init__(self, n, pheromone=1.0, alpha=1.0, beta=1.0):
self.n = n
self.pheromone = [[pheromone for _ in range(n)] for _ in range(n)]
self.alpha = alpha
self.beta = beta
self.distances = self._generate_distances()
def _generate_distances(self):
# randomly generate distances between cities
distances = []
for i in range(self.n):
row = []
for j in range(self.n):
if i == j:
row.append(0)
elif j > i:
row.append(random.uniform(1, 10))
else:
row.append(distances[j][i])
distances.append(row)
return distances
class Ant(object):
def __init__(self, graph, start_city):
self.graph = graph
self.start_city = start_city
self.curr_city = start_city
self.visited = [False for _ in range(graph.n)]
self.visited[start_city] = True
self.tour_length = 0
self.tour = [start_city]
def choose_next_city(self):
# calculate probabilities of all cities
probs = []
total_prob = 0
for i in range(self.graph.n):
if not self.visited[i]:
prob = self.graph.pheromone[self.curr_city][i] ** self.graph.alpha * \\
(1.0 / self.graph.distances[self.curr_city][i]) ** self.graph.beta
probs.append((i, prob))
total_prob += prob
# select the next city randomly based on the probabilities
r = random.uniform(0, total_prob)
upto = 0
for i, prob in probs:
if upto + prob >= r:
self.curr_city = i
self.visited[i] = True
self.tour.append(i)
self.tour_length += self.graph.distances[self.tour[-2]][i]
return
upto += prob
def tour_complete(self):
return len(self.tour) == self.graph.n
def ant_colony(graph, num_ants, num_iterations, evaporation_rate=0.5, q=500):
shortest_tour = None
shortest_tour_length = float('inf')
for i in range(num_iterations):
# initialize ants
ants = [Ant(graph, random.randint(0, graph.n-1)) for _ in range(num_ants)]
# have each ant choose a path
for ant in ants:
while not ant.tour_complete():
ant.choose_next_city()
ant.tour_length += graph.distances[ant.tour[-1]][ant.start_city]
# check if this ant found a shorter tour
if ant.tour_length < shortest_tour_length:
shortest_tour_length = ant.tour_length
shortest_tour = ant.tour[:]
# update pheromones
for i in range(graph.n):
for j in range(graph.n):
if i != j:
graph.pheromone[i][j] *= (1 - evaporation_rate)
for ant in ants:
if (i, j) in zip(ant.tour, ant.tour[1:]):
graph.pheromone[i][j] += q / ant.tour_length
return shortest_tour, shortest_tour_length
# generate a 11-city TSP problem and solve it using the ant colony algorithm
graph = Graph(11)
shortest_tour, shortest_tour_length = ant_colony(graph, num_ants=10, num_iterations=50)
# print the shortest tour and its length
print("Shortest tour:", shortest_tour)
print("Shortest tour length:", shortest_tour_length)
寫(xiě)在最后，第二次上熱門(mén)，流量還可以，我也是認(rèn)真對(duì)待了這篇文章，寫(xiě)這篇博客的原因就是順便把老師的作業(yè)也寫(xiě)了，作業(yè)你們也看到了，就是用代碼實(shí)現(xiàn)蟻群算法去解決TSP問(wèn)題，對(duì)于蟻群算法，我也是第一次去學(xué)習(xí)，并不是你們所認(rèn)識(shí)的“佬”，說(shuō)是博客，其實(shí)更像一篇記錄我學(xué)習(xí)過(guò)程的日記，對(duì)于人工智能，說(shuō)實(shí)話(huà)，挺有意思的，但考慮到本身實(shí)力情況，只能當(dāng)作暫時(shí)的興趣，大概這門(mén)課結(jié)課的時(shí)候，人工智能系列估計(jì)就不更了，唉畢竟是興趣，不能吃飯，我的實(shí)力也不可能達(dá)到那些“佬”級(jí)別，下一篇估計(jì)也快了，應(yīng)該是神經(jīng)網(wǎng)絡(luò)（泛泛而談），有像了解的可以期待一下，我盡量把正確的，易懂的，可能老師考慮不到的方面給你們講清楚，現(xiàn)學(xué)現(xiàn)賣(mài)的優(yōu)勢(shì)就是能將難點(diǎn)給它點(diǎn)出來(lái)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-449616.html
到了這里，關(guān)于【人工智能】蟻群算法(密恐勿入)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
