Многокритериальная оптимизация

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

Для задачи многокритериальной оптимизации не гарантируется, что одно решение одновременно оптимизирует каждую цель. Говорят, что целевые функции конфликтны. Решение называется недоминируемым , оптимальным по Парето, эффективным по Парето или не худшим, если ни одна из целевых функций не может быть улучшена по значению без ухудшения некоторых других целевых значений. Без дополнительной информации о субъективных предпочтениях может существовать (возможно, бесконечное) количество оптимальных по Парето решений, все из которых считаются одинаково хорошими. Исследователи изучают проблемы многокритериальной оптимизации с разных точек зрения, и, таким образом, существуют разные философии решения и цели при их постановке и решении. Целью может быть поиск репрезентативного набора оптимальных по Парето решений и/или количественная оценка компромиссов при удовлетворении различных целей и/или поиск единого решения, которое удовлетворяет субъективным предпочтениям человека, принимающего решения (ЛПР).

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

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

Введение

Смотрите также: порядок Парето

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

$\min _{x\in X}(f_{1}(x),f_{2}(x),\ldots ,f_{k}(x))$

где целое число $k\geq 2$ количество целей и набор $X$ - это допустимый набор векторов решений, который обычно $X\subseteq \mathbb {R} ^{n}$ но это зависит от $n$-мерная область приложения. Допустимый набор обычно определяется некоторыми функциями ограничений. Кроме того, векторнозначную целевую функцию часто определяют как

${\begin{aligned}f:X&\to \mathbb {R} ^{k}\\x&\mapsto {\begin{pmatrix}f_{1}(x)\\\vdots \\f_{k}(x)\end{pmatrix}}\end{aligned}}$

Пример границы Парето (красным), набора оптимальных по Парето решений (тех, в которых не доминируют какие-либо другие возможные решения). Точки в рамке представляют возможный выбор, и меньшие значения предпочтительнее больших. Точка C поскольку в ней доминируют как точка A , так и точка B. не находится на границе Парето , Точки A и B строго не доминируют над другими и, следовательно, лежат на границе.

Если какую-то целевую функцию необходимо максимизировать, это эквивалентно минимизации ее отрицательной или обратной функции. Обозначим $Y\subseteq \mathbb {R} ^{k}$ образ $X$; $x^{*}\in X$ или осуществимое решение осуществимое решение ; и $z^{*}=f(x^{*})\in \mathbb {R} ^{k}$объективный вектор или результат .

При многокритериальной оптимизации обычно не существует подходящего решения, которое бы минимизировало все целевые функции одновременно. Поэтому внимание уделяется оптимальным по Парето решениям, ; то есть решения, которые нельзя улучшить ни в одной из целей, не ухудшив при этом хотя бы одну из других целей. С математической точки зрения, возможное решение $x_{1}\in X$ Говорят, что (Парето) доминирует над другим решением $x_{2}\in X$, если

1. $\forall i\in \{1,\dots ,k\},f_{i}(x_{1})\leq f_{i}(x_{2})$, и
2. $\exists i\in \{1,\dots ,k\},f_{i}(x_{1})<f_{i}(x_{2})$.

Решение $x^{*}\in X$ (и соответствующий результат $f(x^{*})$) называется оптимальным по Парето, если не существует другого доминирующего над ним решения. Множество оптимальных по Парето результатов, обозначаемых $X^{*}$, часто называют фронтом Парето , границей Парето или границей Парето.

Фронт Парето задачи многокритериальной оптимизации ограничен так называемым целевым вектором надира. $z^{nadir}$и идеальный объективный вектор $z^{ideal}$, если они конечны. Целевой вектор надира определяется как

$z^{nadir}={\begin{pmatrix}\sup _{x^{*}\in X^{*}}f_{1}(x^{*})\\\vdots \\\sup _{x^{*}\in X^{*}}f_{k}(x^{*})\end{pmatrix}}$

и идеальный объективный вектор как

$z^{ideal}={\begin{pmatrix}\inf _{x^{*}\in X^{*}}f_{1}(x^{*})\\\vdots \\\inf _{x^{*}\in X^{*}}f_{k}(x^{*})\end{pmatrix}}$

