1. 概述

比利時(shí)研究人員馬可·多里戈（Marco Dorigo）創(chuàng)建了一個(gè)數(shù)學(xué)模型，科學(xué)地描述了蟻群中集體智慧的過程。 他于 1992 年在他的博士論文中發(fā)表，并將其作為算法實(shí)現(xiàn)。

蟻群優(yōu)化（ACO） 是一種基于種群的隨機(jī)搜索方法，可解決各種組合優(yōu)化問題。 ACO 的核心是信源動(dòng)作（stigmergy）的概念。 1959年，皮埃爾-保羅·格拉塞特（Pierre-Paul Grasset）發(fā)明了信源動(dòng)作 理論來解釋白蟻筑巢的行為。 Stigmergy 由兩個(gè)希臘詞組成：stigma - 信源，和 ergon - 動(dòng)作。

規(guī)范定義是一種間接互動(dòng)類型，經(jīng)與環(huán)境的相互作用，在種群成員之間，依時(shí)間擴(kuò)展。 換言之，其中一個(gè)代理者留下了蹤跡、或以某種方式修改了現(xiàn)場(chǎng)位置，如此其它代理者在進(jìn)入其區(qū)域時(shí)會(huì)收到一些信息。 在螞蟻的情況下，信源動(dòng)作是信息素。 螞蟻在覓食過程中的溝通就是一個(gè)示例：螞蟻彼此相互間接交流，在地面上留下信息素蹤跡，從而影響其它螞蟻的決策過程。 個(gè)體螞蟻之間的這種簡(jiǎn)單交流形式導(dǎo)致了整個(gè)蟻群的復(fù)雜行為和能力。

螞蟻是群居昆蟲，它們按領(lǐng)地生活。 螞蟻的行為是由尋找食物的意圖所控制。 在覓食時(shí)，它們?cè)陬I(lǐng)地漫游。 螞蟻反復(fù)從一個(gè)地方漫游到另一個(gè)地方尋找食物，當(dāng)它爬動(dòng)時(shí)，它會(huì)在地面上沉積一種叫做信息素的有機(jī)化合物。 因此，螞蟻是利用信息素蹤跡相互交流。

當(dāng)一只螞蟻發(fā)現(xiàn)了食物，它會(huì)攜帶盡可能多的食物。 返回時(shí)，它會(huì)沿途沉積信息素，具體取決于食物的數(shù)量和品質(zhì)。 結(jié)果就是，其它螞蟻可以遵循這條路線。 信息素水平越高，選擇這條特定路徑的概率就越高，通過特定路徑的螞蟻越多，這條路線上留下的信息素就越多。

我們來看下面的例子。 假設(shè)有兩條途徑可以從蟻群獲取食物。 首先，地面上沒有信息素。 如此，選擇這兩條路徑的概率相等（50%）。 我們假設(shè)兩只螞蟻分別選擇了這兩條不同的覓食路徑。 這兩條路徑的距離是不同的。 走較短路線的螞蟻會(huì)先于另一只螞蟻到達(dá)食物。 當(dāng)它找到食物時(shí)，它會(huì)帶走一些食物并返回蟻群。 為了追溯返回的路徑，它會(huì)在地面上沉積信息素。 走較短路徑的螞蟻會(huì)更早到達(dá)蟻群。

當(dāng)?shù)谌晃浵佅氤鋈ふ沂澄飼r(shí)，它會(huì)根據(jù)地面上的信息素水平選擇距離較短的路徑。 因?yàn)檩^短的路徑比較長(zhǎng)的信息素較濃，所以第三只螞蟻將遵循信息素較濃的路徑。 當(dāng)螞蟻沿著更長(zhǎng)的路徑返回蟻群時(shí)，更多的螞蟻已經(jīng)邁上了信息素含量更高的路徑。 然后，當(dāng)另一只螞蟻試圖從蟻群到達(dá)目的地（食物）時(shí)，它會(huì)發(fā)現(xiàn)每條路徑都有相同的信息素水平。 那么它會(huì)隨機(jī)選擇其中之一。 一遍遍地重復(fù)這個(gè)過程，一段時(shí)間后，較短的路徑將比其它路徑獲得更多的信息素，且螞蟻?zhàn)哌@條路徑的概率會(huì)更高。

