Введение в скалолазание | Искусственный интеллект

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

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

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

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

1. Generate possible solutions. 
2. Test to see if this is the expected solution. 
3. If the solution has been found quit else go to step 1.

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

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

Виды восхождения на холм

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

Step 1 : Evaluate the initial state. If it is a goal state then stop and return success. Otherwise, make initial state as current state. 

Step 2 : Loop until the solution state is found or there are no new operators present which can be applied to the current state. 

a) Select a state that has not been yet applied to the current state and apply it to produce a new state. 

b) Perform these to evaluate new state 
    i. If the current state is a goal state, then stop and return success. 
    ii. If it is better than the current state, then make it current state and proceed further. 
    iii. If it is not better than the current state, then continue in the loop until a solution is found. 

Step 3 : Exit. 
 

2. Восхождение на холм с самым крутым подъемом: сначала проверяются все соседние узлы, а затем выбирается узел, ближайший к состоянию решения на следующий узел. Алгоритм простого восхождения на гору:

Step 1 :  Evaluate the initial state. If it is a goal state then stop and return success. Otherwise, make initial state as current state. 

Step 2 : Repeat these steps until a solution is found or current state does not change 

a) Select a state that has not been yet applied to the current state.

b)  Initialize a new ‘best state’ equal to current state and apply it to produce a new state.

c) Perform these to evaluate new state                                                                                                                      i. If the current state is a goal state, then stop and return success.                                                                       ii. If it is better then best state, then make it best state else continue loop with another new state.

d) Make best state as current state and go to Step 2: b) part.

Step 3 : Exit

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

Шаг 1: Оцените начальное состояние. Если это целевое состояние, остановитесь и верните успех. В противном случае сделайте начальное состояние текущим.

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

а) Выберите состояние, которое еще не было применено к текущему состоянию.

б) Применить функцию-преемник к текущему состоянию и сгенерировать все соседние состояния.

c) Среди сгенерированных соседних состояний, которые лучше текущего состояния, выберите состояние случайным образом (или на основе некоторой функции вероятности).

г) Если выбранное состояние является целевым состоянием, то вернуть успех, иначе сделать его текущим состоянием и повторить шаг 2: б) часть.

Шаг 3: Выйти.
Диаграмма пространства состояний для восхождения на холм

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

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

1. Локальный максимум: это состояние, которое лучше, чем его соседнее состояние, однако существует состояние, которое лучше, чем оно (глобальный максимум). Это состояние лучше, потому что здесь значение целевой функции выше, чем у ее соседей.
   
2. Глобальный максимум: это наилучшее возможное состояние на диаграмме пространства состояний. Это потому, что в этом состоянии целевая функция имеет наивысшее значение.
3. Платея / плоский локальный максимум: это плоская область пространства состояний, где соседние состояния имеют одинаковое значение.
4. Хребет: это регион, который выше, чем его соседи, но сам по себе имеет уклон. Это особый вид локального максимума.
5. Текущее состояние: область диаграммы пространства состояний, в которой мы находимся в данный момент во время поиска.
6. Плечо: это плато с крутым подъемом.

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

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

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

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

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