Силаева Т.А. - Методы решения задач оптимального проектирования ВС (Методы решения задач оптимального проектирования ВС (Силаева Т.А.)), страница 3

В методе сопряженных градиентов при вычислении направления у учитывается предысторня пояска экстремума: (А) где у~ )= О. Отметим, что при Ь= О (1.12) совпадает с формулой для э в методе наискорейшего спуска. Сходвмость метода сопряженных градиентов по сравнению с методом наискорейшего спуска лучше, однако сложность выполнения действий на каждой яторацнн выше. В обоих рассматриваемых методах в отличие от метода грэдиептного спуска шаг Ь( ) в направлении поиска экстремума выби(/с) раем оптимальным на каждой итерации й, т.е. Ь к сопз(.

Рассмотрим два способа определения оптимального шага. 1. Точный аналитический слособ На каждой итерации Ь получаем выражение для Т(Х ) в виде функции от й (~): г(й(~) )= 7(Х( + ) )= 7(Х( )+ й( )б(~~) . Для нахождения оптимального шага Ь в направлении но(/с) иска экстремума решаем задачу одномерной (так как Ь вЂ” ска(з) ляр) оптимизации: ех(г г(й ), / (и (1.13) (Ь(е))= О и достаточном условии миаимума ° (')(ьоб)> о ° (') ( ь бб ) < о и максимума где г Ь ) — производная порядка о функции г по й в (/с) точке Ь(). Если г (й( ) ) = О, то исследуются производные более высокого порядка.

Достаточаым условием экстремума будет четный порядок о (о= 4,6, ... )первой встречающейся (наиболее низкого порядка) производаой г (Ь ), не равной нулю, и при г (й ) > 0 достигается минимум г в точке й, а при г (й ) < 0 — мак(/с) симум. 16 причем в качестве экстремума будет минямум функции г(й )) (ь) ') при поиске минимума функции 1(Х) и максимум г(й ) — при (/с) максимуме У(Х) . Для решения задачи (1.13) используется классический метод, основанный аа необходимом условии экстремума: 2. Приближенный слособ Это способ нахождения оптимального шага Ь( ) путем одно(е) (ь- О или многократного деления или умаожения шага Ь на дробное положительное число, в частности, способ половинного деления или умножения шага.

Алгоритм определения на каждой й-й итерации значенай й и Х при поиске минимума 1(Х) состоит в следующем. (Е) (Ь + 1) 1. Принимаем Ь( ) = Ь( 2. Вычисляем Х= Х( )+ й( )д( ) и определяем 7(Х) 3. Если 1(Х) > Т(Х( ), то й = ай ), где 0< сх< 1 (для способа половинного деления или умножения шага принимаем а= 0,5). Пп. 2 и 3 алгоритма повторяем до тех пор, пока не будет выполнено условие 1(Х) < 1(Х ). Тогда примем Х = Х и (/с) н (/с н 1) переходим на п.

5. (Слишком болыпой шаг приводит к расходящемуся процессу при поиске экстремума, поэтому шаг уменыпают до того значения, прн котором обеспечивается сходимость процесса поиска минимума). 4. Если)'(Х) < Т(Х( )), то Ь( = . Запоминаем предыдущее а значение Х: Х = Х . Вычисляем новое значение Х= Х ' ' + й и /'(Х) . П. 4 повторяется до тех пор, пока не выполнится условие у(Х) > 1(Х( ) ), тогда в качестве Х берем предыдущее зна(ь) ') (Ь л 1) чение: Х = Х .

(Слишком маленький шаг приводит к. недо! статочкой скорости сходимости процесса поиска экстремума (большому числу итераций), поэтому шаг увеличивают до тех пор, пока процесс поиска минимума остается сходящимся). 5. Конец алгоритма. Рассмотрим геометрическую интерпретацию метода наискорейшего спуска. Из точки Х идем в направлении антиградиента в случае по(з) иска минимума 1(Х) или градиента при максимуме до точки Х, в которой достигается минимальное значение функции в (Ь + 1) (ь) ~ данном направлении.

Зто направление х ьс/(Х ) перпендикуляр- 17 но касательной к поверхности (линии при л= 2) постоянного уровня функции в точке Х, а также оно само является каса- (й) тельной к поверхности (ливни) постоянного уровня функции )'(Х) в точке Х(й+ . Поэтому перпендикуляр к касательной из точки Х проводим до тех пор, пока он сам не станет касатель- (й) ной к другой линии уровня (в точке Х ).

(/с+ 1) Рнс. 1.4 Геометрическая интерпретация метода наискорейшего спуска представлена на рвс. 1,4, где изображены линии постоянного уровня функции У(х(,х2)= с, (и= 1, 2, 3, 34, 4, 5, б,причем с1> с2> сэ> с84> с4> сэ> се) и полученные в соответствии с данным методом точки Х ( й= 1,3 ) при поиске минимума у'(Х). Для наглядности сравнения градиентных методов на рис. 1.4 показаны также полученные по методу градиентного спуска точки Х() ~)с= 1,3~. Кроме того, ва рис.

1.4 представлена геометрическая интерп- ретация метода сопряженных градиентов. В данном методе по 18 сравнению с методом наискорейшего спуска траектория поиска " (й) экстремума, проходящая последовательно через точки Х (й = О, (2) 1, 2, ...), сглаживается.

Точка Х( ) находится между Х( ) н Х~~~. Отметим, что в связи с выражением Х = Х + сс я выбором одной и тон же начальной точке для трех градиентных методов Х(О)= Х( ) = Х( ) и совпадением формул для у( и Л< ) О (й) й) при й= О в методах наискорейшего спуска и сопряженных градиентов, получаем совпадение в обоих методах точек на первой итерации Х( ) = Х(~) е Х(1) . Методы случайного поиска Если целевая функция такова, что затруднено или невозможно нахождение ее производных, нли онн имеют слишком громоздкий внд, то применяют методы случайного поиска.

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

12. В методах случайного поиска шаг Ь( ) обычно задается по(й) стоянным. Однако возможны модификации методов, в которых используется приближенный способ нахождения оптимального шага Ь на каждой итерации, описанный при рассмотрснив методов наискорейшего спуска и сопряженных граднентов. Направление у( ) поиска экстремума является полностью илн частично случайным. Существует много методов случайного поиска, отличающихся тем, как выбирается направление Х( ).

(й) Рассмотрим особенности нахождения у( ) и Х( ) в трех ос(й) (й + 1) нов пых методах случайного поиска. 1. Метод с возвратом на неудачном шаге Алгоритм нахождения у( ) и Х( ) на каждой итерации й ()с) (й с 1) состоят в следующем. 1. Генерируем случавное направление Л(й) в и-мерном пространстве, т.с. случайный вектор Л( = ~г(), ...,г( ) ~, где г ( ) — случайная величина с известным законом распределения (для простоты часто используют равномерное распределение яа отрезке ( — 1, 1)). 2. Примем у( ) = Л( ) и вычислим Х= Х( )+ 6()у() . 19 3.

Если 1(Х) е У'~Х(~) ~ в случае поиска минимума У(Х) (или У(Х)<,("(Х()) при максимуме), то переходим к и. 1, нначе Х((и+ 1) Х 4. Конец алгоритма. 2. Метод наилучшей пробы Алгоритм нахождения у н Х ' на каждои итерации й (ь> (з + 1) состоит в следующем.

1. Генерируем г случайных направлений 11(1 ) „..., )й ( ); находим соответствующие им з значении векторов Х„= Х( )+ й( ) 1)(„) и= 1,з~ и г значений Г(Хи) функции 1'(Х) в зтих точках Х,. 2. В случае поиска минимума функции 1"(Х) выберем то ((и) Н ., которое соответствует минимальному значению ~(Х,*) среи ди значений Г(Х,), т.е.