Другими словами, компоненты надирного и идеального целевых векторов определяют верхнюю и нижнюю границы целевой функции оптимальных по Парето решений. На практике целевой вектор надира может быть только аппроксимирован, поскольку, как правило, весь оптимальный по Парето набор неизвестен. Кроме того, утопический целевой вектор $z^{utop}$, такой, что $z_{i}^{utop}=z_{i}^{ideal}-\epsilon ,\forall i\in \{1,\dots ,k\}$ где $\epsilon >0$ — небольшая константа, часто определяемая по численным причинам.

Примеры применения

Экономика

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

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

Разработка макроэкономической политики – это контекст, требующий многоцелевой оптимизации. Обычно центральный банк должен выбрать позицию денежно-кредитной политики , которая уравновешивает конкурирующие цели — низкую инфляцию , низкий уровень безработицы , низкий торговый дефицит и т. д. Для этого центральный банк использует модель экономики , которая количественно описывает различные причинно-следственные связи. в экономике; он многократно моделирует модель при различных возможных вариантах денежно-кредитной политики, чтобы получить список возможных прогнозируемых результатов для различных представляющих интерес переменных. Тогда в принципе он может использовать совокупную целевую функцию для оценки альтернативных наборов прогнозируемых результатов, хотя на практике центральные банки используют неколичественный, основанный на суждениях процесс ранжирования альтернатив и принятия политического выбора.

Финансы

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

Оптимальный контроль

Основные статьи: Оптимальное управление , Динамическое программирование и Линейно-квадратичный регулятор.

В инженерии и экономике многие проблемы связаны с множеством целей, которые нельзя описать как «чем больше, тем лучше» или «чем меньше, тем лучше»; вместо этого для каждой цели существует идеальное целевое значение, и желание состоит в том, чтобы максимально приблизиться к желаемому значению каждой цели. Например, энергетические системы обычно имеют компромисс между производительностью и стоимостью. или кто-то может захотеть отрегулировать расход топлива и ориентацию ракеты так, чтобы она прибывала в определенное место и в определенное время; или можно захотеть проводить операции на открытом рынке так, чтобы уровень инфляции и уровень безработицы были как можно ближе к желаемым значениям.

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

Оптимальный дизайн

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

Например, при проектировании бумажной фабрики можно попытаться уменьшить объем капитала, вложенного в бумажную фабрику, и одновременно повысить качество бумаги. Если проект бумажной фабрики определяется большими объемами хранения, а качество бумаги определяется параметрами качества, то задача оптимального проектирования бумажной фабрики может включать в себя такие задачи, как i) минимизация ожидаемого отклонения этих параметров качества от их номинальных значений. значения, ii) минимизация ожидаемого времени перерывов и iii) минимизация инвестиционных затрат на объемы хранения. Здесь максимальный объем башен является расчетной переменной. Этот пример оптимального проектирования бумажной фабрики представляет собой упрощение используемой модели. Многоцелевая оптимизация конструкции также была реализована в инженерных системах в таких случаях, как оптимизация компоновки шкафа управления, оптимизация формы профиля с использованием научных рабочих процессов, разработка нано- КМОП , система проектирования чипов , проектирование ирригационных систем на солнечной энергии, оптимизация систем песчаных форм, конструкция двигателя, оптимальное размещение датчиков и оптимальная конструкция контроллера.

Оптимизация процесса

Многоцелевая оптимизация все чаще применяется в химической технологии и производстве . В 2009 году Фиандака и Фрага использовали многокритериальный генетический алгоритм (MOGA) для оптимизации процесса адсорбции при переменном давлении (процесс циклического разделения). Проблема проектирования заключалась в двойной максимизации извлечения азота и чистоты азота. Результаты хорошо аппроксимировали границу Парето с приемлемым компромиссом между целями.

