在Python中实现AI的爬山算法

教學

Python

爬山演算法是人工智慧和電腦科學中最早和最簡單的優化演算法之一。它屬於一類稱為局部搜索演算法的演算法，通過逐步改進來找到解決方案。

這個演算法的名稱來自一個有用的類比：想像一個被蒙住眼睛的徒步者試圖到達山頂。由於他們無法看到整個地形，他們只能感受到周圍地面。在每一步，他們會向上走的方向移動。這反映了演算法的工作方式 – 它評估附近的解決方案，並迭代地朝著更好的方向移動，試圖找到最優解（山頂的高峰）。

在本文中，我們將深入探討爬山演算法、其變化以及如何在Python中實現它。如果您是AI新手，請務必查看我們的AI基礎技能軌跡以涵蓋基礎知識。

什麼是AI中的爬山演算法？

爬山是一種讓計算機通過尋找最佳答案來解決問題的簡單方法，就像一名遠足者試圖到達山頂一樣。在人工智慧（AI）中，我們常常需要在眾多可能的選擇中找到最佳解決方案。這被稱為優化。

想象一下在玩“熱與冷”遊戲時試圖找到最高點。在這個遊戲中，你只能檢查自己是否越來越“暖和”（更好）或“冷”（更差）當你四處移動時。爬山演算法也是一樣的——它查看附近的解決方案並朝著更好的方向移動。

以下是簡單步驟：

從任何可能的解決方案開始
查看附近的解決方案
如果附近的解決方案更好，則移動到該方案
重複步驟2-3，直到找不到更好的解決方案為止

例如，如果你想教機器人走路，山丘爬升可能會：

從隨機的腿部動作開始
嘗試稍微不同的動作
保留那些有助於機器人走得更好的動作
重複這個過程，直到找到最佳的行走模式

儘管爬山演算法並非人工智慧中最先進的方法，但它是一個重要的基礎模塊，幫助我們理解電腦如何自行解決問題，類似於極小化演算法。

爬山演算法類型

有三種主要類型的爬山演算法，每種都有自己尋找最佳解的方式：

1. 簡單爬山演算法

簡單爬山演算法就像找到的第一個好步驟一樣。在這個版本中：

該算法逐一查看附近的解決方案
一旦找到更好的解決方案，就採用它
它不會檢查其他選項
這樣做速度很快，但可能會錯過稍微遠一點的更好解決方案

2. 最陡上升爬山法

這個版本比簡單的爬山法更徹底：

在採取行動之前，它會查看所有附近的解決方案
從找到的所有選項中選擇最佳選擇
花費更多時間，但通常可以找到更好的解決方案
就像在每一步之前仔細檢查每條路徑

3. 隨機爬山演算法

這種類型增加了一些隨機性，使搜索更有趣：

而不是總是選擇最佳解決方案，它會從更好的選項中隨機選擇
較好的解決方案被選中的機會更高
這種隨機性有助於避免陷入困境
有時候走不同的路線只是想看看它會通向哪裡

每種方法都有其優勢，並且適合解決不同類型的問題。簡單爬山法速度快但基礎，最陡上升法徹底但較慢，隨機法增加有益的隨機性以避免陷入困境。

爬山演算法的運作方式

爬山演算法通過逐步進行小改進，直到找到可能的最佳解決方案為止。讓我們將其工作方式分解為主要部分。

1. 開始

每個爬山演算法都需要一個起點。想像一下就像選擇在山上哪裡開始遠足一樣。你可以隨機開始，或者你可以利用你對問題的了解來選擇一個好的起點。

你的起點真的很重要 – 選擇一個好地點，你可能會很快找到最佳解決方案。選擇一個糟糕的地點，你可能會卡在一個小山上，而不是找到山頂。

例如，在訓練神經網絡時，起點意味著選擇神經元之間連接的初始權重。您可以隨機初始化這些權重，這就像在山上隨機地開始您的徒步旅行。或者您可以使用像Xavier初始化這樣的技術，根據網絡結構選擇智能的起始權重。

良好的初始化有助於網絡更快地學習並找到更好的解決方案，而糟糕的初始化可能使網絡陷入低準確度且永不改善的困境。

