И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 6
Текст из файла (страница 6)
Выбирая различные константы йо исследователь может«осмотреть» соответствующие оптимальные решения х* (й) и затем выбрать «наилучшее среди них» по своим неформальным критериям. В общем случае естественно задать такое множество В, и функцию В„чтобы условие х Е Х (В) ~ (х ~ В, (х, 7, (х), ..., 4 (х)) ~ ~ В,) определяло множество «удовлетворительных решенйй» х, а Трудности приведения многочисленных пожеланий и устремлений к некоторой «единой цели» зачастую оказываютея непреодолимыми и тогда, не имея возможности сформулировать задачу оптимизации, мы вынуждены формулировать еледующую недостаточно строгую задачу многоцелевого управления: какие из возможных действий следует осуществить, чгпобм обеспечить достижение следующих целей (далее перечисляются все цели)Р Перечисляемые цели могут выражать требования~ минимизировать определенные показатели Уе У» ° ° ° Уел (о.
ы) максимизировать некоторые другие показатели Уо+ь ° ° ° е У»> удовлетворить равенствам и (или) неравенствам у,+, = О, ..., у, = О; (ола> У«+~ <й»+ь ° з Ул<йе. затем с помощью вспомогательного критерия В, (более высокого уровня) определить В-оптимальное решение х* (В) = агя гп!ц' В, (х, к«ЖВ! Г! (х), ..., 4 (х)) при условиях (0.16) — (0.17), Если, напрн(чер, выт » брать В, (х, г, (х), ..., 7„(х)) !.'» ~~'., Ь!7! (х) — ~', Ь!)! (х), В, = () (х), =о ! т-!-! то множество Х' всех х* (В), полученных при всевозможных Ь!~» О, ~ Ь; = 1 обладает замечательным свойством: в множестве Х не !=о найдется элемента г, который удовлетворял бы неравенствам ч!' = О, т 1! (г) (7! (х" (В)), !о'1 = т+ 1, й 7! (г) ~ 7! (х (В)) с хотя бы одним сильным неравенством.
В связи с этим множество Х*, которое называют множеством компромиссов, естественно называть решением задачи многоцелевого управления. На практике Х' используется лишь как один из этапов к окончательной формулировке задачи оптимизации. Окончательный выбор оптимальных значений Ь, = Ь! осуществляют либо с помощью максимизации некоторого критерия Р (х* (В), В) «более высокого уровня», т. е. выбирают Ь* = агд ппп Р (х* (В), В), либо (в коньо>о,е»о=! фликтной ситуации) по договоренности «!'-го игрока (стремящегося максимизировать 7! (х))» с остальными.
В последнем случае к существенным факторам прибавляется фактор времени ! — момент принятия окончательного решения о согласованном выборе значений Ь. Этот фактор, а также и другие существенные факторы т конфликта, позволяет каждой стороне выдвигать с помощью функции 5! конструктивные предложения (5-уступки) в виде: — «если выбор Ь будет завершен до момента времени 1, то !-й игрок согласен с любым значением Ь из множества 6! (1, т)». Такие 5-уступки помогают прийти к взаимо согласованному выбору значений Ь, в тот момент („ когда множество П 6! (1,, т) окажется непусто.
Для более конкретных ситуаций исследовались многие важные постановки «коллективных» задач многоцелевого управления, когда разные цели порождаются разными участниками (организациями), и предложены разумные конкретизации коллективных решений, а также алгоритмы для их вычисления (33, 50, 69, 70,?4, 171, 201, 203, 206, 210, 257, 259, 260, 389). 0.2. 0 неноторых методах решения задач оптимизации Любой алгоритм отыскания оптимального решения х«для задачи минимизации функции 7 на множестве Х, г'(х»)(!(х) ЧхсХ, (олв) обычно ориентирован на решение определенного класса задач оптимизации с определенными свойствами функции 1 н множества Х. 20 Поэтому более универсальные алгоритмы, ориентированные на решение более широких классов задач, обычно уступают по эффективности специализированным алгоритмам, использующим специфические свойства конкретно решаемой задачи.
Этим и объясняется современное непрерывно возрастающее разнообразие алгоритмов оптимизации. Приведем примеры основных оптимизационных методов. 1. Метод волвого перебора Если множество допустимых решений состоит из У элементов х', х', ..., х" и Л1 настолько мало, что имеется практическая возможность вычислить все значения ) (х'), 1 (х'), ..., 1 (хн), то сравнением полученных значений найдем наименьшее значение 1(х'*) и одновременно искомое оптимальное решение х* = х' ° = агд пп'п 1' (х'). из! н Такой метод полного перебора используется довольно редко, потому что множество Х обычно содержит слишком много элементов и практически невозможно вычислить 1(х) для каждого х ~ Х. 2.
О врвблвжеввыл методах в овтвмольвыл алгоритмах Среди приближенных методов оптимизации наиболее часто используются: Методы частичного перебора и случайного поиска. В этих методах выбирают некоторое достаточно представительное подмножество Хн = (х', х', ..., хн) с: Х, допускающее возможности использовать метод полного перебора и найденное х'* принимают в качестве приближенного решения исходной задачи оптимизации. Если элементы х', х', ... вычислять как реализации некоторой случайной величины $ ~ Х с заданной мерой р, ) Н)ь (х) = 1 (такой метод х называют методом случайного поиска, или методом Монте — Карло) или задать в виде некоторой сетки узлов Хнс: Х, то получим метод пассивного поиска.
В методах активного (или адаптивного) поиска элементы х', х', ... вычисляют последовательно и, учитывая текущую информацию о значениях Г (х'), 1(х«), ... (или производных 1), стремятся обеспечить более густую сетку (увеличить значения р (х)) в тех подмножествах Х с: Х (с меньшими предсказуемыми значениями1(х)), которые становятся более подозрительными (в процессе вычислений г (х')) «на оптимум» (т. е. на то, что Х*с: Хн). Методы отсечений. В этих методах находят и «отсекают» от множества Х те его подмножества Х, которые заведомо не содержат оптимальных решений, и получают эквивалентную задачу минимивации функции 1 на «меньшем» множестве Х = Х ~, Х. Последова- 21 х»+' = агд ш)п ~(х), «ЯХН«»,Д р (оп 9) то при весьма общих условиях получим сходимость х»-» Х* к локальномд решению задачи оптимизации, т. е.
к такому х« ~ Х, которое при некотором Л ~ 0 удовлетворяет условиюх' = агд ппп Г(х) «ех, Д,М (очевидно при х»+' = х", точка х» является локальным решением). Поиск локальных решений оказывается особенно эффективным при решении тех задач оптимизации, в которых все локальные решения являются одновременно оптимальными решениями (например, выпуклых задач оптимизации). Методы последовательных приближений. Так как вспомогательная задача (0.19) может оказаться довольно трудной даже при малых Л,, то в многочисленных методах последовательных приближений предлагается вычислять х»+' как приближенное решение задачи х»+' = агд пп'п г» (х), «ЯХ» (9.99) где аппроксимации г„Х" выбираются из соображений упростить вычисление х»+', сохранив при этом сходимость х»;- х*. В качестве Х часто выбирают некоторые из множеств Х, Х, Х, (х", Л,), Х, (х", Л,) ('.) (х) (х — х»((Лд), Х» (х", Л„1) Ь ~ (х ( ( х, — х; ) ( Лд, 1 Ч х' с= (1, 2, ..., и) ) н др., или опреде.
тельными отсечениями иногда удается получить последовательность таких вложенных подмножеств Х, ~ Х, ~ Х, ~ ... =з Х» ~ =з ..., для которых б(аш (Х„)„- 0 (тогда при достижении неравенства б)агп (Х„) ( е, любой элемент х» ~ Х» очевидно удовлетворит неравенству ( х„— х«)~ ( з). Различные эффективные варианты методов отсечений разрабатываются в рамках методов ветвей и границ, методов минорант, методов эллипсоидов (особенно эффективных для решения выпуклых задач) и других методов. Методы аппроксимаций.
В этих методах функцию г и (или) множество Х заменяют некоторыми реализуемыми аппроксимациями 1, Х; допускающими практическую возможность вычислить х« = = агд ппп ~ (х). Если Д, Х) достаточно близки к (Г, Х), то можно «ей ожидать, что и Х* будет близким к Агн ппп ~ (к). «ЕХ Методы локальной оптимизации. Если для заданных х» ~ Х, Л» ~ 0 множество Х заменять »меньшим» множеством Х, (х», Лд) = = (х~ Х((х» — х((Л„) и последовательно вычислять ленные пересечения этих множеств.
Очевидно, при уменьшении ) необходимо повышать точность аппроксимации Ч)' (х), поэтому в качестве Р» обычно выбирают линейную аппроксимацию 1 в окрестности х» Р, (х», х)»» 7 (х») + (Ч) (х»), х — х»), реже квадратичную аппроксимацию Р, (х", х) ~1(х») + (Чг (х»), х — х») + + ~ (Ч„! (х")(х — х»), х — х») или аппроксимации более высоких ! порядков, часто, особенно для негладких 7, выбирают негладкие аппроксимации Р, (х», х) = 2„а; (х») шах (с ~ (х»), х) или компо/я! !«».!! вицин таких функций. Множество возможных способов выбора последовательностей (Рм Х»)» !, а также процедур Р, для приближенного вычисления решений х»ы соответствующих упрощенных задач оптимизации (0.20) порождает множество А алгоритмов А конкретной реализации методов последовательных приближений.
В связи с этим актуальной является задача выбора наиболее эффективного (оптимального) на классе (Р, Х) алгоритма А !з (Р,, Х„, Р„, й = = 1, !Ч (А), х»~ Х) ~ А для вычисления по формулам (0.20) приближения х» (А) »з х"!"> к искомому решению х' = аги ш!и 7' (х) при «ех условии, что 7 и Х принадлежат заданным классам Р и Х. Очевидно, это задача многоцелевой оптимизации, преследующая среди наиболее важных следующие цели И77): 1) минимизировать время Т (А) Ь у, '(А, Г, Х) реализации алгоритма А, т. е. время, затраченное на вычисление элемента х' (А); 2) минимизировать погрешность вычисленного приближения х* (А), т.
е. расстояние р (А) ~ у» (А, 7, Х) от х«(А) до множества всех х* для функции ) и множества Х; 3) минимизировать 7'(х' (А)) — ппп7 (х) !з у,'(А, 7, Х); «е» 4) минимизировать число итераций !Ч (А) = у» (А, ), Х); 5) минимизировать объем памяти )', (А),~, у1 (А, 7, Х), занимаемый на 1-м устройстве вычислительной системы при реализации алгоритма А; 6) минимизировать время Т, (А) 1~ у~!(А, 7, Х) работы '1-го устройства при реализации алгоритма А; 7) удовлетворить требуемым ограничениям на допустимые значения г~С (А, 7, Х) йй (у/ у =* ур» (А, 7, Х), Е = 1, 2, 3; й ~ Я (1)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
