Моделирование взаимодействия между обучением и эволюцией НИИ системных исследований РАН Редько Владимир Георгиевич vgredko@gmail.com. - презентация

1 Моделирование взаимодействия между обучением и эволюцией НИИ системных исследований РАН Редько Владимир Георгиевич

2 1. Предпосылки моделирования взаимодействия между обучением и эволюцией 2. Модели предшественников (Hinton, Nowlan, 1987; Mayley, 1997) 3. Каноническая модель эволюции: модель квази видов, оценки скорости и эффективности эволюции 4. Модель взаимодействия между обучением и эволюцией 5. Исследованные механизмы взаимодействия: 5.1. Механизм генетической ассимиляции 5.2. Эффект экранирования 5.3. Влияние нагрузки на обучение 6. Сопоставление с моделью Hinton & Nowlan 7. Выводы План доклада

3 После появления Дарвиновской теории эволюции возник вопрос: могут ли за счет случайного мутационного поиска возникать весьма нетривиальные полезные навыки живых организмов? Появились концепции: обучение может существенно способствовать эволюционному процессу (эффект Болдуина). Baldwin J.M. A new factor in evolution. American Naturalist V. 30. P Morgan C.L. On modification and variation. Science V. 4. P Osborn H.F. Ontogenetic and phylogenetic variation. Science V. 4. P Предпосылки

4 Возможная схема влияния обучения на эволюцию Имеются два этапа 1)Эволюционирующие организмы (благодаря мутациям) приобретают свойство обучаться некоторому полезному навыку. Приспособленность таких организмов увеличивается, они распространяются по популяции. Но обучение имеет свои недостатки, так как оно требует энергии и времени. 2)Поэтому возможен второй этап, который называют генетической ассимиляцией: приобретаемый полезный навык может быть «повторно изобретен» генетической эволюцией, в результате чего он записывается непосредственно в генотип и становится наследуемым. Второй этап длится множество поколений. Таким образом, полезный навык, который первоначально был приобретаемым, может стать наследуемым, хотя эволюция имеет Дарвиновский характер. Предпосылки

5 Был ряд моделей, анализирующих взаимодействие между обучением эволюцией. Hinton G.E., Nowlan S.J. How learning can guide evolution // Complex Systems V. 1. P Mayley G. Guiding or hiding: Explorations into the effects of learning on the rate of evolution // Proceedings of the Fourth European Conference on Artificial Life P Однако, эти модели использовали довольно сложный генетический алгоритм со скрещиванием генотипов, поэтому были продемонстрированы эффекты взаимодействия, но плохо раскрыты механизмы эффектов. Мы будем использовать четкую схему эволюции, основанную на отборе и мутациях – модель квази видов (М. Эйген) Предшественники

6 Hinton G.E., Nowlan S.J. How learning can guide evolution Особи имеют генотип и фенотип. Имеется единственный оптимальный генотип G max (вертикальная полоска). Генотип в течение жизни особи не меняется. В процессе обучения фенотип приближается к оптимуму. Приспособленность особи определяется конечным фенотипом. Чем ближе конечный фенотип к оптимуму, тем больше приспособленность.

7 Схема генетической ассимиляции Mayley G. Guiding or hiding При сильном обучении хороший фенотип находится независимо от генотипа, отбора генотипов не происходит Схема экранирования

8 Каноническая модель эволюции: модель квази видов (М. Эйген) Рассматривается Дарвиновская эволюция популяции особей (цепочек символов, аналогов ДНК) S 1, S 2,..., S n. S ki = 0, 1; k = 1,2,…, n; i = 1,2,…, N. Длина цепочек N и численность популяции n велики: N, n >> 1. N = const, n = const. Имеется оптимальная цепочка S M, имеющая максимальную приспособленность. Приспособленность произвольной особи S определяется расстоянием по Хеммингу (S, S M ) между S и S M (числом несовпадающих символов в соответствующих позициях цепочек): f(S) =exp[- (S, S M )],(1) – интенсивность отбора, > 0.