2. 查看附近的解決方案

一旦算法开始搜索，它会评估与当前位置相似的相邻解决方案。可以将其视为在小步中探索周围环境。例如，如果您正在尝试优化城市之间的交付路线，而当前路线为[A -> B -> C -> D]，算法将检查类似的路线，如[A -> B -> D -> C]或[A -> C -> B -> D]，看它们是否减少总行驶距离。对路线的每个小改变代表了一个“邻居”解决方案，可能比当前解决方案更好。

为了进行这些比较，算法依赖于所谓的客观函数 – 一种为每个可能解决方案分配分数或值的数学公式。

此功能类似指南针，帮助算法了解哪些方向通向“上坡”、通向更好的解决方案，哪些通向“下坡”、通向更差的解决方案。对于送货路线，客观函数会计算总行驶距离——行驶距离更短意味着更好的解决方案。

所以如果路线X需要100英里，而路线Z需要90英里，路线Z会有一个更好（更低）的分数。然后算法会知道朝着类似路线Z的解决方案方向移动。客观函数基本上将路线优化的复杂问题转化为可以比较和最小化的简单数字。

3. 选择下一步

在查看附近解决方案后，算法需要决定下一步往哪里移动。算法会比较附近解决方案与当前解决方案的分数。如果找到更好的解决方案，就会移动到那里。不同版本的爬山算法会以不同的方式做出这个选择：

簡單版本會選擇它找到的第一個更好的解決方案
謹慎版本會在選擇最佳方案之前檢查所有附近的解決方案
隨機版本有時會選擇不是最好的解決方案，這可以幫助它避免陷入困境

4. 何時停止

演算法需要知道何時停止尋找更好的解決方案。通常，當發生以下情況之一時停止：

找不到附近更好的解決方案
運行時間過長
找到一個足夠好的解決方案

隨著演算法的運作，通常會遵循一個模式。一開始，它會快速找到更好的解決方案，就像在陡峭的山丘上大步向前。然後，當它靠近山頂時，速度會變慢，進行較小的改進，直到最終停止。

有時，路徑是平滑且直接的，但有時可能會複雜，有很多起伏。

人工智慧中爬山演算法的優勢和限制

讓我們看看爬山演算法的優點以及在使用時可能遇到的問題。

優勢

爬山演算法是最簡單的優化演算法之一，易於理解和編程。它就像遵循一個基本規則：“如果有更好的，就往那裡走。”這使得它成為解決許多問題的絕佳起點。

當問題簡單時，爬山演算法可以快速找到好的解決方案。它不會浪費時間探索每個可能的解決方案，只是沿著向上的路徑前進。

該演算法不需要太多的計算機內存或處理能力。它只需要記住自己的位置並查看附近的解決方案，使其在許多現實世界問題中實用。

限制

當然，像任何方法一樣，也存在一些潛在的缺點：

1. 卡在小山上

爬山法的最大問題在於可能會陷入所謂的“局部最大值”——這些就像小山丘，而實際上附近可能有座更高的山。一旦演算法到達小山丘的頂端，它就停止了，因為周圍的所有點都比較低，即使可能在其他地方有更好的解決方案。

2. 平地問題

有時演算法會發現自己處於平地上（被稱為高原），附近所有的解決方案都同樣好。想像一下在平坦的足球場上尋找最高點，很難知道該往哪個方向走！

3. 山脊問題

試想著沿著狹窄山脊走路。演算法可能會浪費時間在山脊上來回擺動，而不是向前走向山頂。這是因為每一步向側面走看起來和保持原路線一樣好。

4. 起點很重要

你的起點對演算法的運作有很大的影響。這就像開始一次徒步旅行 – 如果起點錯誤，你可能永遠找不到最高峰。

這些限制並不意味著爬山法是一個壞選擇 – 這只是意味著我們需要在何時以及如何使用它時小心。有時，我們可以將它與其他技術結合以克服這些問題，這將在下一節中討論。

克服限制的策略

在使用爬山法時，我們可以使用一些巧妙的策略來解決我們之前討論的問題。讓我們探索兩種主要方法，這有助於讓爬山法運作得更好。

