Green-sell.info

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

Метод сканирования оптимизация

МЕТОД СКАНИРОВАНИЯ;

ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ

Методы решения нелинейных задач оптимизации.

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

1. По размерности решаемой задачи: одномерные и многомерные.

2. По способу формирования шага многомерные методы делятся на следующие виды:

2.2. Безградиентные: с поочередным изменением переменных и с одновременным изменением переменных.

2.3. Случайного поиска: с чисто случайной стратегией и со смешанной стратегией.

3. По наличию ограничений.

3.1. Без ограничений (безусловные).

3.2. С ограничениями (условные):

• с ограничениями типа равенств;

• с ограничениями типа неравенств;

Методы одномерной оптимизации являются базой для не­которых «многомерных» методов. В многомерной градиентной оптимизации строится улучшающая последовательность в зависимости от скорости изменения критерия по различным направ­лениям. При этом под улучшающей последовательностью пони­мается такая последовательность х, x1, . хi,. , в каждой точке которой значение критерия оптимальности лучше, чем в преды­дущей. В безградиентных методах величина и направление шага к оптимуму при построении улучшающей последовательности формируется однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента). Случайные методы используются в задачах высокой размерности. Многомерная условная оптимизация учитывает ак­тивные ограничения, выраженные в виде равенств и неравенств. В каждом из рассмотренных направлений имеется большое число методов, обладающих своими достоинствами и недостатками, ко­торые зависят прежде всего от свойств тех функций, экстремум которых ищется. Одним из сравнительных показателей качества метода является количество значений функции, которое нужно вычислить для решения задачи с заданной погрешностью. Чем это число меньше, тем при прочих равных условиях эффективнее метод.

Метод заключается в последовательном переборе всех значений а £ х £ b с шагом e (погрешность решения) с вычислением крите­рия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи х*.

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

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

.

На первом этапе сканирование осуществляют с крупным шагом, затем отрезок, внутри которого получено наибольшее значение — R(x), разбивается на более мелкие отрезки, ищется новый отрезок, внутри которого находится уточненное значение максимума. Он (новый отрезок) опять делится на более мелкие и т.д., до тех пор, пока величина отрезка, содержащего максимальное значение R(x), не будет меньше заданной погрешности. Главный недостаток этого вари­анта метода — возможность пропуска «острого» глобального максимума R(x).

Алгоритм метода обратного переменного шага.

Дата добавления: 2015-07-23 ; просмотров: 5771 ; Нарушение авторских прав

Новокузнецк

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

Сибирский государственный индустриальный университет

Кафедра информационных технологий в металлургии

АЛГОРИТМЫ И ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

Методические указания к выполнению лабораторно-практических работ
по курсу «Оптимизация в технике и технологиях»

Специальности: «Информационные системы и технологии» (071900), специализации «Прикладное математическое и программное обеспечение»,
по курсу «Методы оптимизации в металлургии»

Специальности: «Металлургия черных металлов» (110100),

специализации «Информационные технологии и предпринимательство
в металлургии» (110107).

Алгоритмы и примеры решения задач одномерной оптимизации: Метод. указ./ Сост.: С.П Мочалов, И.А. Рыбенко.: СибГИУ.- Новокузнецк, 2004.- 18с., ил.

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

Предназначены для студентов специальности «Информационные системы и технологии» (071900), специализации «Прикладное математическое и программное обеспечение» и «Металлургия черных металлов» (110100), специализации «Информационные технологии и предпринимательство в металлургии» (110107).

Рецензент — кафедра систем автоматизации (зав. кафедрой С.М.Кулаков)

Печатается по решению редакционно-издательского совета университета.

1. ОБЩИЕ ПОЛОЖЕНИЯ

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

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

Постановка задачи одномерной оптимизации заключается в нахождении точки х * , в которой целевая функция f(х * ) принимает минимальное (максимальное) значение. Функция f(x) имеет локальный минимум в точке х 0 , если при e>0 существует окрестность [x-e; x+e ], такая, что для всех значений х в этой окрестности f(x) больше f(x * ). Функция f(x) имеет глобальной минимум в точке х * , если для всех х справедливо неравенство f(x) >f(x * ).

Читать еще:  Оптимизация диска сколько проходов

Аналитический анализ функции. Классический подход к задаче нахождения экстремума функции состоит в поиске условий, которым они должны удовлетворять. Необходимым условием экстремума в точке x * является равенство нулю первой производной, т.е. требуется решить уравнение f ’ (x)=0.

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