9 Алгоритм модели Шаг 0. Формирование начальной популяции {S k (0)}. Для каждого k = 1,...,n, и для каждого i = 1,...,N, выбираем случайно символ S ki, полагая его равным 0 либо 1. Шаг 1. Отбор Подшаг 1.1. Расчет приспособленностей. Для каждого k = 1,..., n, вычисляем величину f(S k ). Подшаг 1.2. Формирование новой популяции {S k (G+1)}. Отбираем n особей в новую популяцию {S k (G+1)} с вероятностями, пропорциональными f(S k ). Шаг 2. Мутации особей в новой популяции. Для каждого k = 1,...,n, для каждого i = 1,...,N, случайно заменяем символ S ki (G+1) на 0 либо 1 с вероятностью P m. P m – интенсивность мутаций, G – номер поколения.

10 Отбор пропорционально-вероятностный (рулеточный метод) Доля k-го сектора рулетки q k = f k [ l f l ] -1, f k = f(S k ). Ровно n раз крутим рулетку, номер сектора определяет номер особи, выбираемой в популяцию следующего поколения. Для каждого вращения вероятность k-й особи попасть в следующее поколение пропорциональна ее приспособленности f k. Показан пример, для которого n = 4, f 1 = 1/2, f 2 = 1, f 3 = 1/4, f 4 = 1/4.

11 Параметры модели N – длина цепочки, длина модельного генотипа n – численность популяции – интенсивность отбора P m – интенсивность мутаций Предположения модели: N, n >> 1, 2 N >> n Будем считать, что >~ P m N

12 Достоинство модели квази видов Можно использовать одну существенную переменную – расстояние до оптимума ρ

13 Качественная схема эволюции N = 500, n = N, = 1, P m = 0.002

14 Роль нейтрального отбора Если численность популяции n сравнительно невелика, то особи могут фиксироваться в популяции случайно, независимо от их приспособленностей Роль нейтрального отбора исследовалась в работах М. Кимуры, было показано, что характерное время (число поколений) нейтрального отбора G n порядка численности популяции n Кимура М. Молекулярная эволюция: теория нейтральности. М.: Мир, 1985

15 Чисто нейтральная игра 1. Имеется популяция черных и белых шаров, общее количество шаров в популяции равно n. 2. Эволюция состоит из последовательности поколений. Каждое поколение состоит из двух шагов На первом шаге дублируем все шары, сохраняя их цвета: черный шар имеет два черных потомка, белый шар имеет два белых потомка На втором шаге мы случайным образом (независимо от цвета) удаляем из популяции ровно половину шаров. Игра определяет Марковский процесс, для которого показано, что: 1)рассматриваемый процесс всегда сходится к одному из поглощающих состояний: все шары белые либо все шары черные. 2)при больших n характерное число поколений G n, требуемое для сходимости к какому-либо из поглощающих состояний, равно 2n

16 Чисто нейтральная игра

17 Популяция находится в l -состоянии, если число черных и белых шаров равны l и n - l. Вероятности переходов P lm есть: Матрица P lm задает Марковский процесс, для которого известно, что при больших n характерное число поколений сходимости G n к какому-либо из поглощающих состояний равно 2n :G n = 2n

18 Оценка скорости эволюции 1)Отбор достаточно интенсивный: >~ NP m. Скорость эволюции определяется мутациями. 2)Мутации «оптимальны»: примерно одна мутация на генотип за поколение: P m ~ N -1. Тогда число поколений всей эволюции при поиске оптимума S M составляет G T ~ N. 3)Численность популяции минимальная, для которой еще можно пренебречь нейтральным отбором: n ~ G n ~ G T ~ N. Число поколений эволюции: G T ~ N n ~ N 2 Общее число особей, участвующих в эволюции: n G T ~ N 2

19 Качественная схема эволюции (повтор) N = 500, n = N, = 1, P m = 0.002

20 Итог оценок G T ~ N Число поколений: G T ~ N n ~ N Численность популяции: n ~ N n общ = n G T ~ N 2 Общее число особей, участвующих эволюционном поиске: n общ = n G T ~ N 2 Оценки были сделаны при разумном выборе параметров: 1) >~ NP m – интенсивность отбора достаточно велика 2) P m ~ N -1 – мутации «оптимальны» (одна мутация на генотип за поколение) 3) n ~ N – условие пренебрежения нейтральным отбором выполняется «на пределе»

