Оптимизирующий итеративный поиск

Во многих задачах поиск целевого состояния (состояний) в пространстве состояний ставится как задача нахождения такого состояния (состояний), которое в определенном смысле наилучшее (оптимальное). При этом не имеет особого значения цена пути нахождения цели, если эта цель может быть достигнута за приемлемые затраты времени и памяти. Идея оптимизирующего итеративного поиска станет понятной, если полагать, что состояния – это точки на поверхности некоторого горного ландшафта. Чем выше точка находится над уровнем моря, тем лучше (оптимальнее) состояние, которое она представляет. Точки, соответствующие пикам, являются оптимальными точками. Задачей оптимизирующего итеративного поиска является такой порядок просмотра точек, или иначе такое движение по поверхности ландшафта, при котором в конце концов достигаются (находятся) оптимальные точки. Имеется большое разнообразие процедур оптимизирующего итеративного поиска. Одной из таких процедур является градиентный поиск. Рассмотрим суть этой процедуры.

Идея градиентного поиска чрезвычайно проста – двигаться в направлении подъема вверх, начиная с некоторого начального состояния. Дерево поиска не хранится, а сохраняется только последнее найденное состояние b и оценка его качества L(b). Если попадаются несколько состояний с одинаковой оценкой качества, то, как правило, выбирается одно из них. Градиентный поиск в чистом виде обладает тремя известными недостатками.

Если вершин несколько, то поднявшись на одну из них, процесс поиска остановится, полагая, что цель достигнута, хотя достигнутая вершина является всего лишь локальным оптимумом и далека от наилучшей.

Если ландшафт имеет плато, то процесс поиска по нему становится случайным.

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

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

Ясно, что если провести достаточное число подобных итераций, то оптимальное решение, в конце концов, будет найдено. Успех градиентного поиска сильно зависит от вида пространства состояний. Если число локальных минимумов невелико, то оптимальное решение будет найдено сравнительно быстро. Процедуры градиентного поиска могут отличаться способом выбора очередной вершины в процессе подъема на вершину, выбором очередной вершины для новой итерации и т.д.