Модель генетической эволюции, предложенная sss

[Комбинатор]

Всем доброго времени суток.
Как и обещал, выкладываю нашу переписку с sss относительно предложенной им модели.

Первое письмо.
===============================================
Относительно "генетической" модели. В перерывах между дипломниками вчера набросал на работе примерные наметки (извините, на VBA - ничего другого под рукой не оказалось!). В основу положил реальный геном, правда, до "безобразия" упрощенный (пока - просто для отладки "логики"). Для начала - крайне упрощенная, но вполне "биологически правдоподная" модель. Затем можно усложнять.

'основные положения модели
'1) существует ограниченное число генов, которые расположены в геноме линейно, каждый ген расположен в своем локусе и не влияет на активность других генов (транспозонов и регуляторных генов нет)
'2) каждый ген представлен в геноме (пока, для упрощения модели) в единственном экземпляре (т.е. гены не амплифицируются)
'3) максимальная длина генома ограничена
'4) есть три типа генов - влияющие на скорость роста, частоту рекомбинаций, частоту мутаций
'5) скорость роста зависит от как от активности отдельных генов, так и от длины генома (увеличение длины в среднем снижает скорость роста из-за увеличения времени копирования ДНК, по крайней мере для прокариотов и вирусов это утверждение справедливо)
'6) перед каждым размножением происходит генетическая рекомбинация по принципу "каждый с каждым", при этом возможно увеличение длины генома - A000 х 0B00, например, дадут A000, 0B00 и AB00 где A и B - гены, 0 - "пустые" локусы
вероятность рекомбинации определяется активностью специального "рекомбинирующего" гена (это примерно соответствует действительности)
'7) перед каждым размножением происходят мутации, приводящие к изменению активности генов (появлению новых аллелей), частота мутаций существенно ниже частоты рекомбинации и определяется активностью специального "мутагенного" гена
' цикл "мутации-рекомбинации-размножение" продолжается до тех пор, пока между разными генотипами не установится равновесие (частоты встречаемости перестанут значимо меняться) (надеюсь, равновесие установится!)
'9) после достижения равновестия условия отбора слегка меняются,
(меняются коэффициенты в формуле, по которй рассчитывается скорость роста), при этом каждое изменение условий осуществляется по очень простому и заранее заданному закону
' (например, роль гена в локусе №3 все время слегка возрастает, а роль гена №4 - падает)
' посте этого цикл повторяется до достижения нового равновестия

'СНИЖЕНИЕ ВРЕМЕНИ ДОСТИЖЕНИЯ РАВНОВЕСИЯ при каждом новом изменении условий отбора будет означать, что СИСТЕМА НАУЧИЛАСЬ
'Отрицательный результат будет означать, что ДАННАЯ МОДЕЛЬ НЕ СПОСОБНА К ОБУЧЕНИЮ. В таком случае можно будет попробовать усложнить модель

'*******************************
'примерный текст программы (писал на VBA, т.к. ничего другого под рукой не было)

'ограничиваем число возможных генов в геноме (чтобы модель не росла "до бесконечности")
Const MAXLOCUSES = 10 'макисмальное допустимое количество генов в геноме

'ограничиваем "теоретически возможную" активность генов
'чтобы избежать появления "супергенов", имеющих "бесконечно высокую" активность
Const MinValue = 0 'минимально возможная активность гена в модели
Const MaxValue = 10 'максимально возможная активность гена в модели

'три возможных типа генов
Const gNormal = 0 'ген влияет на скорость размножения
Const gRecomb = 1 'ген влияет на скорость рекомбинации
Const gMutant = 2 'ген влияет на скорость мутирования

Type Gene 'описание гена
locus As Byte 'номер локуса, в котором расположен ген
activity As Byte 'активность гена
type As Byte 'тип гена
name As String 'название аллели (временно не используется)
End Type

Public Type GenoType 'генотип
Genome(1 To MAXLOCUSES) As Gene 'совокупность всех генов в геноме
CurrentNumber As Double 'текущее количество данных генотипов в биосфере
End Type

Public GenoTypes() As GenoType 'динамический массив, содержащий все существующие генотипы
Public Recombinants() As GenoType 'динамический массив, содержащий все рекомбинации

'главный модуль
Sub work()
Dim CalcStep As Integer 'счетчик

start 'установить стартовые параметры модели

NextIteration:

CalcStep = 0

