爬山算法

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
打印页面
上一页
下一页
广告