1. Overview
1.概述
In this tutorial, we’ll show the Hill-Climbing algorithm and its implementation. We’ll also look at its benefits and shortcomings. Before directly jumping into it, let’s discuss generate-and-test algorithms approach briefly.
在本教程中，我们将展示Hill-Climbing算法及其实现。我们还将看看它的优点和缺点。在直接进入它之前，让我们简单讨论一下生成和测试算法的方法。
2. Generate-And-Test Algorithm
2.生成和测试算法
It’s a very simple technique that allows us to algorithmize finding solutions:
这是一个非常简单的技术，可以让我们通过算法来寻找解决方案。
- Define current state as an initial state
- Apply any possible operation on the current state and generate a possible solution
- Compare newly generated solution with the goal state
- If the goal is achieved or no new states can be created, quit. Otherwise, return to the step 2
It works very well with simple problems. As it is an exhaustive search, it is not feasible to consider it while dealing with large problem spaces. It is also known as British Museum algorithm (trying to find an artifact in the British Museum by exploring it randomly).
它在处理简单问题时效果很好。由于它是一种穷举式搜索，在处理大问题空间时考虑它是不可行的。它也被称为大英博物馆算法（试图通过随机探索在大英博物馆找到一件文物）。
It is also the main idea behind the Hill-Climbing Attack in the world of biometrics. This approach can be used for generating synthetic biometric data.
这也是生物统计学界的爬坡攻击的主要思想。这种方法可用于生成合成生物识别数据。
3. Introduction to the Simple Hill-Climbing Algorithm
3.简单爬坡算法介绍
In Hill-Climbing technique, starting at the base of a hill, we walk upwards until we reach the top of the hill. In other words, we start with initial state and we keep improving the solution until its optimal.
在爬坡技术中，从山脚开始，我们向上走，直到到达山顶。换句话说，我们从初始状态开始，不断改进解决方案，直到达到最佳状态。
It’s a variation of a generate-and-test algorithm which discards all states which do not look promising or seem unlikely to lead us to the goal state. To take such decisions, it uses heuristics (an evaluation function) which indicates how close the current state is to the goal state.
这是一种生成-测试算法的变种，它抛弃了所有看起来没有希望的状态，或者看起来不太可能引导我们到达目标状态。为了做出这样的决定，它使用了启发式方法（一个评估函数），表明当前状态与目标状态的接近程度。
In simple words, Hill-Climbing = generate-and-test + heuristics
简单地说，爬坡=生成和测试+启发式方法。
Let’s look at the Simple Hill climbing algorithm:
让我们来看看简单爬坡算法。
- Define the current state as an initial state
- Loop until the goal state is achieved or no more operators can be applied on the current state:
- Apply an operation to current state and get a new state
- Compare the new state with the goal
- Quit if the goal state is achieved
- Evaluate new state with heuristic function and compare it with the current state
- If the newer state is closer to the goal compared to current state, update the current state
As we can see, it reaches the goal state with iterative improvements. In Hill-Climbing algorithm, finding goal is equivalent to reaching the top of the hill.
我们可以看到，它通过迭代改进达到了目标状态。在爬坡算法中，找到目标就相当于到达了山顶。
4. Example
4.实例
Hill Climbing Algorithm can be categorized as an informed search. So we can implement any node-based search or problems like the n-queens problem using it. To understand the concept easily, we will take up a very simple example.
爬坡算法可以被归类为一种知情搜索。因此，我们可以用它来实现任何基于节点的搜索或像n-queens问题这样的问题。为了便于理解这个概念，我们将举一个非常简单的例子。
Let’s look at the image below:
让我们看一下下面的图片。
Key point while solving any hill-climbing problem is to choose an appropriate heuristic function.
在解决任何爬坡问题时，关键点是要选择一个合适的启发式函数。
Let’s define such function h:
让我们来定义这样的函数h:。
h(x) = +1 for all the blocks in the support structure if the block is correctly positioned otherwise -1 for all the blocks in the support structure.
h(x)=+1，如果该块的位置正确，则支撑结构中的所有块都是+1，否则支撑结构中的所有块都是-1。
Here, we will call any block correctly positioned if it has the same support structure as the goal state. As per the hill climbing procedure discussed earlier let’s look at all the iterations and their heuristics to reach the target state:
在这里，如果任何区块的支持结构与目标状态相同，我们将称之为正确定位。按照前面讨论的爬坡程序，让我们看看所有的迭代和它们的启发式方法，以达到目标状态。
5. Implementation
5.实施
Now, let’s implement the same example using the Hill-Climbing algorithm.
现在，让我们用爬坡算法来实现同一个例子。
First of all, we need a State class which will store the list of stacks representing positions of blocks at each state. It will also store heuristics for that particular state:
首先，我们需要一个State类，它将存储代表每个状态下块的位置的堆栈列表。它还将存储该特定状态的启发式方法。
public class State {
private List<Stack<String>> state;
private int heuristics;
// copy constructor, setters, and getters
}We also need a method which will compute the heuristic value of the state.
我们还需要一个能计算出状态的启发式数值的方法。
public int getHeuristicsValue(
List<Stack<String>> currentState, Stack<String> goalStateStack) {
Integer heuristicValue;
heuristicValue = currentState.stream()
.mapToInt(stack -> {
return getHeuristicsValueForStack(
stack, currentState, goalStateStack);
}).sum();
return heuristicValue;
}
public int getHeuristicsValueForStack(
Stack<String> stack,
List<Stack<String>> currentState,
Stack<String> goalStateStack) {
int stackHeuristics = 0;
boolean isPositioneCorrect = true;
int goalStartIndex = 0;
for (String currentBlock : stack) {
if (isPositioneCorrect
&& currentBlock.equals(goalStateStack.get(goalStartIndex))) {
stackHeuristics += goalStartIndex;
} else {
stackHeuristics -= goalStartIndex;
isPositioneCorrect = false;
}
goalStartIndex++;
}
return stackHeuristics;
}
Furthermore, we need to define operator methods which will get us a new state. For our example we will define two of these methods:
此外，我们还需要定义操作者方法，这些方法将为我们获得一个新的状态。对于我们的例子，我们将定义其中的两个方法。
- Pop a block from a stack and push it onto a new stack
- Pop a block from a stack and push it into one of the other stacks
private State pushElementToNewStack(
List<Stack<String>> currentStackList,
String block,
int currentStateHeuristics,
Stack<String> goalStateStack) {
State newState = null;
Stack<String> newStack = new Stack<>();
newStack.push(block);
currentStackList.add(newStack);
int newStateHeuristics
= getHeuristicsValue(currentStackList, goalStateStack);
if (newStateHeuristics > currentStateHeuristics) {
newState = new State(currentStackList, newStateHeuristics);
} else {
currentStackList.remove(newStack);
}
return newState;
}private State pushElementToExistingStacks(
Stack currentStack,
List<Stack<String>> currentStackList,
String block,
int currentStateHeuristics,
Stack<String> goalStateStack) {
return currentStackList.stream()
.filter(stack -> stack != currentStack)
.map(stack -> {
return pushElementToStack(
stack, block, currentStackList,
currentStateHeuristics, goalStateStack);
})
.filter(Objects::nonNull)
.findFirst()
.orElse(null);
}
private State pushElementToStack(
Stack stack,
String block,
List<Stack<String>> currentStackList,
int currentStateHeuristics,
Stack<String> goalStateStack) {
stack.push(block);
int newStateHeuristics
= getHeuristicsValue(currentStackList, goalStateStack);
if (newStateHeuristics > currentStateHeuristics) {
return new State(currentStackList, newStateHeuristics);
}
stack.pop();
return null;
}Now that we have our helper methods let’s write a method to implement hill climbing technique.
现在我们有了辅助方法，让我们写一个方法来实现爬坡技术。
Here, we keep computing new states which are closer to goals than their predecessors. We keep adding them in our path until we reach the goal.
在这里，我们不断计算新的状态，这些状态比它们的前辈更接近目标。我们不断在我们的路径中加入它们，直到我们达到目标。
If we don’t find any new states, the algorithm terminates with an error message:
如果我们没有找到任何新的状态，该算法就会以错误信息终止。
public List<State> getRouteWithHillClimbing(
Stack<String> initStateStack, Stack<String> goalStateStack) throws Exception {
// instantiate initState with initStateStack
// ...
List<State> resultPath = new ArrayList<>();
resultPath.add(new State(initState));
State currentState = initState;
boolean noStateFound = false;
while (
!currentState.getState().get(0).equals(goalStateStack)
|| noStateFound) {
noStateFound = true;
State nextState = findNextState(currentState, goalStateStack);
if (nextState != null) {
noStateFound = false;
currentState = nextState;
resultPath.add(new State(nextState));
}
}
return resultPath;
}In addition to this, we also need findNextState method which applies all possible operations on current state to get the next state:
除此之外，我们还需要findNextState方法，该方法对当前状态进行所有可能的操作以获得下一个状态。
public State findNextState(State currentState, Stack<String> goalStateStack) {
List<Stack<String>> listOfStacks = currentState.getState();
int currentStateHeuristics = currentState.getHeuristics();
return listOfStacks.stream()
.map(stack -> {
return applyOperationsOnState(
listOfStacks, stack, currentStateHeuristics, goalStateStack);
})
.filter(Objects::nonNull)
.findFirst()
.orElse(null);
}
public State applyOperationsOnState(
List<Stack<String>> listOfStacks,
Stack<String> stack,
int currentStateHeuristics,
Stack<String> goalStateStack) {
State tempState;
List<Stack<String>> tempStackList
= new ArrayList<>(listOfStacks);
String block = stack.pop();
if (stack.size() == 0)
tempStackList.remove(stack);
tempState = pushElementToNewStack(
tempStackList, block, currentStateHeuristics, goalStateStack);
if (tempState == null) {
tempState = pushElementToExistingStacks(
stack, tempStackList, block,
currentStateHeuristics, goalStateStack);
stack.push(block);
}
return tempState;
}6. Steepest-Ascent Hill Climbing Algorithm
6.最陡峭坡度的爬坡算法
Steepest-Ascent Hill-Climbing algorithm (gradient search) is a variant of Hill Climbing algorithm. We can implement it with slight modifications in our simple algorithm. In this algorithm, we consider all possible states from the current state and then pick the best one as successor, unlike in the simple hill climbing technique.
Steepest-Ascent Hill-Climbing算法（梯度搜索）是Hill Climbing算法的一个变体。我们可以在我们的简单算法中稍作修改后实现它。在这个算法中，我们从当前状态开始考虑所有可能的状态，然后挑选最好的一个作为继任者，这与简单的爬坡技术不同。
In other words, in the case of hill climbing technique we picked any state as a successor which was closer to the goal than the current state whereas, in Steepest-Ascent Hill Climbing algorithm, we choose the best successor among all possible successors and then update the current state.
换句话说，在爬坡技术的情况下，我们选择任何比当前状态更接近目标的状态作为继任者，而在最陡坡爬坡算法中，我们在所有可能的继任者中选择最佳继任者，然后更新当前状态。
7. Disadvantages
7.劣势
Hill Climbing is a short sighted technique as it evaluates only immediate possibilities. So it may end up in few situations from which it can not pick any further states. Let’s look at these states and some solutions for them:
爬坡法是一种短视的技术，因为它只评估眼前的可能性。因此，它可能会在一些情况下结束，无法从中选择任何进一步的状态。让我们来看看这些状态和一些解决方案。
- Local maximum: It’s a state which is better than all neighbors, but there exists a better state which is far from the current state; if local maximum occurs within sight of the solution, it is known as “foothills”
- Plateau: In this state, all neighboring states have same heuristic values, so it’s unclear to choose the next state by making local comparisons
- Ridge: It’s an area which is higher than surrounding states, but it can not be reached in a single move; for example, we have four possible directions to explore (N, E, W, S) and an area exists in NE direction
There are few solutions to overcome these situations:
克服这些情况的解决方案很少。
- We can backtrack to one of the previous states and explore other directions
- We can skip few states and make a jump in new directions
- We can explore several directions to figure out the correct path
8. Conclusion
8.结语
Even though hill climbing technique is much better than exhaustive search, it’s still not optimal in large problem spaces.
尽管爬坡技术比穷举搜索好得多，但在大的问题空间中，它仍然不是最优的。
We can always encode global information into heuristic functions to make smarter decisions, but then computational complexity will be much higher than it was earlier.
我们总是可以将全局信息编码到启发式函数中，以做出更聪明的决定，但这样一来，计算的复杂性就会比之前高很多。
Hill climbing algorithm can be very beneficial when clubbed with other techniques. As always, the complete code for all examples can be found over on GitHub.
当与其他技术一起使用时，爬坡算法会非常有益。一如既往，所有例子的完整代码都可以在GitHub上找到。