1. 13.1 Метод общего поиска
2. 13.2 Метод половинного деления (разделение отрезка пополам)
3. 13.3 Метод дихотомии
4. 13.4 Метод "золотого сечения"
5. 13.5 Метод Фибоначчи

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

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

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

1) если проектный параметр один, то обычно ограничения связаны с его значениями, то есть область проектирования сужается до отрезке исследования [a, b];

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

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

Численные методы, которые ориентируются на решение задач безусловной оптимизации, можно разделить на три класса:

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

Рисунок 13.1 - унимодальных целевая функция

Рисунок 13.2 - Целевая функция с локальным и глобальным оптимумом

- градиентные методы, в которых используются точные значения первых производных f (x)

- методы второго порядка, в которых наряду с первыми производными используются также другие производные функции f (x).

Задача одномерной оптимизации ставится таким образом: значение параметра Х целевой функции f (x), который называют проектным параметром, находятся на интервале исследования [a, b]. В процессе поиска оптимума целевой функции этот интервал, который называется интервалом неопределенности, постоянно уменьшается (сужается), поэтому методы одномерной оптимизации иногда называют методами сужения интервала неопределенности.

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

Рисунок 13.3 - однопараметрическим целевая функция

Рисунок 13.4 - двухпараметрического целевая функция

Некоторые алгоритмы оптимизации приспособлены к поиску максимума, а другие - для поиска минимума.

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

Рисунок 13.5 - изменением знака целевой функции на противоположный задача на минимум превращается в задачу на максимум

Общая постановка задачи для методов одномерной оптимизации относится следующим образом: пусть параметр Х находится нa отрезке [a, b], а целевая функция унимодальнa в области, которую исследуем. Большинство численных методов одномерной оптимизации - это методы сужения отрезка, а именно: метод разделения отрезке пополам, метод дихотомии, метод золотого сечения, метод Фибоначчи.

В процессе одномерной оптимизации целевой функции на ЭВМ можно выделить два этапа:

1) установление границ отрезка, на котором реализуется процедура поиска оптимума;

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

Первый этап реализуется с помощью эвристических методов поиска и очень сложно. Второй - называют правилом исключения отрезков, реализуют алгоритм поиска, позволяет найти точку оптимума путем последовательного исключения частей исходного ограниченного отрезка [a, b], то есть с помощью итерационных алгоритмов. В качестве условия окончания итерационного процесса используется момент, когда подинтервал оставшийся уменьшится до достаточно малых размеров (обычно для этого задают значение заданной погрешности вычисления ).

13.1 Метод общего поиска

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

Рисунок 13.6 - метод общего поиска

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

.

Чтобы получить значение f = 0,01, необходимо вычислить целевую функцию в 199 точках, а при f = 0,001 N = 1999. Отсюда видно, что эффективность этого метода при уменьшении интервала неопределенности быстро падает. Напрашивается другой вариант: чтобы получить f = 0,01, необходимо вычислить сначала функцию в 19 точках и получить f = 0,1, а затем вычислить еще 19 значений функции на сокращенном интервале неопределенности, получить f = 0,01, сделав при этом всего 38, а не 199 вычислений. Таким образом, при некоторой изобретательности эффективность поиска можно резко увеличить.

13.2 Метод половинного деления (разделение отрезка пополам)

Суть метода заключается в постоянном делении отрезка исследования целевой функции [a, b] пополам и определении на нем координат трех точек х1, х2, хm. Причем значение их определяются как:

L = ba, , .

Рисунок 13.7 - геометрическая интерпретация метода половинного деления

точки , Разделяют отрезок [a, b] на четыре равные части (рис. 13.6), вычисляем значение целевой функции Затем сравниваем значение и , если , То исключаем из исследования отрезок и положим . Тогда средней точкой нового отрезка [a, b] становится . но если , То сравниваем значение целевой функции и ; если , То исключаем отрезок , положим ; если , То исключаем отрезок и , положим , То есть формируем новый отрезок исследования. Вычисляем L = b - a, если , Если нет, то опять возвращаемся к началу.

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