ACO 算法是一種群體智能算法。 依據(jù)蟻群的覓食過程進(jìn)行建模，利用蟻群的內(nèi)部數(shù)據(jù)傳輸機(jī)制建立各種環(huán)境下的最短路徑。 路徑上殘留的信息素濃度越高，螞蟻選擇這條路徑的可能性就越大。 與此同時(shí)，信息素的濃度隨著時(shí)間的推移而減弱。 因此，由于蟻群的行為，螞蟻通過反饋機(jī)制不斷學(xué)習(xí)和優(yōu)化，從而判定最短的覓食路徑。 ACO 算法廣泛用于路徑規(guī)劃。

2. 算法原理

在 ACO 中，一組稱為人工螞蟻的軟件代理者為給定的優(yōu)化問題尋找良性解決方案。 為了應(yīng)用 ACO，優(yōu)化問題將轉(zhuǎn)換為在加權(quán)圖形上查找最佳路徑的問題。 人工螞蟻（以下簡(jiǎn)稱螞蟻）逐漸構(gòu)建沿圖形移動(dòng)的解決方案。 構(gòu)建解決方案的過程是隨機(jī)的，并且取決于信息素模型 — 與圖形組件（節(jié)點(diǎn)或邊線）相關(guān)的一套參數(shù)，其值在執(zhí)行過程中會(huì)由螞蟻修改。

我們研究旅行推銷員問題的算法。 我們有一組位置（城市）和它們之間的距離。 問題是找到一條最短長(zhǎng)度的封閉路徑，每個(gè)城市只訪問一次。 一組相關(guān)聯(lián)城市，再配合一組圖形頂點(diǎn)而定義的圖形稱為構(gòu)造圖。 由于有可能從任意給定城市移動(dòng)到任意其它城市，因此構(gòu)造圖是完全連接的，頂點(diǎn)數(shù)等于城市數(shù)。 我們將頂點(diǎn)之間的邊線長(zhǎng)度與其所代表城市之間的距離設(shè)定成正比，并將信息素值和啟發(fā)式值與圖形連線相關(guān)聯(lián)。 信息素值在運(yùn)行時(shí)發(fā)生變化，體現(xiàn)蟻群的累積經(jīng)驗(yàn)，而啟發(fā)式值是與問題相關(guān)的值。

螞蟻按以下方式構(gòu)造解決方案。 每只螞蟻從一個(gè)隨機(jī)選擇的城市（構(gòu)造圖形頂點(diǎn)）開始。 然后，在每個(gè)構(gòu)造步驟中，它沿著圖形的邊線移動(dòng)。 每只螞蟻保存其路徑的記憶內(nèi)存，并在后續(xù)步驟中不選擇通往已訪問過頂點(diǎn)的邊線。 一旦螞蟻在遍訪了圖形的所有頂點(diǎn)后，即構(gòu)建了一個(gè)解決方案。 在每個(gè)構(gòu)造步驟中，螞蟻按概率選擇下一個(gè)通向尚未訪問頂點(diǎn)的邊線。 概率規(guī)則基于信息素值和啟發(fā)式信息：與邊線相關(guān)的信息素和啟發(fā)式值越高，螞蟻選擇該特定邊線的概率就越高。 一旦所有的螞蟻都完成了它們的旅程，隨即就會(huì)更新邊線的信息素。 每次信息素值的初值都會(huì)按一定百分比減少。 重復(fù)此過程，直到滿足終止準(zhǔn)則。

基于信息素的交流是自然界中廣泛采用的最有效的溝通方式之一。 信息素由蜜蜂、螞蟻和白蟻等社會(huì)性昆蟲用于代理者之間的交流。 由于其可行性，人工信息素也已被應(yīng)用于多機(jī)器人和群體機(jī)器人系統(tǒng)。 我們能如何理解我們的螞蟻真的找到了最短路線呢？ 這是一個(gè)很棒的測(cè)試用例：所有點(diǎn)排列成一個(gè)圓圈。 對(duì)它們來說，最短的路徑永遠(yuǎn)是一樣的 — 圓圈。

