3. Методы решения задач оптимального планирования

Известные методы решения задач оптимального планирования можно разделить на методы направленного поиска (детерминированные) и методы случайного поиска.

Общей идеей детерминированных методов является последовательное улучшение решения задачи. Вначале выбирается некоторое заведомо не оптимальное решение. Это решение по определенному алгоритму подвергается анализу. Анализ показывает возможности улучшения решения и позволяет перейти в области допустимых решений в направлении приближения к оптимальному решению. Каждое новое решение выбирается на основе анализа и оценки предыдущего. Этот процесс продолжается до тех пор, пока анализ не покажет, что дальнейшее улучшение решения невозможно. К детерминированным методам относятся методы сканирования, Гаусса-Зейделя [27]. Наиболее распространенными в настоящее время являются направленные методы, основанные на известных в математике градиентных методах определения экстремумов функций.

Метод градиента. Поиск оптимального решения ведется в несколько циклов. На цикле из точки делается шаг величины в направлении градиента (при поиске максимума функции цели) или в обратном ему направлении (при поиске минимума функции цели). Если направление вектора составляет острый угол

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

Развитием метода градиента является метод наискорейшего спуска (подъема). Этот метод отличается от градиентного тем, что направление движения не определяется заново после каждого шага. По найденному однажды направлению движение производится до тех пор, пока не будет найдена точка экстремума на прямой, совпадающей с выбранным направлением. В полученной точке снова ищется направление градиента и т. д.

Рис. 36.

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

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

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

Каждый из направленных методов имеет свои недостатки и преимущества. В процессе поиска оптимального

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

Впервые идея случайного поиска была высказана У. Эшби в работе [51]. Как и детерминированные, случайные методы можно разделить на методы локального и нелокального поиска. К локальным методам относится поиск «с возвратом» [27]. Среди нелокальных методов случайного поиска назовем методы поиска «с наказанием» и «с обучением» [27].

Метод поиска «с обучением» состоит в следующем: из точки делается ряд независимых пробных шагов определецной величины. После анализа результатов делается рабочий шаг в направлении того из пробных шагов, который привел к наибольшему увеличению функции цели (при поиске максимума). Здесь обучение состоит в изучении окрестности точки Такое обучение называется локальным. Локальное обучение является неэффективным, так как обнаружение оптимального решения зависит от случая.

Нелокальные обучающиеся алгоритмы могут основываться на разных способах обучения. Одним из таких способов является изменение вероятностных характеристик поиска.

Пусть поиск ведется таким образом, что переход из точки в точку осуществляется по правилу

где величина выдается датчиком случайных чисел и может быть или —1. Если вероятность выбора +l или —1 для всех датчиков равна то вектор

можно считать с достаточной для практики точностью равномерно распределенным во всех направлениях пространства переменных.

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

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

В итоге укажем на преимущества, которые имеют методы случайного поиска перед детерминированными методами.

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