Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 30
Текст из файла (страница 30)
Поскольку здесь Е (х,) ) Е (х,), ясно, что минимум находится на отрезке ~х„Ь,]. Обозначим этот отрезок ~аг, д,], снова выберем одну внутреннюю точку и повторим процедуру сужения интервала неопределенности. Процесс оптимизации повторяется до тех пор, пока длина очередного отрезка [а„, Ь,] не станет меньше заданной величины е. Теперь рассмотрим способ размещения внутренних точек на каждом отрезке ~а~, Ь„]. Пусть длина интервала неопределенности равна Е, а точка деления делит его на части Е„Е,: Е, ~ Ег, Е = Е, + Е,.
Золотое сечение интервала неопределенности выбирается так, чтооы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка: (6.7) Из этого соотношения можно найти точку деления, определив отношение ЕгП~. Преобразуем выражение (6.7) и найдем это значение: Е1 — — Е,Е, Е1 Е,(Е, + Е,), Е, '+ ŠŠ— Е,'=0 — + — ' — 1=0, — 1 + ~/.5 Поскольку нас интересует только положительное решение, то — 1+~/5 06Р Отсюда Е, = 0.618Е, Е, = 0.382Е.
Поскольку заранее неизвестно, в какой последовательности (Е, и Е, или Е, и Е,) делить интервал неопределеи- 12 л, и, турчак гл. э. мптоды оптпмпзлппп ности, то рассматривают внутренние точки, соответствующие двум этим способам деления. На рис. 30, а точки деления х, и х, выоираются с учетом полученных значений для частей отрезка, В данном случае имеем х,— а, = Ь,— х~ = 0.3824, Ь, — х, =х, — а, = 0,618с7„ А = Ь, — а,. После первого шага оптимизации получается новый интервал неопределенности — отрезок [а„Ь,] (см.
рис. 30, б). Можно показать, что точка х, делит этот отрезок в требуемом отношении, при этом 6, — х, = 0.3820„д, = 6~ — а,. Для этого проведем очевидные преобразования: 6, — х, = х, — х, =(Ь, — а,) — (х, — ао) — (Ь, — х,) = = И~ — 0.3824 — 0-38Ыю = 0 236с~о, Ы, = х2 — и, = 0.6180„ Ь, — х, = 0.236(А/0,618) = 0.3824. Вторая точка деления х. выоирается на таком же расстоянии от левой границы отрезка, т. е.
х. — а, = 0.3820,. И снова интервал неопределенностп уменьшается до размера А = Ь, — а, = Ь, — х, = 0 6184 = 0 618'4 Используя полученные соетношення, можно записать координаты точек деления у и а отрезка ~а„6„] на й+ 1-м шаге оптимизации (у ( з): у = 0.618а~+ 0.3826», (6.8) а = 0.382а„+ 0.618Ь„. Прп этом длина интервала неопределенности равна д~ ° 6| — а~ = 0.618М,. (6.9) Процесс оптимизации заканчивается прп выполнении условия д,(е. При этом проектный параметр оптимизации составляет а~(х ~ 6,.
Можно в качестве оптимального значенпя принять х = а„-(или х = Ь~, или х = (а, + Ь,) /2 ит,п.),- 6 з. одномжгнля оптимизлпия На рис. 31 представлена елок-схема процесса одномерной оптимизации методом золотого сечения. Здесь у, з— точки деления отрезка ~а, 63, причем у (з. В результате выполнения алгоритма выдается оптимальное значение Рис. 31. Блок-схема метода золотого сечения проектного параметра х, в качестве которого принимается середина последнего интервала неопределенности. П р и м е р. Для оценки сопротивления дороги движению автомобиля прп скорости и км/ч монино использовать вмпирическую формулу (и) = 2~ — —. и + — и (для шоссе), 2 1 180 Гл.
6. мнтоды оптимлзАции Проиллюстрпруем на этой простейшей задаче метод золотого сечения. Первоначально границы 11нтервала неопределенности примем равными а = 5, Ь =20. Результаты вычислений 'представим в виде таблицы (табл. 5) . Здесь ооозначения аналогичны используемым в блок-схеме (см. рис. 31). Расчеты проводятся в соотвстствпп о блок-схемой с погрешностью е = 1 км/ч. Таблица 5 Шаг 10.7 8.6 10.7 9.9 9.4 20 14.3 14.3 12.1 10.7 10.7 5 5 8.6 14.3 10.7 121 10. 7 20.7 20.73 20.68 20.66 20.68 21.3 20.68 20.81 20.68 20.66 15 9.3 5,7 3.5 21 1.3 Приведем решение для первого этапа; у = 0.618 5+ 0.382 20~ 10,7, г = 0.382 5 + 0.618 20 ~ 14.3, А = 24 — —..10.7 + —,0 10.7'м 20,7, В = 24 — —. 14.3+ = 14.3'-21.3„ А (В.
Прп данной невысокой точности вычислений достаточно четырех шагов оптимизации. В этом случае искомое значение скорости равно ц - (8.6+ 10.7)/2 = 9.65 км/ч После Определить скорость, прн которой сопротивление будет минимальным. Решение. Это простейшая задача одномерной оптпмпзацпи. Здесь сопротивление ~(и) — целевая функцпя, скорость п — проектный параметр. Данную задачу легко решить путем нахождения мпнпмума с помощью вычисления производной, поскольку 7'(и) — функция днфференцируемая. Действительно, 3+ 30 2 2~ 5 3.
МНОГОМЕРНЫК ЗАДАЧИ ОПТИМИЗАИИИ $81 пяти шагов этот'результат получается с меньшей погрешностью ~ и = (9.4+ 10,7) /2 = 10.05 км/ч. $3. Многомерные задачи оптимизации П риме р, В ~ 1 (п. 3) была рассмотрена задача об определении оптимальных размеров контейнера объемом 1 м',. Задача свелась к минимизации его полной поверхности, которая в данном случае является целевой функ- цией 5=2 х,х, + — + — ). 1~ 1 2 (6.11)' Р е шеи не.
В соответствии с (6.10) получим систему — — 2 хя, =О, Отсюда находим х, х, 1 и, х, =-1/(х1х~) =1 м. Таким образом, оптимальной формой контейнера в даппом случае является куб, длина ребра которого равна 1 и, 1. Минимум функции нескольких переменных, В ф 2 мы рассмотрели одномерные задачи оптимизации, в которых целевая функция зависит лишь от одного аргумента.
Однако в большинстве реальных задач оптимизации, представляющих практический интерес, целевая функция зависит от многих проектных параметров. В частности, рассмотренная выше задача оо определении сопротивления дороги движению автомобиля на самом деле является многомерной, поскольку здесь наряду со скоростью имеются и другие проектные параметры (качество покрьгп|я, уклон, температура и др.). Минимум дифферепцируемой функции многих переменных и = ~(х„х.„..., х„) можно пайти, исследуя ее значения в критических точках, которые определяются из решения системы дифференциальных уравнений — =О, — =О,,, — =О, (6.10) д~ д~ д~ дх -' дх '''' дх ГЛ. 6, МЕТОДЫ ОПТПМИЗАЦИП Рассмотренный метод можно нспользовать лишь для дпфференцпруемой целевой функции.
По и в этом случае могут возникнуть серьезные трудности прп решении системы нелинейных уравнений (6.10) . Бо многих случаях никакой формулы для целевой функции нет, а имеется лишь возможность определения ее значен1п1 в произвольных точках рассматриваемой ооласти с помощью некоторого вычислительного алгоритма или путем физических измерений. Задача состоит в при-. ближенном определении наименьшего значения функции во всей области прп известных ее значениях в отдельных точках.
Для решения подооной задачи в области проектирования С, в которой ищется минимум целевой функции и = =~(хо х„..., х„), можно ввести дискретное множество точек (узлов) путем разбиения интервалов изменения параметров х~, х~,..., х, на части с шагами Ь„Ь~, ..., Й.. В полученных узлах можно вычислить значения целевой функции и среди этих значений найти наименьшее.
Следует отметить, что такой метод может быть использован для функции одной переменной. В многомерных задачах оптимизации, где число проектных параметров достигает пяти и более, этот метод потреоовал оы слишком большого ооъема вычислений. Оценим, например, объем вычислений с помощью оощего поиска при решении задачи оптимизации функции пяти неизвестных. Пусть вычисление ее значения в одной точке требует 100 арифметических операций (на практике это число может достигать нескольких тысяч и болыпе). Область проектирования разделим на 100 частей в каждом из пяти направлений, т.
е. число расчетных точек равно 101", т. е. приблизительно 10". Число арифметических операций тогда равно 10", и для решения этой задачи на ЭВМ с быстродействием 1 млн. оп./с потребуется 10' с (более 10 сут) машпнпого времени. Проведенная оценка показывает, что такие методы общего поиска с использованием сплошного перебора для решения многомерных задач оптимизации не годятся.
Необходимы специальные численные методы, основанные на целенаправленном поиске. Рассмотрим некоторые из них. 2. Метод покоордпнатного спуска. Пусть требуется найти наименьшее значение целевой функции и у(х„ х~, ..., х„). В качестве начального прполиженпя выберем в и-мерном пространстве некоторую точку ЛХ, с координа- я;1.
многоз(гене.1Г эАдлч(! Опт)(мизин!!и 183 тами х,, х,, ..., х,„.,3а(1)пкспрует! все координаты (О) (1) (а) (о) (о)~ функции и,кроме первой. Тогда и = Х!х„ х, , ..., х„ )— функция одной переменной хь Решая одномерную задачу оптимизации для этой функции, мы от точки М, пере- / (1) (о) (о) 1 ходим к точке ЛХ, (хт, х~, ..., х„), в которои функция и принимает наименьшее значение по координате х, прн фиксированных остальных координатах.
Б этом состоит первый шаг процесса о)г)н,н)зацпп, состоящтгй в спуске по коордппате х,. Зафиксируем теперь все координаты, кроме х~, и рас- / (!) - (о) смотрим функцию этой переменной Р =Х ~~х,, х„хз, „., х~~~). Снова решая одномерную задачу оптимизации, (1) находим ее наих(еньшее значение при х,, =- х,, т. е. в точке ЛХи (,х1, х2, хз, ..., х.„). Аналогично проводнт- / (!) . (!) (о) ,(о)~ ся спуск по координатам х„ х;, ..., х„, а затем процедура снова повторяется от х, до х„ и т. д. В результате этого процесса получается последовательность точек ЛХ„ М„ ..., в которых значения целевой функции составляют монотонно убывающую последовательность Х(М,) ) Х(ЛХ,) ~...
На любом й-.х! шаге этот процесс можно прервать, и значенне Х(М,) принимается в качестве ттапхтеньшего значения целевой функции в рассматриваемой ооластп. Таким ооразом, метод покаординатного спуска сводит задачу о нахон'денни наименьшего значения функцтш многих переменных к многократному решению одномерных задач оптимизации по каждому проектному параътетру. Данный метод легко про- '~о иллтострировать геометриче- 1 ски для случая функции двух переменных г =/(х, у), опи- О сывающей некоторую поверхность в трехмерном про- Рпс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
