Материал: Методы оптимального проектирования устройств цифровой обработки и защиты информации. Борисов В.И., Гармонов А.В

отброшены все заведомо худшие в смысле векторной оптимизации варианты и предельно

сужена область поиска.

84

85

1.3 Обзор методов решения задач векторной оптимизации

Решение ЗВО УЦОС Ошибка! Источник ссылки не найден. осуществляется в два этапа. Первый этап заключается в определении вариантов построения устройств,

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

Формализация задачи второго этапа чрезвычайно затруднена и на практике очень часто не удается построить автоматический алгоритм отбора. В связи с этим возникает необходимость в организации человеко-машинных процедур (диалога) принятия решения о выборе.

Методы определения множества Парето по типу требуемой априорной информации и способу получения решения можно условно разбить на две группы [11] (см. рис. 1.6) :

методы, основанные на сведении задач векторной оптимизации к задачам скалярной оптимизации [1, 7 - 11, 13, 14, 12, 16, 19 - 20, 24 - 25, 27, 31, 43, 67 - 68, 73, 94, 96, 98],

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

Скаляризация векторного критерия в методах первой группы может быть осуществлено различными способами. Выделение главного критерия [1, 19 – 20, 47 - 48]

является простейшим из таких методов достижения множества Парето, который можно считать частным случаем метода последовательных уступок [19]. Эти методы применимы в том случае, когда один из ЛКО обладает исключительной важностью. В зарубежной литературе это направление получило наименование задачи оптимизации k-го критерия с l-

ограничениями [104]

Методы решения задачи (1.25) - (1.26) хорошо разработаны и продолжают развиваться [3 - 5, 7 – 9, 12 - 13, 16, 18, 26 - 28, 30, 32, 34, 48 - 50, 53 – 55, 64, 66 - 67, 69 - 71, 74, 78, 92 – 93, 99, 100 - 107]. Тем не менее, при

86

Указанные недостатки сохраняются, если рассматривать функцию Лагранжа,

построенную на основе задачи (1.25), (1.26). Метод последовательных уступок обеспечивает выравнивание локальных критериев за счет их последовательной замены при формировании целевой функции. Однако этот путь сложен и не экономичен по затратам времени ПЭВМ,

так как необходимо решать последовательность задач (1.25), (1.26).

Широкое распространение среди методов первой группы получил также метод свертки компонент векторного критерия Qk , k [1,M], который предполагает построение некоторого обобщенного (агрегированного) критерия на множестве значений векторного критерия. Обобщенный критерий должен правильно отражать значимость локальных критериев и не нарушать отношений предпочтения на множестве решений. После того как такой обобщенный критерий построен, решается задача скалярной оптимизации обобщенного критерия. Очевидно, что если обобщенный критерий не нарушает отношения предпочтения, то такой вектор Q принадлежит множеству парето-оптимальных решений задачи векторной оптимизации.

Свертывание векторного критерия в скалярный в методах первой группы может быть осуществлено различными способами [1, 7 – 9, 11, 13, 17, 19, 25, 27, 31, 48, 77], однако наиболее пригодными для целей проектирования УЦОС являются среднестепенная норма [1, 11, 50, 86, 90, 96]

i1

иминимаксная (чебышевская) норма [21, 48, 67, 71, 79]

Для критерия (1.27) 1 р . При р=1 обобщенный критерий (1.27) превращается в линейную комбинацию локальных критериев, а при р=0 - в обобщенный минимаксный критерий [79] типа (1.28). Применяя минимаксный критерий, можно получить гарантированные результаты.

Однако применение среднестепенного критерия (1.27) обладает тем преимуществом,

что в этом случае можно использовать обычные методы оптимизации. За счет увеличения показателя р получают результаты близкие к минимаксному решению. Но с ростом р рельеф результирующего обобщенного критерия Q(X ) будет иметь глубокие «овраги», что замедляет сходимость многих методов оптимизации и часто приводит к преждевременным остановам [11, 13, 96].

88