Помощь по Теле2, тарифы, вопросы

Аннотация: Данная лекция рассматривает основные методы решения задач многомерной оптимизации, в частности, такие как метод Хука – Дживса, метод Нелдера – Мида, метод полного перебора (метод сеток), метод покоординатного спуска, метод градиентного спуска.

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

Математическая постановка таких задач аналогична их постановке в одномерном случае: ищется наименьшее (наибольшее) значение целевой функции, заданной на некотором множестве G возможных значений ее аргументов.

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

1. Метод Хука – Дживса

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

Описание этой процедуры представлено ниже:

А . Выбрать начальную базисную точку b 1 и шаг длиной h j для каждой переменной x j , j = 1, 2, ..., n . В приведенной ниже программе для каждой переменной используется шаг h , однако указанная выше модификация тоже может оказаться полезной.

Б . Вычислить f(x) в базисной точке b 1 с целью получения сведений о локальном поведении функции f(x) . Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b 1 находится следующим образом:

1. Вычисляется значение функции f(b 1) в базисной точке b 1 .

2. Каждая переменная по очереди изменяется прибавлением длины шага.

Таким образом, мы вычисляем значение функции f(b 1 + h 1 e 1) , где e 1 - единичный вектор в направлении оси х 1 . Если это приводит к уменьшению значения функции, то b 1 заменяется на b 1 + h 1 e 1 . В противном случае вычисляется значение функции f(b 1 – h 1 e 1) , и если ее значение уменьшилось, то b 1 заменяем на b 1 -h 1 e 1 . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b 1 остается неизменной и рассматриваются изменения в направлении оси х 2 , т.е. находится значение функции f(b 1 + h 2 e 2) и т.д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b 2 .

3. Если b 2 = b 1 , т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b 1 , но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если , то производится поиск по образцу.

В . При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

1. Разумно двигаться из базисной точки b 1 в направлении b 2 - b 1 , поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца

1) Методы Розенброка и Дэвиса, Свенна, Кемпи более подробно изложены в книге Химмельблау , переведенной на русский язык,- Прим. Перев

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

3.2.3. Метод сопряженных направлений Пауэлла

Наиболее эффективным из алгоритмов прямого поиска является метод, разработанный Пауэллом , в особенности его модифици­рованные варианты, предложенные Зангвиллом и Брентой . При работе этого алгоритма информация, полученная на предыдущих итерациях, используется для построения векторов направлений поиска, а также для устранения зацикливания последовательности координатных поисков. Метод ориентирован на решение задач с квадратичными целевыми функциями и основывается на фундаментальных теоретических результатах.

Задачи с квадратичными целевыми функциями занимают важное место в теории оптимизации по двум причинам.

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

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

Основная идея алгоритма заключается в том, что если квадратичная функция N переменных приведена к виду суммы полных квадратов, то ее оптимум может быть найден в результате реализации N одномерных поисков по преобразованным координатным на­правлениям.

Процедура преобразования квадратичной функции

q (x ) = a + bx + ½ xC x (3.25)

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

Q (x ) = xC x (3.26)

путем преобразования

x = T z (3.27)

приводится к виду

Q (x ) = zTC T z = zD z (3.28)

где D - диагональная матрица, т. е. элементы D отличны от нуля только при i = j

f(x) = 4x+ 3x- 4xx+ x

Рис. 3.8. Линии уровня квадратичной функции с перекрёстными членами.

Пусть t - j -й столбец матрицы Т . Тогда преобразование (3.27) позволяет записать каждый вектор х в виде линейной комбинации вектор-столбцов t.

x = T z = t z + tz+…+ tz . (3.29)

Другими словами, вместо координат вектора х в стандартной коор­динатной системе, определяемой множеством векторов e ( i ) , используются координаты вектора в новой координатной системе, заданной векторами t. Кроме того, система векторов t соответствует главным осям рассматриваемой квадратичной формы, поскольку матрица квадратичной формы приводится к диагональному виду. Такая ситуация возникает, если квадратичную функцию с перекрестными членами, линии уровня которой изображены на рис. 3.8, записать в новой координатной системе, оси которой совпадают с большой и малой осями квадратичной функции (см. рис. 3.9).

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

