Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Общая характеристика и классификация методов многомерной оптимизации

Читайте также:
  1. I. ОБЩАЯ ХАРАКТЕРИСТИКА УЧЕБНО-ОЗНАКОМИТЕЛЬНОЙ ПРАКТИКИ
  2. I. Характеристика проблемы
  3. I. Характеристика проблемы, на решение которой направлена подпрограмма
  4. I. Характеристика проблемы, на решение которой направлена Программа
  5. I. Характеристика проблемы, на решение которой направлена Программа
  6. I.2. Классификация усилителей.
  7. I.8.3. Характеристика клеточного воспалительного ответа

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

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

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

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

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

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

При разработке процедуры многомерного поиска всегдавозникает три вопроса:

1 Откуда (из какой точки х0 ϵ X*) нужно начинать поиск?

2. В каком направлении необходимо двигаться в фактор­ном пространстве?

3. Когда необходимо прекратить поиск?

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

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

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

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

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

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

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

2. Методы покоординатного спуска (метод Гаусса-Зейделя) (иногда их называют релаксационными методами). Эти методы преду­сматривают последовательную циклическую оптимизацию по каждой из варьируемых переменных х1.

Направление движения к экстремуму выбирается пооче­редно вдоль каждой из координатных осей управляемых пара­метров х1

Рассмотрим процесс поиска экстремума целевой функции W(X) для n-мерной задачи оптимизации при X = 1, х2,…хn). Предположим, что осуществляется поиск минимума функции W(х). Тогда улучшению ее на шаге (k + 1) поиска будет соответствовать условие

Из выбранной начальной точки поиска Х0 выполняется пробный шаг h0 в положительном направлении одной из координатных осей (обычно вдоль оси первого управляемого пара­метра х1). В новой точке Х1 с координатами Х1 = (x1,1=x1,0+h0,x2,1=x2,0,…xn,0=xn,0) вычисляется значение целевой функции W(Х) и сравнивается с ее значением в начальной точке W(X0). Если W(X1) < W(X0) это направление принимается для осущест­вления дальнейшего пошагового движения к экстремуму в соот­ветствии с выражением

В противном случае производится, возврат в исходную точку Х0 и движение осуществляется в отрицательном направ­лении оси х1:

Движение в выбранном направлении оси х1 выполняется до тех пор, пока целевая функция улучшается, т.е. выполняется условие (6.97). При его нарушении на шаге (k + 1) производится возврат в точку x1,k, определяется направление движения вдоль следующей координатной оси x2 и совершаются спуски в направлении, обеспечивающем улучшение целевой функции.

После осуществления спусков вдоль всей п осей первый цикл спусков N= 1 завершается и начинается новый цикл N= 2. Если на очередном цикле движение оказалось невозможным ни по одной из осей, тогда уменьшается шаг поиска:

Далее поиск экстремума продолжается с уменьшенным шагом. Условие окончания поиска -

При достижении условия (6.102) поиск прекращается, и полученная точка Хk принимается в качестве искомой экстре­мальной точки X. Точка Xk при этом находится в некоторой ма­лой окрестности точки локального экстремума X*, ограничивае­мой задаваемым минимальным значением шага поиска hmin.

Параметрами алгоритма покоординатного спуска являются ho, hmin и γ. Алгоритм обеспечивает сходимость к решению X* за конечное число итераций, если функция W(X) имеет первую и вторую производные в окрестности экстремума.

 

Пример поиска экстре­мума методом покоординат­ного спуска для двумерной задачи при Х=(х12) пред­ставлен на рис. 6.22, где пока­заны два цикла спусков вдоль осей х1 и х2 Линии равных уровней целевой функции W(X) обозначены Н1..., Н4, причем Н1< Н2< Н3< Н4, а минимум ее соответствует точке X*. Траектория поиска изображена жирной линией.

Движение начато из исходной точки X0. При этом в каждом цикле вдоль каждой из осей выполняется несколько шагов. По­сле достижения точки Х1 значение W(X) начинает возрастать, поэтому произошла смена направления движения. На новом на­правлении вдоль оси Х2 движение осуществляется к точке Х2 и первый цикл спусков на этом завершается. Затем циклы повто­ряются, пока не будет выполнено условие прекращения поиска.

3. Метод градиента

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

Градиент всегда сориентирован в направлении наиболее быстрого изменения функции. Градиентное направление является локально наилучшим направлением поиска при максимизации целевой функции, а антиградиентное - при ее минимизации. Это свойство вектора gradW(X) и используется в методе градиента, определяя вид траектории поиска.

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

