Нежное введение в многоцелевую оптимизацию

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

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

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

Оптимизация и одноцелевая оптимизация

Все алгоритмы глубокого обучения используют алгоритм оптимизации, который помогает сети максимизировать или минимизировать целевую функцию в зависимости от варианта использования. В общем, оптимизация относится к задаче минимизации или максимизации некоторой функции F(x) путем изменения x, где вводится 'x' [1].

Например, мы хотим построить модель классификации изображений собаки 🐶 и кошки 😺. Мы подготовили набор данных. Мы хотим, чтобы модель точно классифицировала изображение, а это значит, что мы хотим максимизировать точность предсказания модели; с другой стороны, мы также можем переопределить мою цель, сказав, что мы хотим минимизировать потери. Хотим ли мы максимизировать точность или минимизировать потери, цель модели достигнута. Так что цель одна. Это известно как одноцелевая оптимизация.

Многоцелевая оптимизация

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

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

Проблема с линейной одномерной оптимизацией

Теперь может возникнуть вопрос: «В чем проблема с одиночной оптимизацией или 1D-оптимизацией?» Что ж, недостатки одномерной оптимизации многоцелевых задач заключаются в том, что мы часто приходим к разным решениям, пытаясь оптимизировать одну целевую функцию по сравнению с другой. Итак, например, предположим, что у нас есть две целевые функции, поэтому, если мы применим метод одномерной оптимизации, мы должны применить его к одной целевой функции за раз, т.е. одномерная оптимизация для цели-1, сохраняя цель-2 постоянной или скрытой. , как только цель-1 оптимизирована, мы применяем оптимизацию к цели-2. Таким образом, мы получаем оптимальное значение, которое может не совпадать с результатом того же процесса, но на этот раз сначала оптимизируется цель-2, а затем цель-1. Таким образом, вместо узкого взгляда мы хотим увидеть пространство решений с высоты птичьего полета, чтобы найти оптимальное решение.

Давайте возьмем пример покупки автомобиля, чтобы понять эту проблему более кристально ясно. Допустим, моя цель — купить недорогую машину с хорошим пробегом. Ось X представляет «пробег» по мере того, как мы движемся вправо от начала координат, тем лучше пробег. Ось Y представляет «Стоимость» автомобиля; по мере продвижения вверх стоимость снижается. Поэтому мы называем ось X и ось Y «Хороший пробег» и «Низкая стоимость», чтобы лучше понять концепцию.

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

У нас есть следующие сценарии -

Сценарий 1. Сначала применяется одномерная оптимизация для цели 1, т. е. "Хороший пробег", а затем одномерная оптимизация для цели 2, т. е. "Низкая стоимость".
Сценарий 2: применение одномерной оптимизации к цели 2, т. е. сначала низкая стоимость, а затем одномерная оптимизация к цели 1, т. е. хороший пробег.

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

Сценарий 1: хороший пробег, за которым следует низкая стоимость

Ссылаясь на вышеизложенное (рис. 3(а)), нам нужна машина с хорошим пробегом, поэтому мы включим факел и двинемся к последней машине, которую видим, то есть к машине «C3».
После того, как мы узнаем, что достигли автомобиля с лучшим пробегом (учитывая видимость факела) в автосалоне, второй целью является поиск недорогого автомобиля, поэтому мы направим свой факел в эту сторону (см. рис. 3. (b). )).
Единственная машина, которую мы можем найти, это машина «C4».

Сценарий 2: Низкая стоимость, за которой следует хороший пробег

Ссылаясь на вышеизложенное (рис. 4 (а)), мы хотим автомобиль с низкой стоимостью, поэтому мы включим факел и двинемся к недорогому автомобилю, который мы могли видеть, то есть к автомобилю «C5».
Теперь мы знаем, что прибыли к лучшему недорогому автомобилю (учитывая видимость факела) в выставочном зале. Вторая цель — найти автомобиль с хорошим пробегом, поэтому я направлю свой факел в эту сторону (см. рис. 4 (b)).
Единственная машина, которую мы можем найти, это машина «C6».

Ниже приведена сводная таблица двух сценариев, обсуждавшихся до сих пор:

Странно, правда 🤔? Итак, в сценарии 1 у нас есть автомобиль C4, а в сценарии 2 у нас есть автомобиль C6.

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

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

Именно по этой причине в подобных задачах более полезен вид с высоты птичьего полета.

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

Типы многоцелевых подходов к оптимизации

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

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

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

Вес целевой функции определит оптимальное решение и покажет нам приоритет производительности (подробнее см. [4]).

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

Подход Парето

Прежде чем понять концепцию Парето, давайте разберемся с тестом на доминирование.

Доминируемые решения — это решения, которые не являются оптимальными, т. е. существуют другие точки, которые превосходят эту точку. Например, на рис. 6 точка «А» доминирует над точкой «В», а точка «С» доминирует как над «А», так и над «В». Решения, над которыми не может доминировать ни одна точка в допустимом пространстве решений, называются «недоминируемыми решениями», также известными как Парето-эффективные.

Набор недоминируемых решений называется Парето-оптимальными решениями/набором. Фронт Парето — это граница, определяемая набором всех точек в целевом пространстве или критериальном пространстве, отображенным из оптимального набора Парето в пространстве решений, см. рис. 7. Как только мы найдем решение Парето, мы можем применить другие алгоритмы поверх него, а не чем вычисление неразрешимого пространства решений, которое мы сократили до конечного множества. Парето-оптимальные решения иногда называют «неуступчивыми».

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

Классические методы MOO
а. Метод взвешенной суммы (подробности см. в [5] на слайде 10)
b. Метод ε-ограничений (подробнее см. [5] на слайде 15)
c. Метод взвешенных метрик (подробнее см. [5] на слайде 18)
d. Подход на основе глобальных критериев (см. [6])
e. Целевое программирование (GP) (см. [6])
MOO с использованием генетических алгоритмов (MOGA) (подробнее см. [5] на слайде 22)
Эволюционные алгоритмы МО (МОЭА) (подробнее см. в [5] на слайде 25)
a. Неэлитарные MOEA
b. Элитарные МОЭ

Приложения

Существует множество замечательных приложений многоцелевой оптимизации, таких как открытие/разработка лекарств [8], задачи ранжирования [9], оптимизация маршрутизации [10], настройка гиперпараметров, выбор ретрансляторов в специальных сетях [4] и многое другое.

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

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

Надеюсь, вы поняли некоторые фундаментальные основы, необходимые для понимания проблем многоцелевой оптимизации. Приветствую дальнейшие исследования в MOO 🥂.