В 2010 году Сендин и др. решена многокритериальная задача термической обработки пищевых продуктов. Они рассмотрели два тематических исследования (двухцелевые и трехкритериальные задачи) с использованием нелинейных динамических моделей. Они использовали гибридный подход, состоящий из взвешенного подхода Чебышева и подхода пересечения нормальной границы. Новый гибридный подход позволил создать оптимальный по Парето набор для термической обработки пищевых продуктов.

В 2013 году Ганесан и др. проведена многокритериальная оптимизация комбинированной углекислотной конверсии и парциального окисления метана. Целевыми функциями были конверсия метана, селективность по оксиду углерода и соотношение водорода к оксиду углерода. Для решения этой проблемы Ганесан использовал метод нормального пересечения границ (NBI) в сочетании с двумя методами, основанными на рое (алгоритм гравитационного поиска (GSA) и оптимизация роя частиц (PSO)). Приложения, связанные с химической экстракцией и процессы производства биоэтанола поставили аналогичные многоцелевые проблемы.

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

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

Управление радиоресурсами

Целью управления радиоресурсами является обеспечение скоростей передачи данных, которые запрашиваются пользователями сотовой сети. Основными ресурсами являются временные интервалы, частотные блоки и мощности передачи. У каждого пользователя есть своя целевая функция, которая, например, может представлять собой некоторую комбинацию скорости передачи данных, задержки и энергоэффективности. Эти цели противоречат друг другу, поскольку частотные ресурсы очень скудны, поэтому существует необходимость в тесном повторном использовании пространственных частот , что приводит к огромным помехам между пользователями, если их не контролировать должным образом. многопользовательские методы MIMO используются В настоящее время для уменьшения помех за счет адаптивного предварительного кодирования . Сетевой оператор хотел бы обеспечить как большое покрытие, так и высокие скорости передачи данных, поэтому оператор хотел бы найти оптимальное по Парето решение, которое сбалансирует общую пропускную способность сети и справедливость для пользователей соответствующим субъективным образом.

Управление радиоресурсами часто решается путем скаляризации; то есть выбор функции полезности сети, которая пытается сбалансировать пропускную способность и справедливость для пользователей. Выбор функции полезности оказывает большое влияние на вычислительную сложность получаемой в результате задачи однокритериальной оптимизации. Например, общая полезность взвешенной ставки суммирования дает NP-сложную задачу со сложностью, которая экспоненциально масштабируется с числом пользователей, в то время как взвешенная полезность максим-минимальной справедливости приводит к квазивыпуклой задаче оптимизации только с полиномиальным масштабированием с количество пользователей.

Электроэнергетические системы

Реконфигурация путем обмена функциональными связями между элементами системы представляет собой одну из наиболее важных мер, которая может улучшить эксплуатационные характеристики распределительной системы. Проблема оптимизации посредством реконфигурации системы распределения электроэнергии, с точки зрения ее определения, представляет собой историческую единую объективную проблему с ограничениями. С 1975 года, когда Мерлин и Бэк выдвинул идею реконфигурации распределительной системы для снижения потерь активной мощности, и до сих пор многие исследователи предлагают разнообразные методы и алгоритмы для решения проблемы реконфигурации как единой объективной задачи. Некоторые авторы предложили подходы, основанные на оптимальности по Парето (включая потери активной мощности и показатели надежности в качестве целей). Для этой цели использовались различные методы, основанные на искусственном интеллекте: микрогенетические, отраслевая АТС, оптимизация роя частиц и генетический алгоритм недоминируемой сортировки.

Осмотр инфраструктуры

Автономная проверка инфраструктуры может снизить затраты, риски и воздействие на окружающую среду, а также обеспечить лучшее периодическое обслуживание проверяемых активов. Обычно планирование таких миссий рассматривается как одноцелевая задача оптимизации, целью которой является минимизация энергии или времени, затрачиваемых на проверку всей целевой структуры. Однако для сложных реальных структур охватить 100% объекта проверки невозможно, и создание плана проверки лучше рассматривать как задачу многокритериальной оптимизации, где цель направлена ​​как на максимизацию охвата проверки, так и на минимизацию времени и затрат. Недавнее исследование показало, что многокритериальное планирование инспекции действительно может превзойти традиционные методы на сложных конструкциях.

