爬山演算法

Table of content
上一頁
下一頁

前面章節中討論的演算法都是系統地執行的。為了達到目標，需要儲存一個或多個之前探索過的路徑來找到最優解。

對於許多問題，通往目標的路徑並不重要。例如，在N皇后問題中，我們不需要關心皇后的最終配置，也不需要關心皇后的新增順序。

爬山法

爬山法是一種解決某些最佳化問題的技術。在這種技術中，我們從一個次優解開始，並反覆改進解，直到某個條件最大化。

Hill Climbing

從次優解開始的想法類似於從山腳下開始，改進解類似於沿著山坡向上行走，最後最大化某個條件類似於到達山頂。

因此，爬山法可以被認為包括以下階段：

  • 構造一個滿足問題約束的次優解
  • 逐步改進解
  • 改進解，直到無法再改進

爬山法主要用於解決計算複雜的問題。它只關注當前狀態和直接的未來狀態。因此，這種技術在記憶體方面效率很高，因為它不維護搜尋樹。

演算法

 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to 
be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

迭代改進

在迭代改進方法中，透過每次迭代都朝著最優解的方向前進，從而達到最優解。但是，這種技術可能會遇到區域性最大值。在這種情況下，沒有附近的更好的解的狀態。

這個問題可以透過不同的方法來避免。其中一種方法是模擬退火。

隨機重啟

這是解決區域性最優問題另一種方法。該技術進行一系列搜尋。每次搜尋都從隨機生成的初始狀態開始。因此，透過比較搜尋的結果，可以得到最優解或接近最優解。

爬山法的侷限性

區域性最大值

如果啟發式函式不是凸函式，則爬山法可能會收斂到區域性最大值，而不是全域性最大值。

山脊和山谷

如果目標函式建立了一個狹窄的山脊，那麼爬山者只能透過之字形的方式才能向上攀登山脊或向下進入山谷。在這種情況下，爬山者需要採取非常小的步驟，需要更多時間才能到達目標。

高原

當搜尋空間是平坦的或足夠平坦時，由於機器用來表示其值的精度，目標函式返回的值與附近區域返回的值無法區分，就會遇到高原。

爬山法的複雜度

這種技術不會遇到與空間相關的問題，因為它只關注當前狀態。之前探索過的路徑不會被儲存。

對於隨機重啟爬山法中的大多數問題，可以在多項式時間內獲得最優解。但是，對於NP完全問題，計算時間可能會隨著區域性最大值的個數呈指數增長。

爬山法的應用

爬山法可以用來解決許多問題，在這些問題中，當前狀態允許使用精確的評估函式，例如網路流問題、旅行商問題、8皇后問題、積體電路設計等。

爬山法也用於歸納學習方法中。該技術在機器人技術中用於協調團隊中多個機器人的協作。還有許多其他問題也使用了這種技術。

示例

該技術可以應用於解決旅行商問題。首先確定一個初始解，該解恰好訪問所有城市一次。因此，這個初始解在大多數情況下都不是最優的。即使這個解也可能非常糟糕。爬山演算法從這樣的初始解開始，並以迭代的方式對其進行改進。最終，很可能獲得一條更短的路線。

以下是上述方法在各種程式語言中的實現：

C C++ Java Python
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NUM_CITIES 4
// Distance matrix representing distances between cities
// Replace this with the actual distance matrix for your problem
int distance_matrix[NUM_CITIES][NUM_CITIES] = {
   {0, 10, 15, 20},
   {10, 0, 35, 25},
   {15, 35, 0, 30},
   {20, 25, 30, 0}
};
int total_distance(int* path, int num_cities) {
   // Calculate the total distance traveled in the given path
   int total = 0;
   for (int i = 0; i < num_cities - 1; i++) {
       total += distance_matrix[path[i]][path[i + 1]];
   }
   total += distance_matrix[path[num_cities - 1]][path[0]]; // Return to starting city
   return total;
}
void hill_climbing_tsp(int num_cities, int max_iterations) {
   int current_path[NUM_CITIES]; // Initial solution, visiting cities in order
   for (int i = 0; i < num_cities; i++) {
      current_path[i] = i;
   }
   int current_distance = total_distance(current_path, num_cities);
   for (int it = 0; it < max_iterations; it++) {
      // Generate a neighboring solution by swapping two random cities
      int neighbor_path[NUM_CITIES];
      for (int i = 0; i < num_cities; i++) {
         neighbor_path[i] = current_path[i];
      }
      int i = rand() % num_cities;
      int j = rand() % num_cities;
      int temp = neighbor_path[i];
      neighbor_path[i] = neighbor_path[j];
      neighbor_path[j] = temp;
      int neighbor_distance = total_distance(neighbor_path, num_cities);
      // If the neighbor solution is better, move to it
      if (neighbor_distance < current_distance) {
         for (int i = 0; i < num_cities; i++) {
            current_path[i] = neighbor_path[i];
         }
         current_distance = neighbor_distance;
      }
   }
   printf("Optimal path: ");
   for (int i = 0; i < num_cities; i++) {
      printf("%d ", current_path[i]);
   }
   printf("\nTotal distance: %d\n", current_distance);
}
int main() {
   srand(time(NULL));
   int max_iterations = 10000;
   hill_climbing_tsp(NUM_CITIES, max_iterations);
   return 0;
}

輸出

