О статье с матмоделью дарвиновской эволюции

Наша братья, народ умный, как мы называем себя, поступает почти так же, и доказательством служат наши ученые рассуждения. Сперва ученый подъезжает в них необыкновенным подлецом, начинает робко, умеренно, начинает самым смиренным запросом: не оттуда ли? не из того ли угла получила имя такая-то страна? или: не принадлежит ли этот документ к другому, позднейшему времени? или: не нужно ли под этим народом разуметь вот какой народ? Цитует немедленно тех и других древних писателей и чуть только видит какой- нибудь намек или, просто, показалось ему намеком, уж он получает рысь и бодрится, разговаривает с древними писателями запросто, задает им запросы и сам даже отвечает на них, позабывая вовсе о том, что начал робким предположением; ему уже кажется, что он это видит, что это ясно -- и рассуждение заключено словами: так это вот как было, так вот какой народ нужно разуметь, так вот с какой точки нужно смотреть на предмет! Потом во всеуслышанье с кафедры, -- и новооткрытая истина пошла гулять по свету, набирая себе последователей и поклонников.
Николай Васильевич Гоголь. Мертвые души

Professor Jeffrey Shallit, Waterloo

Это моя уже довольно старая статья. Выложу тем не менее.

Немного предыстории. Во время оно я оставил комментарий в блоге профессора математики и ярого критика ID Джеффри Шаллита (Jeffrey Shallit).  Он мне указал (на мой взгляд, достаточно резко) на эту статью: "сначала прочти вот это, потом приходи и мы поговорим". Возвращаю должок, ибо лучше поздно, чем никогда.

John R. Koza: Spontaneous Emergence of Self-Replicating and Evolutionarily Self-Improving Computer Programs, Proceedings of the Third Workshop on Artificial Life (ALIFE-3).

Professor John R. Koza, Stanford

   

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

Автор анализирует возможность спонтанного появления компьютерного кода, способного размножаться от одного или двух предков, а также самокорректироваться эволюционным путем при условии существования достаточного числа примитивных вычислительных элементов (primitive computational elements). Предполагается, что примитивные элементы взаимодействуют между собой и совместно обладают свойством вычислительной полноты по Тьюрингу, достаточным, в том числе, и для образования агломераций элементов. На вопрос о возможности как спонтанного возникновения самовоспроизводящихся программ, так и их последующего эволюционного усложнения статья дает положительный ответ. 

Математическое моделирование позволяет создавать некий виртуальный мир со своими законами. Поэтому выводы по результатам моделирования должны всегда восприниматься, как говорят англичане, with a pinch of salt. На мой взгляд, нужно отдавать себе отчет в том, что даже для того, чтобы промоделировать что-то, что способно, по уверению исследователей, спонтанно возникать, необходимо наличие интеллектуальной среды: программиста, сложных вычислительных систем и аккуратного управления экспериментом. В связи с этим иронично воспринимается уже само название направлений исследований: искусственная жизнь (которая призвана продемонстрировать, что биологическая жизнь в определенном смысле — простое следствие десятка-другого тех или иных автоматически действующих правил)... Сделав эти предварительные замечания, двинемся далее. 

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

Модель начинает работу из стартовой конфигурации (так называемое «море» программных элементов) при заданном наборе функций, реализуемых элементами. Набор функций удовлетворяет условию полноты по Тьюрингу (по-просту, из них как из конструктора можно составлять программы, с помощью которых можно вычислять теоретически любую функцию). В этом случае стартовый набор программных элементов носит название тьюринговского газа. В каждый момент времени выполняется одна программа, которая осуществляет поиск соседних программ, причем соседи меняются со временем. Целью является поиск самовоспроизводящихся программ, способных улучшаться от поколения к поколению. Поиск осуществляется по критерию совпадения с шаблонами частей выполняющейся в данный момент программы. Поиск просматривает соседние программы, находящиеся в «море» в данный момент (при условии заданности оператора соседства). Поиск завершается, когда все программы из множества выполнились (число программ может расти со временем). 