Do While ChangesExist 'пока не установилось равновесие между генотипами
Mutation 'мутируем
Recombination 'рекомбинируем
Multiplication 'размножаемся
CalcStep = CalcStep + 1 'подсчитываем число циклов до достижения равновесия
Wend
OutputResults
'выводим генетическую структуру популяции
'и число шагов, потребовавшихся для достижения равновесия

ChangeCriteria
'меняем критерии, по которым определяется "ценность" генов для размножения

'и начинаем все сначала
GoTo NextIteration

End Sub

Хотел сразу написать все процедуры и опробовать, но не успел.
Понятно, что модель крайне примитивная и вряд-ли способна к "обучению", однако она довольно точно соответствует реальному (хотя и очень примитивному) геному, и после написания ее легко можно усложнять, вводить новые типы генов, правила скрещивания и т.д.

[Комбинатор]

Второе его письмо.
======================================
В дополнение к модели:
после отладки программы ее можно начать усложнять, приближая к реальным биологическим объектам (пока она по сложности соответствует примитивному вирусу)
Первое усложнение - введение регуляторных генов, оперонов и влияния местоположения гена на его активность.
У реальных организмов гены, "ответственные" за последовательные стадии какого-либо процесса, обычно сгруппированы в опероны.
Каждый оперон начинается регуляторным геном, который регулирует активность сразу всех генов, входящих в оперон. Мутация в регуляторном гене согласованно меняет активность всех генов, входящих в оперон. Перемещение гена в геноме (выход из оперона, включение в другой оперон) меняет его активность.

Проще всего это сделать, если объявить массив Genome двумерным:
Public Type GenoType 'генотип
Genome(1 to MAXOPERONES, 1 To MAXLOCUSES) As Gene 'совокупность всех генов
CurrentNumber As Double 'текущее количество данных генотипов в биосфере
End Type

и сделать первый ген каждого оперона регуляторным. Возможность "скакать" между оперонами, предположительно, повысит "адаптируемость" системы: например, гены, для которых при каждом "изменении условий отбора" необходимо увеличивать активность могут "собраться" в одном опероне. Тогда единичная мутация будет повышать активность сразу всех необходимых генов.

[Комбинатор]

Третье его письмо.
===============================================
Сегодня, наконец, добрался до домашнего компьютера, начинаю отвечать на письма в порядке поступления.
Первым прочитал это, отвечаю.

'2) каждый ген представлен в геноме (пока, для упрощения модели) в единственном экземпляре (т.е. гены не амплифицируются)
'3) максимальная длина генома ограничена
'4) есть три типа генов - влияющие на скорость роста, частоту рекомбинаций, частоту мутаций
имеется в виду скорость роста чего? Количества молекул ДНК в моделируемой популяции?

Да, конечно. Просто я по микробиологической привычке ростом назвал размножение (профессиональный сленг).

'5) скорость роста зависит от как от активности отдельных генов, так и от длины генома (увеличение длины в среднем снижает скорость роста из-за увеличения времени копирования ДНК, по крайней мере для прокариотов и вирусов это утверждение справедливо)

Таким образом, с каждым геном ассоциируется так же некоторый параметер - "активность гена", так?
Да. Активность для простоты (пока?) принимает только целые значения в диапазоне 0-255 (точнее, от MinValue до MaxValue).
Type Gene 'описание гена
locus As Byte 'номер локуса, в котором расположен ген
activity As Byte 'активность гена
type As Byte 'тип гена
name As String 'название аллели (временно не используется)
End Type
С биологической точки зрения, активность гена - это количество молекул белка, синтезируемых на его основе за единицу времени. В дальнейшем предполагается разделить гены на группы (опероны), каждый оперон снабдить своим геном-регулятором активности (который тоже может мутировать), и дать генам возможность случайным образом скакать из оперона в оперон. Тогда геном будет гораздо более похож на реальный. А модель сможет в ходе эволюции группировать гены по оперонам, что должно резко повысить ее "обучаемость".

'6) перед каждым размножением происходит генетическая рекомбинация по принципу "каждый с каждым"
Здесь я чего-то запутался. Если рекомбинация происходит перед размножением, то что есть само размножение?
Положим, мы моделируем N экземпляров ДНК, представленных в виде векторов типа
- ABC0EF
- 0BCDEF
- 000D00
и т.д.

