Скорость эволюции, возможно, определяется математической простотой

Креационисты любят говорить о том, что для создания всего лишь одного человеческого белка среднего размера эволюции нужно собрать в правильном порядке примерно 300 аминокислот. Поскольку на каждую из позиций в создаваемой белковой молекуле претендуют 20 аминокислот, получается выбор из более чем 20³⁰⁰ вариантов, а это такое количество, по сравнению с которым число атомов в наблюдаемой вселенной выглядит несущественным. Эволюции, утверждают креационисты, не хватило бы и миллиардов лет, чтобы посредством случайных мутаций наткнуться на правильную комбинацию, даже если учесть практическую эквивалентность некоторых из 20³⁰⁰ вариантов.

Если область возможных решений проблемы велика, многие из этих решений, скорее всего, окажутся тупиковыми.
Но эволюция, по-видимому, нашла способы делать успешный выбор более вероятным.

Это рассуждение глубоко ошибочно, ибо эволюцию нельзя сводить к простому перебору возможных вариантов: в процессе естественного отбора их число становится всё меньше и меньше. Более того, природа, похоже, каким-то образом нашла и другие способы действовать быстрее, сужать огромное количество возможностей до таких подмножеств, которые позволяют с большей вероятностью получать полезные решения.

Аналогичные трудности встают перед учёными-компьютерщиками, когда они решают проблемы, связанные с поиском оптимальных решений в астрономических массивах возможностей. Некоторые из этих специалистов, чтобы обрести вдохновение, обращают взор на биологию — даже несмотря на то, что и биологам не очень понятно, как в процессе эволюции происходит выбор оптимальных решений.

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

«Идея о том, что жизнь — эволюционирующее программное обеспечение, плодотворна», —  Грегори Хайтин (Gregory Chaitin), математик

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

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

Обезьяны, бьющие по клавишам

Речь идёт о теории, разработанной в 60-х годах ХХ века. Она имеет дело с так называемой алгоритмической информацией и в качестве отправной точки использует интуитивное понимание вероятности и сложности: идею о том, что на компьютере, по крайней мере, в некоторых случаях, проще дать цифровое описание, как получить что-либо, чем действительно получить. Возьмём затасканную аналогию с обезьяной, которая случайным образом нажимает клавиши на компьютерной клавиатуре. Вероятность того, что она наберёт первые 15 000 цифр числа π, практически равна нулю — и эти шансы экспоненциально убывают по мере набора заданного количества цифр.

Но если обезьяньи удары по клавишам интерпретировать по-другому, как случайно написанные компьютерные программы для генерации π, шансы на успех (их называют «алгоритмической вероятностью») значительно возрастут. Например, код для генерации первых 15 000 цифр числа π на языке программирования C может содержать всего 133 символа.

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

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

В результате алгоритмическая теория информации оказалась приписанной к сфере чистой математики, где её используют для изучения относящихся к ней теорем и определения понятий случайности и структуры. Её практическое применение казалось невозможным. «Она выглядела совершенно непригодной для решения конкретных проблем реального мира, хотя, с математической точки зрения, та мера сложности, которую она предлагает, является простой и красивой», — говорит создатель (наряду с Колмогоровым) алгоритмической теории информации известный математик Грегори Хайтин, в прошлом сотрудник Центра IBM имени Томаса Дж. Уотсона (IBM Thomas J. Watson Center) и Федерального университета Рио-де-Жанейро (порт. Universidade Federal do Rio de Janeiro, UFRJ).

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

Теперь же некоторые учёные надеются решить эту задачу и тем самым сделать алгоритмическую теорию информации актуальной для исследований как в области биологии, так и в области информатики.

Развитие в сторону простоты

Гектор Зенил (Hector Zenil), учёный-компьютерщик из Каролинского института (швед. Karolinska Institutet, англ. Karolinska Institute), Швеция, — один из тех, кто стремится извлечь из алгоритмической теории информации практическую пользу. Он наладил сотрудничество с другими исследователями, чтобы использовать колмогоровскую сложность для измерения сложности биологических сетей — таких, как те, что моделируют генную регуляцию или клеточные белковые взаимодействия. Эта группа исследователей приближённо рассчитывает содержащуюся в сети алгоритмическую информацию (поскольку действительное значение вычислить нельзя), затем вводит в сеть мутацию и тестирует её влияние на колмогоровскую сложность. Применяя данный метод, учёные надеются выяснить относительную важность различных элементов сети, а также характер её функционального реагирования на преднамеренно осуществляемые изменения.

Например, недавно на препринтном сайте arxiv.org эти исследователи сообщили о полученном ими интересном результате: они обнаружили, что увеличение колмогоровской сложности сети — путём введения мутаций, приводящих к увеличению длины определяющей сеть программы, — ведёт к увеличению числа функций данной биологической системы, а заодно делает её более чувствительной к возмущениям. При упрощении сети функций становилось меньше, зато стабильность их осуществления возрастала.

Но верна ли гипотеза Хайтина, согласно которой колмогоровская сложность может быть не только инструментом, но и движущей силой перемен? Пока это неизвестно. И всё же, несмотря на все проблемы, алгоритмическая информация пользуется у биологов определённым успехом. Математической основой, применяемой для описания эволюционной динамики, традиционно является популяционная генетика: статистические модели частоты появления генов в популяции. Однако у популяционной генетики есть границы: она, к примеру, не в состоянии объяснить ни происхождение жизни, ни важные биологические сдвиги, ни появление совершенно новых генов. «В этой прекрасной математической теории не нашлось места для понятия биологической креативности», — отмечает Хайтин. Но, добавляет он, «креативность естественно вписывается» в исследование, которое учитывает алгоритмическую информацию.

Столь же естественно вписывается и идея о том, что со временем улучшается и становится более эффективным сам процесс эволюции. «Я убеждён, что эволюция не может не учиться, — говорит Даниэль Полани (Daniel Polani), учёный-компьютерщик и профессор в области исследования искусственного интеллекта Университета Хартфордшира (University of Hertfordshire), Великобритания. — И я не удивлюсь, если окажется, что это находит своё выражение в асимптотическом уменьшении алгоритмической сложности».

Зенил и его команда решили экспериментально выяснить, какую роль играет алгоритмическая сложность в биологических и вычислительных процессах. Для этого они применили тот же метод приближённого расчёта сложности, какой был разработан для анализа сетей и создания в них возмущений. Исследователи «развивали» искусственные генетические сети в сторону заданных целей — матриц, состоящих из единиц и нулей и предназначенных для репрезентации взаимодействий между генами. При этом учёные так управляли мутациями, чтобы возникали матрицы с меньшей алгоритмической сложностью. Другими словами, экспериментаторы проводили отбор в сторону более совершенной структуры.

Недавно эти исследователи сообщили в журнале Royal Society Open Science, что управление мутациями сделало скорость эволюции сетей значительно более высокой по сравнению с той, какая была при статистически случайных мутациях. Появились и другие особенности, в том числе устойчивые правильные структуры — участки в матрицах, уже достигшие такой степени простоты, какую вряд ли смогут улучшить новые этапы эволюции. «Некоторые области были более или менее предрасположены к мутированию просто потому, что они вышли на некоторый уровень простоты, — говорит Зенил. — Тут сразу возникает ассоциация с генами». Эта генетическая память, в свою очередь, ускоренно породила более совершенную структуру, что, как полагают исследователи, свидетельствует о способности алгоритмически вероятных мутаций приводить к взрывам разнообразия и вымиранию.

«Значит, — делает вывод Зенил, — говоря об эволюции, весьма полезно учитывать вычислительные процессы». Он надеется с помощью данного понимания случайности и сложности определить пути, по которым лучше идут мутации и выяснить, почему определённые генетические взаимодействия могут иметь связь с такими заболеваниями, как рак.

Эволюция программного обеспечения

Зенил надеется установить, что биологическая эволюция работает по описанным выше вычислительным правилам, но большинство экспертов сомневается в успехе его предприятия. Неясно, какой естественный механизм может отвечать за аппроксимацию алгоритмической сложности и запуск мутаций, ведущих к простоте. Более того, по мнению Джузеппе Лонго (Giuseppe Longo), математика Национального центра научных исследований (фр. Centre National de la Recherche Scientifique, CNRS) Франции, «считать, что всё живое кодируется четырьмя буквами, неправильно. ДНК чрезвычайно важна, но от неё нет никакого толку, если [она] не находится в клетке, в организме, в экосистеме». Тут работают другие взаимодействия, и предлагаемое применение алгоритмической информации не в состоянии учесть всю эту сложность.

«Всё значимое для нас так или иначе структурировано», —  Лариса Альбантакис, теоретик-невролог.

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

И действительно, есть кое-какие интригующие намёки на потенциальную связь между гипотезами Хайтина и Зенила о роли колмогоровской сложности и методами генетического программирования. Например, в 2001 году группа исследователей сообщила, что сложность выхода генетической программы можно ограничить колмогоровской сложностью исходной программы.