f(x) = 4x+ 2x+ x+x

Рис. 3.9. Линии уровня квадратичной функции без перекрёстных членов

Пример 3.4. Преобразование к виду суммы квадратов

Рассмотрим функцию

f (x ) = 4 x+ 3x– 4xx+ x

и преобразование

x = z + ½ z, x= z,

Преобразованная квадратичная функция принимает следующий вид:

f (z )= 4 z+ 2 z+ z + ½ z.

Заметим, что это преобразование не является единственным, поскольку система векторов t не удовлетворяет условию ортонормированности. В частности, нетрудно проверить, что преобразование

также приводит матрицу квадратичной формы к диагональному, виду. Задавая начальную точку x = и два столбца матрицы преобразования

t = , t = [½, 1],

можно найти точку оптимума [– ,– ] T в результате проведения двух последовательных поисков в направлениях t и t Поиск в направлении t по формуле

x= x+ λt

позволяет получить значение λ = – и точку х (1) = [– , 0]. Далее из точки х (1) проводится поиск в направлении t 2 . Получаем значение λ = – и решение х (2) = [– ,– ] T .

Из рассмотренного примера и предыдущего изложения следует, что если система векторов t, j = 1,...,N , или система сопряженных направлений, построена, то точку оптимума квадратичной функции можно найти в результате реализации в точности N одномерных поисков, которые проводятся вдоль каждого из N направлений t, j = 1,...,N . Таким образом, нерешенными остаются лишь вопросы, связанные с построением системы векторов t. Если матрица С известна, то матрицу преобразования Т можно найти с помощью метода Гаусса - Жордана (как это выполнено в приложении А). Метод Гаусса - Жордана позволяет представить матрицу С в виде произведения

C = P T DP , откуда (3.30)

(P )C (P ) = D и T = P (3.31)

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

Свойство параллельного подпространства

Пусть заданы квадратичная функция q (x ), две произвольные не­совпадающие точки x (1) и х (2) , а также направление d . Если точка y (1) минимизирует q (x (1) +λ d ), a точка y (2) минимизирует q (x (1) + λ d ), то направление (y (2) - y (1)) сопряжено с d .

Рис. 3.10 иллюстрирует сформулированное свойство для случая двух переменных. Нетрудно видеть, что поиск, проводимый из точки y (1) или y (2) в направлении (y (2) - y (1)), обеспечивает получение точки минимума. Таким образом, в случае двух переменных реализация трех одномерных поисков позволяет построить систему сопряженных направлений и, кроме того, найти точку оптимума квадратичной функции. Прежде чем продолжать алгоритмические построения, докажем теорему о свойстве параллельного подпространства.

Рис. 3.10. Сопряженные направления на плоскости.

Напомним, что по определению С -сопряженные направления задаются системой вектор-столбцов матрицы Т , которая приводит матрицу С к диагональному виду:

ТC Т = D (3.32)

Поскольку все внедиагональные элементыD равны нулю, отсюда следует, что

(3.33)

где t - i -й столбец матрицы Т. Таким образом, мы получили возможность дать более удобное, эквивалентное и, по-видимому, более конструктивное определение сопряженности направлений.

Сопряженные направления

Пусть С - симметрическая матрица порядка NN ; направления s (1) , s (2) , s (3) ,..., s, r ≤ N , называются С -сопряженными, если эти направления линейно независимы и

s
C s= для всех i ≠ j . (3.34)

Опять обратимся к квадратичной функции общего вида

q(x ) = a + b T x+( 1 / t )x T C x.

Точки прямой, исходящей из х (1) в направлении d , задаются формулой

x = x+ λd .

Минимум q (x ) вдоль направления d определяется путем нахождения значения λ*, при котором q / λ=0. Вычислим эту производную по правилу дифференцирования сложной функции:

= =b+ xC d . (3.35)

По предположению теоремы минимум достигается в точке y (1) следовательно,

[(y (1))C b ] d = 0. (3.36)

