Физика процессов эволюции - Эбилинг В.
Скачать (прямая ссылка):
3. Благоприятные условия для эволюции соответствуют уровню, лежащему чуть ниже этого порога.
В той же работе Эйген исследовал интересную модель с гиперциклическими связями между воспроизводящимися последовательностями. Определенный недостаток компьютерных моделей, исследованных Ферстерлингом, Куном и Тьюзом, а также Эйгеном, состоит в том, что должна быть задана «цель эволюции» — идеальная последовательность. Разумеется, для реальных процессов эволюции идеальная последовательность, если она вообще существует, не задана. Существование априорно заданной цели эволюции сделало бы излишним сложный и сопряженный с большими затратами процесс поиска, поскольку был бы известен кратчайший путь к достижению цели. Именно поэтому представляют интерес модели эволюции, которые не исходят из предположения о существовании заданной идеальной последовательности. Такие модели были развиты в более давних работах (Ebeling, Feistel, 1974, 1977; Ebeling, Mahnke, 1979). Изложим наиболее существенные особенности этих моделей.
Рассмотрим последовательности из букв А,. В, С и D длиной до 20 букв, т. е.
1 < v < 20, S = 4 + 42 + 43 + ... + 420 и Ю12.
Приведем несколько примеров таких последовательностей
A, DA, DAC, DABC, BDADB.
Общее число возможных последовательностей S необычайно велико. Компьютерная игра проводится на симплексе N - 100. Стохастические переходы на симплексе происходят по правилам, вытекающим из общего соотношения (8.55). Технически каждая последовательность хранится в сжатом виде в «регистре» длиной в 2ft символов. Например, две последние последовательности хранятся в форме
Каждой из 100 участвующих в игре последовательностей следует поставить в соответствие такой «регистр». Опишем теперь процесс мутации, состоящий либо в перестановке отдельных букв, либо в обрыве какой-то из начинающейся слева последовательности символов. Алгоритм мутации в компьютерной игре состоит из следующих правил.
1. Вписать в одну из ячеек любого из 100 регистров одну из четырех букв А, В, С, D или нуль.
2. Переставить циклически все ячейки, т. е. расположить их в таком порядке, чтобы ячейка 1 шла за ячейкой 2, ячейка 2 — за ячейкой 3,..., ячейка 20 — за ячейкой 1.
3. Вычеркнуть все нули и все части последовательности, стоящие справа от нуля. Возникающая после этих операций последовательность представляет собой результат мутации.
Нетрудно видеть, что в этой игре перестановка буквы в 20-ю ячейку эквивалентна приписыванию этой буквы к левому концу последовательности. Возможны также и перестановки буквы в нулевую позицию справа от последовательности или приписывание буквы к правому концу последовательности. Таким образом, алгоритм мутации допускает удлинение и сокращение цепей с обеих сторон. Для оценки каждой последовательности произвольно устанавливается код из перекрывающихся дублетов. Исходные позиции А, В, С, D оцениваются величиной w = 1,2, 3,4, а каждая последующая позиция оценивается в зависимости от ее ближайшего соседа по следующей таблице:
АА w : = w, CA w : = w/3,
АВ w : = V), CB w : = w + q/2,
АС w : - W + 1, CC w : = w,
AD V) : = w/q, CD w : : = w/3,
ВА w : = w + q/2, DA w : = w + 4/q,
ВВ w: = w, DB w : : = w/4,
ВС w: = w/2, DC w: \ = w + q/4,
BD w ; : = w + 2, DD w : = w.
Если р — позиция первой буквы дублета, то q = p — д[(р — 1 )/д], где квадратные скобки обозначают целую часть числа. Приведем несколько примеров:
w(DAC) = 4 + 4 + 1 = 9,
w(DACBA) = 4 + 4+1 + 1 + 2= 12,
w(BDADBBA) = (2 + 2 + 4/2) • (1/3) • (1/4) • 1 + 6/2 = 3,5.
На рис. 8.10, 8.11 и 8.12 представлены три различных примера компьютерных реализаций эволюционного процесса при различных частотах мутации. Отчетливо видно, как в игру эволюции вступают новые, более приспособленные сорта, доминируют в течение какого-то периода и затем уступают место еще лучшим сортам. При таком процессе длина цепи постоянно растет, и образуются характерные структуры. На рис. 8.13 показано несколько путей эволюции, по которым могло бы пойти развитие системы. Возникает характерное дерево эволюции со все более сильно ветвящейся кроной. На рис. 8.13 представлена лишь часть возможных маршрутов, соответствующих наиболее часто проходимым ветвям. В действительности к последовательностям ведут 262 144 ветвей. Усиливающееся ветвление является характерной особенностью рассматриваемой модели, в то время как модели Ферс-терлинга, Куна и Тьюза (Forsterling, Kuhn, Tews, 1972), а также Эйгена (Eigen, 1976), основанные на задании идеальной последовательности (цели эволюции), должны
Рис. 8.10. Компьютерная реализация стохастического процесса отбора (тип I) с частотой мутаций 0,01 на репликацию и признак (1 — CBDD; 2 — CBDDC; 3 — CBBDC; 4 — CBDDCB)
Q <
« Л Л "I
о о о
< ¦< <
о О а
« « со
Рис. 8.11. Компьютерная реализация детерминистического процесса отбора со стохастическим появлением мутаций с частотой 0,03 на репликацию и признак (тип I)
