5.2. Градиентные методы

Градиентные методы часто используются при решении конкретных задач: суть состоит в том, что для скорейшего достижения вершины надо продвигаться по самому крутому склону. Если мы на автомобиле хотим пересечь город с севера на юг, мы стараемся сохранить это направление как можно дольше, а когда условия движения заставляют нас отклониться от него, мы стремимся сделать это отклонение как можно меньшим. Стратегия градиента, или «подъема в гору», заключается в попытке достичь главного оптимума через последовательность

локальных оптимумов (рис. 5.2). Как показывает опыт, эта стратегия вполне удачна, хотя, когда поисковое пространство не является выпуклым, она становится малоэффективной.

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

Рис. 5 2. Метод градиента.

К градиентным методам относятся симплекс-метод в линейном программировании (разд. 5.3), -процедура (разд. 5.4), методы последовательных приближений в численном анализе, минимаксные методы и альфа-бета процедура (разд. 6.2), динамическое программирование (разд. 5.9), метод ветвей и границ, метод разделения и оценки (разд. 5.4).

Рис. 5.3. Задача о стрелках.

Пример I. Пусть дано пять стрелок, находящихся в положении нужно перевести их в положение причем разрешены только такие действия, при которых одновременно переворачиваются две соседние стрелки (рис. 5.3).

Пять разрешенных действий и — повороты стрелок (1,2), (2,3), (3,4), (4,5), (5,6). Поскольку для любого действия а из этого множества означает возвращение к исходному положению, достаточно рассматривать лишь последовательности элементарных действий. Если в качестве оценочной

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

Рис. 5 4. Примеры неудачного применения метода градиента

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

Метод градиента не гарантирует получения решения (за исключением случая, когда пространство отображения является выпуклым), так как могут возникнуть ловушки трех типов: второстепенные вершины, гребни и плато (рис. 5.4).

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