21 Связь с биологической эволюцией С биологической точки зрения модель квази видов может рассматриваться только как очень грубое приближение. Тем не менее, сопоставим цифры. Для бактерии E-coli число нуклеотидов равно 4·10 6, т.е. порядка N =10 7 бит, для человека число нуклеотидов равно 3·10 9, т.е. порядка N =10 10 бит. Жизнь бактерии ~ 1 час. «Оптимальную» бактерию в популяции 10 7 особей можно найти за 1000 лет. Жизнь млекопитающего ~ 1 год. «Оптимального» млекопитающего в популяции особей можно найти за лет. Полученные оценки дают аргументы в пользу возможности происхождения организмов путем Дарвиновской эволюции.

22 Модель взаимодействия между обучением и эволюцией

23 Эволюционирующая популяция состоит из n особей. Особь имеет генотип S Gk и фенотип S Pk, которые закодированы одинаковыми по форме цепочками символов, k – номер особи, k = 1,2,..,n. Длина цепочек генотипа и фенотипа N одинакова. Символы цепочек S Gk и S Pk равны 0 либо 1. Длина цепочек и численность популяции велики: N, n >> 1, 2 N >> n. Имеется оптимальная цепочка S M той же формы. S M ищется в процессе обучения и эволюции. Пример генотипа – модельная ДНК, фенотипа – веса синапсов нейронной сети. Основная модель

24 При рождении (в начале поколения) потомки наследуют (с мутациями) генотипы S Gk своих родителей. В начале поколения фенотипы S Pk равны генотипам S Gk. В течение поколения генотипы S Gk не меняются. В течение поколения фенотипы S Pk модифицируются путем обучения методом проб и ошибок: случайно меняются отдельные символы (на 0 либо 1), и если происходит приближение S Pk к оптимуму S M, то измененный символ сохраняется, иначе возвращается старый символ. Отбор особей в новое поколение осуществляется в соответствии с приспособленностями особей, которые определяются фенотипами особей S Pk в конце поколения. Основная модель

25 Приспособленность особи определяется расстоянием по Хеммингу ρ = ρ(S FPk,S M ) между оптимумом S M и фенотипом S Pk в конце поколения: f(S k ) = exp[-ρ(S FPk,S M )] + ε, (*) где S FPk = S Pk (t = T), 0 < ε

26 1.Сопоставление: эволюция с обучением и чистая эволюция. 2. Анализ механизма генетической ассимиляции: как приобретаемые путем индивидуального обучения навыки могут стать наследуемыми в течение ряда поколений Дарвиновской эволюции? 3. Анализ механизма эффекта экранирования: при сильном обучении оптимальный фенотип может быть найден независимо от генотипа. 4. Анализ роли эффекта нагрузки на обучение: обучение может иметь и недостатки – оно требует времени и ресурсов. Учет эффекта нагрузки на обучение – приспособленность: f(S k ) = exp{-ρ[S Pk (t = 1), S Pk (t = T)]} {exp[-ρ(S FPk,S M )] + ε} (**) Что исследовалось

27 Длина генотипа и фенотипа N = 100 Численность популяции n = N = 100 Интенсивность мутаций P m = N -1 = 0.01 Параметр стохастичности среды ε = Усреднение по 1000 – расчетам. Ошибка

28 Параметры расчетов: N = 100, n = 100, P m = 0.01, ε = Почему чистая эволюция «не работает»: f(S k ) ε. Эволюция с обучением и эволюция без обучения Зависимость среднего по популяции расстояния генотипа до оптимума = от номера поколения G эволюция без обучения эволюция с обучением G

29 f(S k ) = exp[-ρ(S FPk,S M )] + ε, (*) S FPk = S Pk (t = T), ε = Без обучения S FPk = S Gk, ρ ~ 50, exp(-ρ) ~ f(S k ) ε Приспособленность

30 Механизм генетической ассимиляции Распределение особей n(ρ) по величинам ρ в первом поколении эволюции n(ρ) ρ Генотипы S Gk 1. В начале поколения 4. После отбора Фенотипы S Pk 3. После отбора 2. Перед отбором Генотипы отобранных особей (4) достаточно близки к фенотипам этих особей (3)

31 Механизм эффекта экранирования При сильном обучении оптимум фенотипа находится независимо от генотипа n(ρ) ρ Генотипы S Gk 1. В начале поколения 4. После отбора Фенотипы S Pk 3. После отбора 2. Перед отбором Распределение особей n(ρ) по величинам ρ в конце эволюции (при G = 2000)

