Основы САПР (CAD,CAM,CAE) - (Кунву Ли)(2004) (951262), страница 55
Текст из файла (страница 55)
Поскольку алгоритм требу- :.~»»чтобы внутренняя часть области допустимых значений была не пуста, он не 1ГйгяГет использоваться для обработки ограничений-равенств'. ,"г''" Если задача требует учеш аграничегшй-равенств, пользуются методом смешанных , штрафных функций, согласна которому в дополненную целевую функцига добавляются 'вне»авве штрафа»»е функции длк ограничений-Равенств и внутренние штрафные функ!ции для ограничений-неравенств. Итак, рассмотрим задачу оптимизации ппп Р(Х) прн условиях (9.1З) 6,(Х) > О г = 1, 2, ..., т. (9.14) Хорошая барьерная функция, создающая «стены» на границах области допустимых значений, имеет следующий вид: 1 В(Х) = —. С,(Х) Заметьте, что значения В(Х) стремятся к плюс бесконечности при приближении Х к границе области изнутри, благодаря чему В(Х) и называется барьерной функцией.
Чтобы учесть все т ограничений (9.14), мы можем просто поставить в формуле (9.15) знак суммирования по б Как и для метода внешних штрафных функций, дополненная целевая функция определяется выражением Р(Х,р) = г(Х)+ рВ(Х), (9 1б) где р — положительное число. Метод внутренних штрафных функций требует решения последовательности задач оптимизации без ограничений для я = О, 1, 2, .
„причем сами задачи даются формулой 1 пцпР(Х,р„) = ппп г(Х)+р 2,' —, ', б;(ХЦ' (9.17) где последовательность положительных р» строго убывает. Оптимальные значения Х» для р» будуг сходиться к реальным оптимальным значениям Х при 1::;- :стремлении р» к нулю. Продемонстрируем эту сходимость на следующем примере. '--., Пример 9.2 Найти миним м нкции (9.15) Р(х,) = — + ~— 1 р» 2 г'2 ' Ч бы учить значения хь прадифференцируем фуггкшгга Р па х, прнравняем права волную нулю и решим получившееся уравнение относительно х. Фу г(х) = -Х (Х Е Я) 2 при славин, что х — 1 > О. Оптимальное решение х' = 1, так что нам остается показать, что промежуточные решения, полученные при помаши внутренн у нних :-;,:, 'штрафных функций, будут стремиться к атому числу. Решение Построим дополненную целевую функцию вида (9.17). Мы должны решить задачу оптимизации без ограничений: .Г! ! пипР(х,р„) = гп(п~-х+р» — .
12 х-1 12 Отсюда находим точку минимума функции Р'. х„=1+ ~2р и значение функции Р в этой точке: -".'Зьмтетьте, что при положительных рв оптимальная точка находится внутри об',-',)дгсти допустимых значений исходной задачи, поскольку она больше единицы ' 'При стремлении р» к нулю точки хв стремятся к х = 1.
Исходная н дополненная :'целевые функции для некоторых значений рв приведены на рис. 9.2. Вели опи«„шная процедура осуществляется численным алгоритмом, начальное значение '~4йэательно должно находиться внутри области допустимых решений. ий Рис, 9.2. Дополненная целевая функция в методе внутренних штрафных функций ,.~ив МЕТОДЫ ПОИСвькв "!~~~~:;4о1гска максимума или минимума целевой функции могут использоваться : " ~~$лу[чсные методы. Эти методы могут быть сгруппированы в три больших класса ":"~(ф~ст,„ЙЗ).
Методы первого класса основываются на вычислениях, методы вто'ргях~,эаасса осуществляют направленный случайный поиск, а методы третьего Ллве4а,являются перечислительными [951. На рис. 9.3 показаны только те мето)гй[:щ~иева, которые эффективны при решении задач оптимизации по несколь, й~Ф~:-,~феменным.
Мы не стали указывать простейшие методы поиска, такие как в1е7$11 Фибоначчи и метод золотого сечения, потому что они применяются глав- ,'м~ф~:'э~разом для одномерных задач. Вычислительные алгоритмы могут быть разделены на две группы. Методы первой группы получают оптимальное решение задачи в явном виде, тогда как методы второй группы подходят к нему косвенно, через решение системы нелиней- ных уравнений, которые образуются при приравнивании нулю градиента целевой функции. Прямые метолы ищут решение, выбирая значения из пространства поиска и оценивая градиент в юулой новой точке.
Эта процедура определяет направление поиска. Идея та же, что при подъеме на холм: нужно найти наилучшую точку, поднимаясь по самому крутому склону. Прямые методы делятся на две категории (рнс. 9.3). Методы первой категории используют саму целевую функцию и ее ггервые производные дг дх,. ~":,:-", Здесь à — целевая функция, а вектор переменных оптимизации Х составлен из !!::, компонент хт В качестве примеров методов из этой категории можно назвать метод скорейшего спуска и метод сопряженных градиентов. Методы из второй катего- рии используют матрицу Гессе, составленную из частных вторых производных д'г дх,дх -':;.„'..'помимо первых производных и значений самой функции.
Ко второй категории относится, в частности, метод Ньютона. Ниже мы обсудим идеи, на которых ос- нованы прямые методы, применимые, вообще говоря, только к ограниченному ',~,'...дебору вхорошихв задач. Подробные сведения о методах и решении задач опти" -'мизации приводятся в учебниках [62, 119, 6, 131[ Прямые методы, основанные на градиентах, во многих случаях оказываются не".'="::. применимы, поскольку они используют сведения о локальном поведении фупк.';:,'::;; йии для перемещения в направлении скорейшего спуска. Направление скорей- ;-:': щего спуска противоположно локальному направлению градиента, поэтому алгоритмы этого типа ведут себя плохо, если функция имеет трудносопостави'ыые масштабы по разным переменным или для нее неудачно заданы ограниче иия.
Двумерная целевая функция„для которой алгоритм скорейшего спуска на -:-;:чинает осциллировать и сходится достаточно медленно, представлена на рис. 9.4. :-:.,'На рисунке показаны контуры постоянных значений целевой функции в дву'.:.: мерном пространстве переменных оптимизации. Градиент перпендикулярен та;:" кому контуру в любой его точке. В результате направление скорейшего спуска на каждой итерации оказывается почти перпендикулярным направлению на минимум. Рис. Р.а. Классификация методов поиска Рис. 9.Е. Осциллируккцее поведение алгоритма скорейшего спуска .Методы скорейшего спуска не учитывают вторые производные, то есть матрицу Гессе целевой функции. Методы Ньютона и модифицированные методы Нъютона, напротив, используют матрицу вторых производных в дополнение к градиенту, Модифицированные методы Ньютона обеспечивают лучшую сходимость для плохо обусловленных задач по сравнению с методами скорейшего спуска, однако 'матрица Гессе в общем случае требует достаточно ресурсоемких вычислений.
.. В'результате, хотя сходимость модифицированных методов Ньютона достаточно '4гысока, на практике они оказываются не слишком эффективны из-за высокой й3оимостн каждой итерации. Эта проблема решается при помоши квазиньюто:,иоъвекцх методов, использующих аппроксимацию матрицы Гессе (на самом деле ' обратной к ней матрицы), которая строится по градиентам на каждой итерации. Квазиньютоновскне методы считаются одними из наиболее эффективных для ' вешания задач на оптимизацию без ограничений. В предыдущем разделе мы по' зцьзади; что задачи с ограничениями могут быть преобразованы к задачам без ог',,'"[раничений.
Поэтому квазиньютоновские методы могут использоваться и для решения задач с ограничениями. .,", ':= Описанные выше методы в большинстве своем сходятся к локальному миниму, му, целевой функции. Если целевая функция не является выпуклой, нет никаких щэаитий, что найденный локальный минимум окажется глобальным. Пеленая ффгкция одномерной задачи с несколькими локалъными минимумами показана гга:рис. 95.
Методы перечисления (перебора) способны решить такую задачу, по'йкольку они сканируют всю область определения целевой функции и проверяют каждую точку. Такие методы просты в реализации, но могут потребовать больцшх вычислений, а в большинстве задач пространство оптимизации оказывается йй1)шком большим, чтобы его можно было проверить целиком.
Методы направдег9гого случайного поиска и вероятностные методы проявляют себя лучше мещйой перечисления в эффективности проверки пространства оптимизации. При ,.этом'с[ни просматривают все пространство, а потому с их помошью можно пы'щ5,щ найти глобальный оптимум. Они хорошо распараллеливаются, что позвог[Еет сократить время вычислений несмотря на то, что по объему они превосходят [[ь(числительные методы. Наиболее популярными вероятностными алгоритмами ядляются алгоритм модельной «закалкиь и генетический алгоритм. Эти два ме::.''-:.тоды мы рассмотрим подробно, потому что они все шире используются для решения задач оптимизации во многих приложениях.
Рио. В.В. примеР нескольких локальных минимумов 9.4. Метод модельной закалки Еше в 1953 году Метрополис с коллегами предложили алгоритм эффективного «моделирования эволюции системы к тепловому равновесию. Почти 30 лет по- 1; требовалось Керкпатрику, Гелатту и Веччи [851 и Перин [311, чтобы понять, что между медленным охлаждением твердого тела и минимизацией функции стон- ! мости комбинаторной задачи на оптимизацшо существует глубокая аналогия, а процесс оптимизации может осуществляться прн помощи критерия Метрополиса.
Заменив потенциальную энергию системы на стоимость и (жализовав алгои ритм Метрополиса при постепенно понижающейся температуре, Керкпатрик с коллегами смогли получить алгоритм комбннаторной оптпмизапии„который они называли методом модельной закгики (яти1агегг аппеаг(пй). С тех пор исследования этого алгоритма и его приложений образовали отдельную область знания [971.
! ,-';:, 9.4.1. Комбинаторная оптимизация В 50-х и 60-х гг. основные прорывы в исследованиях по оптимизации были связаны с новыми алгоритмами поиска оптимумов функций непрерывно изме,:". няюшихся переменных. Во многих важных теоретических и практических задачах приходится выбирать «лучшееь решение из большого набора возможных решений. Если переменные оптимизации могут принимать только некоторые днскретные значения, задача оптимизации будет заключаться в том, чтобы найти '!; ' лучшую комбинацию этих значений. Такие задачи называются задачами комбиноторной оптимизации (согпипа~опа( орйт(гагюп ртоЫепи). Основные результаты в исследованиях по комбинаторной оптимизации были получены в 70-х гг.
Дпя многих таких задач решение может рассматриваться как размещение набора 1' дискретных объектов в соответствии с заданными ограничениями. Поэтому Ф решение называется также конфигуроцией (соиЯипгг(оп). Набор всех решений называется пространством решений. Наша задача — разработать эффективные :::., алгоритмы определения конфигурации, минимизирующей значение функции ',;- стоимости илн целевой функции. Примером комбинаторной задачи оптпми- .1:.:!. зации является хорошо известная задачи коммивояжера (ггоге1гпя зо7езтап '::: ргоЫегп — 75Р), которая состоит в определении обладающего минимальной стон мостью маршрута коммивояжера, проходящего через каждьш город только один раз и возврашаюшегося в точку отправления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
