Учебники

Генетические алгоритмы – основы

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

Основная терминология

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

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

  • Хромосомы . Хромосома – одно из таких решений данной проблемы.

  • Ген – ген является одним из элементов хромосомы.

  • Аллель – это значение, которое ген принимает для конкретной хромосомы.

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

Хромосомы . Хромосома – одно из таких решений данной проблемы.

Ген – ген является одним из элементов хромосомы.

Аллель – это значение, которое ген принимает для конкретной хромосомы.

терминология

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

  • Фенотип. Фенотип – это совокупность в реальном пространстве решений реального мира, в которой решения представлены так, как они представлены в ситуациях реального мира.

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

    Например, рассмотрим проблему ранца 0/1. Пространство фенотипа состоит из решений, которые просто содержат номера предметов для выбора.

    Однако в пространстве генотипа его можно представить в виде двоичной строки длиной n (где n – количество элементов). 0 в позиции x означает, что x- й элемент выбран, а 1 – наоборот. Это тот случай, когда генотип и фенотип пространства различаются.

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

Фенотип. Фенотип – это совокупность в реальном пространстве решений реального мира, в которой решения представлены так, как они представлены в ситуациях реального мира.

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

Например, рассмотрим проблему ранца 0/1. Пространство фенотипа состоит из решений, которые просто содержат номера предметов для выбора.

Однако в пространстве генотипа его можно представить в виде двоичной строки длиной n (где n – количество элементов). 0 в позиции x означает, что x- й элемент выбран, а 1 – наоборот. Это тот случай, когда генотип и фенотип пространства различаются.

Фенотип и генотип пространства

  • Функция пригодности – просто определенная функция пригодности – это функция, которая принимает решение в качестве входных данных и выдает пригодность решения в качестве выходных данных. В некоторых случаях фитнес-функция и целевая функция могут быть одинаковыми, в то время как в других они могут различаться в зависимости от проблемы.

  • Генетические операторы – Они изменяют генетический состав потомства. К ним относятся кроссовер, мутация, отбор и т. Д.

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

Генетические операторы – Они изменяют генетический состав потомства. К ним относятся кроссовер, мутация, отбор и т. Д.

Базовая структура

Основная структура ГА выглядит следующим образом –

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

Каждый из следующих шагов рассматривается в отдельной главе далее в этом руководстве.

Базовая структура

Обобщенный псевдокод для GA объясняется в следующей программе: