【正文】 即城市的集合， ??為連接節(jié)點(diǎn)的無(wú)向連接弧即連接兩兩城市的道 路，已知 ?? = ??個(gè)城市兩兩之間的距離，求一條路徑使得旅行商依次經(jīng)過(guò)每個(gè)城市一次且總路程最短。旅行商問(wèn)題作為一個(gè)組合優(yōu)化難題是螞蟻系統(tǒng)最早應(yīng)用的問(wèn)題，而且他是一個(gè)最短路徑問(wèn)題，與蟻群的覓食行為非常相似，因此，為了解釋蟻群算法的基本模型，在本節(jié)首先借由旅行商問(wèn)題（ TSP）給出螞蟻系統(tǒng)的數(shù)學(xué)模型。 （二） 蟻群算法基本模型 在人工螞蟻系統(tǒng)的基礎(chǔ)上， Dorigo 提出了最早的蟻群算法 —— 螞蟻系統(tǒng)，大部分蟻群算法都是以螞蟻系統(tǒng)為原型的。信息素?fù)]發(fā)可以在一定程度上彌補(bǔ)這個(gè)缺點(diǎn)，此外也可以在算法中引入改進(jìn)措施進(jìn)行彌補(bǔ)。此外，由于存在啟發(fā)式信息，蟻群算法獲得初始解的能力較隨機(jī)生成初始解的算法更強(qiáng)，與其他算法結(jié)合可以獲得較好 的結(jié)果，例如使用蟻群算法迭代若干次后作為遺傳算法的初始解進(jìn)行交叉，變異等操作。此外，由于任務(wù)是由群體完成的，所以單個(gè)螞蟻不工作不會(huì)對(duì)群體行為造成影響。螞蟻搜索時(shí)基于概率決策而不是確定型決策，使得解空間較大，所有路徑都有可能被找到。 在人工螞蟻系統(tǒng)的基礎(chǔ)上， Dorigo 提出了蟻群算法。 （ 2） 信息素更新機(jī)制的差別 真實(shí)螞蟻在行進(jìn)的同時(shí)不斷釋放著信息素，并且在前進(jìn)和返回的途中都在釋放信息素；人工螞蟻在前進(jìn)過(guò)程不釋放信息素，只在返回的途中釋放信息素，并且信息素的釋放是在瞬間完成的。螞蟻系統(tǒng)的這種自組織性使蟻群算法具有易于控制等特點(diǎn)。所有分支路徑又組成了螞蟻的整個(gè)路徑，即通過(guò)局部路徑搜索完成整個(gè)路徑的搜索。由于這種行為有利于瑪麗搜索不同路徑，防止過(guò)早收斂，因此在人工螞蟻系統(tǒng)中人為建立了信息素?fù)]發(fā)機(jī)制，定期在所有路徑上揮發(fā)相同量的信息素。這種信息素更新的機(jī)制是螞蟻系統(tǒng)的關(guān)鍵，形成了信息素的正反 饋效應(yīng)，使螞蟻漸漸集中于某些路徑，也使蟻群算法具有收斂性。它們的個(gè)體行為受群體內(nèi)其他個(gè)體行為的影響，同時(shí)影響著其他個(gè)體的行為，而它們這種相互影響、相互合作的行為的目的，是完成群體的共同的任務(wù)，如覓食。 人工螞蟻系統(tǒng)的建立，一方面參照并借鑒了真實(shí)螞蟻系統(tǒng)的特性，是在觀察和實(shí)驗(yàn)的基礎(chǔ)上對(duì)真實(shí)螞蟻覓食行為的一種抽象。信息素的這個(gè)揮發(fā)機(jī)制可以描述為： ?????? ←(1???)?????? ?(??， ??)∈ ?? () 其中 ?? ∈ (0， 1]， 表示揮發(fā)系數(shù)。人工蟻群系統(tǒng)中，信息素的揮發(fā)和信息素的釋放是交互進(jìn)行的。 信息素?fù)]發(fā)機(jī)制 ：自然蟻群系統(tǒng)也有信息素?fù)]發(fā)現(xiàn)象，但是對(duì)于蟻群路徑探索行為的促進(jìn)作用并不明顯。設(shè)更新的信息素的量為 ?????，則信息素的更新機(jī)制可以簡(jiǎn)單描述為： ?????? ←??????+????? () 從式（ ）可以看出，一旦有螞蟻經(jīng)過(guò)某條路徑，那么該路徑上必然會(huì) 增加一定量的信息素。然后，螞蟻會(huì)憑借人工賦予的智能對(duì)解的性能進(jìn)行評(píng)估，如 果當(dāng)前經(jīng)過(guò)的路徑的解較好，則在回蟻穴的途中釋放信息素，這也使蟻群表現(xiàn)為信息素反向更新。此時(shí)第 ??只螞蟻處于第 ??個(gè)節(jié)點(diǎn)選擇 ??作為下一個(gè)節(jié)點(diǎn)的概率為： ???????? = {????????∑ ????????????????? ??∈ ??????0 ?? ? ?????? () 其中， ??????為螞蟻 ??在節(jié)點(diǎn) ??上可以選擇的相鄰節(jié)點(diǎn)的集合。在搜索和行進(jìn)的過(guò)程中，螞蟻不釋放信息素，即沒(méi)有直接的信息素正向更新。選擇概率的大小取決于可選擇的節(jié)點(diǎn)間信息素濃度的大小。為此，可以引入現(xiàn)實(shí)中自然蟻群也具有的信息素?fù)]發(fā)現(xiàn)象，使得所有路徑上的信息素以一定的速度揮發(fā)，降低被搜索過(guò)多的路徑上的信息素，從而讓其他路徑有更大的概率被螞蟻選擇。此外，由于人工螞蟻具備了評(píng)估比較能力，因?yàn)榭梢愿鶕?jù)解的質(zhì)量決定在路徑上釋放的信息素的量。 因此，解決這個(gè)問(wèn)題的關(guān)鍵是賦予人工螞蟻一些不同于自然螞蟻的能力，建立一個(gè)有效的信息素更新機(jī)制。究其根本，這個(gè)問(wèn)題是由螞蟻群體信息素的正反饋?zhàn)饔眉葱畔⑺氐恼蚋乱鸬摹? 然而人們發(fā)現(xiàn)，僅僅對(duì)自然界中的螞蟻進(jìn)行模仿存在很大的缺陷：由于螞蟻在進(jìn)行路徑選擇時(shí)依據(jù)的是信息素，螞蟻本身對(duì)路徑的長(zhǎng)短并沒(méi)有直觀預(yù)見(jiàn)。在這個(gè)例子中，粗線表示的路徑即為螞蟻找到的最短路徑。例如，考慮一個(gè)靜態(tài)連接圖?? = (??， ??)， 如圖 所示，其中 ??表示節(jié)點(diǎn)集合，它的絕對(duì)值為節(jié)點(diǎn)數(shù)量， ??表示連接 ??中節(jié)點(diǎn)的邊的集合。 Deneubourg進(jìn)行的實(shí)驗(yàn)也證明了，這是蟻群集中到較短路徑的必須方式，如果螞蟻僅僅在前往覓食或返回巢穴的過(guò)程中釋放信息素，那蟻群是無(wú)法找到巢穴與食物的最短路徑的。 Liu 采用蒙特卡羅方法對(duì)此系統(tǒng)進(jìn)行了模擬，證實(shí)了模型對(duì)實(shí)驗(yàn)描述的有效性。 ??表示進(jìn)行隨機(jī)選擇程度， ??值越大，螞蟻越忽略信息素對(duì)自己選擇的作用。 ??表示公式的非線性程度， ??值越大，信息素濃度差別的影響就越大。而螞 蟻數(shù)量對(duì)螞蟻路徑選擇的影響，是通過(guò)信息素濃度來(lái)實(shí)現(xiàn)的。設(shè) ????和 ????是第 ??只螞蟻經(jīng)過(guò)某一橋后在A 橋和 B 橋上已經(jīng)經(jīng)過(guò)的螞蟻數(shù)，那么第 ?? +1只螞蟻選擇分支 A 的概率為 ???? = (??+????)??(??+????)?? +(??+????)?? ( ) 同時(shí)，這只螞蟻選擇分支 B 的概率為： ???? = (??+????)??(??+????)?? +(??+????)?? ( ) 顯然，有 ????+???? = 1，也就是說(shuō)這只螞蟻必然需要在兩個(gè)分支中選擇一個(gè)。 圖 雙橋?qū)嶒?yàn)的附加實(shí)驗(yàn)及其結(jié)果 在雙橋?qū)嶒?yàn)后， Deneuborug 和他同事嘗試用數(shù)學(xué)方法解釋在實(shí)驗(yàn)中觀察到的蟻群現(xiàn)象，提出了一個(gè)簡(jiǎn)單的隨機(jī)模型，形成了螞蟻系統(tǒng)和蟻群系統(tǒng)的雛形。有趣的是，在出現(xiàn)新的較短路徑后，螞蟻群體并沒(méi)有選擇較短路徑，而是仍然選擇原來(lái)的較長(zhǎng)路徑，如圖 （ b）所示。 圖 雙橋?qū)嶒?yàn)（ 2）及其實(shí)驗(yàn)結(jié)果 在幾年后， Dorigo 和 Stutzle（ 2021） [21]考慮到另一種情況：如果在螞蟻集中于某一條覓食路徑后在添加一條新的路徑，那么蟻群的 行為會(huì)發(fā)生怎樣的變化？他們?cè)陔p橋的基礎(chǔ)上，進(jìn)行了附加實(shí)驗(yàn)。 與雙橋?qū)嶒?yàn)（ 1）相比，雙橋?qū)嶒?yàn)（ 2）覓食初期隨意波動(dòng)的影響大大減小，起作用的主要是媒介質(zhì)、自身催化和差異路徑長(zhǎng)度等機(jī)制。 其原因可以解釋為：在覓食的最初期，螞蟻隨機(jī)選擇覓食途徑，因此較長(zhǎng)一橋和較短一橋 選擇概率相等 ，然而當(dāng)螞蟻發(fā)現(xiàn)兩橋的長(zhǎng)度差別后，便更傾向于走更短的路徑，從而迅速的在較短路徑上留下濃度很高的信息素，強(qiáng)化了蟻群的正反饋行為。 圖 雙橋?qū)嶒?yàn)（ 1）及其實(shí)驗(yàn)結(jié)果 在 Gross 等人（ 1989）的實(shí)驗(yàn)中 [20]，兩橋的長(zhǎng)度不一樣，較長(zhǎng)的一條為 較短的一條長(zhǎng)度的兩倍，也就是說(shuō)兩橋的長(zhǎng)度比設(shè)定為 2:1（如圖 （ a）所示）。在這個(gè)實(shí)驗(yàn)中，螞蟻的微觀行為可以解釋螞蟻群體集中于一條路徑的宏觀現(xiàn)象。如果時(shí)間足夠長(zhǎng)，這種現(xiàn)象會(huì)導(dǎo)致所有螞蟻?zhàn)罱K都選擇某一條路徑。在初期，兩橋上的信息素濃度大致相等，然而由于隨機(jī)波動(dòng)，雙橋中的一個(gè)也許會(huì)擁有更多的信息素，于是螞蟻群體更加傾向于走這一路徑，并留下更多的信息素。實(shí)驗(yàn)的結(jié)果顯示（如果 （ b）所示），螞蟻群體只有很小的概率會(huì)均勻選擇兩橋，大多數(shù)情況下，螞蟻群體會(huì)漸漸只選擇其中某一橋，而兩橋被單一選擇的概率幾乎是相等的。他們?cè)谠囼?yàn)中測(cè)試了不同長(zhǎng)度的雙橋（分別稱為雙橋?qū)嶒?yàn)（ 1）和雙橋?qū)嶒?yàn)（ 2）），得到了十分重要的結(jié)論。 為了研究螞蟻群體覓食行為的特征， Deneubourg 及他的同事們?cè)O(shè)計(jì)了一種雙橋?qū)嶒?yàn) [19]。于是，蟻群的集體行動(dòng)便表現(xiàn)出一種信息正反饋現(xiàn)象。另外融合了目前解決 TSP 問(wèn)題最好的改進(jìn)思想 —— 最大最小螞蟻系統(tǒng)，在尋優(yōu)過(guò)程中進(jìn)一步提高解的質(zhì)量并盡可能保障其收斂速度。 蟻群算法基于信息素正反饋機(jī)制，為求得質(zhì)量較高的解，由于初期信息素匱乏，導(dǎo)致收斂速度較慢。 2021 年 劉敏等 [18]提出適應(yīng)的模擬遺傳算法，提出自適應(yīng)變異概率的概念與理論改善遺傳算法的收斂速度，以解決遺傳算法中變異概率取值較小且在整個(gè)搜索過(guò)程中固定不變，易陷入局部最小值的不足，雜交母體選擇是以整體退火選擇的方式，可克服種群早熟化，避免過(guò)早收斂。模擬退火算法的 Metropolis 準(zhǔn)則可以有限度地接受惡化解，并可以使 其接受概率趨向于零，使得算法局部搜索能力強(qiáng)。該混合算法是從一組隨機(jī)初始解開(kāi)始，先通過(guò)選擇、交叉、變異等免疫操作來(lái)產(chǎn)生一組的新抗體，然后再對(duì)各新抗體進(jìn)行模擬退火求最優(yōu)解。此混合算法比基本遺傳算法在進(jìn)化速度上有很大提高，且在局部搜索能力方面也有非常明顯的改進(jìn)，此 算法還在從當(dāng)前局部最優(yōu)狀態(tài)向其他未被搜索空間轉(zhuǎn)移的能力上有了較大的實(shí)質(zhì)性突破。 2021 年李紅軍提出模擬退火與遺傳算法相結(jié)合，此混合算法是以遺傳算法為主題流程，側(cè)重全局搜索，將模擬退貨機(jī)制融入其中，側(cè)重局部搜索，是在對(duì)每個(gè)基因個(gè)體實(shí)施一定演變而產(chǎn)生惡化解的設(shè)計(jì)引用了遺傳算法中的變異和倒位的思想。 2. 國(guó)內(nèi)模擬退火算法研究 從模擬退火算法自身要素改進(jìn)的角度出發(fā)， 2021 年，陳華根、李麗華等提出基于 ingber提出的非常快速的模擬退火算法（簡(jiǎn)稱 VFSA）改進(jìn)的 MVFSA 算法，該算法針對(duì) VFSA 算法的兩個(gè)基本特點(diǎn)，主要作兩點(diǎn)改動(dòng)： 1，在高溫下，一模型的全局?jǐn)_動(dòng)方式代替目前的擾動(dòng)方式； 2，在低溫下，對(duì)模型擾動(dòng)進(jìn)行某種約束，邊擾動(dòng)邊逐步減小模型擾動(dòng)空間，以提高新模型被接受的機(jī)率。 等人的實(shí)驗(yàn)結(jié)果表明， SA 算法不但可以很好 地完成圖像恢復(fù)工作，而且它還具有很大的并行性。在 Boltzmann 機(jī)中，即使系統(tǒng)落入了局部最優(yōu)的陷阱，經(jīng)過(guò)一段時(shí)間后，它還能再跳出來(lái)，使系統(tǒng)最終將往全局最優(yōu)質(zhì)的方向收斂。它利用粒子群算法的較強(qiáng)的全局搜索能力生成信息素分布，再利用蟻群算法的正反饋機(jī)制求問(wèn)題的精確解，汲取各自的優(yōu)勢(shì)，以達(dá)到優(yōu)勢(shì)互補(bǔ)。 在雙（多）種群蟻群算法方面，國(guó)內(nèi)的郟宣耀和滕少華（ 2021） [15]也提出一種雙種群改進(jìn)蟻群算法，將兩個(gè)螞蟻群體分別獨(dú)立進(jìn)化，并定期交換信息素，緩解了信息素的局部收斂現(xiàn)象。此外，馮遠(yuǎn)靜等（ 2021） [14]將蟻群算法與模擬退火算法結(jié)合，利用蟻群算法生成初始解，然后在每個(gè)退火溫度上進(jìn)行抽樣準(zhǔn)則檢驗(yàn)產(chǎn)生新解，在更新信息素后再進(jìn)行蟻群搜索，如此讓蟻群算法和模擬退火算法交替進(jìn)行。覃剛力等人（ 2021） [13]提出了一種動(dòng)態(tài)自適應(yīng)調(diào)整信息素的蟻群算法，將普通蟻群系統(tǒng)中定位常數(shù)的 ??改為可變函數(shù)代替，在擴(kuò)大搜索空間和充分用信息素反饋信息之間取得了較好的平衡。吳斌和史忠植（ 2021） [12]提出一種基于蟻群算法的旅行商問(wèn)題分段求解方法，將提出的相遇算法與分段算法相結(jié)合，提高了螞蟻覓食的質(zhì)量和解的質(zhì)量。 3. 國(guó)內(nèi)蟻群算法改進(jìn)研究 從信息素更新機(jī)制的改進(jìn)角度出發(fā)，李士勇等人（ 2021） [10]提出了最優(yōu) —最差螞蟻系統(tǒng)，對(duì)最優(yōu)解進(jìn)行更大限度的增強(qiáng)，而對(duì)最差解進(jìn)行削弱，使得屬于最優(yōu)路徑的邊與屬于最差路徑的邊之間的信息素量差異進(jìn)一步增大，從而 使螞蟻的搜索行為更集中于最優(yōu)解的附近。在此模型的基礎(chǔ)上，考察智能體在動(dòng)態(tài)環(huán)境中的相互協(xié)作行為。其中建立了兩種不同類型的螞蟻模型，并加入了蟻穴模型，食物堆模型和天地模型。 為了充分利用學(xué)習(xí)機(jī)制，強(qiáng)化最優(yōu)信息的反饋， 1995 年 Gambardella 和 Dorigo 提出了AntQ 算法 [9]，該算法建立了螞蟻系統(tǒng)與 Qlearning 的聯(lián)系，僅讓每一次循環(huán)中最短路徑上的信息素濃度作更新。 KAWAMURA 等（ 2021） [8]提出的雙蟻群系統(tǒng)，通過(guò)蟻群間的互動(dòng)分享信息素，在充分利用優(yōu)秀解的同時(shí)夸大搜索的解空間，比單蟻群 系統(tǒng)取得更好的效果。 Merkle 等人（ 2021） [7]提出了精英遺忘策略，使精英螞蟻忘記一部分已找到的局部最優(yōu)解，從而防止過(guò)早收斂，擴(kuò)大搜索空間，有助于找到全局最優(yōu)解。類似于遺傳算法中精英策略保留住一代中最適應(yīng)的個(gè)體，蟻群算法中的精英策略在每次循環(huán)后給最優(yōu)解以額外的信息素量以保持最優(yōu)解的吸引力，從而得到全局最優(yōu)解。Middendorf Gagne， et al 項(xiàng)目調(diào)度 Project scheduling Merkle， et al 組車間 Group scheduling Blum 2. 國(guó)外蟻群算法改進(jìn)研究 在蟻群算法產(chǎn)生之后，許多學(xué)者對(duì)其進(jìn)行了改進(jìn)研究，其中大部分改進(jìn)研究集中于信息素更新機(jī)制的改進(jìn)。在調(diào)度問(wèn)題領(lǐng)域，除了經(jīng)典資源受限項(xiàng)目調(diào)度問(wèn)題，它還被應(yīng)用于車間調(diào)度等多個(gè)問(wèn)題，對(duì)這些問(wèn)題的相關(guān)研究列于表 [4]中。國(guó)內(nèi)學(xué)者鄭超和高連生（ 2021）也將蟻群算法應(yīng)用于RCPSP，采用串行進(jìn)度生