С целью получения более определенных выводов требуется расчет значений вторых производных в точках, удовлетворяющих уравнению равенства нулю первой производной. При этом доказано, что минимуму функции соответствует положительной значение второй производной (f ’” (x)>0), а максимальному – отрицательное (f ’” (x) * — минимуму функции на исходном отрезке. Методы оптимизации отличаются друг от друга лишь различным выбором точек на начальном интервале неопределенности: в методе половинного деления – число Е>0 – наименьший сдвиг по х, при котором еще можно отличить f(x) и f(x+Е); в методе золотого сечения – величина ; в методе Фибоначчи используются числа Фибоначчи.

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

На этапе установления границ интервала на основе априорных данных или правил исключения строится относительно широкий интервал [a, b], содержащий точку оптимума x * . Обычно поиск граничных точек такого интервала проводится с помощью эвристических методов поиска, хотя в ряде случаев можно также использовать методы экстраполяции. Так как минимум x * на [a, b] неизвестен, то этот интервал называется интервалом неопределенности. Для унимодальной функции f(x) интервал неопределенности может быть сокращен с помощью вычисления значений функции в двух точках x, y Î [a, b]. При этом возможны два случая. Если f(x) > f(y), то новым интервалом неопределенности является [x, b], поэтому переприсвоение границ интервала на итерациях для этого случая осуществляется по правилу ak+1 = xk, а bk+1 = bk. При выполнении условия f(x) £ f(y), новым интервалом будет [a, y] и, соответственно, ak+1 = ak, bk+1 = yk.

2.1.1 Метод сканирования

Сканирование или равномерный поиск является примером одновременного поиска, когда точки, в которых вычисляется значение функции, выбираются заранее. Начальный интервал неопределенности [a1, b1] делится на отрезки величиной d сеткой из точек a1 + kd для k = 1, …, n. Тогда b1 = a1+ (n — 1)d. Затем функция f(x) вычисляется в каждой из n точек сетки и определяется , в которой она имеет наименьшее значение. Если f(x) унимодальна, то минимум принадлежит интервалу [ — d , + d].

После n вычислений функции интервал [a1, b1] сокращен до длины 2d. Так как n = [(b1a1)/d] — 1, то для достижения более высокой точности нахождения минимума необходимо большое число вычислений функции.

Алгоритм метода сканирования.

Начальный этап. Выбрать шаг разбиения d> 0 и начальный интервал [a1, b1]. Задать k = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Вычислить значение х=a1 + kd и f(x). Если k=n, то перейти к шагу 2, иначе положить k=k+1 и вернуться к шагу 1.

Шаг 2. Выбрать минимальное значение функции f(x) и соответствующее ему значение . Минимум функции находится в интервале [ -d , + d].

Пример расчета экстремума функции методом сканирования.

Постановка задачи. Определить экстремум функции f(x)=(x-2) 2 +7.

Определение экстремума аналитически. Необходимым условием существования экстремума является равенство нулю первой производной. Решаем уравнение f’(x)=2(x-2)=0. Полученная точка х*=2 является точкой минимума, так как вторая производная в данной точке (x*) =2>0.

Реализация метода сканирования. Выбираем достаточно большой начальный интервал [-100, 100] и количество разбиений n=10. Результаты расчетов точек и значений функции представлены в таблице 2.1.

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

Практика 1

Метод сканирования заключается в последовательном переборе всех значений a≤x≤b с шагом ε (погрешность решения) с вычислением критерия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи x*.

Достоинство метода сканирования состоит в том, что можно найти глобальный максимум критерия, если R(x) – многоэкстремальная функция.

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

На практике можно реализовать одну из основных модификаций метода:

Читать еще:  Расчет и оптимизация сетевой модели

1) последовательное уточнение решения (сканирование с постоянным шагом);

2) сканирование с переменным шагом.

Рис. Модифицированный метод сканирования:

1 – интервал, включающий в себя искомый максимум функции после первого этапа сканирования (исходный участок разбит на 5 участков );

2 – то же, после второго этапа.

На первом этапе сканирование осуществляется с крупным шагом, затем отрезок, внутри которого получено наибольшее значение R(x), разбивается на более мелкие отрезки, ищется новый отрезок, внутри которого находится уточнённое значение максимума.

Новый отрезок опять делится на более мелкие отрезки и так далее до тех пор, пока величина отрезка, содержащего максимальное значение R(x), не будет меньше заданной погрешности. Главный недостаток этого варианта метода – возможность пропуска строгого глобального максимума.

  1. Метод деления отрезка пополам.

Метод основан на делении текущего отрезка [a,b], где содержится искомый экстремум, на две равные части; с последующим выбором в качестве следующего текущего отрезка одной из половин, в которой локализуется максимум,. Экстремум локализуется путём сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на Е/2, где Е – погрешность решения задачи оптимизации.

Если R (х+Е/2)>R(x-Е/2), то максимум располагается на правой половине текущего отрезка [a,b], в противном случае – на левой. Процесс поиска завершается при достижении отрезка [a,b] величины заданной погрешности Е. К недостаткам метода относится его работоспособность только для одноэкстремальных функций R(x). (Функция R(x) называется одноэкстремальной, если содержит один экстремум того типа, который мы ищем в задаче). В других случаях, при сравнении двух критериев оптимальности в соседних точках, невозможно правильно выбрать следующий интервал, где находится максимум.

Существует и другой вариант алгоритма, заключающийся в следующем. После нахождения середины отрезка в одной из половин, находят среднюю точку и, сравнивая значения функций в этих точках, распределяют, в какой из половинок находиться экстремум. Если R(C1) R(C2), то берут новую точку в середине правой половины и в ней вычисляют функцию. В зависимости от сравнения значений функций в точках С3 и С1 и выбирают новый отрезок [с1,b] или [c2, c3] и т.д.

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

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