Решение

Поскольку обычно существует несколько оптимальных по Парето решений для задач многокритериальной оптимизации, то, что означает решение такой проблемы, не так просто, как для обычной задачи однокритериальной оптимизации. Поэтому разные исследователи по-разному определяют термин «решение задачи многокритериальной оптимизации». В этом разделе суммированы некоторые из них и контексты, в которых они используются. Многие методы преобразуют исходную задачу с несколькими целями в задачу оптимизации с одной целью . Это называется скаляризованной задачей. Если оптимальность по Парето полученных однокритериальных решений может быть гарантирована, скаляризация считается выполненной аккуратно.

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

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

Наиболее предпочтительные результаты можно получить, используя различные философии. Методы многокритериальной оптимизации можно разделить на четыре класса.

1. В так называемых методах без предпочтений ожидается, что DM не будет доступен, но нейтральное компромиссное решение идентифицируется без информации о предпочтениях. Другие классы — это так называемые априорные, апостериорные и интерактивные методы, и все они по-разному используют информацию о предпочтениях от DM.
2. В априорных методах информация о предпочтениях сначала запрашивается у DM, а затем находится решение, наилучшим образом удовлетворяющее этим предпочтениям.
3. В апостериорных методах сначала находится представительное множество оптимальных по Парето решений, а затем ЛПР должен выбрать одно из них.
4. В интерактивных методах лицу, принимающему решения, разрешено итеративно искать наиболее предпочтительное решение. На каждой итерации интерактивного метода DM показывает оптимальное по Парето решение(я) и описывает, как решение(я) можно улучшить. Информация, предоставленная DM, затем учитывается при создании нового оптимального по Парето решения для DM для изучения на следующей итерации. Таким образом, ДМ узнает о осуществимости своих желаний и может сконцентрироваться на решениях, которые ему интересны. DM может остановить поиск, когда захочет.

Дополнительная информация и примеры различных методов четырех классов приведены в следующих разделах.

Методы без предпочтений

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

${\begin{aligned}\min &\|f(x)-z^{ideal}\|\\{\text{s.t. }}&x\in X\end{aligned}}$

решено. В вышеуказанной задаче $\|\cdot \|$ может быть любым $L_{p}$ норма , с общим выбором, включая $L_{1}$, $L_{2}$, и $L_{\infty }$. Метод глобального критерия чувствителен к масштабированию целевых функций. Таким образом, рекомендуется нормализовать цели в едином безразмерном масштабе.

Априорные методы

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

Метод функции полезности

Метод функции полезности предполагает, что функция полезности лица, принимающего решения , доступна. Отображение $u\colon Y\rightarrow \mathbb {R}$ является функцией полезности, если для всех $\mathbf {y} ^{1},\mathbf {y} ^{2}\in Y$ он утверждает, что $u(\mathbf {y} ^{1})>u(\mathbf {y} ^{2})$ если лицо, принимающее решение, предпочитает $\mathbf {y} ^{1}$ к $\mathbf {y} ^{2}$, и $u(\mathbf {y} ^{1})=u(\mathbf {y} ^{2})$ если лицо, принимающее решение, безразлично между $\mathbf {y} ^{1}$ и $\mathbf {y} ^{2}$. Функция полезности определяет порядок векторов решений (напомним, что векторы можно упорядочивать разными способами). Один раз $u$ получается, достаточно решить

$\max \;u(\mathbf {f} (\mathbf {x} )){\text{ subject to }}\mathbf {x} \in X,$

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

Лексикографический метод

Основная статья: Лексикографическая оптимизация

Лексикографический метод предполагает, что цели можно ранжировать в порядке важности. Предположим, что целевые функции расположены в порядке важности так, что $f_{1}$ является самым важным и $f_{k}$ наименее важным для лица, принимающего решения. При условии этого предположения можно использовать различные методы для достижения лексикографически оптимального решения. Обратите внимание, что здесь ни для одной задачи не указывается цель или целевое значение, что отличает его от метода лексикографического программирования целей .