Аналогично, так как минимум q (x ) при движении из точки х (2) в направлении d достигается в точке y (2) имеем

[(y (2))C b ] d = 0. (3.37)

Вычитая (3.36) из (3.37), получаем

(y (2) - y (1))C d = 0 (3.38)

В соответствии с данным выше определением направления d и (y (2) - y (1)) оказываются С -сопряженными, и свойство параллельного подпространства для квадратичных функций доказано.

Пример 3.5. Минимизация на основе свойства параллельного подпространства.

Опять рассмотрим квадратичную функцию q (x ) = 4 x+ 3 x - 4 xx+ x . Пусть заданы две точки х (1) = ,х (2) = и направлениеd = T . Первый поиск проводится вдоль прямой

x = +λ

и приводит к точке y (1) = [-,-](λ*= -). Второй поиск проводится вдоль прямой

x = +λ

и позволяет получить точку y (2) = [,– ](λ*=– ). Согласно свойству параллельного подпространства, направление

y (2) – y (1) = [,– ]– [– ,– ]= [,– ]

сопряжено с d = T

C [,– ].

Выше отмечалось, что в случае двух переменных оптимум q (x ) можно найти путем проведения поиска вдоль прямой, заданной направлением (y (2) – y (1)). Этот факт нетрудно проверить, поскольку минимум q (x ) вдоль прямой

x = [– ,– ]+λ [,– ]

достигается в точке х* = [– ,– ] T (λ* = – ), которая сов­падает с полученным ранее решением.

В рассмотренных выше построениях для того, чтобы определить сопряженное направление, требовалось задать две точки и некоторое направление. Это не слишком удобно при проведении расчетов, поэтому предпочтительнее строить систему сопряженных направлений, исходя из одной начальной точки, что легко осуществить при помощи единичных координатных векторов е (1) , е (2) , е (3) ,..., е (N) . (Здесь рассматривается процедура построения сопряженных на­правлений в случае двух переменных, которая допускает очевидное обобщение для N-мерного пространства.) Пусть е (1) = ие (2) = . При заданной начальной точкех (0) вычислим значение λ (0) , которому соответствует минимум f (х (0) + λ (0) е (1)).

x (1) = х (0) + λ (0) е (1) .

и вычислим значение λ (1) , которому соответствует минимум f (х (1) + λ (1) е (2)). Положим

x (2) = х (1) + λ (1) е (2) .

x (3) = х (2) + λ (2) е (1) .

При этом направления (х (3) – х (1)) и е (1) оказываются сопряженными. Для того чтобы убедиться в этом, рассмотрим рис. 3.11. Заметим, что точка х х (0) в направление е (1) , а точка х (3) получена при поиске из точки х (2) в направлении е (1) . Следовательно, направление е (1) и (х (3) – х (1)) являются сопряжёнными согласно свойству параллельного подпространства. Далее если на следующей итерации провести поиск в направлении (x (3) – x (1)), то процедура поиска будет охватывать два сопряженных направления, и поскольку f (x ) предполагается квадратичной функцией двух переменных, в результате будет найдено решение х* .

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

В частности, нетрудно показать, что если точка y (1) найдена в результате поиска из точки х (1) вдоль каждого из М (< N ) сопряженных направлений, а точка y (2) получена в результате поиска из точки х (2) вдоль каждого из тех же М сопряженных направлений s (1) , s (2) , s (3) ,..., s ( M ) то вектор (y (2) – y (1)) задает направление, сопряженное со всеми выбранными М направлениями. Это утверждение известно как обобщенное свойство параллельного подпространства. Используя указанное свойство, можно обобщить метод построения сопряженных направлений, последовательные шаги реализации которого отражены на рис. 3.11 на случай пространства управляемых переменных более высокой размерности. Рис. 3.12 иллюстрирует построение сопряженных направлений в трехмерном пространстве.