Скрещивание - по принципу каждый с каждым. Т.е. в Вашем примере ABC0EF "попарно" скрестится с ABC0EF, с 0BCDEF, с 000D00, 0BCDEF скрестится с 0BCDEF, 000D00 и т.д. Все "родители" выпустили в окружающую среду гаметы (сперматозоиды и яйцеклетки), в количествах, пропорциональном своей "родительской" численности, гаметы перемешались, попарно скрестились и образовали новые генотипы. Эти новые генотипы начнут размножаться в следующем цикле.
("большая шведская семья"  ). Эту процедурку я уже написал.

Означает ли размножение попросту увеличение в определённое число раз числа определённых экземпляров ДНК (чем они "успешнее", тем больше коэффициент мультипликации).
Да. Правило, по которому вычисляется коэффициент мультипликации (т.е. вклад отдельных генов в этот коэффициент), будет плавно меняться по очень простому закону.

А не получится ли так, что установится "тривиальное равновесие", когдв выживет лишь один генотип?

Для этого я ввожу ограничение на длину генома (конечно, организму выгодно собрать в одном геноме все "хорошие" гены, но, с другой стороны, увеличение длины генома при прочих равных условиях снижает коэффициент репликации). Возможно, окажется выгоднее иметь маленький геном с большим количеством "пустых" локусов. Т.е., "на вскидку", единственного решения ("идеального генома") быть не должно.

Вообще, это сильно напоминает классические генетические алгоритмы в ИИ.
Как показывает практика, они способны адаптироваться (выходить в состояние устойчивого равновесия), но к настоящему обучению в нашем понимании (подстройка не только под статическую, но и под динамическую среду, правила игры в которой меняются по достаточно простым законам), похоже, не способны. По видимому, для этого нужно учитывать взаимное влияния генов друг на друга, что бы они могли постепенно выстраиваться в генные сети определённой функциональности и иерархические пирамиды управления.

Про генетические алгоритмы не знаю (не встречался, только слышал краем уха).
А насчет взаимного влияния - см. выше организацию генов в динамически меняющиеся опероны.

Но, как я уже говорил, если уж писать, то, имхо, лучше сразу на С. На одном VB далеко не уедешь.

Согласен. Просто я плохо (очень плохо?) пишу на С.  Поэтому хочу отладить логику на хорошо знакомом VB (здесь мне не надо думать о языке, а только - о модели и алгоритмах), а потом перевести уже отлаженные алгоритмы на С. Мне так проще. А если сразу писать на С, буду думать не столько о логике, сколько о "кодировании".

[Комбинатор]

Четвёртое письмо.
==============================
Цитата:
А может добавить ещё возможность генвм-регуляторам взаимно влиять на активность друг-друга?
Должны ли скачки генов из оперона в оперон быть полностью случайными, или их вероятность и направление может регулироваться генами-регуляторами и зависеть от других факторов (длины генома, скорости роста и т.д.)?  


Надо спросить на форуме у молекулярных биологов/генетиков - как там на самом деле. Кажется, Сергей и Питер - молекулярщики. Хочется вставлять в модель то, что точно есть на самом деле (а читать спец. литературу лень  )

Цитата:
При таком подходе, как мне кажется, количество особей (точнее, типов генофонда?) уже всего через несколько поколений вырастет у Вас на столько, что исчерпаются все ресурсы компьютера как по доступной памяти, так и по быстродействию. Мне кажется, скрещивание должно носить вероятностный характер, а вероятность "скрещивания" зависеть от степени успешности каждой, из особей (генофонда) данной пары.


Возможно. Хотя при скрещивании пары особей при полностью "заполненном" геноме у каждой (без пустых локусов) число комбинаций будет равно
2^(число локусов) - не так уж и много при "не слишком большом" числе генов.
Генотипы, которые окажутся идентичными уже существующим, будут просто приписываться к их текущей численности

ABC х abc, например, в моей процедуре скрещивания дает

ABC
ABc
AbC
Abc
aBC
aBc
abC
abc

Из них 2 - идентичны родительским (ABC и abc - продукт самооплодотворения), т.е. дополнительной памяти не потребуют

Правда, здесь у каждого гена всего по две аллели (A и a, B и b, C и c), а в популяции будут плавать и другие аллели (а1, b1, c1...an, bn, cn), появившиеся в результате мутаций исходных A, B и С.
Возможно, действительно надо будет перед скрещиванием оценивать успешность особи (ее % долю в популяции), а также в процессе скрещивания не запоминать "заведомо проигрышные" комбинации. Или ограничить число аллелей (допустимых "уровней активности") гена,тем более, что дополнительная регуляция активности будет осуществляться небольши числом генов-регуляторов.
В общем, надо подумать.

