Оптимизация. Методы многомерного поиска
Введение
Вопросы и ответы для государственного экзамена (кафедра САПР) - файл metoda.doc
Метод случайного поиска в живой природе Метод случайного поиска относится к группе итерационных методов минимизации. Итерационные методы минимизации функции F x состоят в построении последовательности векторов, то есть точек x 0 , x 1 , Любой такой метод называется методом спуска. Естественно, должна быть обеспечена сходимость. Иными словами, рассматриваются методы, позволяющие получить точку минимума за конечное число шагов, или приблизиться к ней достаточно близко при соответствующем числе шагов. Дето в том, что теоретически все сходящиеся методы этим свойством обладают, но практически близость к минимуму в задачах большой размерности органичивается ошибками вычислений. В этой связи необходимо вести вычисления с самой большой возможной точностью. Для построения итерационной последовательности необходимо выбрать начальное приближение x 0. В задачах с ограничениями это должна быть допустимая точка, а в задачах без ограничений теоретически любая точка. Однако целесообразно использовать всю имеющуюся информацию о поведении целевой функции F x , чтобы выбрать x 0 поближе к точке минимума. После того, как начальное приближение получено, прежде чем перейти к следующей точке нужно принять два решения:. Выбрать направление, по которому пойдем из x 0 в точку с меньши значением целевой функции направление спуска. Определить величину шага по направлению спуска. При этом могут использоваться одна последняя или две последниее или более из уже полученных точек. Для задач безусловной минимизации любое напрвление является возможным никакие ограничения не мешают , но далеко не все направления приемлемы. Нас могут интересовать только те направления, которые обеспечивают убывание целевой функции, хотя бы при достаточно малом шаге. Здесь g - градиент функции, вычисленный в точке х. Итак, направление спуска должно составлять острый угол с антиградиентом. Этот вывод справедлив и для задач с ограничениями, но там ещё дополнительно требуется, чтобы при достаточно малом шаге не нарушалось ни одно из ограничений. Все такие направления называются подходящими приемлемыми. Методы спуска, позволяющие получать последовательно подходящие направления называются методами возможных направлений. Это широкий класс методов, многие из которых имеют собственные названия. Это могут быть методы нулевого порядка прямые методы , методы первого порядка градиентные методы и методы второго порядка, в которых используется вторые частные производные целевой функции. Всё зависит от конкретной задачи и той информации, которая доступна для использования при оптимизации. Вообще говоря, методы второго порядка при наименьшем числе шагов приводят к точкам, достаточно близким к точкам минимума. Однако это не означает, что они являются наиболее эффективными с точки зрения временных затрат. Целевая функция может быть такой сложной, что вычисление её вторых частных производных требует слишком много времени и оказывается лучше сделать несколько малых шагов в смысле уменьшения целевой функции , но при малом объёме вычислений, чем один большой шаг при большом объёме вычислений. Таким образом, невозможно выделить какой-то один метод, пригодный в любом случае. Для отыскания метода, наиболее пригодного для оптимизации конкретной функции, могут оказаться необходимыми рациональный подход, опыт, а может быть, и предварительные исследования. Методами прямого поиска называются методы, в которых используются только значения функции и не используются её производные градиент и матрица Гессе. Таким образом, они относятся к методам нулевого порядка. Если известно градиентное направление, то относительно любого направления можно установить, является ли оно улучшающим по знаку его скалярного произведения на градиент. Если же не известно градиентное направление, то относительно любого направления ничего не ясно, если пробный шаг по нему был не удачным, так как всегда можно предположить, что этот шаг был велик. Другими словами, если есть возможность вычисления градиента, то этой возможностью пренебрегать не следует, так как методы прямого поиска, как правило, менее эффективны, чем методы первого и второго порядка. Однако в некоторых случаях методы первого и второго порядка применить не удаётся, например, из-за разрывности функций и производных. Более того, возможны задачи, в которых целевая функция в явном виде не задана и для вычисления её значений приходится решать дополнительно уравнения, в том числе и дифференциальные, или системы уравнений, относящихся к различным подсистемам некоторой системы. В этих случаях не только аналитическое, но даже численное определение производных оказывается очень сложным и даже невозможным. Другим случаем, когда методы прямого поиска могут конкурировать с градиентными, является случай наличия локальных минимумов и несвязных допустимых областей. Различные алгоритмы прямого поиска основаны на идее обследования окрестности выбранной точки путём пробных шагов в нескольких направлениях. Это могут быть, например, координатные направления. При этом последовательно меняется по одной координате исходной точки. После того как найдено приемлемое направление, в этом направлении делаются постепенно увеличивающиеся шаги, пока целевая функция в этом направлении не перестанет убывать. Если из некоторой точки уже не удаётся сделать шаг большой длины в данном направлении, то уменьшают шаг. Если шаг становится малым, но в данном направлении уменьшить целевую функцию не удаётся, то работа с направлением закончена и нужно найти другое направление. Для этого снова обследуется окрестность полученной точки и т. Фаза обследования может выполняться различным образом, поэтому и методов прямого поиска много. Без существенного усложнения фазы обследования окрестности промежуточных точек эти методы так же, как и градиентные могут "застревать" в точках локальных минимумов и в оврагах. Другая идея прямого поиска состоит в отказе от последовательного поиска, то есть. Это идея так называемого случайного поиска. Существует много алгоритмов случайного поиска, но все они так или иначе основаны на случайном выборе точек из допустимой области. Если нет никакой информации об улучшающих направлениях и никакая часть допустимой области не имеет преимущества, то принимается равная вероятность, иначе могут быть выделены более вероятные направления например, в алгоритмах с самообучением. Случайный поиск, как и прочие прямые методы, чаще всего не имеющие математического обоснования, можно применять в особо сложных случаях "не от хорошей жизни" , к которым, помимо уже описанных, можно отнести задачи с дискретными переменными и смешанные задачи с непрерывными и дискретными переменными. При наличии ограничений общего вида для всех прямых методов, в том числе и, может быть даже особенно для случайного поиска, проблемой является получение не то что подходящего, а просто допустимого направления или точки допустимой области. Метод случайного поиска использует для выявления предпочтительных состоянийпробные смещения от текущей точки в случайных направлениях. Действие каждого из этих операторов может привести к одному из двух результатов: В более сложных случаях алгоритмы случайного поиска обладают свойством адаптивности, реализуемом с помощью запоминания как траектории поискового процесса значений поисковых переменных и целевых функций, а также соответствующих ограничений , так и параметров самого алгоритма величины и направления поискового шага, глубины памяти и т. При собственно поисковой оптимизации существует задача определения момента, когда поиск следует завершить. Поскольку значение экстремума целевой функции a priori неизвестно, определять этот момент с помощью задания величины допустимого отклонения от цели невозможно. Но это можно делать по достижению числом последовательных неудачных поисковых шагов или проб некоторого заранее определенного предела. Последнее можно интерпретировать как признак того, что поиск производится вблизи экстремального значения целевого критерия. Простейший пример метода случайного поиска рассмотрен выше. В более сложных вариантах этот алгоритм обладает свойством адаптивности, реализуемом с помощью запоминания как траектории поискового процесса значений поисковых переменных и целевых функций, а также соответствующих ограничений , так и параметров самого алгоритма величины и направления поискового шага, глубины памяти и т. Именно это свойство делает его весьма эффективным средством решения сложных экстремальных задач самого различного типа. Адаптивный случайный поиск по определению всегда содержит, помимо вероятностной, существенную регулярную составляющую. Это может, в частности, выражаться в различии вероятностей выбора величин приращений по каждой из координат поискового пространства в ненулевой глубине памяти алгоритма адаптации и т. Память алгоритма как основа классификации методов поисковой оптимизации Любая схема поисковой оптимизации представляет собой контур, содержащий, как. Выходом блока вычисления целевой функции является ее скалярная величина Q X. Этот процесс останавливают извне, когда считают, что достигнут достаточно успешный результат. Очевидно, что проблема построения зависимостей Q X для конкретных приложений выходит за рамки теории поисковой оптимизации, и решается всегда средствами соответствующих прикладных наук. Как представляется, к основным особенностям такого алгоритма можно отнести следующие:. Опыт, накапливаемый в процессе поиска экстремума оптимизируемой целевой функции, является основой для введения механизма адаптации алгоритма A, обуславливающего возможность кардинального улучшения эффективности поисковых характеристик последнего. FAQ Обратная связь Вопросы и предложения. Fragga Опубликованный материал нарушает ваши авторские права? Московский государственный институт радиотехники, электроники и автоматики технический университет. Введение Метод случайного поиска относится к группе итерационных методов минимизации. После того, как начальное приближение получено, прежде чем перейти к следующей точке нужно принять два решения: Методы прямого поиска Методами прямого поиска называются методы, в которых используются только значения функции и не используются её производные градиент и матрица Гессе. Метод случайного поиска Метод случайного поиска использует для выявления предпочтительных состоянийпробные смещения от текущей точки в случайных направлениях. Адаптивный случайный поиск Простейший пример метода случайного поиска рассмотрен выше. Как представляется, к основным особенностям такого алгоритма можно отнести следующие:
Многократно отмечавшиеся выше трудности численной реализации общих схем дискретного программирования делают весьма актуальным построение различного рода приближенных методов. В особенности важно это для прикладных задач, часто имеющих большие размеры при специфической структуре матрицы ограничений, что делает применение к ним общих методов неэкономным, а нередко и практически неосуществимым. Во многих подобных ситуациях, особенно когда решение задач носит текущий, оперативный характер, гораздо более ценным является быстрое и гарантированное получение хотя бы приближенного решения, чем получение точного решения через значительное время и притом без полной уверенности в успехе. Кроме того, усилия на доводку приближенного решения до точного оптимума нередко оказываются неоправданными из-за недостаточной надежности исходной информации. Приближенные методы дискретного программирования могут конструироваться двумя принципиально разными путями. Первый из них связан с использованием идеи случайного поиска; такие методы описываются в гл. В наиболее чистом виде идея случайного поиска воплощена в методе, предложенном Пятецким-Шапиро, Волконским, Левиной и Поманским [25]. Другой путь создания приближенных методов, напротив, является чисто детерминированным и заключается в разработке эвристических приемов, максимально использующих специфику задачи. Некоторые такие приемы для задач с фиксированными доплатами описываются в гл. Первый из них основан целиком на использовании случайного поиска, второй сочетает случайный поиск исходных планов с последующей их локальной оптимизацией. По самому своему характеру эти методы являются чисто машинными. В статье Пятецкого-Шапиро, Волконского, Левиной и Поманского [25] был предложен итеративный метод для решения задачи линейного программирования с булевыми переменными. Как отмечают авторы, этот метод навеян идеями теории игр автоматов [2]. Задача ставится обычным образом: Максимизировать при условиях Все коэффициенты предполагаются неотрицательными. Итеративный процесс основан на замене задачи оптимизации решением системы неравенств. Он строится следующим образом. Из некоторых соображений фиксируется число и решается система из неравенств с булевыми переменными. Эта система состоит из ограничений 1. Найдя ее решение, увеличиваем решая новую аналогичную систему, пытаемся найти улучшенный план. Процесс оканчивается, когда решение системы вида 1. Опишем метод итераций для решения системы Начальный набор выбирается произвольным образом. Пусть на шаге процесса получен набор Вычисляем величины После этого, пользуясь случайным выбором, независимо друг от друга изменяем компоненты вектора с одинаковой вероятностью равной где Это приводит к новому вектору для которого проводится следующая итерация. Когда все А обращаются в 0, процесс окончен, решение системы найдено. Указанный метод можно интерпретировать как случайное блуждание, отвечающее некоторой марковской цепи. Состояниями этой цепи являются всевозможные наборы решениям системы отвечают поглощающие состояния. Но, как известно, вероятность попадания из любого начального состояния конечной неприводимой марковской цепи в поглощающее состояние за конечное число шагов равна единице. Тем самым доказана теоретическая сходимость использованного метода итераций. При численном экспериментировании с описанным методом было сосчитано, в частности, несколько примеров, в которых приближенные решения можно сравнить с точными. Так, в примере размером 3X17 при точном значении максимума, равном 14,91, значение было достигнуто за 14 итераций, значение за итераций. В примере при точном значении максимума, равном 20, значение было достигнуто за итерации, значение за итераций тип машины и машинное время не указаны. В этих расчетах величина в 1. В работе Пятецкого-Шапиро, Волконского, Казакевича и Левиной [24] намечено одно усовершенствование описанного метода, позволяющее расширить возможности его применения на реальные прикладные задачи больших размеров. Оно основано на следующих простых соображениях. При решении реальных задач целесообразно искать не один определенный план, а серию близких к оптимальному планов, один из которых будет выбран при окончательном анализе задачи. Далее большую задачу можно разбить более или менее произвольным образом на несколько подзадач и для каждой из них найти серии близких к оптимуму планов. Затем рассматриваются всевозможные комбинации полученных планов и с помощью полного перебора среди них находятся наилучшие для задачи в целом. Кроме того, для упрощения решения системы неравенств 1. Классификация численных методов ГЛАВА 2. Некоторые многоэкстремальные задачи ГЛАВА 3. Другие прикладные задачи ЧАСТЬ II. МЕТОД ОТСЕЧЕНИЯ ГЛАВА 4. Задача целочисленного линейного программирования ГЛАВА 5. Доказательство конечности первого алгоритма Гомори ГЛАВА 6. Алгоритм Данцига ГЛАВА 7. Построение целочисленного правильного отсечения. Модификация третьего алгоритма Гомори ГЛАВА 8. Применение третьего алгоритма Гомори ГЛАВА 9. Некоторые выводы ЧАСТЬ III. Алгоритм Литтла, Мурти, Суини и Кэрел для задачи коммивояжера ГЛАВА Пример и заключительные замечания ГЛАВА Задача теории расписаний для случая двух машин алгоритм Джонсона ГЛАВА Метод последовательных расчетов ЧАСТЬ IV. Случайный поиск с локальной оптимизацией ГЛАВА Некоторые обобщения ЧАСТЬ V. Задачи транспортного типа ГЛАВА Опишем метод итераций для решения системы Начальный набор выбирается. В примере при точном значении максимума, равном 20, значение было достигнуто за итерации, значение за Теорема Гомори и Баумоля.
Сколько должны идти месячные после медикаментозного аборта
Тихая мышь для компьютера
Расписание автобусов 337 балашиха москва
Решите систему уравнений 4х 1
Через сколько дней открываются глазау щенков