Green-sell.info

Новые технологии
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Многомерные задачи оптимизации

Многомерные задачи оптимизации.

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

, (14.1)

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

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

Решение многомерной задачи оптимизации методом покоординатного спуска.

Первоначально выбирается некоторая точка с координатами , как показано на рисунке (14.1). Затем фиксируются все координаты функции кроме первой и получаем функцию одной переменной :

. (14.2)

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

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

. (14.3)

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

(14.4)

Рисунок 14.1 Пояснение к методу покоординатного спуска.

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

Блок-схема метода покоординатного спуска.

Блок-схема данного метода показана на рисунке 14.2. В исходных данных задаются первоначальные значения всех проектных параметров и число этих параметров . Затем выполняется нахождение целевой функции при исходных значениях всех проектных параметров. После чего определяется минимальное значение функции по одному параметру при фиксации всех остальных. Если не достигается требуемая точность , то вычисления продолжаются.

Рисунок 14.2 Блок-схема вычисления методом покоординатного спуска

Многомерные задачи оптимизации

Основные понятия

Определения.

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

В процессе решения задачи оптимизации обычно необходимо найти оптимальные значения некоторых параметров, определяющих данную за­дачу. При решении инженерных задач их принято называтьпроектными параметрами, а в экономических задачах их обычно называют парамет­рами плана. В качестве проектных параметров могут быть, в частности, значения линейных размеров объекта, массы, температуры и т. п. Число п проектных параметров x1,x2,…,xп характеризует размерность (и степень сложности) задачи оптимизации.

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

Целевую функцию можно записать в виде

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

В случае одного проектного параметра (n = 1) целевая функция (6.1) является функцией одной переменной, и ее график — некоторая кривая на плоскости. При n = 2 целевая функция является функцией двух перемен­ных, и ее график — поверхность в трехмерном пространстве.

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

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

Задачи оптимизации.

Можно выделить два типа задач оптимизации — безусловные и условные. Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции (6.1) от действительных переменных и определении соответствующих значений аргументов на некотором множестве а n-мерного пространства.

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

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

Читать еще:  Оптимизация по парето

В результате ограничений область проектирования а, определяемая все­ми п проектными параметрами, может быть существенно уменьшена в соответствии с физической сущностью задачи. Число Мограничений-равенств может быть произвольным. Их можно записать в виде

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

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

Пример постановки задачи.

Пусть требуется спроектировать кон­тейнер в форме прямоугольного параллелепипеда объемом V = 1 м 3 , причем желательно израсходовать на его изготовление как можно меньше материала.

При постоянной толщине стенок последнее условие означает, что пло­щадь полной поверхности контейнера должна быть минимальной. Если обозначить через x1, х2, х3 длины ребер контейнера, то задача сведется к минимизации функции

Эта функция в данном случае является целевой, а условие (V — 1) — ограничением равенством, которое позволяет исключить один параметр:

Задача свелась к минимизации функции двух переменных. В результате ре­шения задачи будут найдены значения проектных параметров х1, x2, а затем и х3.

Одномерная оптимизация

  1. Задачи на экстремум.

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

Теорема Вейерштрасса. Всякая функция f(x), непрерывная на отрезке [а, b], принимает на этом отрезке наименьшее и наибольшее зна­чения, т. е. на отрезке [а, b] существуют такие точки х1 и x2, что для любого х £ [а,b] имеют место неравенства

Пример. Найти наименьшее и наибольшее значения функции f ’ (x) = x 3 /3 — х 2 на отрезке [1,3].

Решение. Вычислим производную этой функции:

Приравнивая ее нулю, найдем критические точки:

Точка х = 0 лежит вне рассматриваемого отрезка, поэтому для анализа оставляем три точки: а = 1, x-i — 2, b = 3. Вычисляем значения функции в этих точках:

Сравнивая полученные величины, находим, что наименьшего значения функция f(x) достигает в точке х = 2, наибольшего — в точке х = 3, т. е.

Методы поиска.

Численные методы поиска экстремальных значе­ний функции рассмотрим на примере нахождения минимума функции f(x] на отрезке [а, b]. Будем предполагать, что целевая функция унимодальна, т. е. на данном отрезке она имеет только один минимум. Отметим, что в ин­женерной практике обычно встречаются именно такие целевые функции.

Погрешность приближенного решения задачи определяется разностью между оптимальным значением х проектного параметра и приближением к нему х*. Потребуем, чтобы эта погрешность была по модулю меньше заданного допустимого значения е:

Процесс решения задачи методом поиска состоит в последовательном сужении интервала изменения проектного параметра, называемого интер­валом неопределенности. В начале процесса оптимизации его длина равна b — а, а к концу она должна стать меньше е, т. е. оптимальное значение про­ектного параметра должно находиться в интервале неопределенности — отрезке [xn,xn+1], причем xn+1 — хп [ a b&i]> • • • .стягивающихся к точке минимума функции/(ж). На каждом шаге, за исключением первого, вычисление значения функции /(х) проводится лишь в одной точке. Эта точка, называемая золотым сечением, выбирается специальным образом.

Пример:

Для оценки сопротивления дороги движению автомобиля при скорости г; км/ч можно использовать эмпирическую формулу

(для шоссе). Определить скорость, при которой сопро­тивление будет минимальным.

Решение.

Это простейшая задача одномерной оптимизации. Здесь сопротивление f(v) — целевая функция, скорость v — проектный па­раметр. Данную задачу легко решить путем нахождения минимума с помощью вычисления производной, поскольку f(v) — функция диффе­ренцируемая. Действительно,