ЯЦитата:
думаю, идеальная стратегия во многом будет зависеть от сложности внешней среды, включая скорость её динамического изменения.


Про это я вообще еще толком не думал (в смысле, не написал). Надо придумать формулу, по которой будет определяться скорость размножения генотипа. Формула должна включать все гены в формате
(активность гена-регулятора)*(активность индивидуального гена)*(коэффициент полезности гена)

активность гена-регулятора сказывается сразу на всех генах, входящих в его оперон
индивидуальная активность гена меняется в результате мутаций и имеет ограниченное "число степеней свободы" (например - целые значения в диапазоне 0..5). Если ее помножить на активность регулятора - уже 25 уровней
"коэффициенты полезности" индивидуальных генов предполагаю менять (по какому-нибудь очень простому закону, все время - в одном направлении, каждое новое изменение - после установления относительного равновестия между генотипами, т.е. раз в несколько поколений)

Еще формула должна включать длину генома (число "непустых") локусов - чем длиннее геном, тем ниже при прочих равных условиях коэффициент размножения.
"Короткие" генотипы быстрее копируются, из-за этого (в том числе) прокариоты размножаются гораздо быстрее, чем эукариоты. А я хочу, чтобы организмам приходилось выбирать между длинным и коротким геномом (а то сделают максимально возможный геном, напихают туда самых лучших аллелей, и успокоятся).

В общем, формула подлежит обсуждению. Надеюсь на Ваше и других форумчан соучастие (Вы, вроде, обещали выложить модель с комментариями на форуме).

С уважением, Сергей
P.S. "Примитивная" модель (без оперонов и генов регуляторов и убогой формулой отбора) готова, т.е. все процедуры работают, но в кучу не сверстал (не успел).

[Basileus]

sss. Модель в таком виде более всего напоминает очередное открытие ГАмерики собственными силами. Мне кажется, логичнее провести для начала рекогносцировочный анализ состояния области ГА-моделирования. Я тут не слишком владею ситуацией пока, но может быть Комбинатор подскажет пару толковых ссылок, откуда можно начать?

[Комбинатор]

sss. Модель в таком виде более всего напоминает очередное открытие ГАмерики собственными силами. Мне кажется, логичнее провести для начала рекогносцировочный анализ состояния области ГА-моделирования. Я тут не слишком владею ситуацией пока, но может быть Комбинатор подскажет пару толковых ссылок, откуда можно начать?

Я так понимаю, что sss xочет создать модель, максимально близкую к имитации эволюции генофонда колонии бактерий. А в генетических алгоритмах, примерняемых в ИИ, во первых, такая задача не стоит, а во вторых, там за основу берутся принципы конкретно эволюции популяции на основе полового размножения (с учётом возможных мутаций).

Вот пара ссылок:
http://algolist.manual.ru/ai/ga/
http://www.neuroproject.ru/gene.php

[sss]

Ответ всем, кто участвовал в обсуждении.
Во-первых, никакой америки я открывать не хотел - Комбинатор предположил "генетический интеллект", я решил проверить.
Во-вторых, как и ожидалось, модель обучается.
В-третьих, это было ясно с самого начала (обучаемость)
В-четвертых - из этой модели я уже склепал виртуальную лабораторную работу
в пятых - (забыл, что хотел сказать)

[Gilgamesh]

Ночной кошмар Уильяма Пейли.
Имитация эволюции... часов
http://cyd2012.livejournal.com/114977.html

[Alexy]

Ночной кошмар Уильяма Пейли.
Имитация эволюции... часов
http://cyd2012.livejournal.com/114977.html

ССылка видимо сдохла:

"Ошибка
Нет такой записи"

[DNAoidea]

фуф... читал модель несколько раз, пока не понял более-менее. И всё равно есть вопросы - как определяется частота мутаций? Ведь именно они являются причиной, определяющий максимально возможный размер значимой части генома Эукариот. У прокариот и вирусов, видимо, рулит скорость.
на основании чего происходит отбор? есть потолок численности особей? но я не видел об этом, может плохо искал
в силу чего, то есть каков механизм обучаемости - условия-то могут меняться как угодно, откуда системе с предыдущего раза знать, что следует копить на следующий?

[Alexy]

фуф... читал модель несколько раз, пока не понял более-менее

А могли бы Вы это изложить в виде кратких ьезисов, если это возможно?