隨機重啟爬山法

避免陷入小山上的最佳方法之一是嘗試從不同的起點開始攀登。這種方法被稱為隨機重啟爬山法，它的運作方式就像它的名字一樣 – 如果卡住了，就在新的地方重新開始。

想象一下在一片迷雾茫茫的山脉中寻找最高的山峰。如果你开始攀登第一座山丘并到达山顶，你可能会错过附近更高的山峰。但如果你可以传送到不同的位置并重新开始攀登，你将更有机会最终找到最高的山峰。

这是如何运作的：首先，你运行正常的爬山算法直到陷入困境。而不是放弃，你会保存找到的最佳解决方案，然后从一个随机的新点开始重新尝试。你会一直这样做几次，最后，你从所有尝试中选择最佳解决方案。

随机重启的美妙之处在于它简单而有效。每次重新启动都会为你提供一个重新寻找最高峰的机会。虽然比普通的爬山算法花费更多时间，但更有可能找到最佳解决方案。

模拟退火

雖然模擬退火並非嚴格意義上的爬山演算法，但它是一個巧妙的變體，有助於解決許多爬山演算法的問題。它受到金屬在金屬加工中怎樣冷卻和硬化的啟發。當金屬慢慢冷卻時，其原子會找到更好的位置，使金屬變得更堅固。

在這種方法中，演算法有時會故意接受較差的解決方案，尤其是在開始階段。隨著時間的推移，它會變得更加挑剔地接受解決方案。這就像一顆球在崎嶇表面上彈跳一樣，一開始它有足夠的能量彈跳上並超越山丘，但隨著失去能量，它會停留在一個好位置。

這是如何運作的：一開始，該算法可能以相當高的概率接受比當前解决方案更糟糕的解决方案。這個概率取決於兩件事：新解决方案比現有解决方案更糟糕多少，以及算法運行的時間有多長。隨著時間的推移，算法變得不太可能接受更糟糕的解决方案，最終行為更像常規的爬山演算法。

<diy5模擬退火的真正威力在於它可以逃離小山丘和平坦區域，特別是在搜索早期。通過有時接受更差的解决方案，它可以：

跳出局部最大值（小山丘）
跨越高原（平坦區域）
導航山脊（狹窄山峰）
探索更多解決方案空間

例如，想像你正在試圖在一個房間裡安排家具以最大化空間利用。移動一把椅子可能暫時讓房間變得更擁擠，但這樣做可能讓你能夠將其他家具移動到更好的位置。模擬退火算法願意嘗試這些暫時更糟的安排，特別是在過程的早期，以找到最佳的整體安排。

這些策略告訴我們，有時解決問題的最佳方式並不總是向前邁出明顯的一步。通過添加隨機性和受控混沌的元素，我們通常可以找到比總是走直接路線更好的解決方案。

在Python中實現一個簡單的爬山演算法

現在我們了解了如何通過策略如隨機重啟和模擬退火來改善爬山算法，讓我們將其應用於一個真實的金融問題：投資組合優化。

投資組合優化幫助投資者決定如何將他們的資金分散投資於不同的項目。當投資者建立投資組合時，他們希望獲得最高可能的回報，同時保持風險低。找到這種平衡很棘手，就像試圖找到具有許多成分的完美食譜一樣。

1952年，一位名為哈利·馬科維茨的經濟學家找到了解決這個問題的聰明方法。他表明投資者可以通過混合不同步上下波動的投資來降低風險。這被稱為多元化，類似於不把所有蛋放在同一個籃子裡。

在建立投資組合時，我們需要弄清楚三個主要問題：

我們預期賺取多少錢（預期回報）
投資的風險有多大（投資組合風險）
潛在利潤是否值得風險（風險調整後回報）

山峰爬升法對這個問題很有效，因為我們如何分配資金的微小變化通常會導致投資組合表現的微小變化。想像一座平滑的山丘，每個點代表一種不同的投資方式。較高的點表示較好的投資選擇。

使用爬山演算法找到優良投資組合的方法如下：

從隨機投資組合開始
嘗試略有不同的組合，看看它們是否更好
持續進行小幅改進，直到找不到更好的選擇
使用我們找到的最佳組合

