1. Обзор
В этом уроке мы покажем алгоритм Hill-Climbing и его реализацию. Мы также рассмотрим его преимущества и недостатки. Прежде чем перейти непосредственно к этому, давайте кратко обсудим алгоритмы генерации и тестирования.
2. Алгоритм создания и тестирования
Это очень простая техника, которая позволяет нам алгоритмизировать поиск решений:
- Определить текущее состояние как начальное состояние
- Примените любую возможную операцию к текущему состоянию и сгенерируйте возможное решение
- Сравните вновь созданное решение с целевым состоянием
- Если цель достигнута или новые состояния не могут быть созданы, выйдите. В противном случае вернитесь к шагу 2
Очень хорошо работает с простыми задачами. Поскольку это исчерпывающий поиск, его невозможно рассматривать при работе с большими проблемными пространствами. Он также известен как алгоритм Британского музея (попытка найти артефакт в Британском музее, исследуя его случайным образом).
Это также основная идея Hill-Climbing Attack в мире биометрии. Этот подход может быть использован для генерации синтетических биометрических данных.
3. Введение в простой алгоритм восхождения на холм
В технике альпинизма, начиная с подножия холма, мы идем вверх, пока не достигнем вершины холма. Другими словами, мы начинаем с начального состояния и продолжаем улучшать решение до тех пор, пока оно не станет оптимальным.
Это вариант алгоритма генерации и тестирования, который отбрасывает все состояния, которые не выглядят многообещающими или вряд ли приведут нас к целевому состоянию. Для принятия таких решений он использует эвристику (функцию оценки), которая показывает, насколько близко текущее состояние к целевому состоянию.
Проще говоря, Hill-Climbing = генерация-и-тестирование + эвристика.
Давайте посмотрим на алгоритм восхождения на простой холм:
Определите текущее состояние как начальное состояние
Цикл до тех пор, пока не будет достигнуто целевое состояние или к текущему состоянию нельзя будет применить больше операторов:
Применить операцию к текущему состоянию и получить новое состояние
Сравните новое состояние с целью
Выйти , если целевое состояние достигнуто
Оцените новое состояние с помощью эвристической функции и сравните его с текущим состоянием.
Если новое состояние ближе к цели по сравнению с текущим состоянием, обновите текущее состояние.
Как мы видим, он достигает целевого состояния с итеративными улучшениями. В алгоритме Hill-Climbing поиск цели эквивалентен достижению вершины холма.
4. Пример
Алгоритм восхождения на холм можно отнести к категории информированного поиска. Таким образом, мы можем реализовать любой поиск на основе узлов или задачи, такие как проблема n-королев, используя его. Чтобы легко понять концепцию, мы возьмем очень простой пример.
Давайте посмотрим на изображение ниже:
Ключевым моментом при решении любой задачи о восхождении на холм является выбор подходящей эвристической функции .
Определим такую функцию h:
h(x) = +1 для всех блоков опорной конструкции, если блок расположен правильно, в противном случае -1 для всех блоков опорной конструкции.
Здесь мы будем называть любой блок правильно расположенным, если он имеет ту же структуру поддержки, что и целевое состояние. В соответствии с описанной ранее процедурой восхождения на холм давайте рассмотрим все итерации и их эвристику для достижения целевого состояния:
5. Реализация
Теперь давайте реализуем тот же пример, используя алгоритм Hill-Climbing.
Прежде всего, нам нужен класс State , в котором будет храниться список стеков, представляющих позиции блоков в каждом состоянии. Он также будет хранить эвристики для этого конкретного состояния:
public class State {
private List<Stack<String>> state;
private int heuristics;
// copy constructor, setters, and getters
}
Нам также нужен метод, который будет вычислять эвристическое значение состояния.
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;
}
Кроме того, нам нужно определить операторные методы, которые дадут нам новое состояние. Для нашего примера мы определим два из этих методов:
- Извлеките блок из стека и поместите его в новый стек
- Извлеките блок из стека и поместите его в один из других стеков.
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;
}
Теперь, когда у нас есть вспомогательные методы, давайте напишем метод для реализации техники восхождения на холм.
Здесь мы продолжаем вычислять новые состояния, которые ближе к цели, чем их предшественники. Мы продолжаем добавлять их на наш путь, пока не достигнем цели.
Если мы не находим никаких новых состояний, алгоритм завершается с сообщением об ошибке:
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;
}
В дополнение к этому нам также нужен метод 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 (поиск градиента) является вариантом алгоритма Hill Climbing. Мы можем реализовать это с небольшими изменениями в нашем простом алгоритме. В этом алгоритме мы рассматриваем все возможные состояния из текущего состояния, а затем выбираем лучшее в качестве преемника , в отличие от простого метода восхождения на холм.
Другими словами, в случае метода восхождения на холм мы выбрали в качестве преемника любое состояние, которое было ближе к цели, чем текущее состояние, тогда как в алгоритме восхождения на вершину с самым крутым подъемом мы выбираем наилучшего преемника из всех возможных преемников, а затем обновляем текущее состояние.
7. Недостатки
Hill Climbing — недальновидный метод, поскольку он оценивает только ближайшие возможности. Таким образом, он может оказаться в нескольких ситуациях, из которых он не сможет выбрать какие-либо дальнейшие состояния. Давайте посмотрим на эти состояния и некоторые решения для них:
- Локальный максимум: это состояние лучше всех соседей, но существует лучшее состояние, которое далеко от текущего состояния; если локальный максимум находится в пределах видимости решения, он известен как «предгорье».
- Плато: в этом состоянии все соседние состояния имеют одинаковые эвристические значения, поэтому неясно выбрать следующее состояние путем локальных сравнений.
- Хребет: это область, которая выше окружающих штатов, но до нее нельзя добраться за один ход; например, у нас есть четыре возможных направления для исследования (N, E, W, S), и существует область в северо-восточном направлении.
Есть несколько решений для преодоления этих ситуаций:
- Мы можем вернуться к одному из предыдущих состояний и исследовать другие направления.
- Мы можем пропустить несколько состояний и сделать прыжок в новых направлениях .
- Мы можем исследовать несколько направлений , чтобы определить правильный путь.
8. Заключение
Несмотря на то, что метод восхождения на холм намного лучше, чем полный поиск, он все же не оптимален в больших проблемных областях.
Мы всегда можем закодировать глобальную информацию в эвристические функции для принятия более разумных решений, но тогда вычислительная сложность будет намного выше, чем была раньше.
Алгоритм восхождения на холм может быть очень полезным, если его сочетать с другими методами. Как всегда, полный код всех примеров можно найти на GitHub .