目錄
極限優化
編輯極限優化(EO)是一種優化啟發式方法,其靈感來自統計物理學領域的自組織臨界性的Bak-Sneppen模型。這種啟發式方法最初是為了解決組合優化問題,如旅行推銷員問題和自旋眼鏡,盡管該技術已被證明可以在優化領域發揮作用。
與自組織臨界性的關系
編輯自組織臨界性(SOC)是一個統計物理學概念,用來描述一類以臨界點為吸引子的動力系統。具體來說,這些是非平衡系統,通過變化和耗散的雪崩來演化,一直到系統的最高尺度。
與計算復雜性的關系
編輯該難題的另一個部分是關于計算復雜性的工作,特別是臨界點已被證明存在于NP-complete問題中,在這些問題中,接近最優的解決方案被廣泛分散,并被搜索空間中的障礙物隔開,導致局部搜索算法被卡住或受到嚴重阻礙。正是Bak和Sneppen的進化自組織臨界點模型以及對組合優化問題中臨界點的觀察,導致了StefanBoettcher和AllonPercus對xxx優化的開發。EO技術被設計為一種用于組合優化問題的局部搜索算法。與遺傳算法不同的是,EO演化出一個單一的解決方案,并對最差的部分進行局部修改,而遺傳算法的工作對象是一群候選解決方案。這需要選擇一個合適的表示方法,允許給單個解決方案的組成部分分配一個質量度量(健身)。這與蟻群優化和進化計算等整體方法不同,后者是根據對目標函數的集體評價,為解決方案的所有組成部分分配同等的適合度。該算法以一個初始解決方案初始化,該解決方案可以隨機構建,也可以從其他搜索過程中獲得。該技術是一種細粒度的搜索,表面上類似于爬坡(局部搜索)技術。更詳細的檢查顯示了一些有趣的原則,這些原則可能具有適用性,甚至與更廣泛的基于群體的方法(進化計算和人工免疫系統)有一些相似之處。這個算法背后的管理原則是通過有選擇地去除低質量的組件,并用隨機選擇的組件取代它們來進行改進。
這顯然與遺傳算法不一致,遺傳算法是典型的進化計算算法,它選擇好的解決方案,試圖制造更好的解決方案。這個簡單的原則所產生的動力首先是一個強大的爬坡搜索行為,其次是一個類似于多次重啟搜索的多樣性機制。將整體解決方案的質量隨時間(算法迭代)變化的圖形化顯示,在質量崩潰(雪崩)之后的改進期,非常類似于懲罰性平衡所描述的方式。正是這些崩潰或搜索空間中的戲劇性跳躍,使算法擺脫了局部優化,并將這種方法與其他局部搜索程序區分開來。盡管這種間斷平衡行為可以被設計或硬編碼,但應該強調的是這是該算法基本的負成分選擇原則的一種突發效應。EO主要被應用于組合問題,如圖形分割和旅行推銷員問題,以及統計物理學中的問題,如自旋眼鏡。
主題的變化和應用
編輯廣義極值優化(GEO)被開發出來,用于操作位串,其中組件質量由位的xxx變化率決定,或位對整體解決方案質量的貢獻。這項工作包括對標準函數優化問題以及工程問題領域的應用。另一個與EO類似的擴展是連續極值優化(CEO)。EO已被應用于圖像柵格化,并在使用蟻群優化后作為局部搜索。EO已被用于識別復雜網絡中的結構。EO已被用于多目標跟蹤問題。最后,在研究用于控制選擇的概率分布方面也做了一些工作。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/176903/