愛華網(wǎng)超啟發(fā)式算法與元啟發(fā)式算法有些類似，也提供了一種高層框架，通過調(diào)用底層啟發(fā)式算子來實(shí)現(xiàn)對(duì)于問題的求解。與元啟發(fā)式算法相比，超啟發(fā)式算法更加側(cè)重如何將應(yīng)用領(lǐng)域知識(shí)屏蔽在高層框架以外。通俗地說，超啟發(fā)式算法是“尋找啟發(fā)式算法的啟發(fā)式算法”。更加嚴(yán)格地定義如下：
定義1. 超啟發(fā)式算法提供了某種高層策略（High-Level Strategy，HLS），通過操縱或管理一組低層啟發(fā)式算法（Low-Level Heuristics, LLH），以獲得新啟發(fā)式算法。這些新啟發(fā)式算法則被運(yùn)用于求解各類NP-難解問題。
上圖給出了超啟發(fā)式算法的概念模型示意圖。從圖中可以看出，超啟發(fā)式算法分為兩個(gè)層面：在問題域?qū)用嫔蠎?yīng)用領(lǐng)域?qū)＜倚韪鶕?jù)本人的背景知識(shí)，提供問題的定義、評(píng)估函數(shù)等信息和一系列LLH；而在高層策略層面上，智能計(jì)算專家則通過設(shè)計(jì)高效的操縱管理機(jī)制，利用問題域所提供的問題特征信息和LLH算法庫，構(gòu)造新的啟發(fā)式算法。因?yàn)檫@兩個(gè)層面之間實(shí)現(xiàn)了嚴(yán)格的領(lǐng)域屏蔽，僅僅需要修改問題域的問題定義和LLH、評(píng)估函數(shù)等領(lǐng)域有關(guān)信息，一種超啟發(fā)式算法就可以被快速地遷移到新的問題上。因此，超啟發(fā)式算法特別適合求解跨領(lǐng)域的問題。需要引起注意的是，研究超啟發(fā)式算法的目標(biāo)并不是取代智能計(jì)算專家，而是如何將智能計(jì)算技術(shù)更快地推廣到更多的應(yīng)用領(lǐng)域，同時(shí)有效第降低啟發(fā)式算法的設(shè)計(jì)難度，從而將領(lǐng)域?qū)＜液椭悄苡?jì)算專家的研究重點(diǎn)有效地劃分開。根據(jù)圖1 可知，智能計(jì)算專家在超啟發(fā)式算法設(shè)計(jì)中主要關(guān)注于高層策略，而領(lǐng)域?qū)＜覄t重點(diǎn)研究問題的目標(biāo)函數(shù)和LLH等。
啟發(fā)式算法_超啟發(fā)式算法 -超啟發(fā)式算法的分類
由于超啟發(fā)式算法的研究尚處于起步階段，對(duì)于已有的各種超啟發(fā)式算法，國際上尚未形成一致的分類方法。按照高層策略的機(jī)制不同，現(xiàn)有超啟發(fā)式算法可以大致分為4類：基于隨機(jī)選擇、基于貪心策略、基于元啟發(fā)式算法和基于學(xué)習(xí)的超啟發(fā)式算法。
基于隨機(jī)選擇的超啟發(fā)式算法該類超啟發(fā)式算法是從給定的集合中隨機(jī)選擇LLH，組合形成新的啟發(fā)式算法。這類超啟發(fā)式算法的特點(diǎn)是結(jié)構(gòu)簡(jiǎn)單、容易實(shí)現(xiàn)。同時(shí)，這類超啟發(fā)式算法也經(jīng)常被用作基準(zhǔn)（benchmark），以評(píng)價(jià)其他類型的超啟發(fā)式算法性能。該類超啟發(fā)式算法可以進(jìn)一步細(xì)分為純隨機(jī)（pure random）、帶延遲接受條件的隨機(jī)（random with late acceptance）等。
基于貪心（greedy）策略的超啟發(fā)式算法該類超啟發(fā)式算法在構(gòu)造新啟發(fā)式算法時(shí)，每次都挑選那些能夠最大化改進(jìn)當(dāng)前（問題實(shí)例）解的LLH。由于每次挑選LLH時(shí)需要評(píng)估所有LLH，故此該類方法的執(zhí)行效率低于基于隨機(jī)選擇的超啟發(fā)式算法。
基于元啟發(fā)式算法的超啟發(fā)式算法該類超啟發(fā)式算法采用現(xiàn)有的元啟發(fā)式算法（作為高層策略）來選擇LLH。由于元啟發(fā)式算法研究相對(duì)充分，因此這類超啟發(fā)式算法的研究成果相對(duì)較多。根據(jù)所采用的元啟發(fā)式算法，該類超啟發(fā)式算法可以細(xì)分為基于禁忌搜索、基于遺傳算法、基于遺傳編程、基于蟻群算法和基于GRASP with path-relinking等。
基于學(xué)習(xí)的超啟發(fā)式算法該類超啟發(fā)式算法在構(gòu)造新啟發(fā)式算法時(shí)，采用一定學(xué)習(xí)機(jī)制，根據(jù)現(xiàn)有各種LLH的歷史信息來決定采納哪一個(gè)LLH。根據(jù)LLH歷史信息來源的不同，該類超啟發(fā)式算法可以進(jìn)一步分為在線學(xué)習(xí)（on-line learning）和離線學(xué)習(xí)（off-line learning）兩種：前者是指LLH的歷史信息是在求解當(dāng)前實(shí)例過程中積累下來的；后者通常將實(shí)例集合分為訓(xùn)練實(shí)例和待求解實(shí)例兩部分，訓(xùn)練實(shí)例主要用于積累LLH的歷史信息，而待求解實(shí)例則可以根據(jù)這些歷史信息來決定LLH的取舍
啟發(fā)式算法_超啟發(fā)式算法 -超啟發(fā)式算法vs.啟發(fā)式算法
超啟發(fā)式算法與已有的啟發(fā)式算法既有一定的相似性，又有顯著的不同。通過分析超啟發(fā)式算法與啟發(fā)式算法的異同點(diǎn)，可以更加深入地理解超啟發(fā)式算法。表2從多個(gè)視角，對(duì)超啟發(fā)式算法與啟發(fā)式算法進(jìn)行了對(duì)比，從中我們可以發(fā)現(xiàn)以下現(xiàn)象：
（1）超啟發(fā)式算法與啟發(fā)式算法均是為了求解問題實(shí)例而提出的。因此，問題實(shí)例可以視為超啟發(fā)式算法和啟發(fā)式算法兩者共同的處理對(duì)象。
（2）超啟發(fā)式算法與啟發(fā)式算法都可能包含有參數(shù)。在傳統(tǒng)的啟發(fā)式算法中，可能有大量的參數(shù)需要調(diào)制。比如遺傳算法中的種群規(guī)模、交叉率、變異率、迭代次數(shù)等。而超啟發(fā)式算法的參數(shù)來源有兩個(gè)層面，在LLH和高層啟發(fā)式方法中均可能有參數(shù)需要調(diào)制。
（3）超啟發(fā)式算法與啟發(fā)式算法都是運(yùn)行在搜索空間上，但是各自的搜索空間構(gòu)成不同：傳統(tǒng)啟發(fā)式算法是工作在由問題實(shí)例的解構(gòu)成的搜索空間上；而超啟發(fā)式算法運(yùn)行在一個(gè)由啟發(fā)式算法構(gòu)成的搜索空間上，該搜索空間上的每一個(gè)頂點(diǎn)代表一系列LLH的組合。因此，超啟發(fā)式算法的抽象程度高于傳統(tǒng)啟發(fā)式算法。
（4）超啟發(fā)式算法與啟發(fā)式算法均可以應(yīng)用到各種不同的領(lǐng)域，但是它們各自對(duì)于問題領(lǐng)域知識(shí)的需求是不同的。啟發(fā)式算法設(shè)計(jì)通常需要依賴于問題的特征；而超啟發(fā)式算法的高層啟發(fā)式方法部分則幾乎不依賴于問題的領(lǐng)域知識(shí)，LLH則是與問題的領(lǐng)域知識(shí)緊密相關(guān)的。目前啟發(fā)式算法的應(yīng)用已經(jīng)十分廣泛，而超啟發(fā)式算法由于歷史較短，還主要局限在部分常見的組合優(yōu)化問題上。
超啟發(fā)式算法與啟發(fā)式算法多視角對(duì)比
啟發(fā)式算法超啟發(fā)式算法處理對(duì)象問題實(shí)例問題實(shí)例參數(shù)可能有可能有搜索空間由實(shí)例的解構(gòu)成由LLH串（啟發(fā)式算法）構(gòu)成應(yīng)用領(lǐng)域廣泛有待拓展
愛華網(wǎng)本文地址 » http://www.klfzs.com/a/8103260103/36971.html
