EO算法源於複雜系統自組織臨界的思想.算法從最佳化問題內部變數之間的聯繫出發,將問題本身作為一個演化的複雜系統,變數之間的相似性構成了變數之問比較、競爭、交流的條件.變數在局部尋優的過程中,驅動整個系統向最優解運動.EO算具有獨特的視角,為算法的研究提供了新的思路.EO算法實現簡單,算法效率高,套用前景廣闊.但目前國內對此算法的研究還很少.
基本介紹
- 中文名：極值最佳化算法
- 外文名：EO
基本信息,由來,算法過程,算法的改進,τ-EO,GEO,其他的EO改進算法,EO的特點及與其他算法的比較,套用,
基本信息
極值最佳化(E0)算法由Boettcher在國際遺傳與進化計算會議上首次提出.算法的思想源於自組
織臨界理論,其突出的特點為非平衡性(準平衡性).
它不同於以往提出的智慧型最佳化方法(如遺傳算法
(GA),模擬退火算法(SA),蟻群算法,PSO算法等),EO算法不會收斂到一個平衡態,而出現斷續平衡,產生的波動性使算法具有更好的持續搜尋和 跳出局優解的能力.EO算法易於實現,計算量小, 算法效果好,因此得到了廣泛的套用.EO算法規則簡單,可追蹤算法的運行過程,建立算法過程模型, 進行理論分析.目前,一些學者對此作了初步研究。
由來
EO算法是受複雜系統自組織臨界進化模型的啟發，發展形成的一種啟發式只能算法。自然界和人類社會中存在許多複雜系統,它們在無外界驅動的情況下,能夠自發地演化形成複雜的結構,這樣的結構能以一種精妙的方式最佳化資源的使用.例如生態系統進化形成了一種強大相互依賴連線的網路, 能高效地使用有限的資源;網路系統如果工作在臨界狀態下,就能獲得最高的數據傳輸效率.為了描述這種突現的複雜性,Bak提出了自組織臨界(SOC)的概念.
SOC普遍存在於複雜系統,如地貌的形成、地震、森林火災、網路交通流、城市演化、收入和財富的分布、經濟破產、技術創新和股市波動等.為了研究SOC系統的內部機理,研究者建立了一些能產生SOC狀態的計算機模擬模型,其中最著名的有沙堆模型和Bak-Snappen進化模型.
根據自然界的物種進化過程,在一個生物群落中,適應能力最差的物種總是被淘汰,或變異以獲得生存的能力.Bak-Sneppen模型就是根據這一原則建立的.設群落中有n個物種,物種i的適值為λi屬於[0,1]，在進化的每一步,適值最差的物種及其相關的物種被選中,它們的適值被更新(賦予一個0~1之間的隨機數).儘管模型的規則簡單,但在演化過程中體現了豐富的動態特性,包括自組織臨界狀態的出現,適值的廣泛分布等.EO算法抽取 Bak-Sneppen模型的機理.發展成為一種動態的最佳化過程.
算法過程
基本的EO算法步驟非常簡單。並且不需要凋整參數,具有實現容易、計算效率高等優點.其具體實現步驟如下:
Stepl:針對具體問題中的變數,定義合適的物種(變數劃分)xi及對應的適值函式λi;
Step2:初始化,隨機產生一個問題的初始配置 (初始變數);
Step3:計算每個物種的適值λi,並根據適值大小對物種xi排序;
Step4:選擇適值最小的物種xm,並且更新(按一定機率分布產生隨機數來替換原有的xm);
Step5:如果滿足停止準則,則算法停止,輸出結果.否則返回Step3.
下面以TSP問題為例,說明EO算法的實現過程.TSP算法是典型的NP難題,並且套用廣泛, 具有代表性.
在TSP問題中,一個城市被定義為一個物種. EO算法的原則是系統內部的各個物種追求局部最好值,並通過局部的相互作用獲得整體最優.在一個巡迴中,城市i追求的局部最優是與相連線的城市之間有最短的路徑,因而定義城市i的適值為λi=3/(pi+qi).將其餘各個城市與城市i的路徑從小到大排序,例如與i相連的兩個城市分別排在第pi位和第qi位,記為和。
此外,更新適值最差的城市m,不採用通常的兩兩交換法(這種方法效率較低),而是按照到城市m的路徑,將其他城市從小到大排列,即n=1是離m最近的城市n=2是離m第二近的城市,依此類推.按照機率P(n)~n^(-τ),選擇一個城市j與城市m相連線;然後同時斷開與m和J相連的兩條路徑,調整形成一條新的合法路徑.數值結果顯示, 對於Euclidean TSP問題.在隨機產生的城市數N=16,32,64,128,256的例子中,EO算法只比SA算法的精度差1%,而在非EuclideanTSP問題中,EO算法得到的結果精度比SA算法的要高.
E0算法中有兩個關鍵問題:
1)如何針對不同的問題定義局部組分(物種)。 這是運用EO算法的突破點.如果一個問題中的各個變數耦合太深或組分之間沒有相似點,即各個組分對目標函式的貢獻不同,這類問題就難以用EO算法來求解.儘管如此,還是有相當多的問題滿足EO算法的要求,或者通過變化能夠達到要求,所以 EO具有廣泛的適用性.
2)如何定義每個局部劃分的適值函式,這是 EO算法發揮效力的關鍵.例如在圖分解問題中, Boettcher定義的適值函式同時考慮了一個頂點的邊(與頂點本部分相連的邊)和差的邊(跨過分界的邊)，所以算法的效果較好。
算法的改進
τ-EO
基本的EO算法只選擇最差的物種更新,限制了解的更新範圍,有時算法會陷入局優解.為了避免陷入僵局,Boettcher等提出了τ-EO算法,引入一個可變參數τ,調節變數的選擇機率。
具體實現為:將各個變數對應的適值xi從小到大排序,得到排列λ_∏(1)<=λ_∏(2)<=……<=λ_∏(n)。適值最差的變數xj排在第1值,j=∏(1);最好的變數,排在第n位,j=∏(n).定義選擇第k位變數的機率函式
,1≤k≤n.其中τ>0,τ越小,選擇機率的差別越小,τ越大,最差的變數越容易被選中。.當τ趨向於0時,對各變數的選擇機會均等,算法成為完全的隨機算法。當τ趨向於無窮時，τ-EO算法便成為基本EO算法，因此基本EO算法是τ-EO算法的一種特殊情況。
GEO
GEO算法適用於求解連續的函式最佳化問題。EO算法的關鍵是給每個五種分配一個適值，但有時這樣的分配不易實現。GEO算法克服了這一缺點,改變了適值的定義方式, ,用一個長度為L的二進制為變數編碼，給二進制串中的每一位分配一個適值，適值決定該位是否變異。在編碼過程中，將問題的N個變數按序排列，每個變數用lj(j=1,2,……，N)位二進制表示，最終得到的編碼序列如同GA算法中的染色體。編碼位上的適值越小，該位變異的機率越大。
如果問題包含約束，則可對不滿足約束位的變異設定一個較高的適值（求最小值），限制不滿足約束變異的發生。文獻[19]用非線性、多峰、多維的檢驗函式作了數值驗證,並與標準的GA和合作進化 GA(CCGA)進行比較,結果表明GEO算法的效果與CCGA相當,對於某幾類函式具有更快的收斂性.
其他的EO改進算法
J-EO算法是一種改進的τ-EO算法.J-EO定義的適值函式在原先基礎上增加了一個記憶變數,記為Γki,.其中:0<Γ<1是衰退參數,ki是物種i被選中的次數.記憶變數增加了被重複選中的物種適值,降低了此變數以後被選擇的機率.這類似於禁忌搜尋算法中禁忌表的作用,可降低孵被重複操作的機率.於是便增加了算法的彈性,擴大了搜尋空間, 提高了算法效率.數值結果表明。對於2維和3維的自旋玻璃基態問題, J-EO算法與τ-EO算法相比,在相同的運算次數內能得到更好的解。
Zhou等提出一種連續極值最佳化(CEO)算法.算法由兩部分組成:一部分是經典的EO算法, 負責全局搜尋;男一部分是局部搜尋算法,負責局部的精細搜尋,將CEO運用於Lennard—Jones聚類最佳化問題,井與SA和GA算法作了比較.取得了較好的效果.
EO算法採用產生新的隨機數來更新適值最差的變數,因此採用的隨機分布對算法效果有重要作用.Menai等提出一種在量子物理學中使用的機率分布Bose-Einstein來更新變數,並將改進的EO算法套用於MΛXSAT問題,取得了良好的效果.
EO的特點及與其他算法的比較
與其他最佳化算法相比,EO算法具有以下特點:
1)EO算法不是全局算法,而是將待解問題分解為相似的局部組分,為每個局部組分定義適值,通過局部比較和相互作用突現全局的最優。所以在一次疊代中只處理一個解,利用解中變數之間的關係進行最佳化,減少了計算時間.
通常的種群最佳化算法(如遺傳算法、PSO算法、蟻群算法等)將多個解組成一個種群,通過比較、移動、交叉、組合等解之間的相互作用,達到尋優的目的。其優勢是種群容易產生，但是每步疊代運算都要計算多個解。隨著問題規模的增加,計算量呈指數增加.例如規模為N的問題,如果PSO算法選擇的微粒個數為30,那么每步疊代需要計算30*N個不同的解.而EO算法只需計算一個解,計算量只有PSO算法的1/30.
2)非平衡性(準平衡性):EO算法不會靜止到一個平衡態,算法隨機更新後,將無條件接受新的 解,算法運行到後期,仍有很大的波動性.保持持續搜尋解空問的活力.模擬退火算法在後期將收斂到一個平衡點,波動很小,對於一些處於臨界狀態的難題難以跨越障礙,因而易陷入局優點。
3)EO算法的最佳化是通過淘汰最差適值的局部分量實現的,而其他算法是通過選擇、培養好的解或向好的方向移動進行最佳化的.EO算法體現了一種新的尋優方式,為智慧型最佳化算法的研究開拓了新的思路,最佳化向題作為一個動態演化的系統,被EO算法加以分解,通過內部分量之間的相互作用與競爭, 進而獲得整體的最佳化.這突出反映了生物群落進化過程中的競爭性,即各物種均向適值最好的方向演化,但對資源的競爭導致最差的物種被淘汰或被迫變異,由此整個群落進化到SOC狀態,獲得對有限資源的高效利用.
套用
EO算法及其各種改進算法已得到廣泛的套用.最初,EO算法只限於求解一些組合最佳化問題和物理學問題,包括圖分解問題、TSP問題、SAT問題、圖著色聞題等.與其他智慧型最佳化算法的比較研究表明,EO算法是解決NP難題的一種有效方法.後來經過改進和變化,EO算法擴大了套用範圍。可求解函式最佳化問題,因而可套用於系統參數的最佳化設計。目前，EO算法已經運用到越來越多的領域,例如模式識別、信號測、各類設計最佳化、分子團簇的聚類等.下面簡要介紹主要的幾方面套用.
EO算法在模式識別和計算機視覺方面的套用主要是設計點匹配算法.文獻提出一種基於EO算法的準確、快速和魯棒性的點匹配方法。定義魯棒點為算法中的變數劃分,並且構造一個有效的外層移除方案,處理有噪聲和外部數據影響的情況. 文獻提出一種新的框架,利用奇異值分解的某些特性,結合EO算法進行點匹配.奇異值分解的作用在於產生配置,而EO算法用於精練匹配.
擴展的GEO算法成功地套用於最佳化系統參數 的設計問題,例如最小化支架質量的10一bar支架設計問題,太空船的熱量控制系統設計,熱傳輸管道的最佳化設計等.這些最佳化設計問題充分體現了GEO算法易於實現,能高效處理非線性,離散或整數變數函式的優勢. 另一個成功套用是識別複雜網路的群落結構,近年來,描述複雜網路的結構成為研究複雜系統的熱點問題.群落結構的劃分原則是:群落結點的相互聯結大於群落內結點與外部的連線,因而可定義一個連線度,通過最大化連線度進行網路中的群落劃分.這是一個NP難題.數值仿真表明,EO算法的效果比SA和GA算法好.
