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

Фонд генетических алгоритмов

Генетические алгоритмы основаны на аналогии со структурой и поведением хромосом популяции с точки зрения генетики. Основа ГА, основанная на этом сравнении, заключается в следующем:

1. Члены популяции конкурируют друг с другом за ресурсы и спариваются
2. Успешные люди (наиболее приспособленные) спариваются, чтобы иметь больше детей, чем менее успешные люди.
3. Гены «самого приспособленного» родителя распространяются по поколению. , что означает, что иногда родители могут производить детей, которые превосходят их обоих.
4. В результате каждое последующее поколение становится более приспособленным к своему окружению.

Пространство поиска

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

Оценка фитнеса

Каждый человек получает оценку физической подготовки, меру его способности «соревноваться». Человек с лучшим показателем физической подготовки (или очень близким к нему) пользуется спросом.

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

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

Операторы генетических алгоритмов

После создания начального поколения алгоритм развивается/улучшается с использованием следующих операторов:

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

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

Преимущества

Генетический алгоритм — это мощный метод оптимизации, который имеет ряд преимуществ, некоторые из которых включают:

  1. Глобальные оптимумы. Генетический алгоритм может выполнять поиск во всем пространстве решений и находить глобальный оптимум, который является наилучшим возможным решением. Это отличается от других методов оптимизации, таких как градиентный спуск, который может застрять в локальных оптимумах.
  2. Решение сложных и нелинейных задач. Генетический алгоритм хорошо подходит для решения сложных и нелинейных задач, например задач с несколькими решениями или с неизвестными или меняющимися отношениями между переменными.
  3. Надежность. Генетические алгоритмы устойчивы к зашумленным или неполным данным и могут решать проблемы с большим количеством переменных и ограничений. Они также могут обрабатывать ограничения, которые трудно выразить математически, что делает их универсальным методом оптимизации для широкого круга задач.

Недостатки

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

Краткое содержание

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