Метод сканирования

ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ

Методы решения нелинейных задач оптимизации.

Существует достаточно большое количество численных ме­тодов оптимизации. Они классифицируются следующим образом:

1. По размерности решаемой задачи: одномерные и многомерные.

2. По способу формирования шага многомерные методы делятся на следующие виды:

2.1. Градиентные.

2.2. Безградиентные: с поочередным изменением переменных и с одновременным изменением переменных.

2.3. Случайного поиска: с чисто случайной стратегией и со смешанной стратегией.

3. По наличию ограничений.

3.1. Без ограничений (безусловные).

3.2. С ограничениями (условные):

• с ограничениями типа равенств;

• с ограничениями типа неравенств;

• смешанные.

Методы одномерной оптимизации являются базой для не­которых "многомерных" методов. В многомерной градиентной оптимизации строится улучшающая последовательность в зависимости от скорости изменения критерия по различным направ­лениям. При этом под улучшающей последовательностью пони­мается такая последовательность х₀, x_1,..., х_i,., в каждой точке которой значение критерия оптимальности лучше, чем в преды­дущей. В безградиентных методах величина и направление шага к оптимуму при построении улучшающей последовательности формируется однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента). Случайные методы используются в задачах высокой размерности. Многомерная условная оптимизация учитывает ак­тивные ограничения, выраженные в виде равенств и неравенств. В каждом из рассмотренных направлений имеется большое число методов, обладающих своими достоинствами и недостатками, ко­торые зависят прежде всего от свойств тех функций, экстремум которых ищется. Одним из сравнительных показателей качества метода является количество значений функции, которое нужно вычислить для решения задачи с заданной погрешностью. Чем это число меньше, тем при прочих равных условиях эффективнее метод.

Метод заключается в последовательном переборе всех значений а £ х £ b с шагом e (погрешность решения) с вычислением крите­рия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи х*.

Достоинство метода в том, что можно найти глобальный мак­симум критерия, если R(x) — многоэкстремальная функция. К недостаткам данного метода относится значительное число пов­торных вычислений R(x), что в случае сложной функции R(x) требует существенных затрат времени.

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

.

На первом этапе сканирование осуществляют с крупным шагом, затем отрезок, внутри которого получено наибольшее значение - R(x), разбивается на более мелкие отрезки, ищется новый отрезок, внутри которого находится уточненное значение максимума. Он (новый отрезок) опять делится на более мелкие и т.д., до тех пор, пока величина отрезка, содержащего максимальное значение R(x), не будет меньше заданной погрешности. Главный недостаток этого вари­анта метода — возможность пропуска "острого" глобального максимума R(x).

Дата добавления: 2014-01-13