Пример: Дана функция R(x)=DSin(Ax+C), где коэффициенты имеют следующие значения: А=1,0; В=1,0; С=1,0; D=1,0. Найти максимум функции на следующем интервале: [-1;2]. Ошибка задается по х: Е=0,05

Середина отрезка х = 0,5

Значения критерия R=0.9975

Следовательно, искомый максимум лежит в правой половине отрезка, то есть теперь отрезком является [0.5;2].

Далее приведем координаты середины отрезков с номером итерации, значение критерия в них и указывается новый отрезок (правый или левый).

Метод сканирования

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

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

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

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

Известно, что необходимым условием существования экстремума дифференцируемой функции f(x) является выполнение равенства f¢(х) = 0. Точка х, удовлетворяющая данному условию, называется точкой стационарности. Достаточнымусловием существования минимума в точке стационарности является выполнение неравенства f¢¢(х)>0, а максимума — f¢¢(х) 3 – x + e — x на предмет существования экстремумов.

Вначале проведем графическое исследование. Построим график функции f(x) (рис. 1.6.1-2). Из графика видно, что f(x) имеет две точки минимума: х1 и х2, причем точка х1– точка глобального минимума. Исходя из графика, можно принять следующие отрезки неопределенности: для точких1[-4;-3], а для точки х2 [0;1].

Проверим достаточное условие существования минимума на выбранных отрезках:

f¢(x) = 3x 2 – 1 – e -x ; f¢¢ (x) = 6x + e -x ,

f¢(0) 0, f¢¢ (x) > 0 для хÎ[0;1],

f¢(-4) 0, f¢¢ (x) > 0 для хÎ[-4;-3].

Условия существования минимума выполнены, поскольку f¢¢(x) > 0 для всех хÎ[0;1] и хÎ[-4;-3]. Следовательно, функция f(x) является унимодальной на выбранных отрезках.

Задачу одномерной оптимизации можно решить и аналитически. Для Этого следует получить первую производную от целевой функции (в нашем случае f¢(x) = 3x 2 – 1 – e — x ), приравнять ее нулю и решить полученное уравнение. Но тогда возникает задача решения нелинейного уравнения, а это не всегда удается сделать. Кроме того целевая функция может быть задана таблично или не имеет непрерывной производной. Именно в таких случаях применение численных методов оптимизации являются единственно возможным.

Читать еще:  Как оптимизировать приложение на планшете

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

· значения функции f(x) определены в ходе эксперимента;

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

· классические методы поиска оптимального значения не применимы.

Суть методоводномерного поисказаключается в том, что на каждой итерации интервал неопределенности уменьшается и стягивается к точке минимума. Уменьшение отрезка происходит до тех пор, пока на некоторой n-й итерации отрезок неопределенности [bn;an] не станет соизмеримым с заданной погрешностьюe, то есть будет выполняться условие |bn-an|
1 | 2 | 3 | 4 | 5 |

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.028 сек.)

Метод сканирования оптимизация

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

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

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

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

Метод прямого сканирования

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

Рисунок 2.4 — Локализация экстремума методом сканирования:

а — геометрическая интерпретация; б — блок-схема алгоритма

Метод половинного деления

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

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезке с точностью . Отрезок делится пополам и вычисляются значения функции Q (x1) = F1 и Q (x2) = F2 в точках

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

Рисунок 2.5 — Метод деления отрезка пополам:

а — геометрическая интерпретация; б — блок-схема

Метод «золотого сечения»

Гораздо эффективнее, с точки зрения уменьшения затрат на вычисления, метод «золотого сечения»: интервал неопределенности делится не пополам, как в методе дихотомии, а в определенном иррациональном соотношении Это соотношение выполняется при .

Метод заключается в том, что по заданным a и b как можно точнее определяется значение внутренней точки x1 (см. рис. 2.6, б) по формуле

Рисунок 2.6 — Метод «золотого сечения»:

а — золотое сечение; б — геометрическое представление

Точка x2 определяется как точка,симметричная точке x1 на отрезке (ab).

На основе анализа значений F1 = Q (x1) и F2 = Q (x2) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий уни-модальности Q (u). Далее мы определим симметричную точку внутри новых границ, вычисляем значение Q в этой точке, проводим анализ и т.д. до тех пор, пока разность между симметричными точками внутри интервала неопределенности больше . Блок-схема алгоритма метода «золотого сечения» представлена на рис. 2.7.

Рисунок 2.7 — Блок-схема метода «золотого сечения»

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

Метод, использующий числа Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением

При большом «k» отношение соседних чисел Фибоначчи близко к отношению «золотого сечения».

Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее от , число вычислений значений функции Q (u).

По заданному определяется количество вычислений n и соответствующее ему число Фибоначчи Fn, исходя из соотношения

В остальном схема метода близка к методу «золотого сечения» в котором значение x1 и x2 (см. рис. 2.8) определяются отношением соответствующих чисел Фибоначчи.

Рис. 2.8— Блок-схема метода Фибоначчи

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×