Как показано на рис. 3.12, сначала поиск осуществляется вдоль трех координатных направлений е (1) , е (2) и е (3) затем эти направления последовательно заменяются вновь построенными сопряженными направлениями. Серия одномерных поисков из точки x (0) проводится в направлении е (3) , затем е (1) , е (2) и снова е (3) ; в результате построены сопряженные направления е (3) и (x (4) – x (1)). Направление е (1) заменяется новым направлением поиска, которое на рис. 3.12 обозначено цифрой 4 . Следующая серия поисков проводится в направлении 4 , затем е (2) , е (3) и снова 4 . Согласно обобщенному свойству параллельного подпространства, новое направление (x (8) – x (5)), обозначенное на рисунке цифрой 5 , сопряжено не только с 4 , но и с е (3) . Следовательно, направления е (3) , (x (4) – x (1)) и (x (8) – x (5)) образуют систему взаимно сопряженных направлений.

Рис. 3.11. Построение сопряженных направлений из одной точки.

Поэтому если провести дополнительный поиск из точки x (5) в направлении (x (8) – x (5)) (т. е. в направлении 5 на рисунке), то будет найдена точка x (9) , в которой должен достигаться оптимум квадратичной функции трех переменных f (x ) , поскольку поиск последовательно осуществляется в трех взаимно сопряженных направлениях. Таким образом, в трехмерном случае для нахождения точного (если, разумеется, оперировать недесятичными дробями) оптимума квадратичной функции требуется провести девять поисков вдоль прямой с использованием только значений функции. Алгоритм легко обобщается и в случае N -мерного пространства требует проведения последовательности N одномерных поисков, которая приводит к получению точки оптимума квадратичной функции. Ниже представлены шаги обобщенного алгоритма.

Рис. 3.12. Построение сопряженных направлений в трехмерном пространстве.

Метод сопряженных направлений Пауэлла

Шаг 1. Задать начальную точку х (0) и систему N линейно независимых направлений; возможен случай, когда s ( i ) = e ( i ) i = 1, 2, 3,..., N.

Шаг 2. Минимизировать f (x ) при последовательном движении по (N +1) направлениям; при этом полученная ранее точка минимума берется в качестве исходной, а направление s ( N ) используется как при первом, так и последнем поиске.

Шаг 3. Определить новое сопряженное направление с помощью обобщенного свойства параллельного подпространства.

Ш а г 4. Заменить s (l) на s (2) и т. д. Заменить s ( N ) сопряженным направлением. Перейти к шагу 2.

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

Из способа построения алгоритма следует, что в случае, когда целевая функция квадратична и обладает минимумом, точка минимума находится в результате реализации N циклов, включающих шаги 2, 3 и 4, где N - количество переменных. Если же функция не является квадратичной, то требуется более чем N циклов. Вместе с тем можно дать строгое доказательство того, что при некотором предположении метод Пауэлла сходится к точке локального мини­мума с суперлинейной скоростью (см. данное ниже определение).

Скорость сходимости. Рассматриваемый метод позволяет построить последовательность точек х ( k ) , которая сходится к решению x *. Метод называется сходящимся, если неравенство

≤1, где (3.39)

= x – х* , (3.40)

выполняется на каждой итерации. Поскольку при расчетах обычно оперируют конечными десятичными дробями, даже самый эффективный алгоритм требует проведения бесконечной последовательности итераций. Поэтому в первую очередь интерес представляют асимпто­тические свойства сходимости изучаемых методов. Будем говорить, что алгоритм обладает сходимостью порядка r (см. ), если

, (3.41)

где С - постоянная величина. Из формулы (3.39) следует, что при r = 1 имеет место неравенство С ≤ 1. Если r = 1 или r = 2, то алгоритм характеризуется линейной или квадратичной скоростью сходимости соответственно. При r = 1 и С = 0 алгоритм характеризуется суперлинейной скоростью сходимости.

Пример 3.6. Метод сопряженных направлений Пауэлла

Найти точку минимума функции

f (x ) = 2 x + 4 xx – 10 x x+ x,

если задана начальная точка х (0) = T , в которой f (x (0)) = 314.

Шаг 1. s (1) = T , s (2) = T .

Шаг 2. (а) Найдем такое значение λ, при котором

