47875 (Оптимизация. Методы многомерного поиска), страница 2

Один из возможных примеров алгоритмов.

f (x) - > min, x Rⁿ

x⁰-начальное приближение (массив [1: n])

Будем считать, что нам известна функция

minf ( ()), которая вычисляется _min: (_min) =min ()

r: =f (x⁰); r1: =r+2*; x: =x⁰;

Пока abs (r-r1) >=

нц

r1: =r;

x1: =x;

Для i от 1 до n

нц

l [i]: = f (x1) / x [i] ;

x [i]: =x [i] +*l [i] ;

кц

(): =f (x);

_min: = minf ( ());

x: =x1;

Для i от 1 до n

x [i]: =x [i] +_min*l [i] ;

кц

r: =f (x);

кц

6.1 Ступенчатый наискорейший подъем

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

Наискорейший подъем с использованием одномерного поиска

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

x =x +Sv ,

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

Задача 1

Найти прямую наилучшим образом аппроксимирующую совокупность экспериментальных точек. Уравнение прямой y=m*x+b. Суммарная ошибка в случае точек определяется выражением SUM=

Необходимо найти минимум, SUM, оптимальные значения m,b. Экспериментальные точки заданы.

Задача 2

Емкость бака для жидких отходов должна составитьV л. Изготовляется бак из железобетона толщиной t см. Определить геометрические параметры бака, при которых на его изготовление пойдет минимальное количество бетона.

Задача 3

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

Задача 4

Изготовитель контейнеров проектирует открытый контейнер из листового материала. Заготовка вырезается из листа, сгибается по пунктирным линиям и сваривается четырьмя швами. Каковы должны быть размеры контейнера небольшого объема, если площадь его дна не должна превышать 1 м² и ни один из линейных размеров a,b,c не должны быть больше другого более чем в 3 раза?

Задача 5

Сравнительно простая с математической точки зрения целевая функция Розенброка y=100 (x₂-x ) ²+ (1+x₁) ² описывает поверхность с впадиной.

Минимальное значение целевой функции соответствует точке с координатами M (x,y). Если взять начальную точку во втором квадранте, то не всегда удается обеспечить сходимость. Выбрав исходную точку попытаться решить эту задачу оптимизации:

a) методом покоординатного спуска;

b) градиентным методом.

Литература

1. Шуп Т. “Решение инженерных задач на ЭВМ", 1982

2. Брукс С.Ш." О случайных методах поиска максимума ”, 1958