元啟發(fā)式：概述和概論的比較

1、Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison組合優(yōu)化中的元啟發(fā)式：概述和概念比較1元啟發(fā)式2基于人群的方法基于群體的方法是用一組解決方案（而不是一個解決方案）對算法進(jìn)行一次完整的算法。 當(dāng)他們處理大量的解決方案時，基于群體的算法為探索搜索空間提供了一種自然的，內(nèi)在的方式。 然而，最終的表現(xiàn)強(qiáng)烈依賴于人口被操縱的方式。 研究最多的基于種群方法的最優(yōu)化方法是進(jìn)化計算（EC）和蟻群優(yōu)化（ACO）。 在EC算法中，個體種群通過重組和變異算子進(jìn)行修正，而在ACO中，人工螞蟻群體被用來構(gòu)建由

2、信息素路徑和啟發(fā)信息指導(dǎo)的解決方案。3蟻群優(yōu)化算法（ACO）自然界螞蟻群體在尋找食物的過程中，通過一種被稱為信息素（Pheromone）的物質(zhì)實現(xiàn)相互的間接通信，從而能夠合作發(fā)現(xiàn)從蟻穴到食物源的最短路徑。通過對這種群體智能行為的抽象建模，研究者提出了蟻群優(yōu)化算法（Ant Colony Optimization, ACO），為最優(yōu)化問題、尤其是組合優(yōu)化問題的求解提供了一強(qiáng)有力的手段。4蟻群優(yōu)化算法（ACO）在自然界中，螞蟻通過在環(huán)境中釋放信息素來交流信息，完成協(xié)同尋路任務(wù)。螞蟻巢穴食物螞蟻總以較大概率選擇信息素濃度較高的路徑；較短路徑上的信息素積累速度較快；“正反饋”作用使蟻群最終聚集到較短路徑

3、5螞蟻在尋找食物的過程中往往是隨機(jī)選擇路徑的，但它們能感知當(dāng)前地面上的信息素濃度，并傾向于往信息素濃度高的方向行進(jìn)。信息素由螞蟻自身釋放，是實現(xiàn)蟻群內(nèi)間接通信的物質(zhì)。由于較短路徑上螞蟻的往返時間比較短，單位時間內(nèi)經(jīng)過該路徑的螞蟻多，所以信息素的積累速度比較長路徑快。因此，當(dāng)后續(xù)螞蟻在路口時，就能感知先前螞蟻留下的信息，并傾向于選擇一條較短的路徑前行。這種正反饋機(jī)制使得越來越多的螞蟻在巢穴與食物之間的最短路徑上行進(jìn)。由于其他路徑上的信息素會隨著時間蒸發(fā)，最終所有的螞蟻都在最優(yōu)路徑上行進(jìn)。6算法流程路徑構(gòu)建每只螞蟻都隨機(jī)選擇一個城市作為其出發(fā)城市，并維護(hù)一個路徑記憶向量，用來存放該螞蟻依次經(jīng)過的城

4、市。螞蟻在構(gòu)建路徑的每一步中，按照一個隨機(jī)比例規(guī)則選擇下一個要到達(dá)的城市。信息素更新當(dāng)所有螞蟻構(gòu)建完路徑后，算法將會對所有的路徑進(jìn)行全局信息素的更新。更新是在全部螞蟻均完成了路徑的構(gòu)造后才進(jìn)行的，信息素的濃度變化與螞蟻在這一輪中構(gòu)建的路徑長度相關(guān)。7路徑構(gòu)建 偽隨機(jī)比例選擇規(guī)則（random proportional） 對于每只螞蟻k，路徑記憶向量Rk按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號。設(shè)螞蟻k當(dāng)前所在城市為i，則其選擇城市j作為下一個訪問對象的概率如上式。Jk(i)表示從城市i可以直接到達(dá)的、且又不在螞蟻訪問過的城市序列Rk中的城市集合。h(i, j)是一個啟發(fā)式信息，通常由h (i

5、, j)=1/dij直接計算。t(i, j)表示邊(i, j)上的信息素量。8信息素更新（1）在算法初始化時，問題空間中所有的邊上的信息素都被初始化為t0。（2）算法迭代每一輪，問題空間中的所有路徑上的信息素都會發(fā)生蒸發(fā)，我們?yōu)樗羞吷系男畔⑺爻松弦粋€小于1的常數(shù)。信息素蒸發(fā)是自然界本身固有的特征，在算法中能夠幫助避免信息素的無限積累，使得算法可以快速丟棄之前構(gòu)建過的較差的路徑。（3）螞蟻根據(jù)自己構(gòu)建的路徑長度在它們本輪經(jīng)過的邊上釋放信息素。螞蟻構(gòu)建的路徑越短、釋放的信息素就越多。一條邊被螞蟻爬過的次數(shù)越多、它所獲得的信息素也越多。（4）迭代（2），直至算法終止。9信息素更新m是螞蟻個數(shù)；r是

6、信息素的蒸發(fā)率，規(guī)定0r1。 是第k只螞蟻在它經(jīng)過的邊上釋放的信息素量，它等于螞蟻k本輪構(gòu)建路徑長度的倒數(shù)。Ck表示路徑長度，它是Rk中所有邊的長度和。10最大最小螞蟻系統(tǒng)（MMAS）最大最小螞蟻系統(tǒng)（MAX-MIN Ant System，MMAS）在基本AS算法的基礎(chǔ)上進(jìn)行了四項改進(jìn)：(1)只允許迭代最優(yōu)螞蟻（在本次迭代構(gòu)建出最短路徑的螞蟻），或者至今最優(yōu)螞蟻釋放信息素。(2)信息素量大小的取值范圍被限制在一個區(qū)間內(nèi)。(3)信息素初始值為信息素取值區(qū)間的上限，并伴隨一個較小的信息素蒸發(fā)速率。(4)每當(dāng)系統(tǒng)進(jìn)入停滯狀態(tài)，問題空間內(nèi)所有邊上的信息素量都會被重新初始化。11基于軌跡的方法1 模擬退

