複製鏈接
請複製以下鏈接發送給好友

元啓發式算法

鎖定
元啓發式算法(MetaHeuristic Algorithm)是啓發式算法的改進,它是隨機算法與局部搜索算法相結合的產物。 [1] 
中文名
元啓發式算法
外文名
MetaHeuristic Algorigthm

元啓發式算法定義

元啓發式算法是相對於最優化算法提出來的,一個問題的最優化算法可以求得該問題的最優解,而元啓發式算法是一個基於直觀或經驗構造的算法,它可以在可接受的花費(指計算時間和空間)下給出問題的一個可行解,並且該可行解與最優解的偏離程度不一定可以事先預計。
元啓發式算法包括禁忌搜索算法模擬退火算法、遺傳算法、蟻羣優化算法、粒子羣優化算法人工魚羣算法人工蜂羣算法、人工神經網絡算法等。 [1] 

元啓發式算法算法

元啓發式算法禁忌搜索算法

禁忌搜索(tabu search)算法是一種全局性鄰域搜索算法,它模擬了人類具有記憶功能的特徵。禁忌搜索算法最早是由Glover在1986年提出的,隨後很多學者對這個算法進行了完善,形成了一套完整的算法。
禁忌搜索算法主要針對一般的下降算法的缺點而提出來的,一般的下降算法在搜索到某個局部最優解時,算法很容易自動停止,而禁忌搜索算法採用禁忌策略儘量避免已搜索過的對象,從而保證了對不同的搜索路徑的探索。禁忌搜索算法不是搜索到局部最優解就停止搜索,而是引導算法跳出局部最優解,進而轉向全局最優解。禁忌搜索算法是人工智能的一種體現,該算法最重要的思想是記住以往已搜索過的局部最優解,並在進一步迭代搜索中儘量避開這些局部最優解(而不是絕對禁止循環),進而使得搜索途徑多樣化,以此跳出局部最優解。
在禁忌搜索算法中會涉及到鄰域、候選集、禁忌對象、禁忌表、禁忌表規模、評價函數等內容,禁忌表特別指禁忌對象及其被禁的長度;禁忌對象多選擇造成解變換的狀態;候選集中的元素依評價函數而確定,根據評價函數的優劣選擇一個可能替代被禁對象的元素,是否替代取決於禁忌的規則和其他一些特殊規則,如特赦規則;計算中的一些信息,如被禁對象對應的評價值、被禁的頻率等,將對禁忌的長度和停止規則提供幫助。 [1] 

元啓發式算法模擬退火算法

模擬退火(simulated annealing)算法屬於一種通用的隨機探索算法,最初是由Metropolis在1953年提出的,其基本思想是把某類優化問題的求解過程與統計熱力學中的熱平衡問題進行對比,試圖通過模擬高温物體退火過程來找到優化問題的全局最優解或者近似最優解。1983年Kirkpartrick成功地將模擬退火算法應用在了組合優化問題。
模擬退火算法是受到了物體退火過程的啓發。一個物體的退火過程大體如下:首先對該物體高温加熱(融化),顯然物體內原子處於高速運行的高能狀態,然而作為一個實際的物理系統,原子的運動又總是趨於最低的能量狀態。在退火的初始狀態,温度較高,物體處於高能狀態,隨着温度的逐漸降低,物體內部原子的運動趨於低能狀態,這種由高能向低能逐漸降温的過程稱為退火。當温度降至結晶温度後,物體由原子運動變成圍繞晶體格點的微小振動,液體凝固成固體,退火過程結束。在求解組合優化問題時,將物體的內能E模擬為目標函數值f,温度T看成控制參數,就得到了我們所説的模擬退火算法。 [3] 

元啓發式算法遺傳算法

遺傳算法(Genetic Algorithm)是由美國Michigan大學的John Holland教授於1975年首次提出的,它的基本思想是基於Darwin的進化論和Mendel的遺傳學,即生物的遺傳和變異在生物的進化過程中起着重要的作用,它使得生物不僅能夠保持自身固有的特性,同時還能夠不斷地改變自身以適應新的生存環境。遺傳算法是一種基於羣體進化的計算模型,它通過羣體的個體之間繁殖、變異、競爭等方法進行的信息交換優勝劣汰,從而一步步地逼近問題的最優解。對個體的遺傳操作主要通過選擇(繁殖)、交叉和變異這三個基本的遺傳算子來實現。
生物的進化是以羣體的形式進行的,而羣體的進化是通過個體的信息遺傳與交義叉來完成的,與之相對應,遺傳算法的運算對象也是羣體,它由n個個體組成一個集合,通過對該集合進行遺傳操作來模擬生物的進化過程,遺傳算法中的個體就是模擬生物的染色體,稱為人工染色體。為了完成對個體的遺傳操作,需要將個體的表現型轉換成基因型,這一個過程稱為編碼,反之,將基因型轉換成表現型的過程稱為解碼。