Однако в целом учёные-компьютерщики, ознакомившись с идеями Хайтина и Зенила, не оценили важность использования колмогоровской сложности. Взамен они опробовали другие способы модификации генетики и мутаций. Некоторые группы исследователей воздействовали на частоту мутаций, другие так настраивали эту систему, чтобы в ней получали преимущество мутации, изменяющие большие участки кода. «Придуманы десятки, может быть, сотни различных версий мутаций и кроссоверов», — отметил Ли Спектор (Lee Spector), учёный-компьютерщик из Хэмпширского колледжа (Hampshire College) в штате Массачусетс. Спектор в недавнем прошлом возглавлял команду, показавшую, что гораздо удобней добавлять и устранять мутации на всём пространстве геномов, чем всякий раз напрямую заменять один ген другим. Этот новый тип генетического оператора в конечном итоге экспоненциально увеличил число путей через геномное пространство поиска и улучшил результаты.

Тем не менее, многие исследователи, пойдя в противоположном направлении, ищут разумные способы ускорять процесс эволюции, сужая пространство поиска, но не ограничивая его до такого уровня, на котором поиск теряет оптимальные результаты. Была идея сделать целью простоту: как раз тогда, когда Юджин Вигнер (венг. Wigner Jenő Pál, англ. Eugene Wigner) отметил «чрезвычайную эффективность математики в естествознании», — а он сделал это в 1960 году, — учёные-компьютерщики обнаружили, что более простые и изящные модели нередко проявляют себя как более универсальные и эффективные. «И возникает вопрос: позволяет ли это узнать о вселенной нечто важное? — размышляет Спектор. — И вообще: полезно ли это?»

Кроме того, предостерегает он, сами попытки направить эволюционирующие программы в сторону простоты могут оказаться деструктивными: получив в награду что-то вроде более короткой программы, можно, например, удалить как «мусор» то, что на следующих этапах эволюции способно принести пользу. В результате процесс развития не выйдет на уровень оптимальных решений. «Вот такая получается загвоздка», — говорит Спектор.

Но простота продолжает дразнить исследователей как цель, к которой нужно стремиться, и это оказалось полезным. В работе, опубликованной в прошлом году, Спектор и его коллеги сообщили об интересном открытии. С помощью разработанных ими методов генетического программирования они сумели, уменьшая размер исследуемых программ — иногда всего лишь на 25 процентов, — применять их для решения более широкого круга общих проблем, причём обработка новой информации стала более эффективной.

Данное открытие — одна из причин, по которым Ли Спектор следит за попытками практического использования теории алгоритмической информации, хотя, подчёркивает учёный, ему всё ещё не очень-то видно, как эти усилия могут повлиять на генетическое программирование.

Учиться у жизни

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

И всё же, по мнению Лариссы Албантакис (Larissa Albantakis), теоретика-невролога из Висконсинского университета в Мадисоне (University of Wisconsin—Madison), «они поступили очень разумно, введя ограничение на основе структуры». Албантакис также работала над тем, чтобы ускорить действие генетических алгоритмов путём ограничения пространства поиска. «Природа структурирована, причём весьма разнообразно, — сказала она, — и, если исходить из этого, то глупо использовать всевозможные однородные мутации».

«Всё значимое для нас так или иначе структурировано», — добавила она.

Ли Спектор, не найдя в недавней работе Зенила никакого материала, полезного за рамками очень специфической проблемы, которую исследовал каролинский компьютерщик, считает, тем не менее, что «теория информации, лежащая в основе этой концептуальной схемы, вызывает большой интерес и может оказаться чрезвычайно важной». «Я нахожу эту концепцию увлекательной отчасти потому, что кажется, будто она инопланетная, — заявил он. — По-видимому, возможно понимание вещей, которое значительно превосходит принятое в нашем сообществе». Помимо всего прочего, теория алгоритмической информации затрагивает такой широкий спектр идей, включая представление о присущей эволюции открытости (open-ended nature), что некоторые специалисты по генетическому программированию могут и не задействовать какую-то часть этого материала в своих исследованиях.

«Меня одолевает чувство, что здесь скрывается что-то очень важное», — сказал Спектор о наработках Зенила и Хайтина. Как бы то ни было, добавил он, в настоящее время «всё ещё сохраняется огромная дистанция между тем, над чем они работают, и практическим применением».

«Идея о том, что жизнь — эволюционирующее программное обеспечение, плодотворна», — считает Хайтин, хотя судить о ценности этой гипотезы, возможно, ещё преждевременно. Идёт ли речь об искусственной или биологической жизни, «нам нужно видеть, как далеко мы можем продвинуться».

Источник: Джордана Цепелевич (Jordana Cepelewicz) 22century.ru