疊代改進演算法

資料來源: http://cindy.cis.nctu.edu.tw/AI96/team02/iia.html 所謂的 "疊代改進演算法" 主要的觀念就是在搜尋的過程中每次只記得 現在目前這個點的狀況卻不記得以前走過哪些點了 , 就像在霧裡爬山 一樣 , 我們只知到目前所在的位置而只能對周圍的點作探測來決定下一 步要往周圍的那一點走 , 如此 , 我們所在的狀態以此方法不斷的更新直 到目標點為止 . 以下是有用到疊代改進演算法觀念的兩個搜尋方法: 1.登山搜尋法 2. 模擬退火法 1. 登山搜尋法 所謂的 "登山搜尋法" , 顧名思意 , 就是一種像登山的搜尋法 , 其意義很 簡單就是每次搜尋只往那些更接近目標點的點走, 而不往那些會使的遠離 目標的點走, 就像爬山一樣只往山上爬而不往山下爬 . 那怎樣知道離目標 點是遠還是近呢 ? 那便是利用一個估計函數來計算, 以下圖為例 : 我們的例子是要從上面的地圖中從 S 城市找到一條到 G 城市的路徑 並使用登山搜尋法 有直線連接兩個點表示此兩點是有道路連通的,道路上面的數字是表示 道路的長度. 下圖表示每個城市到 G 城市的直線距離,我們以此當作我們的估計函數 下圖是我們的搜尋結果 紅色線部份 表示我們所要的路徑 首先,由 S 點開始搜尋 ,對其作展開 ,得到 h(A)=10.4 , h(D)=8.9 ,我們選擇距離 G 點較近的 D 點 ,對其作展開 ,得到 h(A)=10.4 , h (E)= 6.9 , 我們必須選擇 h 值 小於上一個點的且較接近目標點的點,因此,我們選擇了E點 對其作展開得到了 h(B)=6.7 , h(F)=3.0 同理我們選擇了 F 點 對其作展開便到了 G 點 登山搜尋法演算法

Function Hill-Climbing ( problem ) rteurns a solution state
    inputs: problem , a problem
    static:  current , a node
               next     , a node         current<---- Make-Node(Initial-State[problrm])
     loop do
            
             next<--- a highest - valued successor of current
             current<---next
      end    

但這個搜尋法有一些缺點: 登山搜尋法演算法的缺點 使用登山搜尋法可能遇到下面三個問題 一 山丘問題 什麼是山丘問題呢? 假如有兩座山丘一座比較高一座比較低 而我們的目標是比較高那座山丘的山頂 . 如果我們沿著較小 的山丘往上搜尋當到達較小山丘的山頂時並未到達我們的目 標點 , 但我們的登山搜尋法是不予許往下走的 . 因此 , 我們 的搜尋便在那較小山丘的山頂上動彈不得 . 這就是陷入了所 謂的局部最大點的狀況 . 解決的方式為:我們可以隨機從另一 點開始搜尋 . 二 平原問題 什麼是平原問題呢 ? 假如我們站在一個很大的平原上而比較 高的地方卻遠在我們的視線之外 , 此時使用登山搜尋法將不 知道下一步要走哪一點 !因為周圍都是一樣的平 ,解決的 方式為 :我們可以一次走大步一點 ,就是一次跳躍很多點直到 我們發現有較高的地方出現 . 三 山脊問題 所謂的山脊問題,就像我們爬山時如果只觀察前後左右四個方向, 若此時發現四個方向的路都是往下走的而在我們的右上方卻有 一較高處,而我們卻沒有發現.我們會以為掉近了山丘問題 . 其實 不然 , 其解決方:增加我們搜尋的方向 2. 模擬退火法 模擬退火法的觀念其實很容易理解,它跟登山搜尋法有幾個比較不同 的地方: 它允許往遠離目標點的點走但這是一個機率 , 當我們疊代更新 的次數愈多此機率便越小 . 此法首先會在目前我們走到的點的周圍隨機選出其一個相鄰點 , 然後用估計函數算出其估計值 , 若此值比目前這個點更接進目標 點我們理所當然的往這點走,如果得到的估計質比現在目前的點還 距離目標點遠,則此時就要由機率來決定是否要往這點走 , 若機率 跑出的結果是可以,則我們便往這點走,若否則隨機再取一點作同樣 的測試 . 如此一直反覆的動作直到我們到了目標點 . 模擬退火法演算法

function SIMULATED-ANNEALING(problem,schedule)returns a solution state
   inputs: problem , a problem
              schedule, a mapping from time to " temperature"
static current, a node
         next , a node
         T , a "temperature" controlling the probability of downward steps
current<---Make-None(Initial_state[problem])
for t <--1 to 無限大 do
     T<---schedule[t]
     ifT=0 then return current
      next<---a randomly selected successor of current
      E<--- Value[next]-Value[current]
      if E>0 then current<--- next
      else current <--- next only with probability e 的 E/T 次方    

網路志工聯盟----Visita網站http://www.vista.org.tw ---[ 發問前請先找找舊文章 ]---