Расчеты эволюции на C# - Расчеты эволюции
ОГЛАВЛЕНИЕ
Расчеты эволюции
История генетических расчетов начинается в 1960-е годы, когда первый труд по данной теме был опубликован Джоном Холлэндом, представившим первые идеи о генетических алгоритмах (GA) на основе теории эволюции. С тех пор было сделано много исследований в области расчетов эволюции, обусловивших появление множества разных методов. Большинство из этих методов было тщательно изучено и применено к решению множества разных задач, дав очень хорошую эффективность для большинства из них. Несмотря на весьма долгую историю генетических расчетов, эти методы все еще активно изучаются, и появляются разные новые подходы, увеличивающие число задач, решаемых с помощью этих методов.
GA основан на дарвиновском принципе размножения и выживания сильнейшего и на аналогах естественных генетических операций, таких как кроссовер (рекомбинация) и мутация. Этот метод работает с популяцией индивидуумов (хромосом), каждый из которых кодирует возможное решение задачи, к которой применяется генетический алгоритм. В GA хромосомы представлены строками фиксированной длины (массивы битов, чисел, и т.д.), что упрощает реализацию генетических операторов. Сначала популяция инициализируется случайными хромосомами, но затем начинает эволюционировать путем применения таких генетических операторов, как кроссовер, мутация и селекция.
Простейший вид кроссовера – одноточечный кроссовер: выбирается случайная точка из двух хромосом, и эти две хромосомы обмениваются своими частями:
Другой популярный вид операции кроссовера – двуточечный кроссовер: выбираются две случайные точки, и хромосомы обмениваются своими частями между этими двумя точками. Эти два вида кроссовера наиболее популярны в GA, но они не единственные имеющиеся. В действительности есть много разных вариантов этого оператора, варьирующихся от задачи к задаче. Есть задачи, где эти два классических варианта кроссовера вообще не применимы, поэтому у них есть собственный специальный вариант, специфичный для задачи.
Оператор мутации работает только с одной хромосомой, меняя хромосому произвольно. Одноточечная мутация меняет всего один ген в хромосоме:
Как в случае кроссовера, оператор мутации тоже имеет много разных вариантов, более характерных для конкретных типов задач.
После создания начальной популяции каждая итерация алгоритма GA состоит из следующих шагов:
1. Кроссовер – выбираются случайные индивидуумы, и к ним применяется операция кроссовера;
2. Мутация – выбираются случайные индивидуумы, и к ним применяется оператор мутации;
3. Вычисляется значение пригодности каждого индивидуума;
4. Селекция – выбираются индивидуумы для новой генерации.
Алгоритм можно остановить после заданного числа итераций или когда было найдено довольно хорошее решение. Расчет значения пригодности хромосомы зависит от задачи – значение показывает, насколько хороша хромосома. Чем больше значение, тем лучше хромосома, что повышает ее шансы быть выбранной в следующую генерацию.
Существует несколько операторов селекции. Их главная идея – выбрать индивидуумов для следующей генерации, повышая шансы лучших индивидуумов – с более высокими значениями пригодности. Один из самых популярных методов называется элитизм – определенное количество лучших хромосом выбирается для следующих генераций.
В 1992 году Джон Коза предложил существенно новый подход – генетическое программирование (GP). В GP отдельные члены популяции (хромосомы) не являются линейными символьными строками фиксированной длины, кодирующими возможное решение задачи, как в GA, но они являются программами, дающими решение задачи при выполнении. Эти программы выражаются в виде деревьев разбора GP различных размеров и форм, что делает эти методы гибкими в применении к широкому диапазону задач. Различие в представлении хромосом – главное и почти единственное различие между этим методом и GA. Общий дарвиновский принцип выживания сохраняется, но меняются операторы мутации и кроссовера и расчет функции пригодности. Вместо мутации отдельного гена в строковой хромосоме в GP оператор мутации может переродиться как отдельный узел дерева, как целая ветвь дерева хромосомы. То же самое происходит с кроссовером – вместо обмена частями хромосом одинаковой длины, в GP хромосомы обмениваются своими ветвями, различающимися по размеру и по форме. Однако всегда необходимо проверять хромосомы и урезать их, если они выросли слишком длинными.
Чтобы вычислить значение пригодности отдельной хромосомы в GP, хромосома не просто передается в качестве значения некоторой функции, вычисляющей значение пригодности. Вместо этого выполняется программа, представленная хромосомой, и вычисляется значение пригодности в зависимости от вывода программы.
В 2001 году Кандидо Феррейра ввел еще один метод под названием программирование выражений генов (GEP). Идея метода походит на генетическое программирование и генетические алгоритмы. Метод тоже работает с программами, дающими решение после выполнения, что уподобляет его GP. Но представление этих программ в GEP отличается. В данном методе хромосомы не представляются как деревья, а являются линейными объектами фиксированной длины, как в GA. Такое изменение в представлении хромосомы упрощает реализацию таких генетических операторов, как мутация и кроссовер, но имеет ряд небольших ограничений, чтобы сделать этот оператор безопасным.
* + / a b c a
(a) (b)
Представление хромосомы в GP (a) и GEP (b)
Рисунок выше показывает различие в представлении хромосомы в методах GP и GEP. Обе хромосомы кодируют одну и ту же программу – алгебраическое выражение (a + b) * (c / a). GP представляет хромосому как дерево разбора выражения, но GEP представляет ее как линейную строку, где узлы вышеуказанного дерева разбора записаны в порядке: слева направо, сверху вниз. Строку GEP можно легко преобразовать обратно в дерево разбора, заполнив его слева направо и сверху вниз, учитывая информацию о количестве параметров каждой функции.