亲爱的MBA智库百科用户:


过去的17年,百科频道一直以免费公益的形式为大家提供知识服务,这是我们团队的荣幸和骄傲。 然而,在目前越来越严峻的经营挑战下,单纯依靠不断增加广告位来维持网站运营支出,必然会越来越影响您的使用体验,这也与我们的初衷背道而驰。 因此,经过审慎地考虑,我们决定推出VIP会员收费制度,以便为您提供更好的服务和更优质的内容。


MBA智库百科VIP会员,您的权益将包括: 1、无广告阅读; 2、免验证复制。


当然,更重要的是长期以来您对百科频道的支持。诚邀您加入MBA智库百科VIP会员,共渡难关,共同见证彼此的成长和进步!



MBA智库百科项目组
2023年8月10日
百科VIP
未登录
无广告阅读
免验证复制
1年VIP
¥ 9.9
支付方式:
微信支付
支付宝
PayPal
购买数量:
1
应付金额:
9.9
汇率换算:
1.32
美元(USD)
  • 美元(USD)
  • 加元(CAD)
  • 日元(JPY)
  • 英镑(GBP)
  • 欧元(EUR)
  • 澳元(AUD)
  • 新台币(TWD)
  • 港元(HKD)
  • 新加坡(SGD)
  • 菲律宾(PHP)
  • 泰铢(THB)

按当月汇率换算,

包含手续费

打开手机微信 扫一扫继续付款
立即开通
PayPal支付后,可能会遇到VIP权益未及时开通的情况,请您耐心等待,或者联系百科微信客服:mbalib888。
温馨提示:当无法进去支付页面时,可刷新后重试或更换浏览器
开通百科会员即视为同意《MBA智库·百科会员服务规则》

支付成功

全球专业中文经管百科,由121,994位网友共同编写而成,共计436,064个条目

超啟髮式演算法

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

目錄

[隱藏]

什麼是超啟髮式演算法

  超啟髮式演算法與已有的啟髮式演算法既有一定的相似性,又有顯著的不同。通過分析超啟髮式演算法與啟髮式演算法的異同點,可以更加深入地理解超啟髮式演算法。超啟髮式演算法提供了某種高層策略(High-Level Strategy,HLS),通過操縱或管理一組低層啟髮式演算法(Low-Level Heuristics, LLH),以獲得新啟髮式演算法。這些新啟髮式演算法則被運用於求解各類NP-難解問題。

超啟髮式演算法的出現

  隨著智能計算領域的發展,出現了一類被稱為超啟髮式演算法(Hyper-Heuristic Algorithm)的新演算法類型。智能計算領域的著名國際會議(GECCO 2009, CEC 2010,PPSN 2010)分別舉辦了專門針對超啟髮式演算法的workshop或session。從GECCO 2011開始,超啟髮式演算法的相關研究正式成為該會議的一個領域(self* search-new frontier track)。國際智能計算領域的兩大著名期刊Journal of Heuristics和Evolutionary Computation也在2010年和2012年分別安排了專刊,著重介紹與超啟髮式演算法有關的研究進展。

  超啟髮式演算法分為兩個層面:在問題域層面上應用領域專家需根據本人的背景知識,提供問題的定義、評估函數等信息和一系列LLH;而在高層策略層面上,智能計算專家則通過設計高效的操縱管理機制,利用問題域所提供的問題特征信息和LLH演算法庫,構造新的啟髮式演算法。因為這兩個層面之間實現了嚴格的領域屏蔽,僅僅需要修改問題域的問題定義和LLH、評估函數等領域有關信息,一種超啟髮式演算法就可以被快速地遷移到新的問題上。因此,超啟髮式演算法特別適合求解跨領域的問題。需要引起註意的是,研究超啟髮式演算法的目標並不是取代智能計算專家,而是如何將智能計算技術更快地推廣到更多的應用領域,同時有效地降低啟髮式演算法的設計難度,從而將領域專家和智能計算專家的研究重點有效地劃分開。可知,智能計算專家在超啟髮式演算法設計中主要關註於高層策略,而領域專家則重點研究問題的目標函數和LLH等。

