Шаг 4. Проверка условий окончания вычислений:
положить
и
;
если
и
,
то вычисления прекратить; в противном случае перейти к шагу 2a.
1.4.3 Методы случайного поиска
Наиболее простой процедурой случайного поиска [3,5] является прямая выборочная процедура, заключающаяся в разыгрывании на ЭВМ последовательности точек с координатами
xi = xiL +ri (xiU - xiL), i=1,2,...,N, (1.12)
где ri - случайная величина, равномерно распределенная на интервале [0,1].
После проверки каждой точки на допустимость вычисляются значения целевой функции, которые сравниваются с наилучшим значением, полученным к данному моменту. Если текущая точка дает лучшее значение, то она запоминается, в противном - отбрасывается. Процесс прекращается после заданного числа итераций N или по исчерпанию заданного машинного времени. Для получения 90% доверительного интервала величиной i (xiU - xiL), где 0< <1, для переменной xi совместный случайный поиск требует испытаний. При N=5, i=0,01 число испытаний оценивается в 2,3 1010, что исключает возможность непосредственного использования метода.
Значительного увеличения эффективности процедуры случайного поиска можно достигнуть путем группировки выборок в серии. При этом наилучшая точка в каждой серии используется как начальная точка следующей серии, точки которой уже выбираются из интервала меньшей величины. Данная процедура получила название выборки со сжатием пространства поиска. Рассмотрим более подробно ее алгоритм.
Заданы границы значений всех переменных xiL, xiU, i=1,2,..., N (размерность задачи), начальные допустимая точка xo и интервал поиска D xo = xiU - xiL, количество серий Q, количество точек в серии P и параметр окончания вычислений . Для каждой из серий, начиная с q = 1, необходимо выполнить следующие действия.
Шаг 1. Для i = 1,2,...,N вычислить
xip = xiq-1 +ri D xq-1, (1.13)
где ri - случайная величина, равномерно распределенная на интервале [-0,5;0,5].
Шаг 2.
если xp - недопустимая точка и p < P, то повторить шаг 1;
если xp - допустимая точка, то запомнить xp и W(xp) и
если p < P, то повторить шаг 1;
если p = P, то найти среди всех допустимых точек xp точку с наименьшим значением W(xp) и положить ее равной xq.
Шаг 3. Уменьшить интервал поиска, полагая D∙xiq = i∙D∙xiq-1.
Шаг 4.
Если q > Q, то закончить вычисления.
В противном случае увеличить q=q+1 и продолжить вычисления, начиная с шага 1.
1.4.4 Метод покоординатного спуска
Рисунок 1.1 - Метод покоординатного спуска
Рассмотрим функцию двух переменных. Ее линии уровня представлены на рис. 1.1, а минимум лежит в точке (x1*,x2*). Простейшим методом поиска является метод покоординатного спуска[3,4]. Из точки А произведем поиск минимума вдоль направления оси х1 и, таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси х1. Затем, производя поиск из точки В в направлении оси х2, получаем точку С, производя поиск параллельно оси х2, получаем точку D, и т.д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идею можно применить для функции n переменных.
Теоретически данный метод эффективен в случае единственного минимума функции. Но на практике он оказывается слишком медленным. Поэтому были разработаны более сложные методы, использующие больше информации на основании уже полученных значений функции.
1.5 Градиентные методы
Как следует из названия, эти методы решения нелинейных оптимизационных задач используют понятие градиента функции[3,5,7]. Градиентом функции называется вектор
(1.14)
где - единичные вектора (орты).
Величина этого вектора определяется по выражению
(1.15)
Из (1.14) и (1.15) видно, что функция, градиент которой определяется, должна быть дифференцируемой по всем n переменным.
Физический смысл градиента функции в том, что он показывает направление (1.14) и скорость (1.15) наибольшего изменения функции в рассматриваемой точке. Если в некоторой точке , функция в этой очке не изменяется (не возрастает и не убывает). Эта точка соответствует экстремуму функции.
1.5.1 Градиентный метод с постоянным шагом
Сущность градиентных методов решения нелинейных оптимизационных задач [1,5,7] поясним для случая отыскания абсолютного минимума функции двух переменных , иллюстрируемого рис. 1.2. этот минимум находится в точке с координатами х10 и х20.
Рисунок 1.2 - Иллюстрация градиентного метода с постоянным шагом
В соответствии с граничными условиями (1.3), в большинстве практических оптимизационных задач они принимают только положительные или нулевые значения, областью допустимых значений переменных будет первый квадрант системы координат х1 и х2. в этой области произвольно выберем исходное (нулевое) приближение - точку с координатами х10, х20. значение целевой функции в этой точке составляет Z0. В соответствии с выражением (1.15) вычислим в этой точке величину градиента функции Z.
Выполним шаг единичной длины () в направлении убывание функции Z. В результате выполненного шага получим первое приближение - точки с координатами х11, х21. Значение целевой функции в этой точке составляет Z1.
Далее вычислительная процедура повторяется: последовательно получаем 2-е, 3-е и 4-е приближения - точки с координатами х12, х22; х13, х23 и х14, х24. Значения целевой функции в этих точках соответственно составляют Z2, Z3 и Z4.
Из рис. 1.2 видно, что в результате вычиcлительного процесса последовательно осуществляется "спуск" к минимуму функции Z. Вычислительная процедура заканчивается, когда относительное изменение целевой функции на предыдущем i-м и последующем (i+1)-м шагах оказывается меньше заданной точности вычислений :
(1.16)
Рассмотренная вычислительная процедура носит название градиентного метода с постоянным шагом. В этом методе все шаги выполнялись одинаковой длины . Метод достаточно прост. Основной его недостаток - большая вероятность зацикливания вычислительного процесса в окрестности минимума функции Z. В соответствии с рис. 1.2 вычислительный процесс зациклится между точками с координатами х13, х23 и х14, х24. При этом в качестве искомого решения следует принять одну из этих точек.
Для получения более точного результата необходимо выбрать шаг меньшей длины. При этом объем вычислений (количество шагов) увеличится.
Таким образом, точность и объем вычислений в градиентном методе с постоянным шагом определяются величиной этого шага.
1.5.2 Метод скорейшего спуска
Как было отмечено выше, при увеличении длины шага объем вычислений (количество шагов) уменьшается, однако уменьшается и точность определения минимума целевой функции. При уменьшении длины шага точность увеличивается, однако объем вычислений (количество шагов) возрастает.
Поэтому вопрос о выборе рациональной длины шага в градиентных методах является своего рода оптимизационной задачей. Один из способов определения оптимальной длины шага иллюстрируется на рис. 1.3 и носит название метода скорейшего спуска [1,7].
Рисунок 1.3 - Иллюстрация метода скорейшего спуска (а) и параболическая аппроксимация целевой функции для выбора оптимального шага (б)
В методе наискорейшего спуска желательно использовать рассмотренное свойство направления градиента. Поэтому, если мы находимся в точке хi на некотором шаге процесса оптимизации, то поиск минимума функции осуществляется вдоль направления -. Данный метод является итерационным. На шаге i точка минимума аппроксимируется точкой хi . Следующей аппроксимацией является точка
(1.17)
где λi - значение λ, минимизирующее функцию.
. (1.18)
Значение λi может быть найдено с помощью одного из методов одномерного поиска (например, методом квадратичной интерполяции).
В приложении приведена программа, позволяющая реализовать метод наискорейшего спуска. В ней множитель Лагранжа обозначен через h. Вектор di является единичным.
Для поиска минимума функции
(1.19)
в направлении di из точки xi используется метод квадратичной интерполяции.
В точке , и мы выбираем длину шага λ такой, чтобы шаг "перекрыл " минимум функции φ(λ). Производная
. (1.20)
Данный оператор for(i=0;i<n;i++) g2+=g[i]*d[i]; - вычисляет выражение
. (1.21)
Оператор if (ff[2]>=ff[0] || g2>=0) проверяет условие "перекрытия" минимума, которое выполняется при выполнении либо одного, либо другого условия. Если минимум не попал в отрезок (0,λ), то λ удваивается, и это повторяется столько раз, сколько необходимо для выполнения условия "перекрытия".
Удостоверившись, что отрезок (0,λ) содержит минимум, в качестве третьей точки возьмем точку λ/ 2. Минимальную точку сглаживающего квадратичного полинома находим в соответствии с соотношением
(1.22)
что отражено следующими операторами
l[3]=h*(ff[1]-.75*ff[0]-.25*ff[2]);
l[3]/=2*ff[1]-ff[0]-ff[2];
Оператор for(i=0;i<n;i++)
{ x[i]=y[i]+l[0]*d[i]; y[i]=x[i]; }
производит присваивание xi+1=xi, и если |g(xi+1)| достаточно мало, то процесс заканчивается. В процессе поиска предполагается сходимость к экстремуму, поэтому для эффективности процедуры разумно уменьшить длину шага. При этом деление шага пополам выбрано произвольно.
В методе скорейшего спуска, по сравнению с градиентным методом с постоянным шагом, количество шагов меньше, точность получаемого результата выше, отсутствует зацикливание вычислительного процесса, однако объем вычислений на одном шаге больше.
1.5.3 Метод проектирования градиента
Рассмотренные выше градиентные методы предполагали отыскание абсолютного минимума целевой функции Z. При наличии в математической модели нелинейных ограничений ищется уже не абсолютный, а относительный минимум целевой функции Z [1].
Рассмотрим один из методов отыскания относительного минимума целевой функции, получивший название метода проектирования градиента.
Для упрощения алгоритма допустим, что имеется одно ограничение в виде линейного неравенства
(1.23)
При наличии указанного ограничения минимум целевой функции следует искать в области , расположенной по одну сторону от прямой например выше этой прямой (рис. 1.4).
Начало вычислительной процедуры такое же, как и в предыдущих методах:
в области принимается исходное (нулевое) приближение х10, х20;
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