Скаляризация

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

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

${\begin{array}{ll}\min &g(f_{1}(x),\ldots ,f_{k}(x),\theta )\\{\text{s.t.}}&x\in X_{\theta }\end{array}}$

где $\theta$ — векторный параметр, множество $X_{\theta }\subseteq X$ представляет собой набор, зависящий от параметра $\theta$, и $g:\mathbb {R} ^{k+1}\rightarrow \mathbb {R}$ это функция.

Очень известные примеры:

• линейная скаляризация

$\min _{x\in X}\sum _{i=1}^{k}w_{i}f_{i}(x)$

где веса целей $w_{i}>0$ являются параметрами скаляризации.

• $\epsilon$-метод ограничений (см., напр. )

${\begin{array}{ll}\min &f_{j}(x)\\{\text{s.t.}}&x\in X\\&f_{i}(x)\leq \epsilon _{i}{\text{ for }}i\in \{1,\ldots ,k\}\setminus \{j\}\end{array}}$

где верхние границы $\epsilon _{j}$ являются параметрами, указанными выше, и $f_{j}$ цель, которую необходимо минимизировать.

Несколько более продвинутые примеры:

• достижение скаляризирующей задачи Вежбицкого

Один из примеров проблем скаляризации достижений можно сформулировать как

${\begin{aligned}\min &\max _{i=1,\ldots ,k}\left[{\frac {f_{i}(x)-{\bar {z}}_{i}}{z_{i}^{nadir}-z_{i}^{utop}}}\right]+\rho \sum _{i=1}^{k}{\frac {f_{i}(x)}{z_{i}^{nadir}-z_{i}^{utop}}}\\{\text{s.t. }}&x\in S\end{aligned}}$

где термин $\rho \sum _{i=1}^{k}{\frac {f_{i}(x)}{z_{i}^{nadir}-z_{i}^{utop}}}$ называется термином увеличения, $\rho >0$ является небольшой константой, и $z^{nadir}$ и $z^{utop}$ — векторы надира и утопии соответственно. В приведенной выше задаче параметром является так называемая точка отсчета. ${\bar {z}}$ представляющие значения целевой функции, предпочитаемые лицом, принимающим решения.

• Многоцелевое программирование Сена

${\begin{array}{ll}\max &{\frac {\sum _{j=1}^{r}Z_{j}}{W_{j}}}-{\frac {\sum _{j=r+1}^{s}Z_{j}}{W_{r+1}}}\\{\text{s.t. }}&AX=b\\&X\geq 0\end{array}}$

где $W_{j}$ — индивидуальные оптимумы (абсолютные) для целей максимизации. $r$ и минимизация $r+1$ к $s$.

• гиперобъем/скаляризация Чебышева

$\min _{x\in X}\max _{i}{\frac {f_{i}(x)}{w_{i}}}$

где веса целей $w_{i}>0$ являются параметрами скаляризации. Если параметры/веса нарисованы равномерно в положительном ортанте, показано, что эта скаляризация доказуемо сходится к фронту Парето , даже если передняя часть невыпуклая.

Например, оптимизация портфеля часто проводится с помощью анализа средней дисперсии . В этом контексте эффективный набор представляет собой подмножество портфелей, параметризованных средней доходностью портфеля. $\mu _{P}$ в задаче выбора акций портфеля для минимизации дисперсии доходности портфеля $\sigma _{P}$ при заданном значении $\mu _{P}$; см . в разделе «Теорема о разделении взаимных фондов» Подробности . В качестве альтернативы эффективный набор можно указать, выбрав доли в портфеле, чтобы максимизировать функцию. $\mu _{P}-b\sigma _{P}$; множество эффективных портфелей состоит из решений как $b$ находится в диапазоне от нуля до бесконечности.

Апостериорные методы

Апостериорные методы направлены на получение всех оптимальных по Парето решений или репрезентативного подмножества оптимальных по Парето решений. Большинство апостериорных методов относятся к одному из следующих трех классов:

• Математическое программирование - основанные на апостериорных методах, при которых алгоритм повторяется, и каждый запуск алгоритма дает одно оптимальное по Парето решение;
• Эволюционные алгоритмы , в которых один запуск алгоритма дает набор оптимальных по Парето решений;
• Методы глубокого обучения , при которых модель сначала обучается на подмножестве решений, а затем запрашивается для предоставления других решений на фронте Парето.

Математическое программирование

Хорошо известными примерами апостериорных методов, основанных на математическом программировании, являются нормальное пересечение границ (NBI), Модифицированное нормальное пересечение границы (NBIm), Нормальное ограничение (NC), Последовательная оптимизация Парето (SPO), и домен направленного поиска (DSD) методы, которые решают задачу многокритериальной оптимизации путем построения нескольких скаляризаций. Решение каждой скаляризации дает оптимальное по Парето решение, локальное или глобальное. Скаляризации методов NBI, NBIm, NC и DSD созданы для получения равномерно распределенных точек Парето, которые дают хорошее приближение реального набора точек Парето.

Эволюционные алгоритмы

Эволюционные алгоритмы — это популярные подходы к созданию оптимальных по Парето решений задач многокритериальной оптимизации. Большинство алгоритмов эволюционной многокритериальной оптимизации (EMO) применяют схемы ранжирования на основе Парето. Эволюционные алгоритмы, такие как недоминируемый генетический алгоритм сортировки-II (NSGA-II), его расширенная версия NSGA-III, Силовой эволюционный алгоритм Парето 2 (SPEA-2) и варианты многокритериальной дифференциальной эволюции стали стандартными подходами, хотя некоторые схемы основаны на оптимизации роя частиц и моделировании отжига. являются значительными. Основным преимуществом эволюционных алгоритмов при их применении для решения задач многокритериальной оптимизации является тот факт, что они обычно генерируют наборы решений, позволяющие вычислить аппроксимацию всего фронта Парето. Основным недостатком эволюционных алгоритмов является их меньшая скорость и невозможность гарантировать Парето-оптимальность решений; известно только, что ни одно из сгенерированных решений не доминирует над другим.

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

Методы глубокого обучения

Условные методы глубокого обучения — это новые подходы к созданию нескольких оптимальных по Парето решений. Идея состоит в том, чтобы использовать способность глубоких нейронных сетей к обобщению для изучения модели всего фронта Парето на основе ограниченного числа примеров компромиссов на этом фронте. Задача называется « Обучение фронта Парето» . Несколько подходов решают эту проблему, включая использование гиперсетей. и использование вариационного градиентного спуска Штейна.

Список методов

Ниже перечислены общеизвестные апостериорные методы:

• метод ε-ограничений
• Парето-гиперсети
• Многоцелевой метод ветвей и границ
• Нормальное пересечение границы (NBI)
• Модифицированное нормальное пересечение границы (NBIm)
• Нормальное ограничение (NC)
• Последовательная оптимизация Парето (SPO)
• Домен направленного поиска (DSD)
• НСГА-II
• PGEN (генерация поверхности Парето для выпуклых многокритериальных примеров)
• IOSO (косвенная оптимизация на основе самоорганизации)
• SMS-EMOA (эволюционный многокритериальный алгоритм выбора S-метрики)
• Эволюция, управляемая аппроксимацией (первый алгоритм для прямой реализации и оптимизации формальной концепции аппроксимации из теоретической информатики)
• Реактивная поисковая оптимизация (использование машинного обучения для адаптации стратегий и целей), реализовано в LIONsolver
• Алгоритм Бенсона для многокритериальных линейных программ и многокритериальных выпуклых программ
• Многоцелевая оптимизация роя частиц
• Алгоритм субпопуляции на основе новизны
• MOEA/D (Многоцелевой эволюционный алгоритм, основанный на декомпозиции)

Интерактивные методы

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

В интерактивных методах оптимизации обычно присутствуют следующие шаги:

