標籤: 暫無標籤

在工程實踐中,經常會接觸到一些比較「新穎」的演算法或理論,比如模擬退火,遺傳演算法,禁忌搜索,神經網路等。這些演算法或理論都有一些共同的特性(比如模擬自然過程),通稱為「智能演算法」。它們在解決一些複雜的工程問題時大有用武之地。

1智能演算法研究

這些演算法都有什麼含義?首先給出個局部搜索,模擬退火,遺傳演算法,禁忌搜索的形象比喻:
為了找出地球上最高的山,一群有志氣的兔子們開始想辦法。
1.兔子朝著比現在高的地方跳去。他們找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是局部搜索,它不能保證局部最優值就是全局最優值。
2.兔子喝醉了。他隨機地跳了很長時間。這期間,它可能走向高處,也可能踏入平地。但是,他漸漸清醒了並朝最高方向跳去。這就是模擬退火。
3.兔子們吃了失憶藥片,並被發射到太空,然後隨機落到了地球上的某些地方。他們不知道自己的使命是什麼。但是,如果你過幾年就殺死一部分海拔低的兔子,多產的兔子們自己就會找到珠穆朗瑪峰。這就是遺傳演算法。
4.兔子們知道一個兔的力量是渺小的。他們互相轉告著,哪裡的山已經找過,並且找過的每一座山他們都留下一隻兔子做記號。他們制定了下一步去哪裡尋找的策略。這就是禁忌搜索。

2智能演算法概述

智能優化演算法要解決的一般是最優化問題。最優化問題可以分為(1)求解一個函數中,使得函數值最小的自變數取值的函數優化問題和(2)在一個解空間裡面,尋找最優解,使目標函數值最小的組合優化問題。典型的組合優化問題有:旅行商問題(Traveling Salesman Problem,TSP),加工調度問題(Scheduling Problem),0-1背包問題(Knapsack Problem),以及裝箱問題(Bin Packing Problem)等。
優化演算法有很多,經典演算法包括:有線性規劃,動態規劃等;改進型局部搜索演算法包括爬山法,最速下降法等,本文介紹的模擬退火、遺傳演算法以及禁忌搜索稱作指導性搜索法。而神經網路,混沌搜索則屬於系統動態演化方法。
優化思想裡面經常提到鄰域函數,它的作用是指出如何由當前解得到一個(組)新解。其具體實現方式要根據具體問題分析來定。
一般而言,局部搜索就是基於貪婪思想利用鄰域函數進行搜索,若找到一個比現有值更優的解就棄前者而取後者。但是,它一般只可以得到「局部極小解」,就是說,可能這隻兔子登「登泰山而小天下」,但是卻沒有找到珠穆朗瑪峰。而模擬退火,遺傳演算法,禁忌搜索,神經網路等從不同的角度和策略實現了改進,取得較好的「全局最小解」。

3演算法分類

