Методы поиска

Для поиска максимума или минимума целевой функции могут использоваться различные методы. Эти методы могут быть сгруппированы в три больших класса (рис. 9.3). Методы первого класса основываются на вычислениях, методы второго класса осуществляют направленный случайный поиск, а методы третьего класса являются перечислительными [95]. На рис. 9.3 показаны только те методы поиска, которые эффективны при решении задач оптимизации по нескольким переменным. Мы не стали указывать простейшие методы поиска, такие как метод Фибоначчи и метод золотого сечения, потому что они применяются главным образом для одномерных задач.

Методы поиска

Вычислительные алгоритмы могут быть разделены на две группы. Методы первой группы получают оптимальное решение задачи в явном виде, тогда как методы второй группы подходят к нему косвенно, через решение системы нелинейных уравнений, которые образуются при приравнивании нулю градиента целевой функции. Прямые методы ищут решение, выбирая значения из пространства поиска и оценивая градиент в каждой новой точке. Эта процедура определяет направление поиска. Идея та же, что при подъеме на холм: нужно найти наилучшую точку, поднимаясь по самому крутому склону. Прямые методы делятся на две категории (рис. 9.3). Методы первой категории используют саму целевую функцию и ее первые производные

Методы поиска

Здесь F — целевая функция, а вектор переменных оптимизации X составлен из компонент xi. В качестве примеров методов из этой категории можно назвать метод скорейшего спуска и метод сопряженных градиентов. Методы из второй категории используют матрицу Гессе, составленную из частных вторых производных

Методы поиска

помимо первых производных и значений самой функции. Ко второй категории относится, в частности, метод Ньютона. Ниже мы обсудим идеи, на которых основаны прямые методы, применимые, вообще говоря, только к ограниченному набору «хороших» задач. Подробные сведения о методах и решении задач оптимизации приводятся в учебниках [62, 119, 6, 131].

Прямые методы, основанные на градиентах, во многих случаях оказываются неприменимы, поскольку они используют сведения о локальном поведении функции для перемещения в направлении скорейшего спуска. Направление скорейшего спуска противоположно локальному направлению градиента, поэтому алгоритмы этого типа ведут себя плохо, если функция имеет трудносопоставимые масштабы по разным переменным или для нее неудачно заданы ограниче- ния. Двумерная целевая функция, для которой алгоритм скорейшего спуска начинает осциллировать и сходится достаточно медленно, представлена на рис. 9.4. На рисунке показаны контуры постоянных значений целевой функции в двумерном пространстве переменных оптимизации. Градиент перпендикулярен такому контуру в любой его точке. В результате направление скорейшего спуска на каждой итерации оказывается почти перпендикулярным направлению на минимум.

Методы поиска

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

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

Методы поиска

Смотрите также