1. инициализировать (например, рассчитать идеальные и аппроксимированные целевые векторы надира и показать их лицу, принимающему решения)
2. создать оптимальную по Парето отправную точку (используя, например, какой-либо метод отсутствия предпочтений или решение, данное лицом, принимающим решения)
3. запросить информацию о предпочтениях у лица, принимающего решения (например, уровень стремлений или количество новых решений, которые необходимо разработать)
4. сгенерировать новое оптимальное по Парето решение (решения) в соответствии с предпочтениями и показать его/их и, возможно, некоторую другую информацию о проблеме лицу, принимающему решение.
5. если было предложено несколько решений, попросите лицо, принимающее решение, выбрать лучшее решение на данный момент
6. остановиться (если этого хочет лицо, принимающее решение; в противном случае перейдите к шагу 3).

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

Типы информации о предпочтениях

Существуют различные интерактивные методы, включающие разные типы информации о предпочтениях. На основании можно выделить три типа

1. информация о компромиссе,
2. ориентиры и
3. классификация целевых функций.

С другой стороны, четвертый тип генерации небольшой выборки решений включает: Примером интерактивного метода, использующего компромиссную информацию, является метод Зионца-Валлениуса . где лицу, принимающему решение, показывают несколько объективных компромиссов на каждой итерации, и ожидается, что он скажет, нравится ли ему, не нравится или безразличен в отношении каждого компромисса. В методах, основанных на контрольных точках (см., например, ), ожидается, что лицо, принимающее решение, на каждой итерации будет указывать контрольную точку, состоящую из желаемых значений для каждой цели, а затем вычисляется соответствующее оптимальное по Парето решение(я) и показывается ему для анализа. В интерактивных методах, основанных на классификации, предполагается, что лицо, принимающее решения, дает предпочтения в форме классификации целей при текущем оптимальном по Парето решении на разные классы, указывая, как следует изменить значения целей, чтобы получить более предпочтительное решение. Затем информация классификации учитывается при вычислении новых (более предпочтительных) оптимальных по Парето решений. В методе удовлетворительного компромисса (STOM) используются три класса: цели, значения которых 1) следует улучшить, 2) можно ослабить и 3) приемлемы как таковые. В методе НИМБУС также используются два дополнительных класса: цели, значения которых 4) следует улучшать до заданной границы и 5) можно ослаблять до заданной границы.

Гибридные методы

Существуют разные гибридные методы, но здесь мы рассматриваем гибридизацию MCDM ( многокритериального принятия решений ) и EMO (эволюционной многокритериальной оптимизации). Гибридный алгоритм многокритериальной оптимизации сочетает в себе алгоритмы/подходы из этих двух областей (см., например, ). Гибридные алгоритмы EMO и MCDM в основном используются для преодоления недостатков за счет использования сильных сторон. В литературе было предложено несколько типов гибридных алгоритмов, например, включение подходов MCDM в алгоритмы EMO в качестве оператора локального поиска, ведущего DM к наиболее предпочтительному решению(ям) и т. д. Оператор локального поиска в основном используется для улучшения скорость сходимости алгоритмов ЭМО.

Истоки гибридной многокритериальной оптимизации можно проследить до первого семинара Дагштуля, организованного в ноябре 2004 года (см. здесь ). Здесь одни из лучших умов в EMO (профессор Калянмой Деб, профессор Юрген Бранке и т. д.) и MCDM (профессор Кайса Миеттинен, профессор Ральф Э. Стойер и т. д.) осознали потенциал объединения идей и подходов областей MCDM и EMO для подготовки их гибридов. Впоследствии было организовано еще много семинаров Дагштуля для развития сотрудничества. В последнее время гибридная многокритериальная оптимизация стала важной темой на нескольких международных конференциях в области EMO и MCDM (см., например, ).

Визуализация фронта Парето

