Ученые-компьютерщики обращаются к эволюционной биологии за вдохновением для поиска оптимальных решений для множества возможностей астрономического размера.
Изучая огромные пространства возможных решений проблемы, мы сталкиваемся с тем, что большинство путей окажутся тупиковыми.
Но эволюция, возможно, нашла способы увеличить шансы на успех.
Креационисты любят настаивать на том, что эволюции пришлось бы собрать до 300 аминокислот в правильном порядке только для того, чтобы создать один человеческий белок среднего размера.
А поскольку в каждой позиции может быть одна из 20 возможных аминокислот, то, казалось бы, их больше 20. 300 вариантов поиска, что на много порядков превышает количество атомов в наблюдаемой Вселенной.
Даже если мы обнаружим избыточность, которая сделает некоторые из этих вариантов эквивалентными, вероятность того, что эволюция случайно наткнулась на правильную комбинацию посредством случайных мутаций, кажется чудовищно малой, даже учитывая прошедшие миллиарды лет. Главный недостаток таких аргументов в том, что эволюция опробовала эти последовательности не случайно: процесс естественного отбора отсеял ненужные.
Более того, вполне вероятно, что природа нашла другие обходные пути, способы сузить огромное количество вероятностей до небольших, поддающихся исследованию подмножеств, которые с большей вероятностью дадут полезные решения.
Ученые-компьютерщики сталкиваются с аналогичными проблемами, которые включают поиск оптимальных решений среди множества вариантов астрономического размера.
Некоторые из них за вдохновением обращаются к биологии – несмотря на то, что сами биологи только пытаются понять, как это делает природа.
Генетические алгоритмы, методы оптимизации, популярные на протяжении десятилетий, используют принципы естественного отбора для создания новых конструкций (среди прочего, для роботов, лекарств и транспортных систем), обучения нейронных сетей или шифрования и расшифровки данных.
Эта технология начинается с того, что случайные решения задачи рассматриваются как некие «организмы», обладающие определенными характеристиками или элементами, «генетически» заложенными в их коде.
Эти решения не особенно хороши, но затем они подвергаются различным случайным мутациям (а иногда и другим изменениям, повторяющим процесс перетасовки генов) и производят второе поколение организмов, которые, в свою очередь, проверяются на пригодность для решения задачи.
В конце концов, после многих повторений, этот процесс приводит к появлению чрезвычайно хорошо адаптированного человека или решения.
Некоторые эксперты выводят этот метод на новый уровень, занимаясь генетическим программированием для создания программ, которые могут писать программы и создавать эффективные решения (здесь «генами» могут быть строки кода).
Достичь этой цели оказалось особенно трудно, поскольку исследователи должны учитывать определенные типы и структуры данных, а также многие другие условия.
Интересно, что эти способы мышления, основанные на эволюции (особенно генетическом программировании), концептуально пересекаются с математической теорией, которая всегда находилась где-то на периферии как биологии, так и информатики.
В последнее время некоторые ученые пытаются использовать его, чтобы понять, как эволюция, естественная и искусственная, может эффективно работать, создавать что-то новое и учиться учиться.
Центральное место в этом занимала особая концепция сложности, случайности и информации, которая до сих пор не имела практического применения.
Обезьяны за клавиатурой
Эта теория, изобретенная в 1960-х годах, работает с так называемой алгоритмической информацией.Все начинается с интуитивного мышления о вероятности и сложности: идеи о том, что для некоторых входных данных будет проще с вычислительной точки зрения описать, как что-то создать, чем создать это.
Возьмем известную аналогию с обезьяной, случайным образом нажимающей клавиши.
Шансы на то, что она наберет первые 15 000 цифр числа π, смехотворно малы — и они уменьшаются экспоненциально по мере увеличения количества цифр.
Но если вы интерпретируете нажатия клавиш как случайный текст для компьютерной программы, выводящей число π, то шансы на успех, или «алгоритмическая вероятность», радикально улучшатся.
Например, код для печати первых 15 000 цифр числа π в языке C можно сжать всего до 133 символов.
Другими словами, алгоритмическая теория информации говорит, что вероятность получения некоторых типов вывода намного выше, когда случайные процессы действуют на уровне программы, описывающей данные, чем на уровне самих данных, поскольку программа будет короткой.
В этом смысле сложные структуры, такие как фракталы, гораздо легче получить случайно.
Однако вскоре с этим подходом возникла проблема: математики обнаружили, что алгоритмическая сложность (также известная как Колмогоровская сложность , названный в честь Андрей Николаевич Колмогоров , один из основоположников теории) при данных выходных данных — длине кратчайшей возможной программы, которая их выдаст — невозможно вычислить.
Поэтому ученые-компьютерщики не могут найти идеальный способ сжать строку или другой объект. 
Алгоритмическая сложность сети слева высока, так как ее описание требует перечисления всех ребер, соединяющих вершины.
В середине сложность меньше, так как при описании этой сети можно написать, что вершина А соединена со всеми остальными.
Правая сеть имеет наименьшую сложность, так как ее описание заключается в том, что все вершины соединены ребрами попарно.
В результате алгоритмическая теория информации получила развитие преимущественно в области чистой математики, где она используется для изучения смежных теорем и определения понятий случайности и структуры.
Практическое его использование казалось недоступным.
«Математически это простая и красивая мера сложности», — сказал известный математик Грегори Чайтин, один из основателей теории, работавший в Центре IBM Томаса Дж.
Уотсона и Федеральном университете Рио-де-Жанейро.
«Но с точки зрения применимости в реальном мире это казалось непостижимым».
Но это не заставило его отступить.
Он надеялся, что эту теорию можно будет использовать для формализации идеи о том, что ДНК ведет себя как программа.
В 2012 году он опубликовал книгу, в которой описал, что эволюцию можно рассматривать как случайное блуждание по пространству программного обеспечения.
Мутации, происходящие на этом пути, писал он, не следуют статистически случайному распределению вероятностей; они подчиняются распределению, основанному на колмогоровской сложности.
Но он не мог это проверить.
Теперь некоторые ученые надеются возродить эту теорию в этом контексте и связать ее как с биологией, так и с информатикой.
Стремление к простоте
Гектор Зенил , ученый-компьютерщик из Каролинского института в Швеции, является одним из тех, кто пытается возродить эту теорию.Вместе с другими исследователями он работает над использованием колмогоровской сложности в качестве показателя для анализа сложности биологических сетей — например, сетей регуляции генов или белковых взаимодействий в клетках.
Исследователи грубо оценивают алгоритмическое содержание сети (точное значение невозможно вычислить), затем мутируют сеть и проверяют, насколько это влияет на колмогоровскую сложность.
Они надеются, что этот метод даст им представление об относительной важности различных элементов сети и ее функциональной реакции на преднамеренные изменения.
Известный математик Григорий Чайтин, один из основоположников алгоритмической теории информации.
В последнее время работа , опубликованном на arxiv.org, они описали, что принуждение сети к увеличению сложности по Колмогорову — путем введения мутаций, которые заставляли программу, описывающую сеть, становиться больше — это обычно приводило к увеличению количества функций, которые сеть могла выполнять одновременно.
делая его более чувствительным к помехам.
Поскольку они заставили сеть стать проще, функций стало меньше, а стабильность возросла.
Однако остается неясным, может ли колмогоровская сложность играть большую роль, чем простой инструмент – например, как полагает Чайтин, быть главной движущей силой перемен.
Несмотря на все проблемы, алгоритмическая информация кажется привлекательной теорией для биологии.
Традиционно математика использовалась для описания эволюционной динамики в области популяционная генетика – статистические модели, описывающие частоту встречаемости генов в популяции.
Однако популяционная генетика имеет свои ограничения: она не описывает возникновение жизни и другие важные биологические переходы, а также появление совершенно новых генов.
«Идея биологического творчества каким-то образом затерялась в этой красивой математической теории», — сказал Чайтин.
Но если вы примете во внимание алгоритмическую информацию, сказал он, «то творчество естественным образом впишется в общую картину».
Как и идея о том, что эволюционный процесс со временем совершенствуется и становится более эффективным.
«Я убежден, что эволюция учится», — сказал Дэниел Поланьи , ученый-компьютерщик и профессор искусственного интеллекта в Университете Хартфордшира в Англии.
«Я не удивлюсь, если это можно будет выразить в терминах асимптотического снижения алгоритмической сложности».
Зенил и его команда решили экспериментально проверить биологические и вычислительные последствия алгоритмической сложности платформы.
Используя те же методы оценки сложности, которые они использовали для анализа и возмущения сетей, они «развили» искусственные генетические сети в направлении конкретных целей — матриц из нулей и единиц, представляющих взаимодействие генов — отбирая мутации, которые создавали матрицы с меньшей алгоритмической сложностью.
Другими словами, они сделали выбор в пользу более крупных структур.
Гектор Зенил, ученый-компьютерщик Каролинского института
Недавно они опубликовали результаты в журнале Royal Society Open Science, показывающие, что по сравнению со статистически случайными мутациями их выбор мутаций привел к значительному ускорению эволюции сетей к решениям.
Появились и другие особенности, например, постоянные и регулярные структуры — участки матриц, уже достигшие определенной степени простоты, которые новые поколения вряд ли смогут улучшить.
«Некоторые регионы были более или менее подвержены мутациям просто потому, что они уже достигли определенного уровня простоты», — сказал Зенил.
«Это было очень похоже на гены».
Эта генетическая память помогла крупным структурам возникать быстрее — исследователи полагают, что это означает, что алгоритмически вероятные мутации могут привести к вспышкам разнообразия и вымиранию.
«Это означает, — сказал Зенил, — что рассмотрение вычислительных процессов при изучении эволюции будет весьма плодотворным».
Он надеется использовать это понимание случайности и сложности, чтобы определить метаболические пути, которые могут быть более восприимчивы к мутациям, или понять, почему определенные взаимодействия генов могут быть связаны с такими заболеваниями, как рак.
Ээволюция программ
Зенил надеется понять, работает ли биологическая эволюция по тем же вычислительным правилам, но у большинства экспертов есть сомнения.Неясно, какой естественный механизм может отвечать за аппроксимацию алгоритмической сложности или за целенаправленное развитие мутаций.
Более того, «было бы неправильно считать, что жизнь полностью закодирована четырьмя буквами», — сказал Джузеппе Лонго , математик Национального центра научных исследований во Франции.
«ДНК чрезвычайно важна, но не имеет никакого значения вне клетки, организма, экосистемы».
Существуют и другие взаимодействия, и использование алгоритмической информации не может охватить всю эту сложность.
Тем не менее, эта концепция вызвала некоторый интерес, особенно потому, что эти взгляды на эволюцию и вычисления имеют что-то общее или, по крайней мере, общую тему с целью генетического программирования — создать программу, которая может развиваться.
Уже были некоторые интригующие намеки на потенциальную связь между идеями Чайтина и Зенила о колмогоровской сложности и методах генетического программирования.
Например, в 2001 году группа исследователей сообщил что сложность вывода генетической программы ограничена колмогоровской сложностью исходной программы.
Но по большей части колмогоровская сложность не сыграла роли в попытках ученых-компьютерщиков понять эти идеи.
Они пробовали другие способы изменения генетики и мутаций.
Некоторые группы меняли скорость мутаций, другие заставляли систему отдавать предпочтение мутациям, которые заменяли большие фрагменты кода.
«Люди придумали десятки, а возможно, сотни различных версий мутаций и генотипов», — сказал он.
Ли Спектор , ученый-компьютерщик из Хэмпширского колледжа в Массачусетсе.
Спектор недавно возглавил команду, продемонстрировали преимущества добавление и удаление мутаций во всем геноме организма перед непосредственной заменой одного гена другим.
Этот новый вид генетического оператора экспоненциально увеличил количество путей в пространстве генетического поиска и в конечном итоге привел к лучшим решениям.
Ли Спектор, ученый-компьютерщик из Хэмпширского колледжа в Массачусетсе.
Однако многие исследователи пошли в противоположном направлении, ища умные способы ускорить процесс за счет сужения поля поиска, но не ограничивая его настолько, чтобы поиск упускал оптимальные результаты.
Одна из идей заключалась в том, чтобы сделать простоту целью: в 1960-е годы Юджин Вигнер отметил «необоснованную эффективность математики в естественных науках», а ученые-компьютерщики обнаружили, что часто более простые и элегантные модели были более эффективными и более широко применимыми.
«Вопрос в том, — сказал Спектор, — говорит ли этот факт что-то глубокое о структуре Вселенной или нет? И будет ли это нам полезно? Он также предупреждает, что попытки подтолкнуть развивающиеся программы к простоте могут быть разрушительными: вознаграждение программ за краткость может привести к сокращению того, что сейчас кажется мусором, но может быть полезно для будущих поколений, жертвуя оптимальными решениями.
«И мы застрянем», — сказал он.
Однако простота остается заманчивой целью, которая также доказала свою полезность.
Опубликовано в прошлом году работа Спектор и его коллеги обнаружили, что если программы были уменьшены в размере (иногда всего на 25% от их первоначальной длины) после применения методов генетического программирования, программы лучше справлялись с новыми данными и могли использоваться для более широкого круга общих задач.
проблемы.
В частности, из-за этого он следит за работами в области алгоритмической теории информации, хотя и говорит, что ее влияние на эту область исследований еще предстоит выяснить.
Учимся у жизни
Команда Зенила, возможно, и сделала первый шаг в поиске этого влияния, но чтобы реально применить свою работу, им сначала необходимо проверить свой метод на других типах поисковых задач.Тем не менее, «они убедительно продемонстрировали необходимость структурных ограничений», сказала она.
Лариса Альбантакис , нейробиолог-теоретик из Университета Висконсина, который также работал над ускорением генетических алгоритмов за счет ограничения пространства поиска.
«Природа устроена, и если принять это за отправную точку, было бы глупо пытаться проверить все возможные однородные мутации».
И добавила: «Все, что имеет для нас смысл, каким-то образом структурировано».
И хотя Спектор скептически относится к тому, что работу Зенила можно применить к чему-либо, выходящему за рамки конкретной проблемы, которую он изучал, «теория информации, лежащая в основе их концепций, интригует и потенциально весьма важна», сказал он.
«Мне это кажется интересным отчасти потому, что оно выглядит немного инопланетным».
Возможно, есть идеи, о которых товарищи из нашего сообщества даже не подозревают».
В конце концов, алгоритмическая информация связана с широким спектром идей, которые некоторые эксперты по генетическому программированию могут не включать в свою работу, например, с открытой природой эволюции.
«У меня твердое ощущение, что в этой области есть что-то важное», — сказал Спектор.
Однако, добавил он, пока «между их работой и практическим применением существует огромная дистанция».
«Идея рассматривать жизнь как развивающуюся программу очень плодотворна», — сказал Чайтин, хотя ее ценность еще слишком рано определять.
Говорим ли мы об искусственной жизни или о биологической жизни, «нам придется посмотреть, как далеко мы сможем зайти».
Теги: #эволюция #биология #популярная наука #математика #алгоритмы
-
Программа Ppc Coach: Краткий Обзор
19 Oct, 24 -
Ищу Тире
19 Oct, 24 -
Кандидатов Наук Можно Отменить, Но Не Будут.
19 Oct, 24 -
Офис Одноклассники
19 Oct, 24