通過這種方式使用爬山演算法，我們可以幫助投資者在數百萬種可能的組合中找到更好的投資組合。就像擁有一個聰明的助手，可以快速測試許多不同的投資組合，找到平衡風險和回報的最佳組合。

首先，讓我們定義我們的目標函數，這是一個衡量投資組合表現的指標，平衡了預期收益和風險。它以投資組合權重列表作為輸入，返回一個分數，其中較高的分數表示更好的投資組合。

def objective_function(state):
   """
   Portfolio optimization objective function that maximizes expected returns while minimizing risk.
   The state represents portfolio weights for different assets.

   Args:
       state (list): List of portfolio weights for different assets (should sum to 1)

   Returns:
       float: Portfolio score combining returns and risk
   """
   # 資產的預期年收益（示例數值）
   expected_returns = [0.1, 0.12, 0.18, 0.1, 0.15]  # 8%，12%，等等。

   # 每個資產的風險（波動性）
   volatilities = [0.1, 0.2, 0.3, 0.2, 0.2]  # 10%，20%，等等。

   # 驗證輸入長度是否符合預期的收益/波動性
   if len(state) != len(expected_returns):
       return float("-inf")  # 對於無效狀態返回最壞的可能分數

   # 計算預期投資組合收益
   portfolio_return = sum(w * r for w, r in zip(state, expected_returns))

   # 計算投資組合風險（簡化，不使用協方差矩陣）
   portfolio_risk = sum(w * v for w, v in zip(state, volatilities))

   # 如果權重不為1則處罰（無效的投資組合）
   weight_sum_penalty = abs(sum(state) - 1) * 100

   # 處罰負權重（禁止空頭交易）
   negative_weight_penalty = sum(abs(min(0, w)) for w in state) * 100

   # 將收益和風險與風險厭惡因子2結合
   # 分數越高越好：最大化收益，最小化風險和懲罰
   score = (
       portfolio_return
       - 2 * portfolio_risk
       - weight_sum_penalty
       - negative_weight_penalty
   )

   return score

上述的objective_function幫助我們評估特定投資組合的優劣。讓我們來看看它是如何運作的：

首先，它接受一個數字列表，代表我們想要投資在不同資產（如股票或債券）中的資金百分比。例如，如果我們有五個資產，我們可能每個資產投資20%。

該函數使用兩個重要的資訊：

預期收益：我們預期從每個資產賺取多少錢（如每年8%或12%）
波動性：每個資產的風險程度 – 較高的數字表示該資產價值變動較不可預測（如加密貨幣）

然後函數：

通過將每個資產的預期收益乘以我們投資的金額，計算我們投資組合的總預期收益
通過查看每個資產的波動性，計算總風險
檢查我們的投資百分比是否相加為100%（應該是！）
確保我們沒有嘗試出售我們沒有擁有的資產（不應有負百分比）

最後，將所有這些信息組合成一個分數。分數越高表示投資組合越好。分數隨著收益增加而增加，但隨著風險增加而減少。如果我們的百分比不相加為100%，或者嘗試使用負百分比，分數也會變得更糟。

這個函數將幫助我們使用遵循山峰爬升算法找到最佳投資組合。如果你不完全理解目標函數，不用擔心 – 關鍵是它告訴我們一個特定投資組合有多好，我們將使用它來找到越來越好的組合。

現在，讓我們定義一個新函數來通過對權重進行微小調整來生成鄰近的投資組合狀態。

def get_neighbors(state):
   """
   Generates neighboring states by making small adjustments to portfolio weights

   Args:
       state (list): Current portfolio weights

   Returns:
       list: List of neighboring portfolio weight configurations
   """
   neighbors = []
   step_size = 0.01  # 對權重進行微小調整（1%）

   for i in range(len(state)):
       for j in range(len(state)):
           if i != j:
               # 將資產 i 的權重轉移到資產 j
               neighbor = state.copy()
               if neighbor[i] >= step_size:  # 只有在足夠的權重可用時才轉移
                   neighbor[i] -= step_size
                   neighbor[j] += step_size
                   neighbors.append(neighbor)

   return neighbors