32 При ослаблении обучения роль эффекта экранирования уменьшается, P l = 0.5 Зависимость среднего по популяции расстояния генотипа до оптимума = от номера поколения G G

33 Роль эффекта нагрузки на обучение Оптимальный генотип находится. Экранирования нет. Эволюция в 10 раз быстрее, чем без учета эффекта нагрузки Зависимость среднего по популяции расстояния генотипа до оптимума = от номера поколения G. Приспособленность особи равна: f(S k ) = exp{-ρ[S Pk (t = 1), S Pk (t = T)]} {exp[-ρ(S FPk,S M )] + ε} G

34 Механизм эффекта нагрузки на обучение Распределение особей n(ρ) по величинам ρ в первом поколении эволюции n(ρ) ρ Генотипы S Gk 1. В начале поколения 4. После отбора Фенотипы S Pk 3. После отбора 2. Перед отбором Распределения (3) и (4) резко сближаются. Это приводит к эффективному ускорению поиска

35 Механизм генетической ассимиляции (повтор) Распределение особей n(ρ) по величинам ρ в первом поколении эволюции – без нагрузки на обучение n(ρ) ρ Генотипы S Gk 1. В начале поколения 4. После отбора Фенотипы S Pk 3. После отбора 2. Перед отбором

36 Сопоставление с моделью Hinton & Nowlan (1987)

37 Дополнительная модель Строится так же, как и основная, меняется только приспособленность особей 1. При наличии обучения (ε = 0): Без учета нагрузки на обучение: f(S k ) = exp[-ρ(S FPk,S M )] С учетом нагрузки: f(S k ) = exp{-ρ[S Pk (t = 1), S Pk (t = T)]} exp[-ρ(S FPk,S M )] 2. Если нет обучения, то f(S k ) = Расчеты велись для случая наличия обучения

38 В дополнительной модели наблюдаются: 1)Генетическая ассимиляция 2)Эффект экранирования 3)Влияние нагрузки на обучение Совпадение в двух моделях почти полное Совпадение существенных результатов показывает, что роль параметра ε в основной модели взаимодействия между обучением и эволюцией невелика. Этот параметр существенен только для явного сопоставления режимов обучения с эволюцией и чистой эволюции

39 Параметры расчетов: N = 100, n = 100, P m = 0.01, ε = Почему чистая эволюция «не работает»: f(S k ) ε. Эволюция с обучением и эволюция без обучения (повтор) Зависимость среднего по популяции расстояния генотипа до оптимума = от номера поколения G эволюция без обучения эволюция с обучением G

40 Итоги Таким образом а) генетическая ассимиляция, б) эффект экранирования и в) значительное ускорение генетической ассимиляции и эволюционного процесса под влиянием нагрузки на обучение в наших моделях наблюдаются при следующих условиях: 1) Каждая особь эволюционирующей популяции имеет генотип и фенотип 2) Генотип и фенотип представляют собой цепочки символов одинаковой формы 3) Генотипы предаются от родителей к потомкам с небольшими мутациями. Генотип особи не меняется в течение ее жизни

41 Итоги Условия моделей (продолжение): 4) Начальный фенотип особи равен ее генотипу 5) Имеется определенная оптимальная цепочка символов, которая ищется в процессе обучения и эволюции 6) Фенотип существенно модифицируется путем обучения в течение жизни особи. В процессе обучения фенотип приближается к оптимальной цепочке 7) Отбор особей в новое поколение определяется конечными фенотипами особей

42 Выводы 1.Показано, что обучение может радикально ускорять эволюционный поиск 2.Показано, что генетическая ассимиляция может происходить так: при обучении фенотипы особей приближаются к оптимуму, происходит отбор, генотипы отобранных особей тоже движутся к оптимуму 3. Роль эффекта экранирования состоит в том, что при сильном обучении оптимальный фенотип может быть найден независимо от генотипа 4.Показано, что эффект нагрузки на обучение может значительно ускорить генетическую ассимиляцию и эволюционный процесс

43 Основные результаты доклада представлены в статье Редько В.Г. Модель взаимодействия между обучением и эволюционной оптимизацией // Математическая биология и биоинформатика (электронный журнал), Т С pdf pdf Журнал:

44 Спасибо за внимание!