vlambda博客
学习文章列表

“爬山算法是一种简单的贪心搜索算法，用于求解局部最优问题”

本文目录：

• 一、爬山算法简介

• 二、爬山算法的Python实现

一、爬山算法简介

    爬山算法是一种简单的贪心搜索算法，是一种用于求解局部最优的算法，是深度优先搜索算法的一种改进，属于人工智能算法的一种。该算法一般从一个随机的解开始进行，每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。其主要思想如下图所示：

    该算法的特点有：实现简单、效率高，但在处理大规模多约束问题时可能会陷入局部最优解，此时的解决方案往往不是最好的。如下图所示，若初始随机解选择在了C点，那么在局部搜索时算法到A点就会终止，因为此时在A点无论向哪个方向小幅度移动都不能找到更大的点。

二、爬山算法的Python实现

    设方程    ，   是区间   中的整数，   是区间   中的整数，   是区间   中的整数。使用爬山法，找到使得   取值最小的解。实现代码如下：

 1import random
 2def evaluate(x1, x2, x3):
 3    return x1+x2-x3
 4
 5h=1
 6if __name__ == '__main__':
 7    x_range = [ [-3, 5], [1, 6], [-6, 2] ]
 8    best_sol = [random.randint(x_range[0][0], x_range[0][1]),
 9                random.randint(x_range[1][0], x_range[1][1]),
10                random.randint(x_range[2][0], x_range[2][1])]
11
12    while True:
13        best_evaluate = evaluate(best_sol[0], best_sol[1], best_sol[2])
14        current_best_value = best_evaluate
15        sols = [best_sol]
16
17        for i in range(1,len(best_sol)):
18            if best_sol[i-1] > x_range[i-1][0]:
19                sols.append(best_sol[0:i-1] + [best_sol[i-1]-1] + best_sol[i:])
20            if best_sol[i-1] < x_range[i-1][1]:
21                sols.append(best_sol[0:i-1] + [best_sol[i-1]+1] + best_sol[i:])
22
23        print(sols)
24        for s in sols:
25            el = evaluate(s[0], s[1], s[2])
26            if el < best_evaluate:
27                best_sol = s
28                best_evaluate = el
29        if best_evaluate == current_best_value:
30            break
31
32    print ('best sol：', current_best_value, best_sol)

    下图为某次运行后的结果，因为是从随机解开始，所以会有很多种不同的结果。该次运行结果为   ，最后的最小值为-1。