при У(Х, )= ю(п 1(Х,) примем и=1,» у() = )( ° н Х= Х И) и и в случае поиска максимума функции )(Х) при У(Х, )= ® (з) = гпах Т(Х„) примем у( ) = Н ° и Х= Х„ »=1,« 3, Если Г(Х) > Г(Х ) при поиске минимума 1(Х) (или У(Х) ~ У(Х®) при максимуме), то переходим к и. 1, иначе Х(л+ 1) Х 4. Конец алгоритма.

д. Метод с обучением В отличив от первых двух методов без обучения в данном методе учитывается опыт выбора удачного направления поиска зкстремума на двух предыдущих итерациях. Алгоритм нахождения у(") и Х ) на й-й итерации состоит (А+ 1) в следующем. 1. Вычисляем где )1 — случайный вектор с известной функцией распределения (часто используют равномерное распределение на отрезке — 1]); йр — детерминированный вектор, определяемый по Щ формуле: И,(ь) (1 Иг(з- И+ + Ь зап (1(Х®~- Т~Х" ")~~Х("'- Х"-"~ с использованием знака «+» прн Ь в случае поиска максимума фун- 1 при у>0, кцнн,)'(Х) я «-» при минимуме 1'(Х); зпп(у)= — 1 при у«0, 0 при у=О; И~ = 0; () — параметр запоминания; Ь вЂ” параметр обучения, (О) () к Ь вЂ” малые положительные величины, которыми регулируют степень детерминированности и случайности направления у по(«) иска зкстремума.

2. Находим Х= Х(Ю+ 6(")у 3. Если )(Х) >.((ХОО) при поиске минимума 1(Х) (илн ,Г(Х) Я „((Х ) ) при максимуме), то переходим к п. 1, иначе ((и) ' Х(~+ ) = Х. 4. Конец алгоритма. ВАРИАНТЫ ЗАДАНИЯ Для каждого номера варианта )й= 1, 20 в табл. 1,1 задана целевая функция 1(Х) в задаче се безусловной оптимизации ех1г 1(Х) . Х Табли~(а 1.1 20 21 ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ Окончание табл. 1.1 Ном зерна Ф х,+ хг+ хг+ хгхг — Зх,+ 9хг+ 1 3 2 2 х, + хгг+ х з+ 2х г — 2 хг — 3 хе+ 7 2 2 3 х, + 2 хе+ хг- 3 х, — 4 хе — 6х3 — 2 3 г 2 9 — + х, + х,+ хз- Зх, — 2х3+ 2хз+ 2 3 2 2 х,+ хг+ хг — 2х,— 4хг — Зхз — 1 2 2 3 х,+ хг+ хг+ хгхгт Зхг Зхг+ 3 г г 3 ПРИМЕ.Р х1+ хг+ Зхг+ хгхз Зхг 4 2 3 2 ~- (Х)= а дх, — ~ (Х)= Э ах, — Е- (Х)= а д Зхг — 3= О, 2 2хх + хз+ 6= О, 2хз+ хз= О.

22 х, + х,+ хз+ х, хг+ 9х,— Зхг+ ЗЗ 2 2 3 Для Вашего варианта задания необходимо: 1. Найти решение задачи безусловной оптимизации функции 1(Х) с помощью следующих методов: 1) классического; 2) Ньютона; 3) градиентного спуска при заданном й= 0.2; 4) наискорейшего спуска. В трех итерационных методах выполнить вручную только по одной итерации, используя одинаковое значение Х, компонен(о) ты которого должны отличаться от найденного по классическому методу экстремума на +1. 2.