f (x (0) + λs (2)) → min.

Получим: λ* - 0,81, откуда

x (l) = T - 0,81 T = T , f (x (l)) = 250.

(б) Найдем такое значение λ, при котором f (x (1) + λs (1)) → min.

λ* = – 3,26, x (2) = T , f (x (2)) = 1.10.

(в) Найдем такое значение λ, при котором f (x (2) + λs (2)) → min.

λ* = – 0.098, x (3) = T , f (x (3)) = 0.72.

Шаг 3. Положим s (3) = х (3) - x (1) = [-3.26,-0.098] T . После нормировки получим

s (3) = = [– 0,99955, – 0,03] T .

Положим s (1) = s (2) , s (2) = s (3) и перейдем к шагу 2 алгоритма.

Шаг 4. Найдем такое значение λ, при котором f (x (3) + λs (2)) → min.

λ* = – 0.734, x (4) = T , f (x (4)) = – 2,86.

Примечание. Если бы f (x ) была квадратичной функцией, то полученная точка являлась бы решением задачи (если пренебречь ошибкой округления). В данном случае итерации следует продолжить до получения решения.

Направления поиска, полученные в процессе реализации метода, показаны на рис. 3.13.

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

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

Материал из Википедии - свободной энциклопедии

Метод Хука - Дживса (англ. Hooke - Jeeves, Pattern search ) так же, как и алгоритм Нелдера - Мида , служит для поиска безусловного локального экстремума функции и относится к прямым методам, то есть опирается непосредственно на значения функции. Алгоритм делится на две фазы: исследующий поиск и поиск по образцу.

На начальном этапе задаётся стартовая точка (обозначим её 1) и шаги h i по координатам. Затем замораживаем значения всех координат кроме 1-й, вычисляем значения функции в точках x 0 +h 0 и x 0 -h 0 (где x 0 - первая координата точки, а h 0 - соответственно значение шага по этой координате) и переходим в точку с наименьшим значением функции. В этой точке замораживаем значения всех координат кроме 2-й, вычисляем значения функции в точках x 1 +h 1 и x 1 -h 1 , переходим в точку с наименьшим значением функции и т. д. для всех координат. В случае, если для какой-нибудь координаты значение в исходной точке меньше, чем значения для обоих направлений шага, то шаг по этой координате уменьшается. Когда шаги по всем координатам h i станут меньше соответствующих значений e i , алгоритм завершается, и точка 1 признаётся точкой минимума.

Иллюстрация первого этапа для двух координат:

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

На этапе поиска по образцу откладывается точка 3 в направлении от 1 к 2 на том же расстоянии. Её координаты получаются по формуле x ¯ 3 = x ¯ 1 + λ (x ¯ 2 − x ¯ 1) {\displaystyle {\overline {x}}_{3}={\overline {x}}_{1}+\lambda ({\overline {x}}_{2}-{\overline {x}}_{1})} , где x i - точка с номером i, λ - параметр алгоритма, обычно выбирающийся равным 2. Затем в новой точке 3 проводится исследующий поиск, как на 1 фазе алгоритма, за исключением того, что шаг на этой фазе не уменьшается. Если на этой фазе в результате исследующего поиска удалось получить точку 4, отличную от точки 3, то точку 2 переобозначим на 1, а 4 на 2 и повторим поиск по образцу. В случае если не удаётся найти точку 4, отличную от точки 3, то точку 2 переобозначим на точку 1 и повторим 1-ю фазу алгоритма - исследующий поиск.

Иллюстрация второго этапа для двух координат:

В скобках отмечены имена точек после переобозначения. На иллюстрации хорошо заметно, как алгоритм корректирует своё направление в зависимости от найденных значений функции.

Литература

1. Р. Хук, Т. А. Дживс «Прямой поиск решения для числовых и статических проблем», 212-219 с., 1961.
2. C. T. Kelley. Iterative methods for optimization, 180 p

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное

образовательное учреждение высшего образования

Курсовая работа

по дисциплине

«Теория и методы принятия решений»

оптимизация решение хук дживс

Введение

