КУРС ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ
Блок 1) Теория оптимизации
Обзор теории оптимизации и четырех основных типов задач оптимизации
Здравствуйте и добро пожаловать обратно на этот полный курс по эволюционным вычислениям! В этом посте мы начнем с раздела 1 курса «Теория оптимизации». В предыдущем посте мы рассмотрели базовый обзор курса, вы можете ознакомиться с ним здесь:
Для начала, что такое теория оптимизации? Теория оптимизации - это раздел математики, посвященный решению задач оптимизации. Задачи оптимизации - это математические функции, в которых мы хотим минимизировать или максимизировать значение функции. Проблемы такого типа часто встречаются в информатике и прикладной математике. Поиск хороших решений этих проблем - это то, что обеспечивает хорошую точность моделям науки о данных и машинного обучения, поскольку сами они построены на численных методах, используемых для поиска хороших решений для минимизации функций ошибок. Примеры распространенных проблем оптимизации в машинном обучении: минимизация MSE, MAE, кросс-энтропии и т. Д.
Оглавление
- Обзор
- Неограниченные проблемы
- Ограниченные проблемы
- Проблемы с несколькими решениями
- Многоцелевые задачи
- Функции тестирования производительности
- Заключение
Обзор
В кратком обзоре теорию оптимизации можно свести к трем вопросам:
1. Что такое целевая функция?
2. Что такое набор представляющих интерес переменных?
3. Что такое набор ограничений?
Знание того, как выглядит ваша целевая функция с точки зрения количества измерений, области и количества локальных экстремумов, жизненно важно при выборе алгоритма. Кроме того, необходимо понимать тип данных для каждой из переменных: дискретный или непрерывный? Наконец, знание набора ограничений важно для ограничения вашего алгоритма при поиске в доменном пространстве только возможных решений.
Если вы помните из математического анализа, оптимумы, иначе известные как критические точки, - это точки в доменном пространстве, такие, что наклон функции в этой точке равен нулю. Эти точки обычно называют экстремумами, классифицируемыми как минимум или максимум. Экстремумы можно разделить на три основных типа:
1. Слабые экстремумы
2. Сильные экстремумы
3. Глобальные экстремумы
4. Седловые точки
Слабые экстремумы - это критические точки, так что соседние точки вокруг имеют одинаковое значение функции, создавая плато (как видно на рисунке выше). Сильные экстремумы - это критические точки, которые имеют либо наибольшее (для максимизации), либо наименьшее (для минимизации) значение функции из соседних точек, создавая долину или гору. Глобальные экстремумы - это точки сильных экстремумов, значение функции которых является либо наибольшим (для максимизации), либо наименьшим (для минимизации) глобально для всех точек сильных экстремумов. Наконец, седловые точки, мы не будем особо разбираться с ними в нашем курсе, но они случаются. Седловые точки представляют собой точки перегиба между вогнутыми вверх и вогнутыми вниз тенденциями. Поскольку мы не будем иметь дело с седловыми точками, я не буду раскрывать большую часть их интуиции.
Существует четыре основных типа задач оптимизации: без ограничений, с ограничениями, с несколькими решениями и с несколькими целями.
Неограниченные проблемы
Неограниченные Проблемы такие же, как они звучат, неограниченные. Это функции, в которых мы хотим минимизировать или максимизировать функцию с учетом набора переменных, область определения которых является либо непрерывной, либо дискретной, либо и тем, и другим. Вот определение:
Ограниченные проблемы
Ограниченные задачи похожи на неограниченные проблемы с точки зрения настройки, но имеют уникальные ограничения входного пространства. Вот определение:
В качестве наглядного примера ниже приведены примеры этих компонентов. Во-первых, у нас есть целевая функция, обозначенная A. Затем у нас есть глобальный неограниченный минимум в правом нижнем углу в точке E. Однако мы вводим ограничение неравенства, обозначенное линией D, где любое значение в клетчатой области недопустимо. Таким образом, нам остается работать с частью домена. Точки B и C - две критические точки в допустимом доменном пространстве. Однако следующий глобальный минимум в ограниченной среде будет в точке F. Таким образом, в таких сценариях, как этот, мы хотели бы, чтобы наш алгоритм уклонялся от недопустимого доменного пространства и находил следующее наилучшее минимальное значение.
Здесь ниже у нас есть пример взаимодействия доменного пространства между двумя переменными в ограниченной среде. Здесь мы видим, что X и Y - непрерывные переменные, которые могут находиться в диапазоне от 0 до 2. Однако мы добавляем ограничение, так что по мере того, как X стремится к 2, Y уменьшается; но если Y стремится к 2, X начинает уменьшаться. Это можно увидеть по синему полукольцу, которое представляет допустимое пространство ввода, а прозрачный фон представляет недопустимое пространство домена.
Проблемы с несколькими решениями
Задачи с несколькими решениями - это функции, в которых нет уникальных глобальных экстремумов; вместо этого есть привязанные глобальные решения. В этих случаях мы хотим вернуть все связанные глобальные решения (отсюда и название мульти-решение), чтобы предоставить нам ряд вариантов на выбор. В реальном приложении мы могли бы захотеть минимизировать некоторый тип функции стоимости, где мы обнаружили, что существует несколько решений. Наша цель - вернуть эти несколько решений, чтобы у нас была возможность выбрать, какая точка или вектор значений переменных лучше всего соответствует нашим интересам. Вот точное определение:
Ниже приведен пример задачи с несколькими решениями. Это вариация волновой функции sin. Как видим, мы связали глобальные минимумы и максимумы для этой задачи. Обратите внимание, однако, что не все проблемы с множественными решениями возникают периодически, как волна греха, где легко предсказать следующее значение, эти связанные глобальные экстремумы, скорее всего, будут ложно повсюду в доменном пространстве и без шаблона.
Многоцелевые задачи
Многоцелевые задачи (MOP) - это проблемы, в которых у нас есть много разных целей или задач оптимизации, которые нам нужно решать одновременно. Есть два основных метода решения подобных проблем:
1. Взвешенное агрегирование
2. Оптимальность по Парето.
Взвешенное агрегирование - это просто совокупность всех целевых функций. Мы просто суммируем каждую целевую функцию, умножаем на соответствующее значение веса и пытаемся минимизировать или максимизировать эту сумму. Обычно предполагается, что сумма весов равна единице. Здесь у нас есть пример агрегатной функции, которую мы хотим одновременно минимизировать F1 и F2. Обратите внимание, что каждая функция имеет связанное значение веса, где большие значения веса указывают, какая функция имеет наибольшее влияние.
Вот точное определение взвешенной агрегации:
Оптимальность по Парето - еще один способ решить MOP, классифицируя возможные решения в структуре доминирования. Доминирование - это способ отличить хорошие решения от плохих. Есть два основных типа доминирования: сильное и слабое. Сильное доминирование возникает, когда возможное решение равно или лучше, чем другое возможное решение по всем целям, и лучше, чем по крайней мере по одной цели. Вот точное определение из учебника:
С другой стороны, слабое доминирование утверждает, что возможное решение не хуже другого решения по всем целям. Вот точное определение:
В качестве примера обоих типов господства здесь у нас есть фигура из учебника с некоторыми переигранными числами, которые я добавил:
По оси x у нас есть значение F1, а по оси y - значение F2. В этом сценарии мы хотим минимизировать как F1, так и F2, поэтому наилучшее решение возникает в начале координат, когда F1 == F2 == 0. Точка F обозначена в нижнем среднем левом углу красным кружком. Сначала у нас есть все точки, в которых сильно доминирует F, раздел B. В этих точках сильно доминирует F, поскольку они имеют худшие значения в F1 И в F2. С другой стороны, в разделах A и D лишь слабо доминирует F, поскольку они имеют лучшие значения по крайней мере по одной цели. Секция A хуже, чем F, с точки зрения F2, поскольку ее значения функции больше, но лучше с точки зрения F1, поскольку ее значения функции меньше. Раздел D наоборот, он хуже F по F1, но лучше по F2. Наконец, у нас есть Раздел C, который доминирует над Разделами 1, 2, 4 и Пунктом F, поскольку этот раздел лучше, чем все другие функции, по крайней мере, в одной цели, но при этом равен или лучше, чем в остальных.
Вся цель введения этого понятия доминирования - найти Парето-фронт. Парето-фронт - это набор векторов решений, каждый из которых слабо доминирует друг над другом, но сильно доминирует над всеми другими векторами во входном пространстве. Вот пример Парето-фронта для двух целей:
Как мы видим, минимум происходит, когда как F1 == F2 == 0; однако проблема в том, что точка минимума для F1, вероятно, не такая же, как для F2. Таким образом, мы получаем диапазон значений на выбор. Как указывалось ранее, Фронт Парето слабо доминирует над самим собой, в то же время сильно доминируя над остальной частью доменного пространства; Таким образом, возвращение этого фронта дает пользователю возможность выбирать решения, которые лучше всего соответствуют его потребностям. Например, если F1 более важен для минимизации этого F2, тогда вы можете выбрать решение со слабым преобладанием, которое отдает предпочтение F1. Вот еще один пример фронта Парето для дискретной задачи:
Причина, по которой я привожу это изображение выше, состоит в том, чтобы показать, что Парето-Фронт не всегда представляет собой красивую выпуклую кривую, как раньше, но может быть спорадическим и трудно предсказуемым.
Функции тестирования производительности
Функции тестирования производительности предназначены для задач математической оптимизации алгоритмов тестирования. Это искусственно созданные задачи, не имеющие приложения, но разработанные таким образом, что они будут «такими же трудными» или более «трудными», чем приложения в реальном мире. В литературе, вместо сравнения алгоритмов, основанных на определенных приложениях, которые могут потребовать обширных знаний предметной области; Исследователи часто сравнивают функции по тому, насколько хорошо они могут находить глобальные экстремумы в этих тестовых функциях. Существует множество различных типов функций тестирования производительности, вот три функции тестирования, которые обычно встречаются в литературе:
Позже в ходе курса мы будем тестировать наши алгоритмы на таких тестовых функциях, как эти.
Заключение
Таким образом, проблемы оптимизации можно разделить на четыре категории. Неограниченные задачи, в которых границы фиксированы и не меняются. Ограниченные проблемы, когда домен изменялся в зависимости от значений переменных. Задачи с несколькими решениями, когда нет уникальных глобальных минимумов / максимумов, и мы хотим вернуть все значения. Наконец, многоцелевой, где мы хотим найти фронт Парето.
Проблемы оптимизации чрезвычайно многочисленны во многих областях исследований, будь то планирование трафика, максимизация производства на основе различных переменных, эффективное использование электроэнергии для обучения нейронной сети, игрового моделирования или оптимизации моделей науки о данных. В этих обстоятельствах цель состоит в том, чтобы минимизировать или максимизировать функцию оптимизации, где каждый оптимум представляет собой возможное решение. Однако нам не нужно просто возможное решение, мы хотим лучшее решение, глобальные минимумы или максимумы. Так как же нам найти эти глобальные точки экстремумов? Мы могли бы использовать стандартные численные методы, такие как метод Ньютона или сопряженный градиент; или, возможно, мы могли бы использовать другие методы оптимизации, такие как чехарда, восхождение на гору или имитация отжига. В этой серии статей мы рассмотрим использование эволюционных вычислений как средство нахождения этих глобальных экстремумов.
Почему мы должны использовать эволюционные вычисления в первую очередь, а не классические методы оптимизации? Проблема с классическими алгоритмами оптимизации обычно заключается в том, что они детерминированы, то есть вы вводите ему одну и ту же начальную точку, и он всегда будет давать вам один и тот же результат, он также является последовательным, что означает, что алгоритм может работать только с использованием одной точки за раз, и для этого может потребоваться дифференциальная информация, особенно о производных первого и второго порядка. С другой стороны, эволюционные вычисления - это метод случайного поиска, что означает, что если вы введете в него одну и ту же начальную точку, нет гарантии, что результат будет таким же, как к лучшему, так и к худшему, он также использует параллельный поиск, работая с популяцией. начальных точек, а не один, и он работает очень хорошо, когда проблема не дифференцируема. По этим причинам эволюционные вычисления обычно используются для задач, которые классифицируются как сложные задачи NP, таких как коммивояжер или планирование, или когда функция оптимизации не дифференцируема.
На этом завершается блок 1 по теории оптимизации, следите за обновлениями для блока 2, посвященного введению в эволюционные вычисления, методологии решения задач оптимизационного типа:
