Содержание к диссертации
Введение
Глава 1. Эволюционная адаптация механизмов наследственной изменчивости 7
1-1. Контроль генотипом механизмов наследственной изменчивости 7
1-2. Подходы к объяснению эволюции механизмов изменчивости 12
1-2-1. Принцип минимизации генетического груза.. 13
1-2-2. Эволюция механизмов изменчивости посредством косвенного действия отбора ... 14
1-3. Кибернетические приложения эволюционной адаптации параметров изменчивости 16
Глава 2. Моделирование эволюции механизмов изменчивости.. 18
2-1. Требования к модели 19
2-2. Описание модели 22
2-3. Качественное поведение 26
2-3-1. Стационарный случай 26
2-3-2. Регулирование темпов изменчивости в меняющейся среде 30
2-4. Эффективность эволюционной адаптации 38
Глава 3. Стохастическая функция Ляпунова в исследовании сходимости случайных процессов 40
3-1. Основные понятия 4I
3-2. Метод стохастической функции Ляпунова 46
3-3. Характеристика разброса 49
3-4. Множество сходимости. Достаточные условия
3-5. Скорость сходимости супермартингала 63
Глава 4, Исследование сходимости эволюционного процесса 66
4-1. Мартингалы и марковские процессы 66
4-2. Построение случайных процессов ( , Исследование сходимости процесса
4-3. Оценка скорости сходимости 76
4-4. Переходные вероятности. Вычисление суб- и супермартингальных характеристик.. 80
Заключение 84
Приложения
Литература
- Подходы к объяснению эволюции механизмов изменчивости
- Эволюция механизмов изменчивости посредством косвенного действия отбора
- Регулирование темпов изменчивости в меняющейся среде
- Переходные вероятности. Вычисление суб- и супермартингальных характеристик..
Подходы к объяснению эволюции механизмов изменчивости
В этом пункте на примере математических моделей обсуждаются возможные подходы к объяснению направленной ЭЕОЛЮЦИИ генов, контролирующих наследственную изменчивость. В первой модели (принцип минимизации генетического груза) для объяснения направленной эволюции механизмов изменчивости используются идеи межгруппового отбора, во второй (модель эволюции генов-модификаторов) показано, что направленные изменения параметров изменчивости, не имеющих фенотипического проявления, могут происходить посредством косвенного действия отбора.
Как показано в предыдущем пункте, механизмы наследственной изменчивости контролируются генами. Естественно ожидать, что в процессе эволюции происходит изменение этих геноЕ, поскольку они участвуют в эволюционном процессе и подвержены наследственным ненаправленным изменениям - мутациям. Трудность объяснения направленной эволюции подобных генов (в дальнейшем будем говорить для определенности о генах-мутаторах) заключается в том, что они не имеют фенотипического проявления и не влияют на приспособленность особи. Тем самым, естественный отбор непосредственно на них не действует.
Существует несколько подходов к объяснению эволюции генов-мутаторов. Общие рассуждения показывают, что частота спонтанного мутирования (или средняя стабильность генетических структур) должна для каждого вида установиться на некотором "оптимальном в эволюционном смысле" уровне.
Действительно, слишком низкая частота мутирования приведет к замедлению скорости эволюции организмов, которые не будут успевать адаптироваться к изменяющимся внешним условиям, С другой стороны,1 высокая изменчивость генетического материала приведет к тому, что эволюция вообще не будет протекать в форме направленного процесса, а сведется к хаотическим флуктуациям, а это, в свою очередь, резко замедляет скорость эволюции. Кроме того, высокая частота спонтанного мутирования снижает среднюю приспособленность популяции, поскольку, большинство мутантов имеет более низкую приспособленность [зо] .
Одним из объяснений направленной эволюции механизмов наследственной изменчивости является межгрупповой отбор. Под его действием скорость мутационных изменений постоянно поддерживается на оптимальном для изменяющейся среды уровне. Этот процесс можно представить себе следующим образом. Имеется несколько изолированных групп или популяций особей одного вида. Каждая группа характеризуется некоторой своей частотой спонтанного мутирования. Через некоторое число поколений та группа, которая имела более "оптимальную" частоту мутирования, достигнет большего эволюционного прогресса и вытеснит другие группы менее приспособленных особей. Заметим, что возможность межгруппового отбора ограничивается многочисленными условиями (изолированность групп, постоянная дифференциация частоты мутирования по группам, возможность вытеснения одной группы другими ш т.д. [62,63]} . Формализация вышеизложенных рассуждений была дана Кимурой [51,52,53 1 , и известна под названием принципа минимизации генетического груза. Генетический груз определялся суммой двух слагаемых где U - соответствовал мутационному грузу, a L+ е. - субсти-туционному (установочному) грузу. Генетический груз [58] характеризует смертность в популяции, вызванную мутациями в генах. Субституционный груз характеризует долю генетических элиминаций, связанных с заменой старого аллеля новым в результате адаптации к изменившимся условиям (Холденовская плата за отбор [461) . Принцип минимизации генетического груза. Изменение скорости мутации N. происходит таким образом, чтобы минимизировать генетический груз популяции В качестве простых следствий получим, что в постоянной среде, при условии, что популяция к ней адаптировалась, частота мутаций будет уменьшаться, поскольку Ле = Q , и условие /д— тл.ги равносильно требованию L . — vrun. . Если среда изменяется с течением времени, то Ue Ф 0 » и частота мутаций установится на некотором оптимальном уровне (поскольку, уменьшение JA. приводит к возрастанию Ue , а увеличение № - к возрастанию т. ).
Эволюция механизмов изменчивости посредством косвенного действия отбора
Другой подход не предполагает действия каких-либо форм межгруппового отбора и объясняет эволюцию механизмов наследственной изменчивости на основе естественного отбора. Как уже отмечалось, механизмы изменчивости не влияют на приспособленность организма непосредственно, и, следовательно, прямого отбора по ним не происходит. Косвенная связь с отбором механизмов наследственной изменчивости заключается в том, что они контролируют изменения признаков, участвующих в отборе. Так, "удачно" изменившийся мутатор имеет некоторое селективное преимущество с точки зрения выживания потомства, поскольку, определит лучшие мутации гена, отвечающего за непосредственно отбираемый признак. Поэтому можно надеяться на направленную эволюцию механизмов изменчивости в сторону "ускорения приспособляемости". Описанный механизм эволюции будем называть косвенным действием отбора. Возможность косвенного действия отбора была исследована на модели модификаторов Карлиным и Мак-Грегором [49,501 . Эта модель представляет классическую двулокусную двуаллельную модель математической генетики. Модель модификаторов имеет следующую структуру: имеются первичные локусы, определяющие фишеровскую приспособленность [43 и подверженные действию различных факторов (таких, как мутация, рекомбинация и т.п.). Вторичные локусы - модификаторы -определяют значения параметров, характеризующих степень действия факторов, например, частоту мутаций или рекомбинаций. Модификаторы рассматриваются как нейтральные.
Рассмотрим конкретную модель модификаторов скорости мутаций. Первичный локус имеет два аллеля А и При этом с некоторой частотой происходят мутации A - CL и CL - А . Мута-торный локус контролирует частоту мутаций и определяет три различных значения частоты мутаций Ц. , Qt и O UL . Обозначим р (0ч устойчивое положение равновесия частот А и О- при фиксированном параметре & , а ї"(0.) -"VlW vij ] среднюю приспособленность популяции в положении равновесия. Тогда изменение частоты аллеля nv будет происходить таким образом, чтобы увеличивалась приспособленность ; в частности, при flGUw) СІК&ІА (їС& міь) фиксируется аллель nv ; а при З О ц) ((W %&ък) Фиксируется аллель М. . Исследование различных конкретных моделей модификаторов позволило сформулировать общий вывод: эволюция генов-модификаторов происходит таким образом, чтобы увеличивалась средняя приспособленность популяции. Таким образом, частота нейтральных (в смысле фишеровской приспособленности) генов-модификаторов может направленно изменяться под действием отбора. Это явление было названо вторичным или индуцированным отбором. Исследование закономерностей эволюции механизмов изменчивости можно найти и в работах других авторов 40,41,42,48,54, 60]. В этом пункте обсуждается возможность применения эволюционной адаптации параметров изменчивости при решении задач оптимизации. В задачах оптимизации возможно применение "эволюционных" принципов, основанных на случайных изменениях оптимизируемого объекта с последующим отбором. Эти принципы используются, например, в алгоритмах случайного поиска, в методах эволюционного моделирования и др. [2,18,311 . Простейшие эволюционные схемы, предусматривающие изменения только тех параметров, по которым непосредственно производится отбор (т.е. тех, от которых зависит значения критерия оптимизации), являются недостаточно эффективными. Поэтому в большинстве случаев изменениям подвергаются и сами механизмы формирования этих параметров. Изменение механизмов ("второй уровень" оптимизации [2 "J ) происходит, как правило, детерминированным образом, в зависимости от предистории развития оптимизируемого объекта и эвристических соображений, связанных со спецификой конкретной оптимизационной задачи. При построении алгоритмов оптимизации сложных объектов нахождение механизмов адаптации параметров второго уровня затруднено.
Поэтому естественно рассмотреть более общий подход, заменив детерминированные изменения механизмов формирования параметров изменчивости случайными, не использующими никакой априорной информации о необходимой "направленности" этих изменений. Нужная направленность возникнет вследствие косвенного действия отбора. Предлагаемая в п.11-2 "эволюционная схема" позволяет положительно ответить на Еопрос о принципиальной и практической осуществимости такого подхода. В п.11-4 изучена эффективность процесса эволюционной адаптации параметров изменчивости, рассматриваемого как поиск максимума функции приспособленности. В приложении I приведен пример использования схемы из п.11-2 для конструирования алгоритма поиска экстремума функций "овражного" типа.
Регулирование темпов изменчивости в меняющейся среде
Рассмотрим в качестве функции отбора функцию, непосредственно зависящую от времени ($,4) » достигающей максимума в момент т. в точке XoCw (будем предполагать, что при фиксированном t функция О Д ) унимодальна). Рассмотрим простейший случай временной зависимости т.е. в момент времени Ч1 , соизмеримый со временем эволюции популяции, описанной в п. Ш-3-І, происходит резкое изменение условий так, что положение максимума функции отбора Х0 резко изменяется. Результаты моделирования на ЭВМ для модели конечной популяции и ее модификации приведены на рис. 4 и 5 соответственно. Течение эволюционного процесса до момента Т будет про- текать, как описано в п. П-3-І. После момента Т "стабилизирующий" отбор сменится "направленным", и величина мутатора xH t) снова начнет возрастать. Рассмотрим функцию; непрерывно изменяющуюся во времени (х, \.) . В этом случае значение мутатора устанавливается на некотором "оптимальном" для зависимости ЇС Л ) уровне» Исследовались два случая временной зависимости, В первом случае максимум функции приспособленности ХоС ) изменялся детерминированным образом с некоторой постоянной скоростью . Функция приспособленности имела вид -f (хД4) «. Во втором случае моделировались "случайные блуздания" максимума х0(Д) . Функция приспособленности имела вид f (хД) а tfx- &lLlvvj, , где V) і независимые реализации случайной величины i , равномерно распределенной в отрезке Результаты моделирования на ЭВМ для модели конечной популяции приведены на рис. 6 и 8, и для ее модификации - на рис, 7 и 9.
В каждом случае величина мутатора X (V) устанавливалась на уровне порядка значения , т.е. на уровне скорости изменения максимума функции приспособленности (дальнейшего уменьшения мутатора не происходило). При этом отклонение параметра X(Vj от оптимального значения Xo(M оставалось в процессе эволюции на уровне порядка Х (т) , т.е. \ъ(\) - X0tV}\ (V) Таким образом, адаптация мутатора посредством косвенного действия отбора представляет естественный механизм регулирования темпов мутационной изменчивости в изменяющейся среде. Сравнение эффективности эволюционного процесса, рассматриваемого как поиск максимума функции приспособленности -р , с эффективностью оптимальных алгоритмов оптимизации показало, что они имеют одинаковую по порядку (экспоненциальную) скорость сходимости. Оценить относительную величину затрат на адаптацию мутато-ра можно, если рассмотреть эволюцию системы как поиск максимума функции -f и сравнить его эффективность с эффективностью известных методов оптимизации. Будем рассматривать эволюционный процесс X (t4) = (хiX), & (Л) ) определяемый модификацией модели из п. П 2 и Ж (JC - класс унимодальных функций). Одним из возможных подходов к оценке эффективности является исследование оптимальности методов оптимизации с информационной точки зрения ][з]
Такой подход оправдан в тех случаях, когда вычисление значений функции связано с большими затратами, и более оптимальным считается метод, который обеспечивает нахождение максимума функции XJJ на классе «К на основе меньшего количества вычислений функции -f (меньшей информации об -f ) или имеет максимальную скорость сходимости к Хо в пересчете на одно вычисление функции Максимальную скорость сходимости на классе унимодальных функций на отрезке имеет оптимальный последовательный алгоритм или алгоритм Фибоначчи (подробнее см. приложение 2). Гарантированная точность вычисления максимума произвольной унимодальной функции f на отрезке [ ОД J при П/ вычислениях функции { равна і/ ., . где Л = lW» _ ! —— J /5 ь VL-число Фибоначчи. Таким образом, оптимальный последовательный алгоритм имеет экспоненциальную скорость сходимости, Т.е. \ &rt - Xj \ : Х C- VL4) ДЛЯ ВСЄХ , больших некоторого Гъ 0 , где Xw очередное приближение к , а 0 константа. Показатель сходимости для метода Фибоначчи = 0,48. Исследование сходимости процесса X(.t} - Г ХС , X (Vn показало, что эволюционный процесс имеет экспоненциальную скорость сходимости, т.е. асимптотически почти всюду выполняется неравенство ч при этом показатель сходимости J в пересчете на одно вычисление функции \ , X = П. меньше наилучшего значения, даваемого методом Фибоначчи, всего приблизительно в 5 раз. Если же сравнивать эволюционный процесс с алгоритмами случайного поиска, то показатели $ различаются в 2-2,5 раза Г 18j .
Переходные вероятности. Вычисление суб- и супермартингальных характеристик..
В этом пункте вычисляются суб- и супермартингальные характеристики процессов (Yfc) и vV ) с использованием численных методов (метода Монте-Карло). Это оправдано с методологической точки зрения, поскольку, даже в случае протейшего эволюционного процесса проводить аналитические вычисления затруднительно. Выпишем функцию распределения С"? ) Рх,я , X (A") Й- j для фиксированного состояния (ъ,х У Обозначим - и " функции распределения св. и . Обозначим функцию распределения св. &у Обозначим функцию распределения св. Ж-т. при фиксированном Обозначим отобранную точку . Тогда функцию совместного распределения ЗД и (!) можно вычислить т.е. считается, что отобрана Хп -ая точка (что эквивалентно условию \Ъчь\ \Ф«,\ э 1,..., ..14. ), и ее характеристики фт х га) не превосходят С& У Имея явный вид для переходной вероятности Гх.31 для процесса ( (V), fcH Y) можно аналитически вычислять различные характеристики процесса. Однако, сложный вид функции Рх: делает теоретическое исследование затруднительным даже в случае простейшего эволюционного процесса. Для исследования более сложных процессов возможным выходом представляется использование численных методов. Наиболее естественно применение метода Монте- Карло, поскольку, для исследуемого процесса, как правило, конструктивно задается переходная вероятность, которую можно моделировать на ЭВМ, используя псевдослучайные числа. Общую схему метода Монте-Карло можно представить в следующем виде [Vf28 . Необходимо вычислить интеграл по некоторой мере Р . Моделируя меру Р на ЭВМ, можно получить N выборочных значений &!, ХІТ и оценку интеграла По закону больших чисел Ідо сходится к I [l2"\ .
Поскольку функция т имеет конечную дисперсию D-f EQ -E-f-), то по центральной предельной теореме Гі2"] для достаточно больших Среднеквадратичная погрешность одг = — оценки і к убывает как і /J д[ .В последующих вычислениях доверительный интервал выбирался равным 3d# , что обеспечивает правильность вычисления 1 с вероятностью 0,997, т.е, Оценка дисперсии _до производилась одновременно с вычислением оценки математического ожидания Ідо по формуле Для вычисления суб- и супермартингальных характеристик процессов (Ч{ ) и (УО необ дда0 вычислять интегралы, завися- щие от параметра Используя схему метода Монте-Карло, можно вычислить значе ния интеграла I ( Л") в конечном числе точек к. Поскольку для каждого Я І использовалась независимая выбор ка Х а... &м f то можно оценить вероятность правильности вы числений интеграла во всех точках {\1ц ОЛ -1СЦ лО У "U 099? Таблицы с вычислениями суб- и супермартингальных характеристик для процессов (Л/J ) и \у ) приведены в приложении 5. В работе, в рамках стохастической модели, изучены основные закономерности процесса эволюции механизмов изменчивости. Для исследования сходимости и скорости сходимости эволюционных процессов предложен новый подход, основанный на использовании стохастической функции Ляпунова. К основным новым результатам, полученным в работе, относятся следующие [22-26]
Построена стохастическая модель, описывающая эволюционные изменения механизмов изменчивости. 2. Показана возможность направленной эволюции параметров изменчивости посредством косвенного действия отбора. Подробно изучена эволюция параметров изменчивости в стационарной и изменяющейся среде. Исследован вопрос об эффективности процесса адаптации мутатора как процедуры оптимизации. Показано, что эволюционный процесс имеет тот же порядок сходимости, что и оптимальный последовательный алгоритм. 3. Для исследования сходимости эволюционных процессов (и процессов вероятностной оптимизации вообще) предложен подход, основанный на использовании стохастической функции Ляпунова (у\). От известных методов его отличает то, что, ломимо функции Ляпунова, рассматривается и другая числовая характеристика исследуемого процесса (\(\ У В терминах пары случайных процессов (Y ) предложены достаточные условия сходимости траекторий процесса \Ч\) к значениям из фиксированного множества Г , что позволяет описать множество сходимости исследуемого процесса.