1.1 Метод Хука-Дживса

1.3 Блок-схема данного метода

Заключение

Список литературы

Введение

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

В этой работе пойдет речь об одном из методов, так называемого, прямого поиска. Это - метод Хука-Дживса. Он применяется для определения минимума функций и переменных. Этот метод, созданный в середине двадцатого столетия, применяется и сейчас, так как очень хорошо себя зарекомендовал.

Целью данной работы, является освещения концепций метода Хука-Дживса.

Основными задачами, подлежащими рассмотрению в связи с поставленной целью, являются:

· объяснить в чем состоит суть метода Хука-Дживса;

· показать его отличие от других методов данного типа;

· рассмотреть алгоритм работы метода;

· пояснить этапы выполнения метода;

· уточнить в чем состоит модификация данного метода;

· наглядно продемонстрировать работу метода с помощью блок-схем.

Актуальность данной работы заключается в конкретизации и резюмированию знаний об этом методе.

1. Освоение алгоритма решения типовой задачи оптимизации на учебном примере

1.1 Метод Хука-Дживса

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

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b 1 и шаг длиной h 1 для каждой переменной x j , j = 1, 2,…, n. В приведенной ниже программе для каждой переменной используется шаг h , однако указанная выше модификация тоже может оказаться полезной.

Б. Вычислить f (х) в базисной точке b 1 с целью получения сведений о локальном поведении функции f (x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f (x) в базисной точке b 1 , находится следующим образом:

1. Вычисляется значение функции f (b 1) в базисной точке b 1 .

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f (b 1 +h 1 e 1), где e 1 - единичный вектор в направлении оси x 1 . Если это приводит к уменьшению значения функции, то b 1 заменяется на b 1 +h 1 e 1 . В противном случае вычисляется значение функции f (b 1 -h 1 e 1), и если ее значение уменьшилось, то b 1 заменяем на b 1 -h 1 e 1 . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b 1 остается неизменной и рассматриваются изменения в направлении оси х 2 , т. е. находится значение функции f (b 1 +h 2 e 2) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b 2 .

3. Если b 2 =b 1 , т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b 1 , но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если b 2 b 1 , то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

1. Разумно двигаться из базисной точки b 2 в направлении b 2 -b 1 , поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца:

P 1 =b 1 +2(b 2 -b 1).

В общем случае:

P i =b i +2(b i+1 -b i).

2. Затем исследование следует продолжать вокруг точки Р 1 (Р i).

3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b 2 (в общем случае b i+1), то получают новую базисную точку b 3 (b i+2), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b 2 (b i+1), а продолжить исследования в точке b 2 (b i+1).

Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.

1.2 Модифицированный метод Хука-Дживса

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

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

1.3 Блок-схема данного метода

1.4 Решение конкретной задачи симплексным методом

Задача:

Минимизируйте функцию

при ограничениях:

Решение:

Шаг 1. Задаем начальную точку x 0 =(1,21); приращения (шаги): ?x=(1,1); коэффициент уменьшения шага: б = 2; е=0.1

Вычислим значение функции в т. x 0 =(1,21) T: f(x 0) = -3366.5

Итерация №0 .

Шаг №2. Исследующий поиск.

Фиксируя переменную x 2 = 21, дадим приращение x 1:

f(2;21) = -1980.3 > -3366.5

x 2 =21 + 1 = 22

f(1;22) = -3870.7 < -3366.5

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 1 =(1;22) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу. Осуществляется шаг из полученной базовой точки вдоль прямой, соединяющей эту точку с предыдущей базовой.

Итерация №1 .

Фиксируя переменную x 2 = 23, дадим приращение x 1:

f(2;23) = -2601.7 > -4422.9

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =23 + 1 = 24

f(1;24) = -5025.3 < -4422.9

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 2 =(1;24) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №2 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 25, дадим приращение x 1:

f(2;25) = -3341.1 > -5680

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =25 + 1 = 26

f(1;26) = -6389.2 < -5680

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 3 =(1;26) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №3 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 27, дадим приращение x 1:

f(2;27) = -4208.9 > -7155.1

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =27 + 1 = 28

f(1;28) = -7979.9 < -7155.1

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 4 =(1;28) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №4 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 29, дадим приращение x 1:

f(2;29) = -5215.2 > -8865.8

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =29 + 1 = 30

f(1;30) = -9815 < -8865.8

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 5 =(1;30) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №5 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 31, дадим приращение x 1:

f(2;31) = -6370.3 > -10830

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =31 + 1 = 32

f(1;32) = -11912 < -10830

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 6 =(1;32) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №6 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 33, дадим приращение x 1:

f(2;33) = -7684.5 > -13064

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =33 + 1 = 34

f(1;34) = -14288 < -13064

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 7 =(1;34) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №7 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 35, дадим приращение x 1:

f(2;35) = -9168.1 > -15586

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =35 + 1 = 36

f(1;36) = -16960 < -15586

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 8 =(1;36) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №8 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 37, дадим приращение x 1:

f(2;37) = -10831 > -18413

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =37 + 1 = 38

f(1;38) = -19947 < -18413

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 9 =(1;38) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Итерация №9 .

Шаг №2. Исследующий поиск (после поиска по образцу).

Фиксируя переменную x 2 = 39, дадим приращение x 1:

f(2;39) = -12684 > -21563

Фиксируя переменную x 1 = 1, дадим приращение x 2:

x 2 =39 + 1 = 40

f(1;40) = -23265 < -21563

Значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, поэтому шаг поиска успешный. Базовая точка x 10 =(1;40) T . Переходим к поиску по образцу.

Шаг 3. Поиск по образцу.

Новая точка образца определяется по формуле: x p k =x k +(x k -x k-1)

Ответ:

2. Анализ метода решения реальной задачи оптимизации на основе научной публикации

В статье рассматривается задача о глубоком сверлении стальной заготовки ствола охотничьего ружья.

Путь резания / l рез. / составляет 628м. Расчёт средней стойкости инструмента (T?) проводится по тейлоровской зависимости:

T? = С T / ? µ , где

С T - константа, не зависящая от скорости резания

µ - эмпирическая константа

Скорость резания

Даны параметры:

Коэффициент вариации стойкости инструмента? t изменяется от 0,1 до 0,5.

В задаче рассматриваются 2 критерия оптимизации:

1) Минимум времени обработки детали при заданной вероятности получения брака;