Движение в пространстве управляемых параметров осу­ществляется в соответствии с выражением

где hk - шаг поиска; Sк - единичный вектор направления поиска

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

Дадим краткое изложение алгоритма поиска минимума целевой функции W(X). В каждой точке траектории поиска Хk, в том числе в исходной точке Х0 определяется градиент целевой

функции gradW(Xk) и единичный вектор направления Sk вы­полняется шаг в пространстве управляемых параметров к точ­ке Хк+1 согласно выражению (6.104) и оценивается успешность поиска на основе неравенства (6.97). При этом вычисляется зна­чение целевой функции W(Xk+1) в точке Хк+1 и сравнивается с ее значением W(Xk+1) предыдущей точке Хk.

Если условие (6.97) выполнено, то шаг поиска успешный, поэтому определяется новое направление движения из точки Хk+1 и выполняется следующий шаг в точку Хk+2

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

где γ в коэффициент уменьшения шага: 0 <γ< 1, и повторить движение в том же направлении, но с меньшим шагом.

Условия окончания поиска методом градиента имеют вид

где ε - малая положительная величина.

При выполнении одного из условий: (6.107) или (6.107)-поиск прекращается, а полученная точка Хk принимается в каче­стве искомой точки экстремума X. Если поиск прекращен по ус­ловию (6.107), то считается, что точка Хk находится в некоторой малой окрестности точки X*, ограничиваемой величиной hmin

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

На рис. 6.23, а показан пример поиска минимума целевой функции для двумерной задачи методом градиента. Линии рав­ных уровней целевой функции обозначены H1..., H7, причем H12<...<Н7 а траектория поиска проходит через точ­ки X0, Х1, Х2 ….

 

Движение в градиентном направлении по определению должно приводить к улучшению функции качества Если это не так и W(Xn+1) < W(Xn), можно предположить, что поиск просто «проскочил» оптимальную точку. В этом случае следует уменьшить величину шага и повторить вычисления.

 

 

Билет 26. Вопрос 1. Элементы теории надёжности технических объектов. Определение надёжности и составляющие свойства надёжности: безотказность, долговечность, сохраняемость, ремонтопригодность. Законы распределения случайных величин.

4.1.1. Надежность объектов как комплексное свойство

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

Надежность (в соответствии с ГОСТ 27.002-89) – это свойство объекта сохранять во времени в установленных преде­лах значения всех параметров характеризующих способность выполнять требуемые функции в заданных режимах и условиях
применения, технического обслуживания, ремонтов, хранения и транспортировки.

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

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

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

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

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

Сохраняемость - это свойство объекта сохранять значение показателей безотказности, долговечности и ремонтопригодности в течение и после хранения и (или) транспортирования.

Случайной величиной (СВ) называется переменная величи­на, значения которой зависят от случая, т.е. величина, способная принимать различные случайные значения.

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

 

2. Распределение непрерывных случайных величин Для непрерывной СВ понятие интегральной функции распределения имеет тот же смысл, что и для дискретной. Однако непрерывная величина X может принимать любые значения, находящиеся в некотором интервале [а; Ь], поэтому вероятность того, что она примет какое-либо определенное значение х, равна нулю, так как число возможных случаев бесконечно.


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


Читайте в этой же книге: Билет №12 | Билет 14. вопрос 1. Методы многомерной оптимизации: покоординатного спуска и градиентный. | Метод динамического программирования | Билет 16. Вопрос 1. Регулярные методы оптимизации: симплекс-метод решения задач линейного программирования. | Вопрос 2. Прямые методы оптимизации: общая характеристика и примеры пассивных и последовательных стратегий поиска. | Билет 18. Вопрос 1. Прямые методы оптимизации: методы однородных пар и дихотомии, формулы для интервала неопределённости. | Вопрос 2. Классификация математических моделей в зависимости от степени абстрагирования от структуры и физических свойств объекта. | Билет 20. Вопрос 1. Структура (состав) математической модели. | Билет 24. Вопрос 1. Электрическое аналоговое моделирование. Исследование моделей из сплошных проводящих сред и сетки сопротивлений для моделирования стационарных полей. | Метод золотого сечения. |
<== предыдущая страница | следующая страница ==>
Билет 25. Вопрос 1. Электрическое аналоговое моделирование. Исследование моделей из сплошных проводящих сред и сетки сопротивлений для моделирования стационарных полей.| Вопрос 2. Методы оптимального проектирования. Критерии оптимальности технических объектов. Постановка задач оптималь­ного проектирования.

mybiblioteka.su - 2015-2024 год. (0.012 сек.)