get_neighbors 函數是我們山峰爬升算法的關鍵部分，通過對當前投資組合的權重進行微小調整來生成類似的投資組合分配。下面是它的工作原理：

對於我們投資組合中的每一對資產，它通過將微小金額（1%）從一個資產轉移到另一個來創建新的投資組合分配。例如，如果我們有五個資產，它將嘗試：

將 1% 從資產 1 轉移到資產 2
將 1% 從資產 1 轉移到資產 3
將 1% 從資產 1 轉移到資產 4
將 1% 從資產 1 轉移到資產 5
將 1% 從資產 2 轉移到資產 1，以此類推對所有可能的組合。

該函數包括一個安全檢查，以確保只有在源資產有足夠的分配（至少 1%）時才轉移權重。這可以防止負權重，在真實投資組合中是沒有意義的。

每一次這些小調整都會創建一個“鄰居”——一個與我們當前配置非常相似但略有不同的投資組合。然後，爬山算法將評估這些鄰居，以找到更好的投資組合。

1%的步長提供了在探索不同配置和進行受控變更之間取得良好平衡。步長更大可能會錯過最佳解，而步長更小會使搜索過於緩慢。

現在，讓我們最終實現一個簡單的爬山算法：

def simple_hill_climbing(initial_state, max_iterations=1000):
   """
   Implements Simple Hill Climbing algorithm
  
   Args:
       initial_state (list): Starting point for the algorithm
       max_iterations (int): Maximum number of iterations to prevent infinite loops
  
   Returns:
       tuple: (best_state, best_value) found by the algorithm
   """
   current_state = initial_state
   current_value = objective_function(current_state)
  
   for _ in range(max_iterations):
       # 獲取鄰近狀態
       neighbors = get_neighbors(current_state)
      
       # 標誌以檢查是否找到更好的鄰居
       found_better = False
      
       # 逐一檢查鄰居（簡單爬山法）
       for neighbor in neighbors:
           neighbor_value = objective_function(neighbor)
          
           # 如果找到更好的鄰居，立即移動到該鄰居
           if neighbor_value > current_value:
               current_state = neighbor
               current_value = neighbor_value
               found_better = True
               break
      
       # 如果沒有找到更好的鄰居，則達到了局部峰值
       if not found_better:
           break
  
   return current_state, current_value

該函數從初始狀態開始，反覆移動到更好的鄰近狀態，直到達到局部最大值或最大迭代次數。

該函數接受兩個參數：

initial_state：優化的起點，表示為一組值的列表
max_iterations：一個安全參數，用於防止無限循環，默認為1000次迭代

該算法的工作原理如下：

它從initial_state開始並計算其目標函數值
每次迭代時，它：

使用get_neighbors()生成相鄰狀態
逐個評估每個鄰居
一旦找到更好的鄰居（更高的目標值），它就會移動到該狀態
如果找不到更好的鄰居，它已經達到局部最大值並終止

該函數返回一個元組，其中包含：

找到的最佳狀態（值列表）
該狀態的目標函數值

這種“簡單”的爬山變體是貪婪的 — 它移動到找到的第一個更好的鄰居，而不是評估所有鄰居以找到最佳的。雖然這使其更快，但可能會錯過通過更仔細的方法找到的更好解決方案。

該演算法對於尋找局部最優點很有用，但可能會陷入這些局部最大值中，潛在地錯過全局最大值。儘管存在這種限制，但由於其簡單和高效，它仍然很受歡迎。

讓我們在一個樣本投資組合上進行測試：

# 範例用法
initial_state = [0.15, 0.25, 0.1, 0.3, 0.2]
best_state, best_value = simple_hill_climbing(initial_state)
print(f"Initial State: {initial_state}")
print(f"Best State Found: {best_state}")
print(f"Best Value: {best_value}")

[OUT]:

Initial State: [0.15, 0.25, 0.1, 0.3, 0.2]
Best State Found: [0.9700000000000006, 0.009999999999999913, 1.0408340855860843e-17, 0.009999999999999858, 0.009999999999999969]
Best Value: -0.1053000000000444