首個(gè) ACO 算法被稱為螞蟻系統(tǒng)，旨在解決旅行推銷員問題，其目標(biāo)是找到往返多個(gè)相連城市的最短路徑。 普通算法相對(duì)簡(jiǎn)單，基于一組螞蟻，每只螞蟻完成繞所有城市的可能路徑之一。 在每一步，螞蟻都會(huì)根據(jù)一些規(guī)則選擇一條從一個(gè)城市到另一個(gè)城市的路徑：

1. 它應(yīng)該每個(gè)城市只訪問一次；

2. 選擇遙遠(yuǎn)城市的可能性較?。梢娦裕?；

3. 在兩個(gè)城市之間的邊界上鋪設(shè)的信息素蹤跡越密集，選擇這條邊界的可能性就越大；

4. 一條路徑完成后，如果路徑較短，螞蟻會(huì)在經(jīng)過的所有邊線沉積更多的信息素；

5. 每次迭代后，信息素蹤跡蒸發(fā)。

編輯切換為居中

圖例 1. 五個(gè)節(jié)點(diǎn)的可能路徑示例

3. 修訂版

已知的 ACO 算法的若干種最流行的變體。 我們來研究一下：

螞蟻系統(tǒng)（AS）。螞蟻系統(tǒng)是第一個(gè) ACO 算法。

蟻群系統(tǒng)（ACS）。在蟻群系統(tǒng)算法中，原始的螞蟻系統(tǒng)在三個(gè)方面進(jìn)行了修改： 1. 邊線選擇偏向于因循沿襲（即有利于選擇信息素較多的最短邊線的概率）； 2. 在構(gòu)建解決方案時(shí)，螞蟻應(yīng)用局部信息素更新規(guī)則來改變它們所選邊線的信息素水平； 3. 在每次迭代結(jié)束時(shí)，只有最佳螞蟻才能應(yīng)用修改后的全局信息素更新規(guī)則來更新蹤跡。

精英螞蟻系統(tǒng)。在這個(gè)算法中，全局最佳解決方案在每次迭代后（即使未曾重新訪問該蹤跡）將信息素與所有其它螞蟻一起沉積在其蹤跡上。 精英策略的目標(biāo)是導(dǎo)引所有螞蟻的搜索，從而構(gòu)造包含當(dāng)前最佳路線鏈接的解決方案。

最大最小螞蟻系統(tǒng)（MMAS）。此算法控制每個(gè)蹤跡上信息素的最大和最小數(shù)量。 只有最好的全局旅途、或最好的重復(fù)旅途才能在它們的蹤跡中加上信息素。 為了避免搜索算法陷入停滯，每條蹤跡上可能的信息素量范圍限定在 [τ max, τ min] 區(qū)間。 所有邊線都用 τ max 初始化，以便加快解決方案的探索。 當(dāng)接近停滯時(shí)，蹤跡被重新初始化為 τ max。

基于排位的螞蟻系統(tǒng)（Asrank）。所有解決方案都根據(jù)其長(zhǎng)度進(jìn)行排位。 只有固定數(shù)量的最佳螞蟻才能更新它們的挑戰(zhàn)。 對(duì)于每種解決方案的信息素沉積量進(jìn)行加權(quán)，如此擁有較短路徑的解決方案比較長(zhǎng)路徑的解決方案沉積的信息素更多。

并行蟻群優(yōu)化（PACO）。具有交流策略的蟻群系統(tǒng)（ACS）。 人工螞蟻被分為若干組。 提議七種交流方法，來更新處理旅行推銷員問題的 ACS 群組之間的信息素水平。

