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

По словам Чарльза Дарвина:

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

Интересно, что вся концепция генетических алгоритмов вращается вокруг этой единственной цитаты.

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

Биологическое вдохновение

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

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

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

В генетическом алгоритме рассматриваются пять фаз.

  1. Начальная популяция
  2. Функция фитнеса
  3. Выбор
  4. Кроссовер
  5. Мутация

Начальная популяция

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

В генетическом алгоритме хромосомы представлены набором алфавитов, а гены кодируются в двоичном формате.

Фитнес-функция

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

Расчет значения пригодности выполняется многократно в GA и, следовательно, должен быть достаточно быстрым. Медленное вычисление значения пригодности может отрицательно повлиять на GA и сделать его исключительно медленным.

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

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

Выбор

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

Различные стратегии отбора, используемые в этом процессе, включают следующее:

  1. Выбор колеса рулетки
  2. Стохастическая универсальная выборка (SUS)
  3. Турнирный отбор
  4. Выбор ранга
  5. "Случайный выбор"

Переходить

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

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

Используется несколько видов кроссоверных стратегий, среди которых самые популярные:

  1. Одноточечный кроссовер
  2. Многоточечный кроссовер
  3. Единый кроссовер
  4. Кроссовер Ордена Дэвиса (OX1)
  5. Кроссовер с полной арифметической рекомбинацией

Мутация

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

Различные типы операторов мутации, доступные на выбор разработчикам, включают:

  1. BitFlip Mutation
  2. Случайная перезагрузка
  3. Своп Мутация
  4. Схватка мутации
  5. Инверсионная мутация

Псевдокод

START
Generate the initial population
Compute fitness
REPEAT
    Selection
    Crossover
    Mutation
    Compute fitness
UNTIL population has converged
STOP