輸出顯示了我們的爬山演算法在優化投資組合時的結果。從五個資產的隨機權重開始，它找到了一組改善目標函數值的新權重。儘管這個解決方案改進了初始投資組合，但可能只是一個局部最優，因為演算法在找到第一個高峰時停止。

在人工智慧中的爬山應用

爬山演算法在人工智慧和機器學習的許多領域中找到了實際應用。讓我們探索一些主要應用：

1. 機器學習模型優化

爬山演算法在幾個方面有助於調整機器學習模型：

特徵選擇：為模型找到最佳特徵子集
超參數調整：優化模型參數，如學習率或樹深度
神經網絡訓練：微調網絡權重和架構
模型壓縮：減小模型大小同時保持性能

例如，在選擇預測模型的特徵時，爬山演算法可能從所有特徵開始，並根據模型性能迭代地刪除或添加它們。這有助於找到一個平衡模型準確性和複雜性的最佳特徵集。

2. 機器人和路徑規劃

在機器人領域，爬山演算法有助於：

運動規劃：尋找在物理空間中的有效路徑
關節角度優化：確定機器人手臂的最佳位置
感應器放置：優化感應器的放置位置以獲得最大覆蓋範圍
電池管理：優化功耗模式

機器人吸塵器可能使用爬山演算法找到高效的清潔路徑，根據房間覆蓋範圍和電池壽命不斷調整其路線。

3. 自然語言處理

NLP 應用包括:

文本摘要: 優化摘要內容選擇
詞嵌入: 微調詞向量表示
文件分類：將文件組織成最佳群組
搜索引擎優化：改善搜索結果排名

例如，在文本摘要中，山峰爬升法可以幫助選擇最大化信息內容並最小化冗余的句子。

4. 電腦視覺在圖像處理和電腦視覺中

圖像分割：查找物體之間的最佳邊界
相機校準：調整相機參數以獲得更好的影像質量
物件檢測：優化邊界框位置
特徵匹配：在影像之間找到對應點

一個面部識別系統可能在預處理過程中使用爬山演算法來優化面部特徵的對齊。

5. 遊戲人工智能和決策

爬山演算法有助於：

遊戲策略優化：尋找棋盤遊戲中的致勝之招
資源分配：優化策略遊戲中的資源分配
非玩家角色行為：改善非玩家角色的決策能力
關卡生成：創建平衡且有趣的遊戲關卡

在遊戲過程中，象棋引擎通常使用爬山變種來評估和優化移動順序。

6. 商業和運營

實用的商業應用包括:

供應鏈優化: 尋找高效的交貨路線
資源排程: 優化人員排班或機器使用
投資組合管理: 平衡投資組合
庫存管理：優化庫存水平

一家運輸公司可能使用爬山演算法來根據交通模式和包裹優先級不斷優化送貨路線。

儘管爬山演算法可能並非總是找到絕對最佳解決方案，但其簡單性和效率使其在這些現實應用中具有價值。特別是當：

需要快速解決方案
問題空間過大無法進行詳盡搜索
可接受近似解決方案
解決空間相對平滑
該演算法可以與其他技術結合以獲得更好的結果

結論

爬山演算法是人工智慧中的基礎演算法，提供了一種直觀而強大的優化問題方法。

通過我們的探索，我們看到這個簡單的概念，即逐步朝著更好的解決方案前進，可以應用於機器學習、機器人技術、自然語言處理和業務運營等領域的複雜挑戰中。

儘管演算法有其局限性，例如陷入局部最優解，但諸如隨機重啟和模擬退火等策略已經發展出來，有效應對這些挑戰。

隨著人工智慧的不斷進步，爬山演算法仍然具有重要意義，不僅作為一種實用工具，還是理解更複雜優化演算法的基石。其直觀的特性使其成為進入人工智慧領域的絕佳起點，而其多功能性確保了它在現實應用中的持續使用。

無論您是在優化神經網絡權重、規劃機器人路徑還是管理投資組合，爬山演算法的原則都能為計算機如何系統性地找到更好解決方案提供寶貴見解。

如果您想了解更多有關人工智慧及其背後演算法的知識，請查看我們的資源：

Source:
https://www.datacamp.com/tutorial/hill-climbing-algorithm-for-ai-in-python