Рисунок 13.8 - Схема алгоритма метода половинного деления

Этот метод отличается большой эффективностью.

13.3 Метод дихотомии

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

Рисунок 13.9 - обозначение, используемых в методе дихотомии

Если значение целевой функции при х1 больше, чем при х2, то новый интервал неопределенности равен Z1 = z1 + z2. В противном случае он определяется выражением Z2 = z2 + z3. Задача состоит в том, чтобы одновременно минимизировать Z1 i Z2, удовлетворив условиям

z1 + z2 + z3 = Z,

z1> 0,

z2> 0,

z3> 0.

С равенства можно исключить z2. тогда

Z - z3 = min, Z - z1 = min.

Так как величина Z задана, то правые части этих уравнений будут тем меньше, чем больше z1 i z3. Итак, оптимум соответствует условию

z1 = z3 = 0,5Z.

Но тогда z2 = 0, что противоречит условию z2> 0.

Рисунок 13.10 - метод дихотомии

Пусть z2 имеет некоторое очень маленькое значение . Тогда с z1 i z3 вычтем по . В результате после вычисления первой пары значений целевой функции при близких значениях х интервал неопределенности сузится, как показано на рис. 13.10, и коэффициент деления будет равен

.

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

13.4 Метод "золотого сечения"

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

Рисунок 13.11 - обозначение, используемых в методе золотого сечения

Суть этого метода заключается в следующем. Интервал неопределенности делится на две неравные части, отношение длины большего отрезка к длине всего интервала равна отношению длины меньшего отрезка к длине большего отрезка. На рис. 13.11 показан интервал неопределенности Z, который состоит из отрезков z1 i z2, отношение длин которых определяется правилом золотого сечения.

Кроме того, z1 + z2 = Z. С первого уравнения следует . Подставив значение Z из второго уравнения и разделив обе части на , получим

Решая это квадратное уравнение, находим для положительного корня значение

На рис. 13.12 показано деления интервала неопределенности в этом отношении и нанесены соответствующие значения целевой функции, которые позволяют уменьшить интервал неопределенности в 1 / 0,618 раз.

Рисунок 13.12 - Метод золотого сечения

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

При n> 2 эффективность метода золотого сечения выше, чем в метода дихотомии, так как при каждом вычислении целевой функции интервал неопределенности сокращается в 1 / 0,618 раз. После вычисления N значений целевой функции коэффициент дробления интервала неопределенности составляет

f = 0,618 N-1.

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

ZJ-2 = ZJ-1 + ZJ, 1

где ZJ длина интервала неопределенности после вычисления J-го значения целевой функции.

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

Рисунок 13.13 - последовательность этапов выбора следующей точки поиска

Истинный минимум находится в точке 1,76322211, где значение функции равно -0, 0972601313.

Рисунок 13.14 - Схема алгоритма метода "золотого сечения"

При разработке программ для решения задач однопораметричнои оптмизации используют следующие соотношения:

13.5 Метод Фибоначчи

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

Предположим, что имеется интервал неопределенности и известно значение функции внутри этого интервала (см. рис. 13.15).

Рисунок 13.15 - унимодальных целевая функция. Геометрическая интерпретация метода Фибоначчи

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

Предположим и , причем , Как показано на рис. 13.15, и эти значения будут фиксированы, если известны и . если находится в интервале , То:

1. Если , То новым интервалом неопределенности будет длиной .

2. Если , То новым интервалом неопределенности будет длиной .

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

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

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

Интервал неопределенности будет иметь длину , Следовательно, (Рис. 13.16, нижняя часть).

Рисунок 13.16 - геометрическая интерпретация итерационного процесса Фибоначчи

На предварительном этапе точки и должны быть помещены симметрично внутри интервала с на расстоянии от концов этого интервала. Итак, (Рис. 13.16, средняя часть).

Замечания. Из рисунка понятно, что на предпоследнем этапе остается в качестве внутренней точки.

аналогично

. (Рис. 13.16, верхняя часть)

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

Похожие

Комментарии