2) Минимум экономического риска.

Используется численный метод - метод касательных Ньютона:

? * = (С T / C) 1/(µ-1)

Математическое ожидание равно 1.

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

Для второго критерия оптимальности применяют выражение:

C R = C 1 + С 2 , где

C R - среднее значение экономического ущерба из-за возможного отказа инструмента при обработке детали;

C 1 - коэффициент, характеризующий среднюю стоимость потерь в связи с неблагоприятным исходом обработки заготовки;

С 2 - коэффициент, учитывающий потери, пропорциональные среднему времени резания до отказа инструмента или до окончания обработки заготовки;

Вероятность безотказной работы инструмента за время резания t.

Для второго критерия оптимальности решение зависит от коэффициентов С 1 и С 2 . С увеличением разброса стойкости усиливается влияние С 1 /С 2 на оптимизацию. Чем больше величина С 1 /С 2 , т.е. чем больше зависимость потерь от брака, тем меньшую скорость обработки следует назначать.

При малых значениях коэффициента вариации стойкости оптимальная скорость резания стремится к оптимальной скорости, рассчитанной детерминировано по формуле:

T? (?) ? = l рез

В данной задаче? = 75,1 м/мин

Решение:

T? = С T / ? µ = 1,5410 9 / 75,1 4,4 = 2,73783976 Ч 10 ? 7

l рез =T? (?) ? = 2,73783976 Ч 10 ? 7 * (75,1) * 75,1 = 0,00154414436

Оптимальная скорость резания равна 0,00154414436.

Заключение

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

Решение задач линейного программирования - это достаточно трудоемкий процесс, особенно при большом числе переменных и ограничений. Поэтому решать такие задачи целесообразно с применением ЭВМ.