Проиллюстрируем на этой простейшей задаче метод золотого сечения. Первоначально границы интервала неопределенности примем равными a = = 5, b = 20. Результаты вычислений представим в виде (табл. 6.1). Здесь обозначения аналогичны используемым в структурограмме (см. рис. 6.3). Расчеты проводятся в соответствии со структурограммой с погрешностью

Приведем решение для первого этапа:

Замечание. Согласно табл. 6.1 заданная точность е будет достигну­та уже на третьем шаге:

Однако определить достижение заданной точности на третьем шаге мож­но только тогда, когда известно точное решение г; = 10 км/ч. Но в этом

случае вообще нет смысла в проведении численного расчета. Поэтому в реальном расчете нужно выполнить большее число шагов до выполнения условия (6.11).

Для рассмотренного выше примера (6.12) дает N = 6.

Метод Ньютона.

Задача одномерной оптимизации дифференцируемой функции f(x) сводится к нахождению критических точек этой функции, определяемых уравнением

Когда уравнение (6.13) нельзя решить аналитически, для его решения можно применить численные методы. В этом случае говорят о методе Ньютона решения задачи опти­мизации.

Читать еще:  Скалярная оптимизация логистика

Пример. Решим методом Ньюто­на задачу оптимизации из п. 3.

Решение. Заметим, что функция

квадратичной, т. е. ее разложение вида (6.15) представляет собой точное ра­венство: f(v) = φ(v). Поэтому первая же итерация по методу Ньютона и* = с при любом начальном приближении C даст точное решение задачи. Второе приближение совпадет с первым: с2 = с1, поскольку f ‘ (c1)= 0. Таким образом, после двух итераций будет выполнено условие завершения итерационного процесса.

Многомерные задачи оптимизации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

МНОГОМЕРНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ

2.1. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ: МЕТОД ПОКООРДИНАТНОГО СПУСКА.

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

б) Е — точность нахождения значений независимых переменных, при которых функция достигает минимума,

Зафиксируем все значения х-ов в виде начальных приближений, кроме первого. Тогда f(х1, х20 . , хn0) — функция одной переменной х1. Решая задачу одномерной оптимизации, найдем минимум этой функции по координате х1 при фиксированных остальных координатах – хi1. В этом состоит первый шаг процесса оптимизации, заключающийся в спуске по координате x1.

Зафиксируем теперь все координаты, кроме x2. Снова решая одномерную задачу оптимизации, находим минимум функции по координате x2. Далее процедура повторяется до xn. На этом заканчивается первая итерация.

Читать еще:  Как повысить оптимизацию в играх

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

После каждой итерации вычисляется

и если D 2 ) 2 + (1-x1) 2

из начальной точки ( 0,5;0,5) c точностью 0,0001.

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

Решим эту задачу на EXCEL на новом рабочем листе.

Выделим столбец А под значения х1, столбец В — под значения х2, в столбец С будем заносить значения целевой функции и, наконец, в столбец D — значения погрешности D.

Занесем в ячейки А3 и В3 значения начальных приближений, равных 0,5 и в ячейку С3 формулу =(В3-А3^2)^2+(1-A3)^2. Скопируем эту формулу в блок ячеек С4:С17. На этом заканчивается подготовительный этап.

1 шаг. Скопируем содержимое ячейки В3 в ячейку В4. Сделаем текущей ячейку С4. Процесс одномерной оптимизации для нахождения X1 выполним с помощью подпрограммы EXCEL Поиск решения.

В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С4, а в поле Изменяя ячейки — адрес А4. Щелкнем по кнопке Выполнить и по кнопке ОК. В результате в ячейке А4 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С4 по координате х1.

2 шаг. Скопируем содержимое ячейки А4 в ячейку А5.

Текущая ячейка С5, меню Сервис- Поиск решения. В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С5, а в поле Изменяя ячейки — адрес В5, Выполнить.

В результате в ячейке В5 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С5 по координате х2.

3 шаг. Занесем в ячейку D5 формулу =ABS(A3-A5)+ABS(B3-B5) для вычисления погрешности решения на первом шаге. На этом заканчивается первая итерация.

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

Можно построить диаграмму изменения на каждой итерации, выделив блок А2:В17 с помощью Мастера Диаграмм, выбрав тип диаграммы XY-точечная и формат 2. На диаграмме хорошо видны перпендикулярные ломаные линии движения от точки к точке параллельно одной из осей координат.

2.2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ: МЕТОД НАИСКОРЕЙШЕГО СПУСКА.

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

Даны: а) формулу целевой функции f(x1,x2, . , xn),

б) Е — точность нахождения значений независимых переменных, при которых функция достигает минимума,

г) формулы первых частных производных целевой функции по каждой независимой переменной.

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

Можно попытаться модифицировать этот метод таким образом, чтобы на каждом шаге поиск минимума производился вдоль “наилучшего” направления. Известно, что направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление — антиградиента — является направлением наискорейшего убывания функции.

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

Идея метода наискорейшего спуска:

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

Например, для функции двух переменных формулы первой итерации будут иметь вид

где х1нов = х10— h(du/dх1)X10 и х2нов = х20 -h(du/dх2) X20, а h — длина отрезка от точки нулевого приближения до точки минимума по выбранному направлению. Эта длина определяется методом одномерной оптимизации.

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

Решим задачу примера 2.1 методом наискорейшего спуска. Для этого прежде всего найдем частные производные целевой функции

Составляющие антиградиента должны быть взяты с обратным знаком

Выделим столбец А под переменную h, столбцы В и С — под х12, столбцы D и Е — под составляющие антиградиента, столбцы F и G — под х1нов2нов , столбец Н — под целевую функцию u, столбец I — под переменную D.

Приведем таблицу формул в соответствующих ячейках для первых двух итераций в строках 21 и 22.

Ссылка на основную публикацию
Adblock
detector