В этом разделе представлена основная терминология, необходимая для понимания ГА. Кроме того, общая структура GA представлена как в псевдокоде, так и в графической форме . Читателю рекомендуется правильно понимать все концепции, представленные в этом разделе, и помнить о них при чтении других разделов этого учебника.
Основная терминология
Прежде чем начать обсуждение генетических алгоритмов, важно ознакомиться с некоторой базовой терминологией, которая будет использоваться в этом учебном пособии.
-
Население — это подмножество всех возможных (закодированных) решений данной проблемы. Население для ГА аналогично населению для людей, за исключением того, что вместо людей у нас есть кандидатские решения, представляющие людей.
-
Хромосомы . Хромосома — одно из таких решений данной проблемы.
-
Ген — ген является одним из элементов хромосомы.
-
Аллель — это значение, которое ген принимает для конкретной хромосомы.
Население — это подмножество всех возможных (закодированных) решений данной проблемы. Население для ГА аналогично населению для людей, за исключением того, что вместо людей у нас есть кандидатские решения, представляющие людей.
Хромосомы . Хромосома — одно из таких решений данной проблемы.
Ген — ген является одним из элементов хромосомы.
Аллель — это значение, которое ген принимает для конкретной хромосомы.
-
Генотип — генотип — популяция в вычислительном пространстве. В вычислительном пространстве решения представлены таким способом, который можно легко понять и манипулировать с помощью вычислительной системы.
-
Фенотип. Фенотип — это совокупность в реальном пространстве решений реального мира, в которой решения представлены так, как они представлены в ситуациях реального мира.
-
Декодирование и кодирование — Для простых задач фенотип и пространство генотипа одинаковы. Однако в большинстве случаев пространства фенотипа и генотипа различны. Декодирование — это процесс преобразования решения из генотипа в пространство фенотипа, в то время как кодирование — это процесс преобразования из фенотипа в пространство генотипа. Декодирование должно быть быстрым, поскольку оно выполняется многократно в GA во время вычисления значения пригодности.
Например, рассмотрим проблему ранца 0/1. Пространство фенотипа состоит из решений, которые просто содержат номера предметов для выбора.
Однако в пространстве генотипа его можно представить в виде двоичной строки длиной n (где n — количество элементов). 0 в позиции x означает, что x- й элемент выбран, а 1 — наоборот. Это тот случай, когда генотип и фенотип пространства различаются.
Генотип — генотип — популяция в вычислительном пространстве. В вычислительном пространстве решения представлены таким способом, который можно легко понять и манипулировать с помощью вычислительной системы.
Фенотип. Фенотип — это совокупность в реальном пространстве решений реального мира, в которой решения представлены так, как они представлены в ситуациях реального мира.
Декодирование и кодирование — Для простых задач фенотип и пространство генотипа одинаковы. Однако в большинстве случаев пространства фенотипа и генотипа различны. Декодирование — это процесс преобразования решения из генотипа в пространство фенотипа, в то время как кодирование — это процесс преобразования из фенотипа в пространство генотипа. Декодирование должно быть быстрым, поскольку оно выполняется многократно в GA во время вычисления значения пригодности.
Например, рассмотрим проблему ранца 0/1. Пространство фенотипа состоит из решений, которые просто содержат номера предметов для выбора.
Однако в пространстве генотипа его можно представить в виде двоичной строки длиной n (где n — количество элементов). 0 в позиции x означает, что x- й элемент выбран, а 1 — наоборот. Это тот случай, когда генотип и фенотип пространства различаются.
-
Функция пригодности — просто определенная функция пригодности — это функция, которая принимает решение в качестве входных данных и выдает пригодность решения в качестве выходных данных. В некоторых случаях фитнес-функция и целевая функция могут быть одинаковыми, в то время как в других они могут различаться в зависимости от проблемы.
-
Генетические операторы — Они изменяют генетический состав потомства. К ним относятся кроссовер, мутация, отбор и т. Д.
Функция пригодности — просто определенная функция пригодности — это функция, которая принимает решение в качестве входных данных и выдает пригодность решения в качестве выходных данных. В некоторых случаях фитнес-функция и целевая функция могут быть одинаковыми, в то время как в других они могут различаться в зависимости от проблемы.
Генетические операторы — Они изменяют генетический состав потомства. К ним относятся кроссовер, мутация, отбор и т. Д.
Базовая структура
Основная структура ГА выглядит следующим образом —
Мы начнем с начальной популяции (которая может быть сгенерирована случайным образом или посеяна другими эвристиками), выбираем родителей из этой популяции для спаривания. Примените кроссовер и операторы мутации на родителях, чтобы произвести новых потомков. И, наконец, эти потомки заменяют существующих людей в популяции, и процесс повторяется. Таким образом, генетические алгоритмы в некоторой степени пытаются имитировать эволюцию человека.
Каждый из следующих шагов рассматривается в отдельной главе далее в этом руководстве.
Обобщенный псевдокод для GA объясняется в следующей программе: