Въведение в алгоритъма за катерене на хълм

alpidelmareoutdoor

Алгоритъмът за изкачване на хълм е локален алгоритъм за търсене, който се движи непрекъснато нагоре (увеличава се), докато се постигне най-доброто решение. Този алгоритъм приключва, когато е достигнат пикът.

Този алгоритъм има възел, който се състои от две части: състояние и стойност. Започва с неоптимално състояние (основата на хълма) и надгражда това състояние, докато се изпълни определена предпоставка. Евристичната функция се използва като основа за това предпоставка. Процесът на непрекъснато подобряване на текущото състояние на итерация може да се нарече катерене. Това обяснява защо алгоритъмът се нарича алгоритъм за изкачване на хълм.

Целта на алгоритъма за изкачване на хълм е да постигне оптимално състояние, което е надграждане на съществуващото състояние. Когато текущото състояние се подобри, алгоритъмът ще извърши допълнителни постепенни промени в подобреното състояние. Този процес ще продължи, докато се постигне пиково решение. Пиковото състояние не може да претърпи допълнителни подобрения.

Анализ на диаграмата състояние-пространство

Диаграмата на пространството на състоянията осигурява графично представяне на състоянията и функцията за оптимизация. Ако целевата функция е оста y, ние се стремим да установим локалния максимум и глобалния максимум.

Ако функцията на разходите представлява тази ос, ние се стремим да установим местния минимум и глобалния минимум. Повече информация за местния минимум, местния максимум, глобалния минимум и глобалния максимум можете да намерите тук.

Следващата диаграма показва проста диаграма пространство-състояние. Целевата функция е показана на оста y, докато пространството на състоянията представлява оста x.

Местен максимум

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

Този проблем може да бъде решен с помощта на инерция. Тази техника добавя определена пропорция (m) от първоначалното тегло към текущата. m е стойност между 0 и 1. Импулсът дава възможност на алгоритъма за изкачване на хълм да предприеме огромни стъпки, които ще го накарат да премине от местния максимум.

Плато

В този регион стойностите, постигнати от съседните държави, са еднакви. Това затруднява алгоритъма при избора на най-добрата посока.

Това предизвикателство може да бъде преодоляно чрез огромен скок, който ще ви отведе до пространство без плато.