1.4.1.2 Поиск по образцу
Поиск по образцу [5,6] заключается в реализации единственного шага из полученной базовой точки вдоль прямой, соединяющей эту точку с предыдущей базовой точкой. Новая точка образца определяется в соответствии с формулой
Xp(k+1)=X(k)+(X(k)-X(k-1)). (1.9)
Как только движение по образцу не приводит к уменьшению целевой функции, точка Xp(k+1)фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением целевой функции, чем в точке X(k), то она рассматривается как новая базовая точка X(k+1). С другой стороны, если исследующий поиск неудачен, необходимо вернуться в точку X(k) и провести исследующий поиск с целью выявления нового направления минимизации. В конечном счете возникает ситуация, когда такой поиск не приводит к успеху. В этом случае требуется уменьшить величину шага путем введения некоторого множителя и возобновить исследующий поиск. Поиск завершается, когда величина шага становится достаточно малой. Последовательность точек, получаемую в процессе реализации метода, можно записать в следующем виде:
X(k) - текущая базовая точка,
X(k-1)- предыдущая базовая точка,
Xp(k+1)- точка, построенная при движении по образцу,
X(k+1)- следующая (новая) базовая точка.
Приведенная последовательность характеризует логическую структуру поиска по методу Хука-Дживса.
1.4.1.3Описание алгоритма метода
Шаг 1. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной xj, j=1,2,...,n.
Шаг 2. Вычислить f(x) в базисной точке b1 с целью получения сведений о локальном поведении функции f(x). Функция f(x) в базисной точке b1 находится следующим образом:
Вычисляется значение функции f(b) в базисной точке b1.
Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f(b1+h1*e1), где e1-единичный вектор в направлении оси х1.
Если это приводит к уменьшению значения функции, то d1 заменяется на b1+h1*e1. В противном случае вычисляется значение функции f(b1-h1*e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1*e1.
Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т.е. находится значение функции f(b1+ h2*e2) и т.д. Когда будут рассмотрены все n-переменныx, мы будем иметь новую базисную точку b2.
Если b2=b1, т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага.
Если b2 b1, то производится поиск по образцу.
Шаг 3. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:
Разумно двигаться из базисной точки b2 в направлении b2-b1, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца
P1=b1+2*(b2-b1). (1.10)
В общем случае
Pi=bi+2*(b(i+1)-bi). (1.11)
Затем исследование следует продолжать вокруг точки P1(Pi).
Если наименьшее значение на шаге B,2 меньше значения в базисной точке b2(в общем случае b(i+1)), то получают новую базисную точку b3 (b(i+2)), после чего следует повторить шаг B,1 . В противном случае не производить поиск по образцу из точки b2(b(i+1)), а продолжить исследования в точке b2(b(i+1)).
Шаг 4. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.
1.4.2 Метод комплексов
Алгоритм [7]:
Заданы границы значений всех переменных xiL, xiU, i=1,2,..., N (размерность задачи), допустимая точка xo, параметр отображения a (рекомендуется a =1,3) и параметры окончания вычислений ? и d .
Шаг 1. Построение начального комплекса, состоящего из P допустимых точек (рекомендуется P=2N). Для каждой точки p = 1, 2,...,P-1
случайным образом определить координаты xp;
если xp - недопустимая точка, то найти центр тяжести xцт уже найденных точек и положить xp = xp + (xцт - xp); повторять процедуру до тех пор, пока xp не станет допустимой;
если xp - допустимая точка, повторять до тех пор, пока p=P;
вычислить W(xp) для p=0,1,...,P-1.
Шаг 2. Отражение комплекса:
выбрать точку xR, для которой W(xR) = max W(xp) = Wmax (решается задача минимизации);
найти центр тяжести xцт и новую точку xm = xцт + a (xцт - xR);
если xm - допустимая точка и W(xm)< Wmax, уменьшить в два раза расстояние между xm и центром тяжести xцт, продолжать поиск, пока W(xm)<Wmax;
если xm - допустимая точка и W(xm)<Wmax, то перейти к шагу 4;
если xm - недопустимая точка, то перейти к шагу 3.
Шаг 3. Корректировка для обеспечения допустимости:
если xim<xiL(нижняя граница допускаемой области), то положить xim = xiL;
если xim>xiU(верхняя граница допускаемой области), то положить xim = xiU;
если xm - недопустимая точка, то уменьшить в два раза расстояние до центра тяжести; продолжать до тех пор, пока xm не станет допустимой точкой.
Шаг 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, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
