爬山算法

爬山算法（Hill Climbing）是一种最简单的优化算法（优化算法就是找最大或者最小值），这种算法是通过模拟人们爬山的行为，也因此得名。

爬山算法的基本思路

• 不断的和邻居值进行比较，朝着邻居值大的方向前进，就像爬山一样，为了到达山顶，在到达之前肯定是朝着上山的方向，而不会朝着下山的方西。
• 当左右邻居的值相同的时候，就停止，这个值就是算法找到的最优解。同样，对于爬上来说，如果你爬到山顶了，那就是到达终点了，刚开始设立的爬上山顶的目标就达成了，你就可以大吼一声我成功了。
• 但是爬山算法有很大的缺陷，就是它只能找到局部的最优解。同样类比爬山，当爬到山顶的时候你就结束了，非常开心，以为自己已经是the king of the world，但是实际情况是可能你没看到你身后有一座比你这座山高很多的山，就很尴尬。程序就更惨，所有的别的山它都无法看到。

爬山算法的步骤

1. Current_solution = generate initial candidate solution randomly (首先随便找一个值作为解)
2. Repeat（循环）
   1. generate neighbour solutions(differ from current solution by a single element) (找到所有和当前点（步骤1中生成点的位置）相邻的点)
   2. Best_neighbour = get highest quality neighbour of current_solution(比较所有邻居的解的大小，找到值最大的那一个)
   3. if quality(best_neighbour) <= quality(current_solution)（如果最好的邻居对应的值仍然比当前点的值小）
      1. return current_solution(返回当前点对应的值)
   4. current_sulotion = best_neighbour(邻居中对应值最大的值作为结果)

爬山算法需要注意的内容

• 如何存储设计的变量，也就是变量的类型，是整型浮点型还是数组或者是布尔型
• 如何初始化，通常初始化都是伴随着随机行为的
• 如何湖区邻居值，也就是说对于邻居的取值是如何的
• 同时应该有目标函数

爬山算法举例

假设现在想要找到这个函数的最大值

分析：对于这个问题，首先我们要找到表示自变量和解空间的变量，在这里就是整数变量初始值在这里就是一个随机的整数，寻找邻居解的过程就是每次对自变量进行+1或者-1然后求对应自变量的值。

概括

爬山算法是贪婪算法中的一种，他的主要缺点是只能找到局部最优解，，如果函数中有一段是平滑的，也就是他的所有邻居自变量对应的因变量的值都是一样的，那么就无法求解。