Визуализация фронта Парето является одним из методов апостериорного предпочтения многокритериальной оптимизации. Методы апостериорного предпочтения представляют собой важный класс методов многокритериальной оптимизации. Обычно методы апостериорного предпочтения включают четыре этапа: (1) компьютер аппроксимирует фронт Парето, т. е. оптимальный по Парето набор в целевом пространстве; (2) лицо, принимающее решения, изучает приближение фронта Парето; (3) лицо, принимающее решение, определяет предпочтительную точку на фронте Парето; (4) компьютер обеспечивает оптимальное по Парето решение, результат которого совпадает с целевой точкой, определенной лицом, принимающим решение. С точки зрения лица, принимающего решения, второй этап техники апостериорных предпочтений является наиболее сложным. Существует два основных подхода к информированию лиц, принимающих решения. Во-первых, ряд точек фронта Парето можно представить в виде списка (интересное обсуждение и ссылки приведены в ) или с помощью тепловых карт.

Визуализация в двухцелевых задачах

В случае двухцелевых задач информирование лица, принимающего решения, о фронте Парето обычно осуществляется путем его визуализации: фронт Парето, часто называемый в этом случае кривой компромисса, может быть нарисован на объективной плоскости. Кривая компромисса дает полную информацию о целевых значениях и о объективных компромиссах, которые сообщают, как улучшение одной цели связано с ухудшением второй при движении по кривой компромисса. Лицо, принимающее решение, учитывает эту информацию при определении предпочтительной целевой точки, оптимальной по Парето. Идея аппроксимации и визуализации фронта Парето была предложена для линейных бицелевых задач принятия решений С. Гассом и Т. Саати. Эту идею разработал и применил в экологических проблемах Дж. Л. Кохон. Обзор методов аппроксимации фронта Парето для различных задач решения с небольшим числом целей (в основном двумя).

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

Существует две общие идеи визуализации фронта Парето в задачах многокритериального принятия решений высокого порядка (задачах с более чем двумя целями). Один из них, применимый в случае сравнительно небольшого числа объективных точек, представляющих фронт Парето, основан на использовании разработанных в статистике приемов визуализации (различные диаграммы и т. д.; см. соответствующий подраздел ниже). Вторая идея предлагает отображение двухобъектных сечений (срезов) фронта Парето. Он был представлен WS Meisel в 1973 году. который утверждал, что такие срезы информируют лиц, принимающих решения, об объективных компромиссах. Рисунки, отображающие серию двухцелевых срезов фронта Парето для трехкритериальных задач, известны как карты решений. Они дают четкую картину компромисса между тремя критериями. Недостатки такого подхода связаны со следующими двумя фактами. Во-первых, вычислительные процедуры для построения бицелевых срезов фронта Парето нестабильны, поскольку фронт Парето обычно нестабилен. Во-вторых, оно применимо только в случае трех целей. В 1980-е годы идея У.С.Мейзеля была реализована в другой форме — в виде методики Interactive Decision Maps (IDM). Совсем недавно Н. Веснер предложил использовать комбинацию диаграммы Венна и нескольких диаграмм рассеяния объективного пространства для исследования границы Парето и выбора оптимальных решений.

См. также

• Параллельное программирование
• Программное обеспечение для принятия решений
• Целевое программирование
• Интерактивные карты решений
• Многокритериальное принятие решений
• Многоцелевое линейное программирование
• Многопрофильная оптимизация дизайна
• Парето-эффективность
• Функция полезности
• Векторная оптимизация

Внешние ссылки

• Эммерих, МТМ, Дойц, А.Х. Учебное пособие по многокритериальной оптимизации: основы и эволюционные методы. Nat Comput 17, 585–609 (2018). https://doi.org/10.1007/s11047-018-9685-y
• Международное общество по принятию решений по множественным критериям
• Эволюционная многокритериальная оптимизация , Демонстрационный проект Wolfram
• Учебное пособие по многокритериальной оптимизации и генетическим алгоритмам , Scilab профессиональный партнер
• Томойага, Богдан; Чиндрис, Мирча; Сампер, Андреас; Судрия-Андреу, Антони; Вильяфафила-Роблес, Роберто. 2013. «Оптимальная по Парето реконфигурация систем распределения электроэнергии с использованием генетического алгоритма на основе NSGA-II». Энергии 6, нет. 3: 1439-1455.
• Список литературы по эволюционной многокритериальной оптимизации