元啓發式算法蟻羣算法

蟻羣算法(ant colony optimization, ACO)是由意大利學者Marco Dorig於1992年在他的博士論文中提出來的一種仿生進化算法。它產生於對蟻羣行為的研究:蟻羣中的螞蟻以“信息素”為媒介,問接異步地相互聯繫,螞蟻在尋找食物或巢穴的路徑過程中,會在它們經過的地方留下一些化學物質,稱之為“信息素”,這些物質能被同一蟻羣中後來的螞蟻感受到,並作為一種信號使後到的螞蟻選擇有這些物質的路徑的可能性比選擇沒有這些物資的路徑的可能性大得多,後到的螞蟻也會留下信息素對原有的信息素進行加強。這樣,尋找最優選址變現為一種正反饋過程,螞蟻到過次數多的地點,後來的螞蟻選擇到此處的可能性就越大。
蟻羣算法的設計利用了螞蟻個體的運動規則:
1)搜索範圍:可具體設定蟻羣個體的搜索參數半徑,這樣就限定了其運動過程中的觀察能力和移動能力。
2)局部環境:螞蟻個體僅需要感知它周圍的局部環境信息,並且該局部環境中點的信息素是按一定速度消失的。
3)覓食規則:每隻螞蟻只是在其能感知的範圍內進行信息探索和留存,在局部環境中,哪一點的信息素最多,就以較大的概率決定了它的運動方向。這樣,雖然在其運動過程中,會出現小概率的搜索錯誤,但從總體上説,其搜尋的效率和正確性會通過其他螞蟻的行為反饋加以調整。
4)移動規則:每隻螞蟻都朝着信息素最多的方向移動,當週圍沒有信息素指引的時候,螞蟻會按照自己原來運動的方向慣性地運動下去,並且,在運動的方向上有一個隨機的小的運動,以保留原來的運動記憶。如果發現有其已經經過的地點,則以較大概率進行避讓。
5)避障規則:如果在螞蟻即將移動的方向上存在障礙物,則它會隨機選擇一個方向,或者按照信息素的指引繼續其覓食行為。
6)通信規則:實際上,每隻螞蟻是通過其信息素的播撒和感知來進行通信的。其具體規則是多元化的,它可以在找到相對最優解的時候散發最多的信息素,並且隨着它走的距離越來越遠,播撒的信息素也越來越少。 [1] 

元啓發式算法粒子羣優化

粒子羣優化(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具有原理簡單、易於實現、全局尋優能力較好、魯棒性強等特點,因此在科學研究和工程應用領域都得到了廣泛應用。

元啓發式算法人工蜂羣

人工蜂羣跟粒子羣算法類似,人工蜂羣算法也是通過模擬生物界羣體智能行為而提出一種羣智能算法。蜂羣算法的關鍵在於:羣體中的蜜蜂跟它的鄰居蜜蜂之間的信息交流和傳播能力使得蜜蜂可以利用其他蜜蜂的信息去尋找最好的食物源。ABC算法最早是由土耳其的Karaboga在2005年提出來的。之後,其研究團隊又對系統地研究了該算法的性能。在基本的ABC算法中,用食物源表示問題的解,蜂羣中的個體分成三種:僱傭蜂、旁觀蜂和偵察蜂。去探索其對應的食物源的蜜蜂稱為僱傭蜂,在蜂房中等待並決定選擇哪個食物源的蜜蜂稱為旁觀蜂,而偵察蜂負責進行隨機搜索。 [2] 
參考資料
  • 1.    王其濤. 元啓發式算法在離散選址中的應用[D]. 南京航空航天大學, 2010.
  • 2.    鄧冠龍. 基於元啓發式算法的調度問題若干研究[D]. 華東理工大學, 2012.
  • 3.    王端著. 核科學中的運籌學[M]. 2017:164