Визуальный язык ДРАКОН

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

Восхождение к вершине можно применять, когда:

1. Состояние имеет вид набора из нескольких параметров.
2. Необходимо найти такое состояние, в котором целевая функция достигает максимума (или минимума).

Поиск начинается из случайной точки.

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

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

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

Алгоритм может работать неэффективно или даже не найти решение для некоторых пространств поиска. Например, для тех, которые имеют несколько локальных максимумов (несколько холмов). Другая опасность – плато, а также гребни, которые не параллельны одной из координатных осей.

Для борьбы с этим применяют разные дополнительные средства, такие как несколько перезапусков алгоритма.

ДРАКОН-схема поиска восхождением к вершине:

Скачать исходник в формате DRAKON Editor: hill-climbing-ru.drn

ДРАКОН-схема поиска восхождением к вершине на гибридном языке ДРАКОН-Lua:

Скачать исходник в формате DRAKON Editor: hill-climbing.drn Из этого файла можно сгенерировать работающий скрипт на Lua.

Степан Митькин