連續(xù)正交蟻群（COAC）。COAC 信息素沉積機(jī)制，令螞蟻能夠協(xié)調(diào)、有效地搜尋解決方案。 通過運(yùn)用正交設(shè)計(jì)方法，允許區(qū)域內(nèi)的螞蟻可以快速、有效地探索其所選區(qū)域，并具有增強(qiáng)的全局搜索能力和準(zhǔn)確性。 正交設(shè)計(jì)方法和自適應(yīng)半徑調(diào)整方法，也可以擴(kuò)展到其它優(yōu)化算法，為解決實(shí)際問題提供更廣泛的優(yōu)勢(shì)。

蟻群的遞歸優(yōu)化。這是一種遞歸形式的蟻群，它將整個(gè)搜索區(qū)域劃分為若干個(gè)子域，并解決這些子域中的問題。 比較所有子域的結(jié)果，取少量最佳子域進(jìn)入下一個(gè)級(jí)別。 與所選結(jié)果相對(duì)應(yīng)的子域被進(jìn)一步細(xì)分，并重復(fù)該過程，直到獲得所需的精度。 該方法已在矯正地球物理反演問題上進(jìn)行了測(cè)試，證明了其有效性。

上面研究的蟻群算法最初是為解決圖形的優(yōu)化問題而開發(fā)的。 將問題集成到此類算法中，并將問題條件作為算法參數(shù)給出 — 圖形節(jié)點(diǎn)的坐標(biāo)。 因此，基于 ACO 原理的算法是高度專業(yè)化的。 此類算法不適用于我們的任務(wù)，因?yàn)槲覀兾床捎霉潭ㄗ鴺?biāo)。 我們也許有任意坐標(biāo)，包括類似的坐標(biāo)。 為了解決交易金融產(chǎn)品領(lǐng)域的各種優(yōu)化問題，包括訓(xùn)練神經(jīng)網(wǎng)絡(luò)，我們需要開發(fā)一種新的通用算法，如此它能夠通過我們的特殊測(cè)試，即它應(yīng)該是一個(gè)全新的 ACO。

我們研究一下算法的基本概念。 就像在規(guī)范版本中一樣，我們將擁有一個(gè)蟻群。 我們不用信息素標(biāo)記已踏過的路徑，它們可以去多維空間中的任何地方，記住和保存路線。 對(duì)于連續(xù)的步驟，這似乎不合適，因?yàn)檠刂宦肪€前進(jìn)的概率趨于零。 此外，根本不需要記憶節(jié)點(diǎn)，因?yàn)闆]有重復(fù)的順序通道問題 — 有必要將問題從算法中摘出。 那好，我們應(yīng)該怎么做呢？ 在現(xiàn)階段，完全不清楚這個(gè)概念的發(fā)展方向。

好吧，然后我們?cè)俅巫⒁獾綄⑽覀兊男滤惴ㄅc規(guī)范算法區(qū)分開來的要點(diǎn)：

1. 空間中沒有固定點(diǎn)。

2. 沒有必要按一定的順序通過路徑。

3. 由于沒有路徑，因此無物需用信息素來標(biāo)記。

然后，我們喚醒駐留腦海的蟻群的念頭。 我們可以用信息素標(biāo)記螞蟻?zhàn)哌^的點(diǎn)，而非它們走過的路徑。 我們將適應(yīng)度函數(shù)的值作為信息素?cái)?shù)，設(shè)置到當(dāng)前迭代中螞蟻位置。 然后螞蟻將不得不向信息素更多的坐標(biāo)移動(dòng)。 但當(dāng)所有的螞蟻都跑到一個(gè)點(diǎn)時(shí)，我們可能會(huì)遇到一個(gè)問題 — 該點(diǎn)的信息素肯定最多。 考慮到這些點(diǎn)都是優(yōu)化函數(shù)的變量，故這不一定是問題的最佳解決方案。 我們還記得，在經(jīng)典 ACO 中，節(jié)點(diǎn)路徑的長(zhǎng)度也很重要。 選擇的路徑越短越好。 故我們不得不計(jì)算從當(dāng)前位置到螞蟻前往地點(diǎn)的距離。 下一個(gè)地方是其它螞蟻所在的地方，即我們接受螞蟻以一定的隨機(jī)性相互移動(dòng)的概念。