Optimal path: 1 0 2 3 
Total distance: 80

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;
#define NUM_CITIES 4
// Distance matrix representing distances between cities
// Replace this with the actual distance matrix for your problem
int distance_matrix[NUM_CITIES][NUM_CITIES] = {
   {0, 10, 15, 20},
   {10, 0, 35, 25},
   {15, 35, 0, 30},
   {20, 25, 30, 0}
};
int total_distance(const std::vector<int>& path) {
   // Calculate the total distance traveled in the given path
   int total = 0;
   for (size_t i = 0; i < path.size() - 1; i++) {
       total += distance_matrix[path[i]][path[i + 1]];
   }
   total += distance_matrix[path.back()][path[0]]; // Return to starting city
   return total;
}
void hill_climbing_tsp(int num_cities, int max_iterations) {
   vector<int> current_path(num_cities); // Initial solution, visiting cities in order
   for (int i = 0; i < num_cities; i++) {
      current_path[i] = i;
   }
   int current_distance = total_distance(current_path);
   for (int it = 0; it < max_iterations; it++) {
      // Generate a neighboring solution by swapping two random cities
      std::vector<int> neighbor_path = current_path;
      int i = rand() % num_cities;
      int j = rand() % num_cities;
      swap(neighbor_path[i], neighbor_path[j]);
      int neighbor_distance = total_distance(neighbor_path);
      // If the neighbor solution is better, move to it
      if (neighbor_distance < current_distance) {
         current_path = neighbor_path;
         current_distance = neighbor_distance;
      }
   }
   cout << "Optimal path: ";
   for (int city : current_path) {
      cout << city << " ";
   }
   cout << endl;
   cout << "Total distance: " << current_distance << endl;
}
int main() {
   srand(time(NULL));
   int max_iterations = 10000;
   hill_climbing_tsp(NUM_CITIES, max_iterations);
   return 0;
}

輸出

Optimal path: 0 1 3 2 
Total distance: 80

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class HillClimbingTSP {
   private static final int NUM_CITIES = 4;
   // Distance matrix representing distances between cities
   // Replace this with the actual distance matrix for your problem
   private static final int[][] distanceMatrix = {
      {0, 10, 15, 20},
      {10, 0, 35, 25},
      {15, 35, 0, 30},
      {20, 25, 30, 0}
   };
   private static int totalDistance(List<Integer> path) {
      // Calculate the total distance traveled in the given path
      int total = 0;
      for (int i = 0; i < path.size() - 1; i++) {
         total += distanceMatrix[path.get(i)][path.get(i + 1)];
      }
      total += distanceMatrix[path.get(path.size() - 1)][path.get(0)]; // Return to starting city
      return total;
   }
   private static List<Integer> generateRandomPath(int numCities) {
      List<Integer> path = new ArrayList<>();
      for (int i = 0; i < numCities; i++) {
         path.add(i);
      }
      Random rand = new Random();
      for (int i = numCities - 1; i > 0; i--) {
         int j = rand.nextInt(i + 1);
         int temp = path.get(i);
         path.set(i, path.get(j));
         path.set(j, temp);
      }
      return path;
   }
   public static void hillClimbingTSP(int numCities, int maxIterations) {
      List<Integer> currentPath = generateRandomPath(numCities); // Initial solution
      int currentDistance = totalDistance(currentPath);
      for (int it = 0; it < maxIterations; it++) {
         // Generate a neighboring solution by swapping two random cities
         List<Integer> neighborPath = new ArrayList<>(currentPath);
         int i = new Random().nextInt(numCities);
         int j = new Random().nextInt(numCities);
         int temp = neighborPath.get(i);
         neighborPath.set(i, neighborPath.get(j));
         neighborPath.set(j, temp);
         int neighborDistance = totalDistance(neighborPath);
         // If the neighbor solution is better, move to it
         if (neighborDistance < currentDistance) {
            currentPath = neighborPath;
            currentDistance = neighborDistance;
         }
      }
      System.out.print("Optimal path: ");
      for (int city : currentPath) {
         System.out.print(city + " ");
      }
      System.out.println();
      System.out.println("Total distance: " + currentDistance);
   }
   public static void main(String[] args) {
      int maxIterations = 10000;
      hillClimbingTSP(NUM_CITIES, maxIterations);
   }
}

輸出

Optimal path: 1 3 2 0 
Total distance: 80

import random
# Distance matrix representing distances between cities
# Replace this with the actual distance matrix for your problem
distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
def total_distance(path):
    # Calculate the total distance traveled in the given path
    total = 0
    for i in range(len(path) - 1):
        total += distance_matrix[path[i]][path[i+1]]
    total += distance_matrix[path[-1]][path[0]]  # Return to starting city
    return total
def hill_climbing_tsp(num_cities, max_iterations=10000):
    current_path = list(range(num_cities))  # Initial solution, visiting cities in order
    current_distance = total_distance(current_path) 
    for _ in range(max_iterations):
        # Generate a neighboring solution by swapping two random cities
        neighbor_path = current_path.copy()
        i, j = random.sample(range(num_cities), 2)
        neighbor_path[i], neighbor_path[j] = neighbor_path[j], neighbor_path[i]
        neighbor_distance = total_distance(neighbor_path)
        
        # If the neighbor solution is better, move to it
        if neighbor_distance < current_distance:
            current_path = neighbor_path
            current_distance = neighbor_distance
    return current_path
def main():
    num_cities = 4  # Number of cities in the TSP
    solution = hill_climbing_tsp(num_cities)
    print("Optimal path:", solution)
    print("Total distance:", total_distance(solution))
if __name__ == "__main__":
    main()

輸出

Optimal path: [1, 0, 2, 3]
Total distance: 80
列印頁面
上一頁
下一頁
廣告