7、火2 禁忌搜索3 探索性本地搜索方法（1）變鄰域搜索（VNS）（2）引導(dǎo)本地搜索（GLS）12模擬退火模擬退火算法(Simulated Annealing, SA)的思想借鑒于固體的退火原理，當(dāng)固體的溫度很高的時候，內(nèi)能比較大，固體的內(nèi)部粒子處于快速無序運(yùn)動，當(dāng)溫度慢慢降低的過程中，固體的內(nèi)能減小，粒子的慢慢趨于有序，最終，當(dāng)固體處于常溫時，內(nèi)能達(dá)到最小，此時，粒子最為穩(wěn)定。模擬退火算法便是基于這樣的原理設(shè)計而成。模擬退火算法從某一較高的溫度出發(fā)，這個溫度稱為初始溫度，伴隨著溫度參數(shù)的不斷下降，算法中的解趨于穩(wěn)定，但是，可能這樣的穩(wěn)定解是一個局部最優(yōu)解，此時，模擬退火算法中會以一定的概率跳出這

8、樣的局部最優(yōu)解，以尋找目標(biāo)函數(shù)的全局最優(yōu)解。13禁忌搜索標(biāo)記已經(jīng)解得的局部最優(yōu)解或求解過程，并在進(jìn)一步的迭代中避開這些局部最優(yōu)解或求解過程。局部搜索的缺點在于，太過于對某一局部區(qū)域以及其鄰域的搜索，導(dǎo)致一葉障目。為了找到全局最優(yōu)解，禁忌搜索就是對于找到的一部分局部最優(yōu)解，有意識地避開它，從而或得更多的搜索區(qū)域。14變鄰域搜索（VNS）變鄰域搜索算法的主要思想是：采用多個不同的鄰域進(jìn)行系統(tǒng)搜索。首先采用最小的鄰域搜索，當(dāng)無法改進(jìn)解時，則切換到稍大一點的鄰域。如果能繼續(xù)改進(jìn)解，則退回到最小的鄰域，否則繼續(xù)切換到更大的鄰域。15引導(dǎo)本地搜索（GLS）引導(dǎo)本地搜索在搜索過程中建立的懲罰。它利用點球幫助

9、局部搜索算法跳出局部極小和高原。當(dāng)給定的局部搜索算法解決局部最優(yōu)，GLS修改目標(biāo)函數(shù)，采用特定的方法。然后，本地搜索將使用增廣目標(biāo)函數(shù)，其目的是使搜索跳出局部最優(yōu)。關(guān)鍵是，目標(biāo)函數(shù)是改性的方法。16元啟發(fā)式算法是相對于最優(yōu)化算法提出來的，一個問題的最優(yōu)化算法可以求得該問題的最優(yōu)解，而元啟發(fā)式算法是一個基于直觀或經(jīng)驗構(gòu)造的算法，它可以在可接受的花費(指計算時間和空間)下給出問題的一個可行解，并且該可行解與最優(yōu)解的偏離程度不一定可以事先預(yù)計。圖為蟻群優(yōu)化算法原理17 METAHEURISTICS的分類。自然啟發(fā)與非自然啟發(fā) ?；谌丝谂c單點搜索。內(nèi)存使用量與無內(nèi)存方法圖為ID框架然而不論它究竟屬于

10、哪個分類，我們都可以從強(qiáng)化和多樣化的角度去分析。18強(qiáng)化是要仔細(xì)和密集地搜索在過去的搜索中找到的良好解決方案。 相反，多樣化則是將搜索引導(dǎo)至未訪問區(qū)域。Yagiura和Ibaraki 2001每個元啟發(fā)式方法的設(shè)計目的都是為了有效和高效地探索搜索空間。為了獲得有效的元啟發(fā)式，強(qiáng)化和多樣化之間的正確平衡是必需的。而且，這種平衡不應(yīng)該固定或只能向一個方向改變（例如不斷增加的強(qiáng)度）。這種平衡應(yīng)該是動態(tài)的。19作者在這里引入了ID框架來試圖將擁有著不同的功效機(jī)理以及動態(tài)平衡的metaheuristics組件進(jìn)行描述和分類，以便引出Metaheuristics雜交的概念。位于角落OG附近的AND組件的例子是本地搜索中最陡的下降選擇規(guī)則NOG表示的角覆蓋了除目標(biāo)函數(shù)以外的一個或多個函數(shù)所引導(dǎo)的所有ID組件，由R表示的第三個角落包含完全隨機(jī)的所有ID組件。20關(guān)于Metaheuristics雜交事實上很多的成功的應(yīng)用程序都是雜交的結(jié)果，當(dāng)然其混合形式也是多樣的。兩個元啟發(fā)式的順序鏈接，由一個到另一個不同的部分以某種方式交換信息以完成合作完全整合為一個統(tǒng)一系統(tǒng)雜交最常用的方法之一就是在基于群體的方法中使用軌跡方法?；谌后w的方法的優(yōu)勢