В данной работы были освещены концепции метода Хука-Дживса. Основываясь на данной работе и на материалах использованных для ее написания, можно сделать следующие выводы:

Метод Хука-Дживса применим для широкого числа приложений, не смотря на то, что он был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным;

Метод Хука-Дживса использует информацию на основании уже полученных значений функции, это экономит время работы;

Метод Хука-Дживса нетрудно модифицировать для учета ограничений.

Список литературы

1.Пушкин Н.М., ИноземцевА.Н., Савушкин В.Н. Оптимизация режимов обработки деталей спортивного и охотничьего оружия путём уменьшения риска потери качества/ Н.М. Пушкин, А.Н. Иноземцев, В.Н. Савушкин / /Автоматизация и современные технологии. 2002. №6. с. 10-13.

2.Бразовская Н.В., Бразовская О.В. Методы оптимизации: Учебное пособие / Алт. Госуд. Технич. Ун-т им. И.И. Ползунова. Барнаул: изд. АлтГТУ, 2006. 127 с.

3.Кулаков С.М., Бондарь Н.Ф. Методические указания к выполнению курсовой работы и практическим работам / С.М. Кулаков, Н.Ф. Бондарь. Новокузнецк: Изд. центр СибГИУ, 2016. 62 с.

4. Б.Банди. Методы оптимизации. М., 1998 г.

5. Р.Хук, Т.А. Дживс. Прямой поиск решения для числовых и статических проблем. 1961 г.

Размещено на Allbest.ru

Подобные документы

Понятие управленческого решения и требования к нему. Процесс выработки решения и основные задачи при его принятии. Сущность и принципы метода мозгового штурма, его виды, этапы, достоинства и недостатки. Роль творческого мышления для принятия решения.

презентация , добавлен 12.03.2012


Принятие управленческих решений с использованием метода "платежной матрицы". Линейное программирование (задача планирования производства). Пример решения транспортной задачи, определение начального плана перевозок с помощью метода северо-западного угла.

контрольная работа , добавлен 17.12.2013


Характеристика количественной школы, направления, основные тенденции развития. Практика принятия решений в области ценообразования в ООО "Евроокна". Анализ количественных методов для решения задачи оптимизации процесса принятия управленческих решений.

курсовая работа , добавлен 18.05.2009


Основные управленческие решения и их классификация. Теория исследования операций и ее применение в анализе. Теории массового обслуживания, оптимизации и нечетких множеств. Процедура решения задачи. Принятие решений как важнейшая функция управления.

реферат , добавлен 08.12.2014


Сущность, классификация и разработка управленческого решения. Общая характеристика и структура органов Федерального казначейства. Задачи и принципы оптимизации. Разработка управленческого решения в сфере оптимизации органов Федерального казначейства.

курсовая работа , добавлен 17.06.2010


Принятие решений и обмен информацией как составная часть управленческой функции. Отличительные особенности управленческих и организационных решений. Анализ системы участия персонала в принятии управленческого решения. Виды информации для принятия решения.

презентация , добавлен 17.02.2015


Процедура решения задачи методом мозгового штурма. Этапы генерации идей и их анализа. Правила этапа генерации и аналитического этапа. Поиск новых направлений решения как основная цель метода мозгового штурма. Базовые принципы работы для аналитика.

контрольная работа , добавлен 25.03.2011


Концептуальные подходы к разработке и принятию управленческих решений. Принятие управленческих решений в сфере планирования. Система нормативного учета затрат. Экономическая диагностика предприятия. Анализ внешней среды предприятия. Принятие решения.

курсовая работа , добавлен 31.10.2008


Сущность методов планирования, их использование при разработке и принятии управленческих решений. Применение балансового метода при финансовом планирования деятельности ОАО "Газпром". Рекомендации по преодолению трудностей в применении балансового метода.

курсовая работа , добавлен 28.11.2015


Возникновение кибернетики, моделирования; формирование количественной школы управления: направления, основные тенденции развития, представители. Применение количественных методов для решения задачи оптимизации процесса принятия управленческих решений.