模擬退火演算法
模擬退火演算法的依據是固體物質退火過程和組合優化問題之間的相似性。物質在加熱的時候,粒子間的布朗運動增強,到達一定強度后,固體物質轉化為液態,這個時候再進行退火,粒子熱運動減弱,並逐漸趨於有序,最後達到穩定。
模擬退火的解不再像局部搜索那樣最後的結果依賴初始點。它引入了一個接受概率p。如果新的點(設為pn)的目標函數f(pn)更好,則p=1,表示選取新點;否則,接受概率p是當前點(設為pc)的目標函數f(pc),新點的目標函數f(pn)以及另一個控制參數「溫度」T的函數。也就是說,模擬退火沒有像局部搜索那樣每次都貪婪地尋找比現在好的點,目標函數差一點的點也有可能接受進來。隨著演算法的執行,系統溫度T逐漸降低,最後終止於某個低溫,在該溫度下,系統不再接受變化。
模擬退火的典型特徵是除了接受目標函數的改進外,還接受一個衰減極限,當T較大時,接受較大的衰減,當T逐漸變小時,接受較小的衰減,當T為0時,就不再接受衰減。這一特徵意味著模擬退火與局部搜索相反,它能避開局部極小,並且還保持了局部搜索的通用性和簡單性。
在物理上,先加熱,讓分子間互相碰撞,變成無序狀態,內能加大,然後降溫,最後的分子次序反而會更有序,內能比沒有加熱前更小。就像那隻兔子,它喝醉后,對比較近的山峰視而不見,迷迷糊糊地跳一大圈子,反而更有可能找到珠峰。
值得注意的是,當T為0時,模擬退火就成為局部搜索的一個特例。
模擬退火的偽碼錶達:
procedure simulated annealing
begin
t:=0;
initialize temperature T
select a current string vc at random;
evaluate vc;
repeat
repeat
select a new string vn in the neighborhood of vc; (1)
if f(vc)<f(vn)
then vc:=vn;
else if random [0,1] <exp ((f (vn)-f (vc))/T) (2)
then vc:=vn;
until (termination-condition) (3)
T:=g(T,t); (4)
T:=t+1;
until (stop-criterion) (5)
end;
上面的程序中,關鍵的是(1)新狀態產生函數,(2)新狀態接受函數,(3)抽樣穩定準則,(4)退溫函數,(5)退火結束準則(簡稱三函數兩準則)是直接影響優化結果的主要環節。雖然實驗結果證明初始值對於最後的結果沒有影響,但是初溫越高,得到高質量解的概率越大。所以,應該盡量選取比較高的初溫。
上面關鍵環節的選取策略:
(1)狀態產生函數:候選解由當前解的鄰域函數決定,可以取互換,插入,逆序等操作產生,然後根據概率分佈方式選取新的解,概率可以取均勻分佈、正態分佈、高斯分佈、柯西分佈等。
(2)狀態接受函數:這個環節最關鍵,但是,實驗表明,何種接受函數對於最後結果影響不大。所以,一般選取min [1, exp ((f (vn)-f (vc))/T)]。
(3)抽樣穩定準則:一般常用的有:檢驗目標函數的均值是否穩定;連續若干步的目標值變化較小;規定一定的步數;
(4)退溫函數:如果要求溫度必須按照一定的比率下降,SA演算法可以採用,但是溫度下降很慢;快速SA中,一般採用 。目前,經常用的是 ,是一個不斷變化的值。
(5)退火結束準則:一般有:設置終止溫度;設置迭代次數;搜索到的最優值連續多次保持不變;檢驗系統熵是否穩定。
為了保證有比較優的解,演算法往往採取慢降溫、多抽樣、以及把「終止溫度」設的比較低等方式,導致演算法運行時間比較長,這也是模擬退火的最大缺點。人喝醉了酒辦起事來都不利索,何況兔子?
禁忌搜索演算法
為了找到「全局最優解」,就不應該執著於某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索,導致一葉障目,不見泰山。禁忌搜索就是對於找到的一部分局部最優解,有意識地避開它(但不是完全隔絕),從而獲得更多的搜索區間。兔子們找到了泰山,它們之中的一隻就會留守在這裡,其他的再去別的地方尋找。就這樣,一大圈后,把找到的幾個山峰一比較,珠穆朗瑪峰脫穎而出。
當兔子們再尋找的時候,一般地會有意識地避開泰山,因為他們知道,這裡已經找過,並且有一隻兔子在那裡看著了。這就是禁忌搜索中「禁忌表(tabu list)」的含義。那隻留在泰山的兔子一般不會就安家在那裡了,它會在一定時間后重新回到找最高峰的大軍,因為這個時候已經有了許多新的消息,泰山畢竟也有一個不錯的高度,需要重新考慮,這個歸隊時間,在禁忌搜索裡面叫做「禁忌長度(tabu length)」;如果在搜索的過程中,留守泰山的兔子還沒有歸隊,但是找到的地方全是華北平原等比較低的地方,兔子們就不得不再次考慮選中泰山,也就是說,當一個有兔子留守的地方優越性太突出,超過了「best to far」的狀態,就可以不顧及有沒有兔子留守,都把這個地方考慮進來,這就叫「特赦準則(aspiration criterion)」。這三個概念是禁忌搜索和一般搜索準則最不同的地方,演算法的優化也關鍵在這裡。
偽碼錶達:
procedure tabu search;
begin
initialize a string vc at random,clear up the tabu list;
cur:=vc;
repeat
select a new string vn in the neighborhood of vc;
if va>best_to_far then {va is a string in the tabu list}
begin
cur:=va;
let va take place of the oldest string in the tabu list;
best_to_far:=va;
end else
begin
cur:=vn;
let vn take place of the oldest string in the tabu list;
end;
until (termination-condition);
end;
以上程序中有關鍵的幾點:
(1)禁忌對象:可以選取當前的值(cur)作為禁忌對象放進tabu list,也可以把和當然值在同一「等高線」上的都放進tabu list。
(2)為了降低計算量,禁忌長度和禁忌表的集合不宜太大,但是禁忌長度太小容易循環搜索,禁忌表太小容易陷入「局部極優解」。
(3)上述程序段中對best_to_far的操作是直接賦值為最優的「解禁候選解」,但是有時候會出現沒有大於best_to_far的,候選解也全部被禁的「死鎖」狀態,這個時候,就應該對候選解中最佳的進行解禁,以能夠繼續下去。
(4)終止準則:和模擬退火,遺傳演算法差不多,常用的有:給定一個迭代步數;設定與估計的最優解的距離小於某個範圍時,就終止搜索;當與最優解的距離連續若干步保持不變時,終止搜索;
禁忌搜索是對人類思維過程本身的一種模擬,它通過對一些局部最優解的禁忌(也可以說是記憶)達到接納一部分較差解,從而跳出局部搜索的目的。
總結
模擬退火,遺傳演算法,禁忌搜索,神經網路在解決全局最優解的問題上有著獨到的優點,並且,它們有一個共同的特點:都是模擬了自然過程。模擬退火思路源於物理學中固體物質的退火過程,遺傳演算法借鑒了自然界優勝劣汰的進化思想,禁忌搜索模擬了人類有記憶過程的智力過程,神經網路更是直接模擬了人腦。
它們之間的聯繫也非常緊密,比如模擬退火和遺傳演算法為神經網路提供更優良的學習演算法提供了思路。把它們有機地綜合在一起,取長補短,性能將更加優良。
這幾種智能演算法有別於一般的按照圖靈機進行精確計算的程序,尤其是人工神經網路,是對計算機模型的一種新的詮釋,跳出了馮·諾依曼機的圈子,按照這種思想來設計的計算機有著廣闊的發展前景
上一篇[評價函數]  

相關評論

同義詞:暫無同義詞