Раздел 7. Многокритериальные задачи, парето-оптимальность, схемы компромиссов
7.1 Постановка многокритериальных задач принятия решений
Постановка многокритериальных задач принятия решений
Целевая функция (критерий качества) — это выражение, для которого необходимо найти максимальное или минимальное значение. Целевая функция позволяет количественно сравнить два альтернативных решения. С математической точки зрения целевая функция описывает некоторую (n+1)-мерную поверхность. Ее значение определяется проектными параметрами J = J (x1, x2 ,…, xn ) = J (x̅ ) .
Примерами целевой функции могут являться стоимость, вес, прочность, габариты, КПД и пр. Если целевая функция зависит от одного параметра, то ее можно представить кривой на плоскости. Если от двух, то целевая функция графически отображается поверхностью в трехмерном пространстве. При зависимости целевой функции от трех или более параметров поверхности, задаваемые целевой функцией, называются гиперповерхностями и не поддаются изображению обычными средствами. Топологические свойства поверхности целевой функции играют большую роль в процессе оптимизации, так как от них зависит выбор наиболее эффективного алгоритма.
Для задания целевой функции иногда может потребоваться таблица технических данных (например, таблица состояния водяного пара) или может понадобиться провести эксперимент. В ряде случаев проектные параметры могут принимать только целые значения, логические и т.д. Однако в каком бы виде не была представлена целевая функция, она должна быть однозначной функцией проектных параметров.
В большинстве практических задач оптимизации требуется введение более одной целевой функции. Иногда одна из них может оказаться несовместимой с другой. Примером служит проектирование самолетов, когда одновременно требуется обеспечить максимальную прочность, минимальный вес и минимальную стоимость. В таких случаях проектировщику необходимо ввести систему приоритетов и поставить в соответствие каждой целевой функции некоторый безразмерный множитель с целью сведения нескольких функция к одной составной целевой функции — функции компромисса.
Известно, что для решения задач минимизации и максимизации можно использовать одни и те же алгоритмы оптимизации, т. к. задача минимизации легко превращается в задачу поиска максимума, путем замены знака целевой функции на обратный.
Область, определяемая всеми n проектными параметрами представляет собой множество допустимых решений (пространство решения). Пространство решения обычно ограничено рядом условий, связанных с физической сущностью задачи, причем можно задать столь сильные ограничения, что задача не будет иметь ни одного удовлетворительного решения. Следует отметить, что очень часто в связи с ограничениями оптимальное значение целевой функции достигается на одной из границ области множества допустимых решений задачи.
При решении задач многокритериальной оптимизации различают локальный и глобальный оптимумы. Локальным оптимумом называется точка пространства решений, в которой целевая функция имеет наибольшее значение по сравнению с ее значениями во всех других точках ее ближайшей окрестности. Достаточно часто пространство проектирования содержит много локальных оптимумов (невыпуклое) и следует соблюдать осторожность, чтобы не принять первый из них за оптимальное решение задачи. Глобальный оптимум — это оптимальное решение для всего множества допустимых решений. Возможен случай нескольких равных глобальных оптимумов, расположенных в разных частях пространства проектирования. Поэтому в таких случаях выбор оптимального решения зависит от проектировщика.
Математические модели принятия решений, используемые в задачах оптимального управления, характеризуются детерминированными или случайными исходными данными; непрерывными или дискретными искомыми переменными; линейными или нелинейными зависимостями между переменными. Причем, если хотя бы одна зависимость нелинейная, то и вся задача является нелинейной.
Можно выделить несколько причин, приводящих к многокритериальности в технических задачах:
- множественность технических требований;
- необходимость обеспечения оптимальности проектируемого устройства при различных условиях его функционирования, т. е. при неопределенности условий, в которых приходится работать устройству;
- отражение требований функциональной полноты с одной стороны и физического смысла с другой с помощью критерия оптимальности;
- наличие в проектируемой системе нескольких взаимосвязанных узлов и блоков, каждый из которых характеризуется, по крайней мере, хотя бы одним частным критерием оптимальности.
Многокритериальная (векторная) оптимизация представляет собой поиск наилучшего значения для некоторого множества характеристик рассматриваемого объекта, т. е. поиск некоторого компромисса между частными критериями Ji (x̅ ), i = 1, 2,...,s , по которым требуется оптимизировать решение.
Постановка такой задачи выглядит следующим образом:
где Ji (x̅ ) - целевые функции, которые зависят от проектных параметров xj, 𝑔m (x1,x2,...,xn) - ограничения.
Часто в многокритериальных задачах задается некоторая система нормативов J *1, J *2,..., J *n. Это значит, например, что параметры системы должны быть таковы, чтобы минимизировать функции Ji (x̅ ) при условиях
Ji (x̅ ) > J *1, i = 1,2,...,k,
называемых критериальными ограничениями, или контрольными показателями.
В таких случаях иногда бывает удобным представить критерий качества в виде:
и искать вектор x̅, который обеспечивает минимальное значение 𝜎 (x̅ ). При данном значении вектора x̅ величина 𝜎 (x̅ ) дает нам значение наихудшего из показателей Ji (x̅ ). Таким образом, условие 𝜎 (x̅ ) → min означает выбор такой системы параметров x̅, которая максимизирует отношение i- го реально достигнутого критерия к его худшему значению. Если значение жестко не задано, то они могут быть определены в результате экспертного опроса.