Генетическое программирование и генетические алгоритмы очень похожи. Они оба используются для выработки решения проблемы путем сравнения пригодности каждого кандидата в группе потенциальных кандидатов на протяжении многих поколений.
В каждом поколении новые кандидаты находят путем случайного изменения (мутации) или замены частей (кроссовера) других кандидатов. Наименее «подходящие» кандидаты исключаются из состава населения.
Структурные различия
Основным отличием между ними является представление алгоритма / программы.
A генетический алгоритм представлен в виде списка действий и значений, часто в виде строки. например:
1+x*3-5*6
Для этой кодировки должен быть написан синтаксический анализатор, чтобы понять, как превратить это в функцию. Результирующая функция может выглядеть так:
function(x) { return 1 * x * 3 - 5 * 6; }
Синтаксическому анализатору также необходимо знать, как обращаться с недопустимыми состояниями, поскольку операции мутации и пересечения не заботятся о семантике алгоритма, например, может быть получена следующая строка: 1+/3-2*. Необходимо принять решение, чтобы справиться с этими недействительными состояниями.
A генетическая программа представлена в виде древовидной структуры действий и значений, обычно это вложенная структура данных. Вот тот же пример, проиллюстрированный в виде дерева:
-
/ \
* *
/ \ / \
1 * 5 6
/ \
x 3
Для этой кодировки также должен быть написан синтаксический анализатор, но генетическое программирование (обычно) не создает недопустимых состояний, потому что операции мутации и кроссовера работают в структуре дерева.
Практические отличия
Генетические алгоритмы
- По своей природе имеет фиксированную длину, что означает, что результирующая функция имеет ограниченную сложность
- Часто выдает недопустимые состояния, поэтому с ними нужно обращаться неразрушающе
- Часто полагайтесь на приоритет оператора (например, в нашем примере умножение происходит перед вычитанием), что можно рассматривать как ограничение
Генетические программы
- По своей природе имеют переменную длину, что означает, что они более гибкие, но часто усложняются
- Редко выдает недопустимые состояния, обычно их можно отбросить
- Использовать явную структуру, чтобы полностью исключить приоритет операторов