元啟發式算法（MetaHeuristic Algorigthm）是啟發式算法的改進，它是隨機算法與局部搜尋算法相結合的產物。
基本介紹
- 中文名：元啟發式算法
- 外文名：MetaHeuristic Algorigthm
定義,算法,禁忌搜尋算法,模擬退火算法,遺傳算法,蟻群算法,粒子群最佳化,疊代貪婪,差分進化,人工蜂群,
定義
元啟發式算法是相對於最最佳化算法提出來的，一個問題的最最佳化算法可以求得該問題的最優解，而元啟發式算法是一個基於直觀或經驗構造的算法，它可以在可接受的花費(指計算時間和空間)下給出問題的一個可行解，並且該可行解與最優解的偏離程度不一定可以事先預計。
算法
禁忌搜尋算法
禁忌搜尋(tabu search)算法是一種全局性鄰域搜尋算法，它模擬了人類具有記憶功能的特徵。禁忌搜尋算法最早是由Glover在1986年提出的，隨後很多學者對這個算法進行了完善，形成了一套完整的算法。
禁忌搜尋算法主要針對一般的下降算法的缺點而提出來的，一般的下降算法在搜尋到某個局部最優解時，算法很容易自動停止，而禁忌搜尋算法採用禁忌策略儘量避免已搜尋過的對象，從而保證了對不同的搜尋路徑的探索。禁忌搜尋算法不是搜尋到局部最優解就停止搜尋，而是引導算法跳出局部最優解，進而轉向全局最優解。禁忌搜尋算法是人工智慧的一種體現，該算法最重要的思想是記住以往已搜尋過的局部最優解，並在進一步疊代搜尋中儘量避開這些局部最優解(而不是絕對禁止循環)，進而使得搜尋途徑多樣化，以此跳出局部最優解。
在禁忌搜尋算法中會涉及到鄰域、候選集、禁忌對象、禁忌表、禁忌表規模、評價函式等內容，禁忌表特別指禁忌對象及其被禁的長度;禁忌對象多選擇造成解變換的狀態;候選集中的元素依評價函式而確定，根據評價函式的優劣選擇一個可能替代被禁對象的元素，是否替代取決於禁忌的規則和其他一些特殊規則，如特赦規則;計算中的一些信息，如被禁對象對應的評價值、被禁的頻率等，將對禁忌的長度和停止規則提供幫助。
模擬退火算法
模擬退火(simulated annealing)算法屬於一種通用的隨機探索算法，最初是由Metropolis在1953年提出的，其基本思想是把某類最佳化問題的求解過程與統計熱力學中的熱平衡問題進行對比，試圖通過模擬高溫物體退火過程來找到最佳化問題的全局最優解或者近似最優解。1983年Kirkpartrick成功地將模擬退火算法套用在了組合最佳化問題。
模擬退火算法是受到了物體退火過程的啟發。一個物體的退火過程大體如下:首先對該物體高溫加熱(融化)，顯然物體內原了處於高速運行的高能狀態，然而作為一個實際的物理系統，原子的運動又總是趨於最低的能量狀態。在退火的初始狀態，溫度較高，物體處於高能狀態，隨著溫度的逐漸降低，物體內部原了的運動趨於低能狀態，這種有高能向低能逐漸降溫的過程稱為退火。當溫度降至結晶溫度後，物體由原了運動變成圍繞晶體格點的微小振動，液體凝固成固體，退火過程結束。在求解組合最佳化問題時，將物體的內能E模擬為目標函式值f，溫度T看成控制參數，就得到了我們所說的模擬退火算法。
遺傳算法
生物的進化是以群體的形式進行的，而群體的進化是通過個體的信息遺傳與交義叉來完成的，與之相對應，遺傳算法的運算對象也是群體，它由n個個體組成一個集合，通過對該集合進行遺傳操作來模擬生物的進化過程，遺傳算法中的個體就是模擬生物的染色體，稱為人工染色體。為了完成對個體的遺傳操作，需要將個體的表現型轉換成基因型，這一個過程稱為編碼，反之，將基因型轉換成表現型的過程稱為解碼。
蟻群算法
蟻群算法(ant colony optimization, ACO)是由義大利學者Marco Dorig於1992年在他的博士論文中提出來的一種仿生進化算法。它產生於對蟻群行為的研究:蟻群中的螞蟻以“信息素”為媒介，問接異步地相互聯繫，螞蟻在尋找食物或巢穴的路徑過程中，會在它們經過的地方留下一些化學物質，稱之為“信息素”，這些物質能被同一蟻群中後來的螞蟻感受到，並作為一種信號使後到的螞蟻選擇有這些物質的路徑的可能性比選擇沒有這些物資的路徑的可能性大得多，後到的螞蟻也會留下信息素對原有的信息素進行加強。這樣，尋找最優選址變現為一種正反饋過程，螞蟻到過次數多的地點，後來的螞蟻選擇到此處的可能性就越大。
蟻群算法的設計利用了螞蟻個體的運動規則:
1)搜尋範圍:可具體設定蟻群個體的搜尋參數半徑，這樣就限定了其運動過程中的觀察能力和移動能力。
2)局部環境:螞蟻個體僅需要感知它周圍的局部環境信息，並且該局部環境中點的信息素是按一定速度消失的。
3)覓食規則:每隻螞蟻只是在其能感知的範圍內進行信息探索和留存，在局部環境中，哪一點的信息素最多，就以較大的機率決定了它的運動方向。這樣，雖然在其運動過程中，會出現小機率的搜尋錯誤，但從總體上說，其搜尋的效率和正確性會通過其他螞蟻的行為反饋加以調整。
4)移動規則:每隻螞蟻都朝著信息素最多的方向移動，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性地運動下去，並且，在運動的方向上有一個隨機的小的運動，以保留原來的運動記憶。如果發現有其已經經過的地點，則以較大機率進行避讓。
5)避障規則:如果在螞蟻即將移動的方向上存在障礙物，則它會隨機選擇一個方向，或者按照信息素的指引繼續其覓食行為。
6)通信規則:實際上，每隻螞蟻是通過其信息素的播撒和感知來進行通信的。其具體規則是多元化的，它可以在找到相對最優解的時候散發最多的信息素，並且隨著它走的距離越來越遠，播撒的信息素也越來越少。
粒子群最佳化
粒子群最佳化(particle swarm optimization, PSO )是美國心理學家Kennedy和電氣工程師Eberhart受鳥類覓食行為的啟發，於1995年提出了粒子群最佳化算法。PSO是一種基於群體智慧型的全局隨機尋優算法，它模仿鳥類的覓食行為，將問題的搜尋空間類比於鳥類的飛行空間，將每隻鳥抽象成為一個微粒，用以表征問題的一個候選解，所需要尋找的最優解等同於要尋找的食物。算法為每個微粒給定位置和速度，每個微粒通過更新速度來更新其自身的位置。通過疊代搜尋，種群可以不斷地找到更好的微粒位置，從而得到最佳化問題的較優解。
提出PSO之後，Kennedy和Eberhart又在基本PSO算法基礎上做了擴展，提出了一種離散二進制PSO算法，套用於函式最佳化問題，驗證了其有效性，但該算法難以有效地跳出局部最優。Clerc推廣了這一工作，研究了離散PSO算法，並將其套用於旅行商問題的求解。近年來湧現了很多PSO套用於調度問題的研究。Tasgentirenetal.最先對於flow shop問題提出了一種基於變鄰域搜尋(variable neighborhood search, VNS )的混合PSO算法，採用基於隨機鍵的SPV ( smallest position value)規則將標準PSO算法推廣到排序問題，並利用VNS來改進PSO環節所得到的解。Lianetal.針對相同的問題，提出了一種新型的PSO算法，直接利用GA的交叉和變異操作作為PSO算法中微粒速度和位置的更新操作。
疊代貪婪
疊代貪婪(iterated greedy, IG)是Ruiz和Stutzle在2007年提出的一種簡單而有效的求解調度問題的元啟發式算法。疊代貪婪算法始終記錄兩個解:算法找到的最好解以及算法使用的當前解。算法初始化這兩個解之後(通常由啟發式規則實現)，從當前解出發，考慮針對所解決問題設計的局部搜尋方法，若局部搜尋中有更好的解則貪婪地移動到那個解，局部搜尋結束之後算法會採用類似模擬退火的接受準則以一定的機率接受比最好解更差的解，然後更新最好解，再對當前解採用破壞重建過程以跳出局部最優並準備下一次的疊代過程。該算法結構非常簡單，參數較少，且求解效果非常好。Ruiz和Stutzle隨後又將該算法用於具有順序相關準備時間的flow shop問題，取得了較好的效果。Panetal.提出了改進的IG算法用於零等待的flow shop問題。Framinan和Leisten提出了一種多目標IG算法用於flow shop調度。
差分進化
差分進化(differential evolution, DE )是由Storn和Price於1997年提出的一種智慧型最佳化算法。它是一種針對實變函式最佳化的隨機搜尋算法，也可看作是遺傳算法的進一步擴展。差分進化算法利用選擇、交叉和變異三個操作來更新種群個體。首先，利用父代個體間的差分矢量進行變異得到變異個體;然後，該變異個體以一定的機率與父代個體進行交叉得到一個試驗個體;最後，採用一對一的競爭機制貪婪地選擇試驗個體和父代個體之間的較優者作為子代對種群進行更新。DE具有原理簡單、易於實現、全局尋優能力較好、魯棒性強等特點，因此在科學研究和工程套用領域都得到了廣泛套用。
