Chapter 4 Search in Complex Environments

Chapter 4 Search in Complex Environments

Local Search Algorithms and Optimization Algorithms

alt text

  • 狀態空間搜尋: 當問題的解不包含到達解的path 的時候 改用這種
    • 例如: 八皇后問題、數獨
    • 因為過程中放置皇后的順序並不重要 重要的是結果有沒有滿足皇后互不攻擊
  • 因此我們將systematic algorithm 換成 local search algorithm

alt text

  • 根據目標函數找到最佳狀態
  • 通常只需要常數量的空間
  • 並能在無限狀態中 找到合理的解
  • alt text

alt text

  • 算法

alt text

  • 八皇后例題

alt text

  • 又被稱為貪心本地搜尋
  • 找得很快 但可能會卡住

alt text

  • Steepest-ascent hill climbing 通常更快速解決問題 但絕大多數問題無法被他處理
  • 允許sideways move 可以向沒有提升的鄰居移動 通常較慢解決問題 但能處理大多數問題

alt text

  • Stochastic hill climbing: 隨機爬山 根據鄰居的陡峭程度 有不同機率被選擇
  • first hill climbing: 選擇第一個比當前更好的狀態 速度更快
  • random restart hill climbing: 重複多次隨機選擇起始點做 hill climbing
  • 如果狀態空間的景觀充滿平台 則爬山算法結果較差
    • 但如果存在明顯的全域最佳解 局部最佳解少的情況 結果就會較好

Simulated Annealing

alt text

  • alt text
  • 溫度高的時候 更容易接受較差的選擇

alt text

  • 很像random restart hill climbing 但不同搜尋thread之間的有用資訊會互相分享

Genetic Algorithms

alt text

alt text

  • 透過fitness function來評估狀態 並選擇父母
  • 交配點是隨機選擇的
  • alt text

Local Search in Continuous Spaces

alt text

  • 六維度問題 在羅馬尼亞設置機場
  • alt text
    • 從連續問題 轉換成離散問題
  • alt text
    • 透過斜率找最大值
    • alt text
    • 如何前進 將斜率乘上步長加上去

alt text

  • 如果步長太小 要走很久 步長太大 可能衝過最優解
    • sol. 線性搜尋: 當f(x)減小又增加後 選擇f(x)最小的點當作新步長
  • Newton-raphson method: 解g(x) = 0
    • 快速收斂: 如果解距離起點很近 誤差會指數減少
    • 梯度的前進方向是讓f 前進最多的方向
      • level curve的斜率正交 f’(x) => 當level curve趨近於0 剛好就是f(x)的最佳前進方向
      • alt text
    • 考慮在局部 找到平移後函數的根 這個局部是連續且平滑的 可微分 導數不為0 => 向著切線斜率 負方向移動 會逐漸收斂到根
      • 是下一個近似點 考慮以此點獲取g()的切線斜率
      • 藉由牛頓法 代換兩邊後可以得到該近似點
      • alt text

alt text

  • 應用newton-raphson method

alt text

  • constrained optimization problem: 限制以及目標函數都是線性的
    • 讓可行解的任兩點連線都在該空間內 => 解空間是凸集
    • 是凸優化的特例

Simple Examples of Linear Programs

alt text

  • alt text
  • 例題

Searching with Nondeterministic Actions

alt text

alt text

  • 吸塵器的行動帶來的結果有不確定性
  • transition的結果變成可能的狀態集

alt text

  • 解變成巢狀的 是一種樹的結構 而非sequence
  • alt text
    • AND-OR tree
    • alt text
  • 解應該包含什麼?
    • alt text

alt text

  • 小心循環
  • alt text
    • 使用label代替
    • alt text

Searching with Partial Observations

alt text

  • agent的percept 不足以確定準確的狀態
  • 使用信念狀態估計 這是一組狀態以及Agent可能處在這些狀態的機率

alt text

  • 吸塵器的例子

alt text

  • 機器人走迷宮的例子
  • alt text
    • 透過行動促使狀態坍縮至確定狀態的例子
    • alt text
    • 有些時候 可能也沒那麼有用
    • alt text

Online Searching Agents with Unknown Environments

alt text

  • 線上搜尋以及未知環境
  • 在一間建築中尋找A點到B點的路徑

alt text

  • 規定
    • 只能知道在當前狀態的可選行動
    • step cost: 當Agent知道 行動的結果後才能計算
    • goal test
  • agent 不知道result 除非他在該狀態並且進行了a
    • alt text
  • agent 知道目標資訊 從而能夠使用啟發式函數去估算距離
    • alt text

alt text

  • 如果agent知道整個搜尋空間 就會比較理想成本與agent實際走過路徑的成本 這稱之為競爭比
    • 實際成本除以理想成本

alt text

  • 我們需要從局部展開節點 => 選擇DFS
  • alt text

alt text

  • online local search
    • 但因為local maximun 所以這沒什麼用
Introduction to AI
#AI
Chapter 4 Search in Complex Environments
https://z-hwa.github.io/webHome/[object Object]/Introduction to Artificial Intelligence/Chapter-4-Search-in-Complex-Environments/
作者
crown tako
發布於
2024年11月25日
許可協議