超啟髮式演算法的分類

  由於超啟髮式演算法的研究尚處於起步階段,對於已有的各種超啟髮式演算法,國際上尚未形成一致的分類方法。按照高層策略的機制不同,現有超啟髮式演算法可以大致分為4類:基於隨機選擇、基於貪心策略、基於元啟髮式演算法和基於學習的超啟髮式演算法。

  基於隨機選擇的超啟髮式演算法

  該類超啟髮式演算法是從給定的集合中隨機選擇LLH,組合形成新的啟髮式演算法。這類超啟髮式演算法的特點是結構簡單、容易實現。同時,這類超啟髮式演算法也經常被用作基準(benchmark),以評價其他類型的超啟髮式演算法性能。該類超啟髮式演算法可以進一步細分為純隨機(pure random)、帶延遲接受條件的隨機(random with late acceptance)等。

  基於貪心(greedy)策略的超啟髮式演算法

  該類超啟髮式演算法在構造新啟髮式演算法時,每次都挑選那些能夠最大化改進當前(問題實例)解的LLH。由於每次挑選LLH時需要評估所有LLH,故此該類方法的執行效率低於基於隨機選擇的超啟髮式演算法。

  基於元啟髮式演算法的超啟髮式演算法

  該類超啟髮式演算法採用現有的元啟髮式演算法(作為高層策略)來選擇LLH。由於元啟髮式演算法研究相對充分,因此這類超啟髮式演算法的研究成果相對較多。根據所採用的元啟髮式演算法,該類超啟髮式演算法可以細分為基於禁忌搜索、基於遺傳演算法、基於遺傳編程、基於蟻群演算法和基於GRASP with path-relinking等。

  基於學習的超啟髮式演算法

  該類超啟髮式演算法在構造新啟髮式演算法時,採用一定學習機制,根據現有各種LLH的歷史信息決定採納哪一個LLH。根據LLH歷史信息來源的不同,該類超啟髮式演算法可以進一步分為線上學習(on-line learning)和離線學習(off-line learning)兩種:前者是指LLH的歷史信息是在求解當前實例過程中積累下來的;後者通常將實例集合分為訓練實例和待求解實例兩部分,訓練實例主要用於積累LLH的歷史信息,而待求解實例則可以根據這些歷史信息來決定LLH的取捨。

超啟髮式演算法與啟髮式演算法

  (1)超啟髮式演算法與啟髮式演算法均是為了求解問題實例而提出的。因此,問題實例可以視為超啟髮式演算法和啟髮式演算法兩者共同的處理對象。

  (2)超啟髮式演算法與啟髮式演算法都可能包含有參數。在傳統的啟髮式演算法中,可能有大量的參數需要調製。比如遺傳演算法中的種群規模、交叉率、變異率、迭代次數等。而超啟髮式演算法的參數來源有兩個層面,在LLH和高層啟髮式方法中均可能有參數需要調製。

  (3)超啟髮式演算法與啟髮式演算法都是運行在搜索空間上,但是各自的搜索空間構成不同:傳統啟髮式演算法是工作在由問題實例的解構成的搜索空間上;而超啟髮式演算法運行在一個由啟髮式演算法構成的搜索空間上,該搜索空間上的每一個頂點代表一系列LLH的組合。因此,超啟髮式演算法的抽象程度高於傳統啟髮式演算法。

  (4)超啟髮式演算法與啟髮式演算法均可以應用到各種不同的領域,但是它們各自對於問題領域知識需求是不同的。啟髮式演算法設計通常需要依賴於問題的特征;而超啟髮式演算法的高層啟髮式方法部分則幾乎不依賴於問題的領域知識,LLH則是與問題的領域知識緊密相關的。目前啟髮式演算法的應用已經十分廣泛,而超啟髮式演算法由於歷史較短,還主要局限在部分常見的組合優化問題上。

本條目對我有幫助3
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您認為本條目還有待完善,需要補充新內容或修改錯誤內容,請編輯條目投訴舉報

本条目由以下用户参与贡献

LuyinT.

評論(共0條)

提示:評論內容為網友針對條目"超啟髮式演算法"展開的討論,與本站觀點立場無關。

發表評論請文明上網,理性發言並遵守有關規定。

打开APP

以上内容根据网友推荐自动排序生成

官方社群
下载APP
告MBA智库百科用户的一封信
亲爱的MBA智库百科用户: 过去的17年,百科频道一直以免费公益的形式为大家提供知识服务,这是我们团队的荣幸和骄傲。 然而,在目前越来越严峻的经营挑战下,单纯依靠不断增加广告位来维持网站运营支出,必然会越来越影响您的使用体验,这也与我们的初衷背道而驰。 因此,经过审慎地考虑,我们决定推出VIP会员收费制度,以便为您提供更好的服务和更优质的内容。 MBA智库百科VIP会员(9.9元 / 年,点击开通),您的权益将包括: 1、无广告阅读; 2、免验证复制。 当然,更重要的是长期以来您对百科频道的支持。诚邀您加入MBA智库百科VIP会员,共渡难关,共同见证彼此的成长和进步!
MBA智库百科项目组
2023年8月10日

闽公网安备 35020302032707号

添加收藏

    新建收藏夹

    编辑收藏夹

    20