Как оптимизировать наборы признаков с помощью генетических алгоритмов

Оптимизация наборов признаков с генетическими алгоритмами

Предварительные требования

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

Введение в оптимизацию

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

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

Давайте рассмотрим y = f(x); если f’(x) = 0 в точке x = x*, то в этой точке существует оптимум (максимум или минимум) или точка перегиба.

При ближайшем рассмотрении становится ясно, что первая ненулевая производная более высокого порядка обычно обозначается как ‘n’, так что.

  • Если n – это нечетное число, то x* – это точка перегиба.
  • В противном случае x* – это локальная оптимальная точка. 

Дополнительные пояснения…

  • Если значение следующей производной высокого порядка +ve, то x* – это локальная минимальная точка.
  • Если значение следующей производной высокого порядка -ve, то x* – это локальная максимальная точка. 

Например:

Принципы оптимизации

Рассмотрим задачу оптимизации с ограничениями ниже:

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

Что такое генетический алгоритм?

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

Генетические алгоритмы (ГА) были разработаны Джоном Холландом, а также его студентами и коллегами в университете Мичигана, в частности, Дэвидом Э. Голдбергом. С тех пор ГА были применены в широком спектре задач оптимизации и всегда достигали высоких результатов.

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

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

Почему генетический алгоритм?

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

  • Универсальность: ГА могут применяться к широкому спектру задач оптимизации, что делает их универсальным выбором для различных областей, включая инженерию, финансы, биологию и другие.
  • Глобальный поиск: ГА отлично справляются с исследованием всего пространства поиска, что позволяет находить решения, которые могут быть пропущены локальными алгоритмами поиска. Это делает их подходящими для проблем с несколькими локальными оптимумами.
  • Не требуются производные: В отличие от многих методов оптимизации, ГА не требуют производных целевой функции, что позволяет применять их к проблемам с не непрерывными, зашумленными или сложными функциями приспособленности.
  • Параллелизм: ГА могут эффективно параллелиться, что позволяет быстрее сходиться на высокопроизводительных вычислительных системах.
  • Стохастический характер: Стохастический характер ГА обеспечивает возможность избежать локальных оптимумов и более полно исследовать пространство поиска.
  • Адаптируемость: ГА могут адаптировать и корректировать свои стратегии поиска со временем, что особенно полезно для динамических или изменяющихся задач оптимизации.
  • Разнообразие решений: ГА

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

    Терминология генетического алгоритма

    • Популяции и поколения: Популяция – это массив индивидуумов. Например, если размер популяции равен 100, а количество переменных в функции приспособленности равно 3, то популяцию можно представить в виде матрицы размером 100 на 3. Один и тот же индивид может появиться в популяции несколько раз. Например, индивид (2, -3, 1) может появиться в нескольких строках массива. На каждой итерации генетический алгоритм выполняет серию вычислений на текущей популяции для создания новой популяции. Каждая последующая популяция называется новым поколением.
    • Родители и потомки: Для создания следующего поколения генетический алгоритм выбирает определенных индивидуумов в текущей популяции, называемых родителями, и использует их для создания индивидуумов в следующем поколении, называемых потомками. Обычно алгоритм предпочитает выбирать родителей с более высокими значениями приспособленности.
    • Индивидуумы: Индивидуум – это любая точка, к которой можно применить функцию приспособленности. Значение функции приспособленности для индивида является его оценкой. Например, если функция приспособленности имеет вид:
      • f(x1,x2,x3)=(2×1+1)2+(3×2+4)2+(x3−2)2
      • Вектор (2, -3, 1), длина которого равна количеству переменных в задаче, является индивидом. Оценка индивида (2, –3, 1) составляет f(2, –3, 1) = 51.

    Индивидуум иногда называют геномом или хромосомой, а записи вектора индивида – генами.

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

    Основной генетический алгоритм (ГА): псевдокод

    Подробные стратегии основного генетического алгоритма (ГА)

    Кодирование и популяция

    Хромосома кодирует решение в пространстве поиска.

    • Обычно в виде строк из 0 и 1.
    • Если l – длина строки, то количество различных хромосом (или строк) равно 2l.

    Популяция

    • Набор хромосом в поколении.
    • Размер популяции обычно постоянный.
    • Обычной практикой является случайный выбор начальной популяции.

    Оценка приспособленности

    • Функция пригодности/целевая функция ассоциируется с каждым хромосомом.
    • Это указывает на степень хорошести закодированного решения.
    • Если решается задача минимизации, то пригодность = 1 / цель или пригодность = -1 * цель.
    • Если решается задача максимизации, то пригодность = цель.

    Отбор

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

    Кроссовер

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

    Мутация

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

    Элитизм

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

    Критерии остановки

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

    Количество поколений (или итераций) больше некоторого порога (наиболее часто используется).

    Вариации генетических алгоритмов (ГА)

    • Дифференциальная эволюция (DE): DE – это вариант ГА, специально разработанный для оптимизации вещественных значений. Он использует мутационные и рекомбинационные операторы на основе векторов.
    • Алгоритмы оценки распределений (EDAs): EDAs моделируют и изучают вероятностное распределение перспективных решений в популяции и используют это распределение для генерации новых кандидатских решений.
    • Самоадаптивные генетические алгоритмы: Позволяют алгоритму адаптировать свои генетические операторы (скорости мутации, типы кроссовера) на основе характеристик развивающейся популяции, что приводит к эффективной сходимости.
    • Алгоритмы ниширования: Эти алгоритмы фокусируются на поиске нескольких разнообразных решений за один запуск, часто в многомодальной оптимизации, где есть несколько пиков или режимов в ландшафте пригодности.
    • Многокритериальные эволюционные алгоритмы (MOEAs): MOEAs решают проблемы с несколькими противоречивыми целями. Они стремятся найти набор Парето-оптимальных решений, представляющих компромиссы между этими целями.
    • Гибридные алгоритмы: Интегрируют ГА с другими методами оптимизации, моделями машинного обучения или доменно-специфичными эвристиками для повышения производительности и надежности.

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

    Я благодарен за ваше время и внимание! Вы можете связаться со мной на Linkedin.