Hill Climbing - это эвристический поиск, используемый для задач математической оптимизации в области искусственного интеллекта.
Учитывая большой набор входных данных и хорошую эвристическую функцию, он пытается найти достаточно хорошее решение проблемы. Это решение может не быть глобальным оптимальным максимумом.

· В приведенном выше определении задачи математической оптимизации подразумевают, что восхождение на холм решает проблемы, в которых нам нужно максимизировать или минимизировать заданную реальную функцию, выбирая значения из заданных входных данных. Пример - Задача коммивояжера, где нам нужно минимизировать расстояние, пройденное продавцом.

· «Эвристический поиск» означает, что этот алгоритм поиска может не найти оптимального решения проблемы. Однако это даст хорошее решение в разумное время.

· эвристическая функция - это функция, которая ранжирует все возможные альтернативы на любом шаге ветвления в алгоритме поиска на основе доступной информации. Это помогает алгоритму выбрать лучший маршрут из возможных.

Особенности восхождения на холмы

1. Вариант алгоритма генерации и тестирования: это вариант алгоритма генерации и тестирования. Алгоритм генерации и тестирования следующий:

1. Сгенерируйте возможные решения.
2. Проверьте, является ли это ожидаемым решением.
3. Если решение найдено, перейдите к шагу 1 .

Следовательно, мы называем восхождение на холм как вариант алгоритма генерации и тестирования, поскольку он учитывает обратную связь от процедуры тестирования. Затем эта обратная связь используется генератором при принятии решения о следующем шаге в пространстве поиска.

2. Использует жадный подход: в любой точке пространства состояний поиск движется только в том направлении, которое оптимизирует стоимость функции в надежде найти оптимальное решение в конце.

Типы восхождений

1. Простое восхождение на гору:

Простое восхождение на холм - это самый простой способ реализовать алгоритм восхождения на холм. Он оценивает только состояние соседнего узла за раз и выбирает первый, который оптимизирует текущую стоимость, и устанавливает его как текущее состояние. Он проверяет только одно состояние-преемник, и если обнаруживает, что состояние лучше, чем текущее, перемещается, иначе будет в том же состоянии. Этот алгоритм имеет следующие особенности:

  • Меньше времени
  • Менее оптимальное решение, и решение не гарантируется

Алгоритм простого восхождения на гору:

  • Шаг 1: Оцените начальное состояние, если это целевое состояние, вернуть успех и Стоп.
  • Шаг 2: Цикл до тех пор, пока не будет найдено решение или не останется нового оператора, который можно было бы применить.
  • Шаг 3. Выберите и примените оператор к текущему состоянию.
  • Шаг 4. Проверьте новое состояние:

а. Если это состояние цели, вернуть успех и выйти.

б. В противном случае, если оно лучше, чем текущее состояние, тогда назначьте новое состояние как текущее состояние.

c. В противном случае, если не лучше, чем текущее состояние, вернитесь к шагу 2.

  • Шаг 5. Выйдите.

2. Восхождение на самый крутой подъем:

Алгоритм наискорейшего подъема - это разновидность простого алгоритма подъема на холм. Этот алгоритм проверяет все соседние узлы текущего состояния и выбирает один соседний узел, который ближе всего к целевому состоянию. Этот алгоритм требует больше времени, так как ищет несколько соседей.

Алгоритм восхождения на холм по самому крутому подъему:

  • Шаг 1: Оцените начальное состояние, если это целевое состояние, вернуть успех и остановить, иначе сделайте текущее состояние начальным.
  • Шаг 2: Повторяйте цикл до тех пор, пока не будет найдено решение или пока текущее состояние не изменится.

а. Пусть SUCC будет таким состоянием, что любой преемник текущего состояния будет лучше, чем он.

б. Для каждого оператора, относящегося к текущему состоянию:

а. Примените новый оператор и сгенерируйте новое состояние.

б. Оцените новое состояние.

c. Если это целевое состояние, верните его и выйдите, иначе сравните его с SUCC.

d. Если он лучше, чем SUCC, установите новое состояние как SUCC.

е. Если SUCC лучше, чем текущее состояние, установите текущее состояние на SUCC.

  • Шаг 5. Выйдите.

3. Стохастический подъем на холм:

Стохастик при восхождении на холм не исследует всех своих соседей перед движением. Скорее, этот алгоритм поиска случайным образом выбирает один соседний узел и решает, выбрать ли его в качестве текущего состояния или исследовать другое состояние.

Диаграмма пространства состояний для восхождения на холм

Диаграмма пространства состояний - это графическое представление набора состояний, которых может достичь наш алгоритм поиска, в зависимости от значения нашей целевой функции (функции, которую мы хотим максимизировать).
Ось X: обозначает пространство состояний, то есть состояний или конфигурации, которых может достичь наш алгоритм.
Ось Y: обозначает значения целевой функции, соответствующие определенному состоянию.
Лучшим решением будет это состояние. пространство, в котором целевая функция имеет максимальное значение (глобальный максимум).

Различные регионы на диаграмме пространства состояний

1. Локальный максимум: это состояние, которое лучше, чем его соседнее состояние, однако существует состояние, которое лучше, чем оно (глобальный максимум). Это состояние лучше, потому что здесь значение целевой функции выше, чем у ее соседей.

2. Глобальный максимум: это наилучшее возможное состояние на диаграмме пространства состояний. Это потому, что в этом состоянии целевая функция имеет наивысшее значение.

3. Плато / плоский локальный максимум: это плоская область пространства состояний, в которой соседние состояния имеют одинаковое значение.

4. Хребет. Это регион, который выше, чем у соседа, но сам по себе имеет уклон. Это особый вид локального максимума.

5. Текущее состояние: область диаграммы пространства состояний, в которой мы находимся в данный момент во время поиска.

6. Плечо. Это плато с крутым подъемом.

Проблемы в разных регионах при восхождении на холмы

Восхождение на холм не может достичь оптимального / лучшего состояния (глобального максимума), если оно входит в любой из следующих регионов:

1. Локальный максимум: при локальном максимуме все соседние состояния имеют значения, которые хуже текущего состояния. Поскольку при восхождении на гору используется жадный подход, он не перейдет в худшее состояние и не прекратит свое существование. Процесс завершится, даже если существует лучшее решение.
Чтобы преодолеть проблему локального максимума: используйте технику обратного отслеживания. Ведите список посещенных состояний. Если поиск достигает нежелательного состояния, он может вернуться к предыдущей конфигурации и исследовать новый путь.

2. Плато: на плато все соседи имеют одинаковое значение. Следовательно, выбрать лучшее направление невозможно.

Чтобы преодолеть плато: сделайте большой прыжок. Случайным образом выберите состояние, удаленное от текущего состояния. Скорее всего, мы приземлимся в регионе, отличном от плато.

3. Гребень: любая точка гребня может выглядеть как пик, потому что движение во всех возможных направлениях идет вниз. Следовательно, алгоритм останавливается, когда достигает этого состояния.
Чтобы преодолеть гребень: В этом виде препятствия используйте два или более правил перед тестированием. Подразумевает движение сразу в нескольких направлениях.

Имитация отжига:

Алгоритм подъема на холм, который никогда не движется к более низкому значению, гарантированно будет неполным, потому что он может застрять на локальном максимуме. И если алгоритм применяет случайное блуждание, перемещая преемника, он может завершиться, но неэффективно. Имитация отжига - это алгоритм, который обеспечивает как эффективность, так и полноту.

С механической точки зрения отжиг - это процесс закалки металла или стекла до высокой температуры с последующим постепенным охлаждением, что позволяет металлу достичь низкоэнергетического кристаллического состояния. Тот же процесс используется при моделировании отжига, в котором алгоритм выбирает случайный ход вместо выбора лучшего хода. Если случайный ход улучшает состояние, то он следует по тому же пути. В противном случае алгоритм следует по пути, вероятность которого меньше 1, или он движется под уклон и выбирает другой путь.

Ссылки:

Https://www.javatpoint.com/hill-climbing-algorithm-in-ai

Https://www.geeksforgeeks.org/introduction-hill-climbing-artificial-intelligence/'/