Вселенная. Происхождение жизни, смысл нашего существования и огромный космос

В информатике, как и в жизни, часто встречается простая задача: найти конкретный элемент, выбрав его из множества вариантов. Рассмотрим задачу коммивояжера: имея список городов и расстояний между ними, нужно проложить между этими городами кратчайший маршрут, на котором каждый город будет встречаться только один раз. Задачу можно перефразировать. Возьмём список городов и расстояний между ними. Далее сделаем новый список, перечислив в нём все возможные маршруты, по которым коммивояжер заходит в каждый город как минимум один раз (это будет невероятно длинный, но всё-таки конечный список). Какой маршрут будет кратчайшим?

Поисковый алгоритм — это чётко сформулированная процедура для нахождения нужного элемента в списке объектов. Разумеется, можно перебрать все элементы один за другим, каждый раз спрашивая: «Этот?». Такой способ, вероятно, будет сложен, так как при поиске ответов на вполне разумные вопросы порой требуется отсортировать немыслимо огромные списки. В случае с задачей коммивояжера число возможных маршрутов возрастает примерно как факториал от числа охватываемых городов. Факториал числа n равен произведению 1 умножить на 2 умножить на 3 умножить на 4... умножить на (n − 1). Таким образом, в случае с двадцатью семью городами потребуется проверить около 10²⁸ маршрутов. Если бы поиск шёл со скоростью миллиард маршрутов в секунду, то занял бы больше времени, чем существует наблюдаемая Вселенная.

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

Естественный отбор можно сравнить с поисковым алгоритмом. Эволюция решает следующую задачу: какой организм сможет наиболее эффективно размножаться и выживать в данной конкретной среде? Только поиск охватывает не организмы как таковые, а их геномы либо конкретные нуклеотидные последовательности в нити ДНК. В человеческом геноме содержится около трёх миллиардов нуклеотидов. Это много по сравнению, скажем, с бактериальным геномом, где насчитывается лишь несколько миллионов нуклеотидов. Но давайте не будем задаваться: у некоторых цветковых растений в ДНК имеется более 100 миллиардов пар нуклеотидных оснований. Некоторым организмам удастся выжить и размножиться, другим — нет. Однако как среди многих поколений найти такие последовательности ДНК, которые повышают шансы организма на выживание?

С вычислительной точки зрения эта проблема считается сложной. Каждый из трёх миллиардов наших нуклеотидов может соответствовать одной букве: А, Ц, Г или Т. Общее число возможных комбинаций в ДНК такого размера, как у человека, составляет не четырежды три миллиарда (что было бы ещё не так плохо), а четыре в степени три миллиарда: 4^3000000000, то есть единица, за которой следует примерно два миллиарда нулей. Это ошеломительно, грандиозно огромное число. Кроме того, оно завышено; некоторые нуклеотидные последовательности функционально идентичны друг другу, а из абсолютного большинства последовательностей организм бы просто не получился. Можно подсчитать гены, а не нуклеотиды; в таком случае число значительно уменьшится, хотя каждый ген допускает значительно больше четырёх форм. Итак, число остаётся огромным, а из-за взаимозависимости различных генетических функций любые подсчёты такого рода остаются в некоторой степени неопределёнными. Итак, при любом мыслимом раскладе проблема поиска «лучшего» организма путём перебора всех возможных геномов представляется титанической.

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

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

* * *