【文章內(nèi)容簡(jiǎn)介】 行某種約束，邊擾動(dòng)邊逐步減小模型擾動(dòng)空間，以提高新模型被接受的機(jī)率。 從模擬退火算法與其他搜索算法相結(jié)合的角度出發(fā)， 1997 年王雪梅、王義和提出模擬退火算法與遺傳算法相結(jié)合，主要思想是在傳統(tǒng) GA的生存策略中引入 Bloztman 生存機(jī)制，將模擬退火算法融入遺傳算法的新個(gè)體產(chǎn)生中，以求得最優(yōu)解作為遺傳的父本。 2021 年李紅軍提出模擬退火與遺傳算法相結(jié)合，此混合算法是以遺傳算法為主題流程，側(cè)重全局搜索，將模擬退貨機(jī)制融入其中，側(cè)重局部搜索，是在對(duì)每個(gè)基因個(gè)體實(shí)施一定演變而產(chǎn)生惡化解的設(shè)計(jì)引用了遺傳算法中的變異和倒位的思想。此算法策略是從全局最優(yōu)解的搜索角度和算法的進(jìn)化速度上來(lái)提高模擬退火遺傳算法的性能。此混合算法比基本遺傳算法在進(jìn)化速度上有很大提高，且在局部搜索能力方面也有非常明顯的改進(jìn)，此 算法還在從當(dāng)前局部最優(yōu)狀態(tài)向其他未被搜索空間轉(zhuǎn)移的能力上有了較大的實(shí)質(zhì)性突破。 2021 年余建軍，孫樹棟 [17]提出將模擬退火與免疫算法混合。該混合算法是從一組隨機(jī)初始解開始，先通過(guò)選擇、交叉、變異等免疫操作來(lái)產(chǎn)生一組的新抗體，然后再對(duì)各新抗體進(jìn)行模擬退火求最優(yōu)解。免疫算法的全局搜索能力好，可以快速在解空間的全體解搜索出來(lái)，不會(huì)陷入局部最優(yōu)級(jí)解，其局部搜索能力較差。模擬退火算法的 Metropolis 準(zhǔn)則可以有限度地接受惡化解，并可以使 其接受概率趨向于零，使得算法局部搜索能力強(qiáng)。兩種算法合理融合，使算法的在全局和局部搜索能力均有提高。 2021 年 劉敏等 [18]提出適應(yīng)的模擬遺傳算法，提出自適應(yīng)變異概率的概念與理論改善遺傳算法的收斂速度，以解決遺傳算法中變異概率取值較小且在整個(gè)搜索過(guò)程中固定不變，易陷入局部最小值的不足，雜交母體選擇是以整體退火選擇的方式，可克服種群早熟化，避免過(guò)早收斂。 （三） 小結(jié) 模擬退火算法是目前來(lái)說(shuō)最成功的啟發(fā)式鄰域搜索算法，雖然具有較大分為快速全局搜索能力，但是由于對(duì)系統(tǒng)中的反饋信息利用不夠，當(dāng)求解到一定范圍時(shí)往往 做大量無(wú)為的冗余迭代，使解的質(zhì)量不高。 蟻群算法基于信息素正反饋機(jī)制，為求得質(zhì)量較高的解，由于初期信息素匱乏，導(dǎo)致收斂速度較慢。 為了解決蟻群算法存在的不可避免的缺陷，本文將模擬退火算法的鄰域搜索思想應(yīng)用于蟻群算法的尋優(yōu)中，完美解決了各自算法的問(wèn)題和缺陷。另外融合了目前解決 TSP 問(wèn)題最好的改進(jìn)思想 —— 最大最小螞蟻系統(tǒng)，在尋優(yōu)過(guò)程中進(jìn)一步提高解的質(zhì)量并盡可能保障其收斂速度。 三、 蟻群算法 （一） 蟻群算法產(chǎn)生與發(fā)展 昆蟲學(xué)家發(fā)現(xiàn)，在覓食過(guò)程中，螞蟻在它所經(jīng)過(guò)的路徑上留下濃度與食物源質(zhì)量成比例的信息素，并能夠感知信息素的存在及其濃度，以此指導(dǎo)自己朝著信息素濃度高的地方移動(dòng)。于是，蟻群的集體行動(dòng)便表現(xiàn)出一種信息正反饋現(xiàn)象。螞蟻群體就是通過(guò)這種間接交流機(jī)制達(dá)到在覓食過(guò)程中沿著最短路徑前進(jìn)的目的。 為了研究螞蟻群體覓食行為的特征， Deneubourg 及他的同事們?cè)O(shè)計(jì)了一種雙橋?qū)嶒?yàn) [19]。雙橋的首尾分別連接了蟻穴和食物源。他們?cè)谠囼?yàn)中測(cè)試了不同長(zhǎng)度的雙橋（分別稱為雙橋?qū)嶒?yàn)（ 1）和雙橋?qū)嶒?yàn)（ 2）），得到了十分重要的結(jié)論。 在 Deneubourg 等人的實(shí)驗(yàn)中，兩個(gè)橋的長(zhǎng)度是一樣的，如圖 （ a）所示。實(shí)驗(yàn)的結(jié)果顯示（如果 （ b）所示），螞蟻群體只有很小的概率會(huì)均勻選擇兩橋，大多數(shù)情況下，螞蟻群體會(huì)漸漸只選擇其中某一橋，而兩橋被單一選擇的概率幾乎是相等的。 造成這種現(xiàn)象的原因是：在覓食的最初期，螞蟻們對(duì)任何一橋都沒(méi)有偏好，于是隨意選擇一座橋，并在經(jīng)過(guò)的路徑上留下信息素。在初期，兩橋上的信息素濃度大致相等，然而由于隨機(jī)波動(dòng)，雙橋中的一個(gè)也許會(huì)擁有更多的信息素，于是螞蟻群體更加傾向于走這一路徑，并留下更多的信息素。于是，這種正 反饋效應(yīng)隨著時(shí)間慢慢放大。如果時(shí)間足夠長(zhǎng)，這種現(xiàn)象會(huì)導(dǎo)致所有螞蟻?zhàn)罱K都選擇某一條路徑。 這種自身催化或者正反饋的過(guò)程，實(shí)際就是螞蟻群體實(shí)現(xiàn)自組織行為的一個(gè)例子，這種宏觀模式（螞蟻群體傾向于選擇某一條路徑）的出現(xiàn)來(lái)自于微觀層面的過(guò)程與交互作用。在這個(gè)實(shí)驗(yàn)中，螞蟻的微觀行為可以解釋螞蟻群體集中于一條路徑的宏觀現(xiàn)象。螞蟻在覓食過(guò)程中，感知周圍環(huán)境的變化并進(jìn)行信息傳遞，從而調(diào)整自身的群體行為。 圖 雙橋?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)的結(jié)果顯示，經(jīng)過(guò)一定的時(shí)間以后，大部分的螞蟻會(huì)選擇較短的一橋進(jìn)行覓食，小部分的螞蟻會(huì)選擇較長(zhǎng)的一橋進(jìn)行覓食。 其原因可以解釋為：在覓食的最初期，螞蟻隨機(jī)選擇覓食途徑，因此較長(zhǎng)一橋和較短一橋 選擇概率相等 ，然而當(dāng)螞蟻發(fā)現(xiàn)兩橋的長(zhǎng)度差別后，便更傾向于走更短的路徑，從而迅速的在較短路徑上留下濃度很高的信息素，強(qiáng)化了蟻群的正反饋行為。由于較短路徑上信息素濃度積累得比較長(zhǎng)路徑要快得多，因此大多數(shù)螞蟻在選擇路徑時(shí)都會(huì)選擇較短路徑，形成 了如圖 （ b）所表現(xiàn)的現(xiàn)象。 與雙橋?qū)嶒?yàn)（ 1）相比，雙橋?qū)嶒?yàn)（ 2）覓食初期隨意波動(dòng)的影響大大減小，起作用的主要是媒介質(zhì)、自身催化和差異路徑長(zhǎng)度等機(jī)制。值得注意的是，雖然較長(zhǎng)路徑遠(yuǎn)長(zhǎng)于較短路徑，但仍有一部分螞蟻會(huì)選擇較長(zhǎng)路徑，螞蟻這種不依據(jù)信 息素濃度進(jìn)行路徑選擇的行為 稱為 路徑探索，對(duì)蟻群優(yōu)化模型的建立有著不容忽視的作用。 圖 雙橋?qū)嶒?yàn)（ 2）及其實(shí)驗(yàn)結(jié)果 在幾年后， Dorigo 和 Stutzle（ 2021） [21]考慮到另一種情況：如果在螞蟻集中于某一條覓食路徑后在添加一條新的路徑，那么蟻群的 行為會(huì)發(fā)生怎樣的變化？他們?cè)陔p橋的基礎(chǔ)上，進(jìn)行了附加實(shí)驗(yàn)。他們?cè)趯?shí)驗(yàn)初期只提供一條較長(zhǎng)的覓食路徑，在 30 分鐘以后再添加一條較短路徑（如圖 （ a）所示。有趣的是，在出現(xiàn)新的較短路徑后，螞蟻群體并沒(méi)有選擇較短路徑，而是仍然選擇原來(lái)的較長(zhǎng)路徑，如圖 （ b）所示。 實(shí)驗(yàn)者對(duì)此的解釋為：由于長(zhǎng)路徑上信息素濃度過(guò)高，而信息素蒸發(fā)又太慢，即使有螞蟻進(jìn)行路徑探索，但較短路徑的信息素濃度仍遠(yuǎn)遠(yuǎn)低于較長(zhǎng)路徑，從而使大部分螞蟻個(gè)人仍然選擇較長(zhǎng)分支而不選擇較短分支。 圖 雙橋?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)的雛形。假設(shè)信息素不會(huì)揮發(fā)（實(shí)驗(yàn)進(jìn)行的時(shí)間很短，故可不考慮信息素?fù)]發(fā)的情況）。設(shè) ????和 ????是第 ??只螞蟻經(jīng)過(guò)某一橋后在A 橋和 B 橋上已經(jīng)經(jīng)過(guò)的螞蟻數(shù)，那么第 ?? +1只螞蟻選擇分支 A 的概率為 ???? = (??+????)??(??+????)?? +(??+????)?? ( ) 同時(shí)，這只螞蟻選擇分支 B 的概率為： ???? = (??+????)??(??+????)?? +(??+????)?? ( ) 顯然，有 ????+???? = 1，也就是說(shuō)這只螞蟻必然需要在兩個(gè)分支中選擇一個(gè)。這兩個(gè)公式要表達(dá)的現(xiàn)象很簡(jiǎn)單：以往走分支 A 的螞蟻越多，正在選擇路徑的這種螞蟻選擇分支 A的概率就越大。而螞 蟻數(shù)量對(duì)螞蟻路徑選擇的影響，是通過(guò)信息素濃度來(lái)實(shí)現(xiàn)的。在模型中，信息素的濃度的影響又是通過(guò)參數(shù) ??和 ??來(lái)控制的。 ??表示公式的非線性程度， ??值越大，信息素濃度差別的影響就越大。當(dāng) ??值很大時(shí)，兩分支上信息素濃度些微的差距就會(huì)導(dǎo)致選擇高信息素濃度路徑的螞蟻數(shù)量遠(yuǎn)大于低濃度路徑。 ??表示進(jìn)行隨機(jī)選擇程度， ??值越大，螞蟻越忽略信息素對(duì)自己選擇的作用。當(dāng) ??值相對(duì)于螞蟻數(shù)量達(dá)到無(wú)限大時(shí)，所有螞蟻都以 1/2的概率選擇兩條分支。 Liu 采用蒙特卡羅方法對(duì)此系統(tǒng)進(jìn)行了模擬，證實(shí)了模型對(duì)實(shí)驗(yàn)描述的有效性。值得注意的是，在這個(gè)模型中，螞蟻在前往覓食和返回巢穴的過(guò)程中都會(huì)釋放信息素。 Deneubourg進(jìn)行的實(shí)驗(yàn)也證明了，這是蟻群集中到較短路徑的必須方式，如果螞蟻僅僅在前往覓食或返回巢穴的過(guò)程中釋放信息素，那蟻群是無(wú)法找到巢穴與食物的最短路徑的。 雙橋?qū)嶒?yàn)向人們展示了螞蟻群內(nèi)在的搜尋最短路徑的能力，于是人們嘗試去設(shè)計(jì)一種人 工螞蟻，使之在類似雙橋系統(tǒng)的圖上移動(dòng)并尋找最短路徑。例如，考慮一個(gè)靜態(tài)連接圖?? = (??， ??)， 如圖 所示，其中 ??表示節(jié)點(diǎn)集合，它的絕對(duì)值為節(jié)點(diǎn)數(shù)量， ??表示連接 ??中節(jié)點(diǎn)的邊的集合。引入蟻群使之在這個(gè)連接圖中進(jìn)行路徑搜索，尋找從源節(jié)點(diǎn)（蟻巢）到目的節(jié)點(diǎn)（食物源）目的的最短距離。在這個(gè)例子中，粗線表示的路徑即為螞蟻找到的最短路徑。 圖 螞蟻在靜態(tài)連接圖中找到的最短路徑解 在螞蟻路徑搜索能力的基礎(chǔ)上，人們開始試圖開發(fā)人工螞蟻。 然而人們發(fā)現(xiàn)，僅僅對(duì)自然界中的螞蟻進(jìn)行模仿存在很大的缺陷：由于螞蟻在進(jìn)行路徑選擇時(shí)依據(jù)的是信息素，螞蟻本身對(duì)路徑的長(zhǎng)短并沒(méi)有直觀預(yù)見。因此，如果在搜索初期的隨機(jī)選擇中螞蟻選擇了較差的路 徑解（如形成環(huán)路）而這個(gè)解又被強(qiáng)化，那么由于正反饋?zhàn)饔?，這個(gè)較差解的路徑上會(huì)積累越來(lái)越多的信息素從而使得螞蟻群體集中于這個(gè)較差路徑解。究其根本，這個(gè)問(wèn)題是由螞蟻群體信息素的正反饋?zhàn)饔眉葱畔⑺氐恼蚋乱鸬?。然而，如果只是去掉信息素的正向更新而只保留信息素的逆向更新（信息素的揮發(fā)），螞蟻群體將只遵循隨機(jī)搜索而無(wú)法獲得最短路徑。 因此，解決這個(gè)問(wèn)題的關(guān)鍵是賦予人工螞蟻一些不同于自然螞蟻的能力，建立一個(gè)有效的信息素更新機(jī)制。人工螞蟻的這種智能首先表現(xiàn)為一種記憶力，它們可以把所有已經(jīng)被搜索過(guò)的路徑的長(zhǎng)度都記住，然 后使人工螞蟻具備對(duì)路徑的評(píng)估比較能力，從而排除較差的解（如距離較長(zhǎng)的路徑或包含了較好路徑的環(huán)路路徑），而在較好的解上釋放信息素。此外，由于人工螞蟻具備了評(píng)估比較能力，因?yàn)榭梢愿鶕?jù)解的質(zhì)量決定在路徑上釋放的信息素的量。 另一個(gè)問(wèn)題是如何利用螞蟻的路徑探索能力，使螞蟻在一定程度上搜索 “較差 ”的路徑， 避免過(guò)分重復(fù)搜索已有的路徑和解的過(guò)早收斂。為此，可以引入現(xiàn)實(shí)中自然蟻群也具有的信息素?fù)]發(fā)現(xiàn)象，使得所有路徑上的信息素以一定的速度揮發(fā)，降低被搜索過(guò)多的路徑上的信息素，從而讓其他路徑有更大的概率被螞蟻選擇。 在解決了這 兩個(gè)問(wèn)題后，便可以根據(jù)以下幾個(gè)關(guān)鍵模塊建立人工螞蟻系統(tǒng)： 螞蟻的路徑搜索行為 ：在靜態(tài)連接圖中，螞蟻在節(jié)點(diǎn)以一定的概率選擇下一個(gè)節(jié)點(diǎn)，建立一個(gè)局部解。選擇概率的大小取決于可選擇的節(jié)點(diǎn)間信息素濃度的大小。螞蟻完成多次節(jié)點(diǎn)選擇后構(gòu)成一個(gè)完整解。在搜索和行進(jìn)的過(guò)程中，螞蟻不釋放信息素，即沒(méi)有直接的信息素正向更新。在搜索的初期，每條邊都被賦予一定數(shù)量的信息素，螞蟻開始搜索路徑。此時(shí)第 ??只螞蟻處于第 ??個(gè)節(jié)點(diǎn)選擇 ??作為下一個(gè)節(jié)點(diǎn)的概率為： ???????? = {????????∑ ????????????????? ??∈ ??????0 ?? ? ?????? () 其中， ??????為螞蟻 ??在節(jié)點(diǎn) ??上可以選擇的相鄰節(jié)點(diǎn)的集合。螞蟻依據(jù)這個(gè)概率在每一個(gè)節(jié)點(diǎn)做出路徑選擇，直至形成從蟻穴到食物源的完整路徑。然后，螞蟻會(huì)憑借人工賦予的智能對(duì)解的性能進(jìn)行評(píng)估，如 果當(dāng)前經(jīng)過(guò)的路徑的解較好，則在回蟻穴的途中釋放信息素，這也使蟻群表現(xiàn)為信息素反向更新。 信息素更新機(jī)制 ：螞蟻在到達(dá)食物源后，會(huì)沿原路返回蟻穴，并根據(jù)路徑解的性能釋放一定量的信息素。設(shè)更新的信息素的量為 ?????，則信息素的更新機(jī)制可以簡(jiǎn)單描述為： ?????? ←??????+????? () 從式（ ）可以看出，一旦有螞蟻經(jīng)過(guò)某條路徑，那么該路徑上必然會(huì) 增加一定量的信息素。 ?????的選擇通常設(shè)定為所經(jīng)過(guò)路徑長(zhǎng)度的函數(shù)，所經(jīng)過(guò)的路徑越短，更新的信息素越多。 信息素?fù)]發(fā)機(jī)制 ：自然蟻群系統(tǒng)也有信息素?fù)]發(fā)現(xiàn)象，但是對(duì)于蟻群路徑探索行為的促進(jìn)作用并不明顯。與此不同，人工蟻群的信息素?fù)]發(fā)強(qiáng)度可以進(jìn)行人工控制，因此信息素?fù)]發(fā)強(qiáng)度可以進(jìn)行人工控制，因此信息素的揮發(fā)機(jī)制在人工蟻群系統(tǒng)中有著重要的作用。人工蟻群系統(tǒng)中，信息素的揮發(fā)和信息素的釋放是交互進(jìn)行的。與信息素的釋放不同，在所有路徑山信息素的揮發(fā)量是一樣的。信息素的這個(gè)揮發(fā)機(jī)制可以描述為： ?????? ←(1???)?????? ?(??， ??)∈ ?? () 其中 ?? ∈ (0， 1]， 表示揮發(fā)系數(shù)。每個(gè)周期（例如一只螞蟻完成一次搜索）每條邊都會(huì)揮發(fā)相同量 ????????的信息素。 人工螞蟻系統(tǒng)的建立，一方面參照并借鑒了真實(shí)螞蟻系統(tǒng)的特性，是在觀察和實(shí)驗(yàn)的基礎(chǔ)上對(duì)真實(shí)螞蟻覓食行為的一種抽