Задачи многокритериальной оптимизации

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

Компромисс разрешается введением тех или иных дополнительных ограничений или субъективных предположений. Поэтому невозможно говорить об объективном единственном решении такой задачи.

В задачах многокритериальной оптимизации поиск решений возможен рядом способов.

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

Множество допустимых решений разделяется на множество худших и множество нехудших решений. Худшим считается такое решение, если можно найти другое решение, значения критериев у которого не хуже (такие же) или лучше, чем у рассматриваемого. Решение, для которого из множества допустимых решений нельзя найти ни одного лучшего по всем критериям, называется нехудшим.

Множество нехудших решений ещё называют неулучшаемым: замена одного решения из этого множества на другое ведет к улучшению одних критериев и обязательному ухудшению других.

Математический алгоритм выбора нехудших решений основан на использовании бинарных отношений предпочтения теории принятия решений. Смысл бинарных отношений заключается в последовательном попарном сравнении элементов в соответствии с установленным правилом предпочтения. Обычно для поиска множества нехудших решений используют отношения предпочтения Слейтера или Парето, последние — чаще.

Область Парето — это область компромиссов: все решения здесь равнозначны, а окончательный выбор решения связан с введением дополнительного условия, часто — субъективного характера. Поиск решений, оптимальных по Парето, позволяет объективно сократить область возможного выбора, причем наибольшее усечение области допустимых решений достигается при назначении двух критериев. При увеличении числа критериев эффективность этого метода падает. Целесообразен одновременный учёт 2…5 критериев.

Замена критериев ограничениями и последующий поиск решений в области, задаваемой этими и ранее заданными ограничениями. Вводя те или иные ограничения, будем получать одно из нехудших решений из области Парето.

Например, задачу минимизации массы и потерь энергии изделия можно свести к задаче проектирования изделия, у которого потери не превысят, допустим, 5 %, а масса — 10 кг. Если в полученной области будет находиться несколько решений, то ограничения можно ужесточить (скажем, ограничить предельную массу 6 кг). Если же решений нет, то ограничения смягчают.

Сложность такой задачи — в удачной её постановке, то есть в быстром усечении области до одного решения при минимальном влиянии субъективных факторов, связанном с выбором ограничений.

Сведение задачи к однокритериальной и последующее её решение методами скалярной оптимизации.

Такое сведение осуществляется на основе введения дополнительных предположений о взаимосвязи и взаимозависимости учитываемых в задаче критериев. Выбор конкретного способа сведения зависит от многих обстоятельств, таких как квалификация специалистов, объём и достоверность имеющейся в их распоряжении информации, срочность решения, степень ответственности за получаемый результат. При этом следует учитывать, что характер решения меняется и со временем (то, что выгодно сегодня, может быть разорительным завтра).

Сведение задачи к однокритериальной проводится посредством выбора одного критерия из нескольких, введения общей единицы измерения для всех критериев, свертки нескольких критериев в один и другими методами.

Выбор из рассматриваемого перечня критериев одного, главного, который отражает наиболее существенные свойства исследуемого объекта. Выбор основывается на опыте разработчика или на мнении экспертов. С оставшимися критериями поступают следующими способами:

• заменяют их ограничениями, которые при необходимости ужесточают или смягчают;
• ранжируют критерии, то есть упорядочено располагают по степени важности характеризуемых свойств. Далее выбирают решение при главном критерии, вводя пороговые ограничения на остальные или же вообще их не учитывая. Если решений оказывается несколько, то лучшее из них выбирают на основе второго по важности критерия из ранжированного ряда, и т. д.

Введение общей единицы измерения критериев. В качестве такой меры часто выбирают стоимость достижения того или иного уровня качества, будь то снижение массы и потерь энергии, современный дизайн и т. д. То есть для каждого варианта изделия, характеризуемого своим уровнем качества, подсчитывают (или оценивают), с одной стороны, расходы на производство, эксплуатацию и утилизацию, а с другой стороны — доходы от использования. По величине экономической эффективности (разности доходов и расходов) делают вывод о предпочтительности вариантов.

Свёртка векторного критерия, то есть замена рассматриваемых критериев одним новым, называемым функцией полезности или целевой функцией. Выбор целевой функции — сложная задача:

• нужно числено оценить, а не только ранжировать каждый критерий;
• нужно объединить критерии, которые имеют, как правило, разную размерность (например, рубли, килограммы, проценты и т. д.);
• нужно объединить критерии, величины и диапазоны изменения которых могут существенно разниться (например, потери измеряются сотыми долями, что несравнимо меньше величины, допустим, массы, измеряемой десятками и сотнями килограммов);
• сложно, а иногда и невозможно найти численную меру критерия, например, таких как степень красоты, удобство работы;
• величины разных критериев могут определяться с различной достоверностью. Так, например, если масса изделия оценивается достаточно точно, то надежность задается заметно грубее.

Грамотное выполнение свертки с получением максимально достоверного результата достигается тщательным проведением предварительных исследований, привлечением знаний и опыта специалистов-экспертов.

В качестве целевой функции ƒ часто используют:

• аддитивную функцию, то есть функцию, подсчитываемую для каждого варианта (j=1, …, n) решения как сумму отдельных критериев К (i=1, …, m) с

1 Основные группы методов

• 2 Эвристические методы
• 2.1 Метод итераций (последовательного приближения)
• 2.2 Метод декомпозиции
• 2.3 Метод контрольных вопросов
• 2.4 Метод мозговой атаки (штурма)
• 2.4.1 Метод синектики
• 2.5 Теория решения изобретательских задач (ТРИЗ)
• 2.6 Метод морфологического анализа
• 2.7 Функционально-стоимостной анализ
• 2.8 Методы конструирования
• 3 Экспериментальные методы
• 3.1 Цели и виды экспериментальных методов
• 3.2 Планирование эксперимента
• 3.3 Машинный эксперимент
• 3.4 Мысленный эксперимент
• 4 Формализованные методы
• 4.1 Методы поиска вариантов решений
• 4.2 Методы автоматизации процедур проектирования
• 4.3 Методы оптимального проектирования
• 4.3.1 Задачи оптимального проектирования
• 4.3.2 Методы принятия решений
• 4.3.2.1 Однокритериальные задачи
• 4.3.2.2 Задачи многокритериальной оптимизации

4.3.3 Принятие решений в условиях неопределенности