在本文中，让我们尝试了解爬山算法。这是人工智能领域常用的启发式搜索技术。启发式技术是选择多个选项中哪一个最能成功实现特定目标的标准。
什么是爬山算法？
爬山来自深度优先搜索（生成和测试策略的一种变体）中的质量测量。这是一种优化策略，属于本地搜索家族的一部分。
这是一个相当简单的实施策略，因为我们探索了流行的第一个选项。在某些情况下，爬山是有效的，尽管更复杂的算法可能会产生更大的好处。
爬山可以通过多种解决方案来解决问题，但有些解决方案比其他解决方案更好。旅行商问题可以通过爬山来解决。找到一种能够访问每个城市的解决方案很简单，但与理想的解决方案相比，该解决方案可能会低于标准。
如果有一种技术来排列选项，以便首先探索最有希望的节点，那么搜索效率可能会提高。爬山按照深度优先的顺序遍历路径树，但选项是根据一些启发值（即从当前状态到目标状态的剩余成本的度量）排列的。
例如，在旅行推销员问题中，两个城市之间的直线（乌鸦飞翔）距离可以作为剩余距离的启发式测量。
要记住的属性
- 本地搜索算法
- 遵循贪婪方法
- 没有回头路。
爬山算法的类型
简单爬山：最简单的爬山方法称为简单爬山。目标是登上这座山的最高峰。在这里，登山者的步伐和动作决定了他的移动方式。如果他认为下一步会比之前更好，或者保持在同一位置，他就会继续前进。这个搜索只是关注他之前和之后的行为。
最陡爬山：与直接的爬山搜索相反，它会比较所有后续节点并选择最接近答案的节点。因为它集中于每个节点而不仅仅是一个，所以最陡的爬山搜索与最佳优先搜索相当。
随机爬山：随机爬山时节点并不全部集中。它随机选择一个节点，然后决定是扩大它还是寻找更好的节点。
随机重启爬山：尝试和尝试方法是随机重启算法的基础。在未达到目标之前，它会迭代搜索节点并在每个阶段选择最佳候选节点。成功常常取决于山的形状。如果没有太多山脊、高原或局部最大值，那么到达那里会更容易。
爬山的简单例子
为了更好地理解这个概念，让我们尝试使用爬山算法来实现旅行推销员的问题。下面给出问题的描述。
找到必须访问的多个点和地点之间的最短路径是称为“旅行商问题”（TSP）的算法问题的目标。这里的输入是城市坐标的二维数组，输出是一个整数列表，表示按顺序排列的城市数量（从零开始）
用Python实现爬山算法
import randomimport numpy as npimport networkx as nx#coordinate of the points/citiescoordinate = np.array([[1,2], [30,21], [56,23], [8,18], [20,50], [3,4], [11,6], [6,7], [15,20], [10,9], [12,12]])#adjacency matrix for a weighted graph based on the given coordinatesdef generate_matrix(coordinate): matrix = [] for i in range(len(coordinate)): for j in range(len(coordinate)) : p = np.linalg.norm(coordinate[i] - coordinate[j]) matrix.append(p) matrix = np.reshape(matrix, (len(coordinate),len(coordinate))) #print(matrix) return matrix#finds a random solution def solution(matrix): points = list(range(0, len(matrix))) solution = [] for i in range(0, len(matrix)): random_point = points[random.randint(0, len(points) - 1)] solution.append(random_point) points.remove(random_point) return solution#calculate the path based on the random solutiondef path_length(matrix, solution): cycle_length = 0 for i in range(0, len(solution)): cycle_length += matrix[solution[i]][solution[i - 1]] return cycle_length#generate neighbors of the random solution by swapping cities and returns the best neighbordef neighbors(matrix, solution): neighbors = [] for i in range(len(solution)): for j in range(i + 1, len(solution)): neighbor = solution.copy() neighbor[i] = solution[j] neighbor[j] = solution[i] neighbors.append(neighbor) #assume that the first neighbor in the list is the best neighbor best_neighbor = neighbors[0] best_path = path_length(matrix, best_neighbor) #check if there is a better neighbor for neighbor in neighbors: current_path = path_length(matrix, neighbor) if current_path < best_path: best_path = current_path best_neighbor = neighbor return best_neighbor, best_pathdef hill_climbing(coordinate): matrix = generate_matrix(coordinate) current_solution = solution(matrix) current_path = path_length(matrix, current_solution) neighbor = neighbors(matrix,current_solution)[0] best_neighbor, best_neighbor_path = neighbors(matrix, neighbor) while best_neighbor_path < current_path: current_solution = best_neighbor current_path = best_neighbor_path neighbor = neighbors(matrix, current_solution)[0] best_neighbor, best_neighbor_path = neighbors(matrix, neighbor) return current_path, current_solutionfinal_solution = hill_climbing(coordinate)print("The solution is \n", final_solution[1]) |
输出
解决办法是
[2、4、8、3、7、5、0、6、9、10、1]
爬山的问题
爬山有一些问题。搜索过程可能到达一个不是解决方案的位置，但从那里开始没有任何行动可以改善情况。如果我们达到了局部最大值、高原或山脊，就会发生这种情况。
局部最大值：它是一个比它所有邻居都好但不比其他一些较远的状态好的状态，（前面可能有更好的解，这个解称为全局最大值。）从这个状态，所有的举动看起来都更糟。在这种情况下，请回溯到某个较早的状态并尝试朝不同的方向寻找解决方案。
高原：它是搜索空间的平坦区域，其中所有相邻状态都具有相同的值。无法确定最佳方向。在这种情况下，朝某个方向大跳并尝试到达搜索空间的新部分。它也称为平坦最大值。
山脊：它是搜索空间中高于周围区域的区域，但不能通过任何一个方向的单次移动来遍历。它是一种特殊的局部最大值。这里在进行测试之前应用两个或多个规则，即同时向多个方向移动。
概括
本文深入解释了爬山算法的概念。我们了解解决著名的旅行商问题的不同类型以及算法的实现。爬山算法广泛应用于数据科学和人工智能领域。