Подробности:

1. В исследовании предполагается наличие первобытного вычислительного «супа», состоящего из фиксированного числа примитивных вычислительных элементов, моделирующих базовые функции органических молекул. Все это хорошо, однако хотя появление примитивных вычислительных элементов и принимается как данность, нельзя «правила», действующие в физическом мире, лишь на основе грубой аналогии отождествлять с правилами поведения вычислителя. Автор статьи полагает, что физико-химические взаимодействия аналогичны поведению вычислительной системы. Но на каком основании мы можем предположить, что, скажем, свойства атома углерода аналогичны свойствам вычислительных систем? Это самое слабое место всякого исследования подобного рода, поскольку это предположение неверно. По замечанию современного американского философа науки Алекса Розенберга, ни один сгусток материи сам по себе не обозначает какой-либо другой сгусток материи (no clump of matter is about any other clump of matter). Напротив, трансляция информации, предполагающая, что одни конфигурации материи обозначают другие, – свойство лишь живых и сложных искусственных систем особого рода. Таким образом, главный вопрос состоит в том, каким образом появилась первая популяция трансляторов информации (физически реализованных вычислительных комплексов «данные-протокол-процессор»). Разумеется, компьютерный код, генерируемый некоторой процедурой вычислительного элемента или агломерации, должен удовлетворять правилам транслятора (иначе просто никакого смысла нет в том, чтобы генерировать программы).
2. Специфическая сложность: не всякая сложная строка символов функционально специфична. Фактически то, что демонстрируется в статье, является игрой по неким базовым правилам с явно заданной целью. Причем новой эволюционно приобретенной функциональностью считается всякая функция, реализуемая элементом, присоединенным из «моря» по критерию поиска, удовлетворившемуся в данный момент времени. К примеру, если до присоединения нового элемента программа имела одну функцию типа А, а после присоединения – две функции типа А, то вторая считается новой, хотя никакой реальной новизны с точки зрения того, что выполняет программа-агломерат, она не привносит.
3. Ограничение по вложенности циклов также налагаются: если программа выполняется дольше какого-то разрешенного времени, она прекращает выполнение (вспомним Хайтина, который также вынужден был в своих экспериментах выполнять роль оракула останова). Таким образом, эффективность поиска неявно завышается. Синтаксические правила проверяются явным программным образом. Это также искусственно завышает эффективность поиска.
4. На практике при создании эффективных вычислительных комплексов исследователь-разработчик сообщает вычислительной системе статистически значимые количества так называемой активной информации, эвристически организующей процесс поиска решений [Ewert et al. 2012]. Естественный отбор в реальных условиях наиболее эффективен при крайне малом числе признаков, по которым он ведётся. Чем больше число признаков, тем менее эффективен и менее чувствителен естественный отбор. Проблема чувствительности отбора модели в статье совсем не рассматривается. Системы, полагающиеся лишь на возможности случайного поиска, на практике неэффективны. Весь вопрос в том, каково количество активной информации, сообщаемой алгоритму, и каким образом она сообщается вычислительной системе интеллектуальным агентом в каждом конкретном случае. Активная информация выступает мерой того, насколько естественный отбор, имеющий место в реальных условиях жизнедеятельности популяций, неявно заменяется на искусственный отбор программиста-селекционера. Вычислительными методами, называющимися генетическими алгоритмами, это иллюстрируется наиболее ярко:
   1. функция цели, как правило, задается явно (в природе этого нет);
   2. программист имеет возможность со сколь угодно большой точностью измерять значения градиента функции цели и активно управлять процессом поиска решений в зависимости от измеренного градиента (в природе этого нет);
   3. возможность управления поиском осуществляется программистом также путем компоновки желаемых операторов мутаций и вывода нежелательных членов популяции из процесса размножения с тем, чтобы они не оказывали отрицательное влияние на будущее поколение (в природе этого нет).
   Одним словом, выразить это более емко, чем сам автор статьи, вряд ли возможно: the controller exists outside of the individuals. Таким образом, представленная модель – это модель искусственной селекции, так как имеет место управление экспериментом. В статье целый параграф 6 посвящен описанию того, какие правила реализуют вычислительные элементы и их агломерации. Здесь и осуществляется неявное наделение алгоритма поиска активной информацией о том, что необходимо искать. В частности, оговаривается, в каких случаях при нахождении элемента из «моря» следует его выполнить и анализировать результаты, а в каких следует лишь проверить символьно, имеет ли данный элемент искомую структуру. Аналогичные правила действуют относительно начала поиска выполняющеся программой соседних программ. В результате поиска при совпадении искомого шаблона и просматриваемой программы может осуществиться замещение выполняемой программы новой программой, большей, чем выполнявшаяся до этого. Как и следует ожидать, размер программ-агломератов растет экспоненциально. Поэтому вычислительные ресурсы неизбежно ограничивались. С этой целью вводилась фильтрация результирующих программ по размеру и другим свойствам.
5. Как я уже сказал выше, я согласен с автором, что вследствие ограниченности ресурсов окружения само существование популяции различающихся по своим свойствам открытых самовоспроизводящихся систем автоматически ведет к возникновению эволюционного процесса в этой популяции. Тем не менее, эволюционные движения на практике ограничены целым рядом ключевых биологических факторов. Пределы эволюционирования определяются биологически совместимыми изменениями ключевых параметров жизнеобеспечения. В результате этого участки фазового пространства, отвечающие состояниям рассматриваемой живой системы, в которых могут быть заключены эволюционные траектории, ограничены. Имеет место не фазовый континент функциональности, а архипелаг. Причем переходы с одного острова на другой запрещены биологически. Итак, вместо связного фазового пространства в реальности мы имеем дело с рядом ограниченных «карманов», в которых происходит эволюция популяций живых организмов. Границы «карманов» со временем, вероятно, могут изменяться и перекрываться. Однако это не решает вопроса органиченности эволюционных движений живых систем в принципе.
6. Исследование опирается на необходимость целого ряда последовательных вычислительных прогонов с целью получения начального пула программ, способных реплицироваться. Таким образом, вопрос о том, откуда взялась начальная популяция репликаторов остается «за кадром». Требование независимых прогонов нереалистично. Природа не будет ждать, прогонять, сохранять и очищать промежуточные результаты, потому что у неё нет возможности целеполагания. Поэтому не совсем верен вывод автора, что при возможности спонтанного образования нескольких репликаторов, нахождение «остальных» (до некоторого числа, с которого может начаться массовый процесс эволюционного роста сложности) – дело времени.
7. Что касается демонстрации способности обучаться, то это, как и всё предыдущее, – результат осмысленных действий программиста, целенаправленно сообщающего нужные свойства программному коду. Соответствующие явные правила допуска программы-потомка к размножению описаны в статье. Целевые функции обучения задаются явно. Чем точнее программа-организм эмулирует заданную целевую функцию, тем больше шансов у нее выжить и произвести больше потомства.
8. Автор постоянно оговаривает: «если бы наши вычислительные ресурсы не были ограничены, то не нужно было бы так тонко управлять экспериментом». Однако в реальности природные ресурсы действительно ограничены, но столь тонкого управления со стороны естественного отбора ожидать не приходится. Естественный отбор осуществляет лишь пассивное управление (по бинарному критерию "выжил-невыжил"), тогда как искусственный отбор, возможности которого продемонстрированы в статье, — активное (с использованием градиента функции цели, управления операторами соседства и размножения).

Вот такие пироги. Так что, Jeffrey, Design is written all over it...

Литература

1. Winston Ewert, William Dembski, Robert J. Marks II (2012): Climbing the Steiner Tree—Sources of Active Information in a Genetic Algorithm for Solving the Euclidean Steiner Tree Problem, Bio-complexity.org. 
2. Cм. также мою заметку о семантическом замыкании здесь.
3. Перевод моей статьи, которую вы только что прочитали, на английский язык (то есть фактически мой ответ проф. Дж. Шаллиту) см. здесь.