Введение в эволюционную информатику

Роберт Маркс, Уильям Дембски, Уинстон Эверт

Введение  
в эволюционную информатику

I N T RO D U CT I O N TO 
EVOLUTIONARY 
INFORMATICS

NEW JERSEY • LONDON • SINGAPORE • BEIJING • SHANGHAI • HONG KONG • TAIPEI • CHENNAI • TOKYO

Robert J Marks II
Baylor University, USA

William A Dembski
Evolutionary Informatics Lab, USA

Winston Ewert
Evolutionary Informatics Lab, USA

В В Е Д Е Н И Е  
В ЭВОЛЮЦИОННУЮ  
ИНФОРМАТИКУ

Роберт Маркс
Университет Бэйлор, США

Уильям Дембски
Лаборатория эволюционной информатики, США

Уинстон Эверт
Лаборатория эволюционной информатики, США

Москва, 2020

УДК 004.421, 57.08
ББК 32.972, 28.0
М25

Маркс Р., Дембски У., Эверт У.
М25 Введение в эволюционную информатику / пер. с анг. В. С. Яценкова. – М.: 
ДМК Пресс, 2020. – 276 с.: ил. 

ISBN 978-5-97060-725-1

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

УДК 004.421, 57.08
ББК 32.972, 28.0

Authorized Russian translation of the English edition of Introduction to Evolutionary 
Informatics ISBN 9789813142145 © 2017 by World Scientific Publishing Co. Pte. Ltd.
This translation is published and sold by permission of Packt Publishing, which owns or 
controls all rights to publish and sell the same.

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

ISBN 978-9-8131-4214-5 (анг.) 
© 2017 by World Scientific Publishing Co. Pte. Ltd.
ISBN 978-5-97060-725-1 (рус.) 
© Оформление, издание, перевод, ДМК Пресс, 2020

Содержание

Вступительное слово от издательства .....................................................9
Предисловие ....................................................................................................10
Об авторах ........................................................................................................19

Глава 1. Введение ...........................................................................................21
1.1. Королева ученых и инженеров ......................................................................22
1.2. Наука и модели ...............................................................................................23
1.2.1. Компьютерные модели ...........................................................................24
1.2.2. Невероятное и невозможное ..................................................................24
Источники .............................................................................................................25

Глава 2. Информация: что это такое? .....................................................27
2.1. Определение информации ............................................................................27
2.2. Измерение информации ...............................................................................29
2.2.1. Cложность по KCS ....................................................................................30
2.2.2. Информация Шеннона ...........................................................................37
2.3. Заключение .....................................................................................................44
Источники .............................................................................................................44

Глава 3. Эволюционный поиск и требования к информации ......47
3.1. Эволюция как поиск ......................................................................................47
3.1.1. WD-40TM и Formula 409TM .........................................................................48
3.1.2. Тесла, Эдисон и знания в предметной области .....................................48
3.2. Инженерная разработка с помощью компьютера .......................................49
3.3. Разработка рецепта вкусных блинов ............................................................50
3.3.1. Поиск хорошего блина № 1 ....................................................................50
3.3.2. Поиск хорошего блина № 2: время приготовления плюс  
настройка оборудования ..................................................................................53
3.3.3. Поиск хорошего блина № 3: больше переменных параметров  
рецепта ..............................................................................................................53
3.3.4. Поиск хорошего блина № 4: имитация блинов на компьютере  
с искусственным языком с использованием одного агента ..........................55
3.3.5. Поиск хорошего блина № 5: моделирование блинов  
на компьютере с помощью эволюционного поиска ......................................57
3.4. Источники знаний .........................................................................................58
3.4.1. Проектирование антенн с использованием эволюционных  
вычислений .......................................................................................................60

 Содержание

3.5. Проклятие размерности и потребность в знаниях ......................................62
3.5.1. Поможет ли Мур? Как насчет Гровера? ..................................................63
3.6. Неявные цели .................................................................................................64
3.7. Оптимальная неоптимальность ....................................................................67
3.7.1. Потеря функции ......................................................................................67
3.7.2. Оптимизация Парето и оптимальная субоптимальность ....................68
3.7.3. Человек в цикле как фактор активной информации ............................70
3.8. Ландшафты отбора поисковых алгоритмов .................................................71
3.9. Выводы ............................................................................................................73
Источники .............................................................................................................73

Глава 4. Детерминизм в случайности .....................................................81
4.1. Принцип равной вероятности событий .......................................................83
4.1.1 «Ничто есть то, о чем мечтают скалы» ...................................................83
4.1.2. Принцип недостаточного основания Бернулли (PrOIR) ......................84
4.2. Потребность в шуме .......................................................................................99
4.2.1. Фиксированные точки в случайных событиях ......................................99
4.2.2. Выборка по значимости .......................................................................103
4.2.3. Предельные циклы, странные аттракторы и тетербол .......................104
4.3. Потолок Бейснера ........................................................................................105
4.3.1. Tierra ......................................................................................................106
4.3.2. Край эволюции ......................................................................................109
4.4. Заключение ...................................................................................................110
Источники ...........................................................................................................111

Глава 5. Сохранение информации в компьютерном поиске ......114
5.1. Основы ..........................................................................................................114
5.2. Что такое сохранение информации? ..........................................................116
5.2.1. Обманчивые контрпримеры ................................................................118
5.2.2. Взаимосвязь между обучением и поиском .........................................120
5.2.3. Человек в цикле, вносящий активную информацию .........................125
5.3. Удивительная стоимость слепого поиска в битах ......................................128
5.3.1. Анализ ....................................................................................................128
5.3.2. Вычислительная стоимость ..................................................................129
5.4. Измерение сложности поиска в битах ........................................................131
5.4.1. Эндогенная информация .....................................................................131
5.4.2. Активная информация .........................................................................136
5.4.3. Извлечение активной информации из оракулов ...............................148
5.5. Источники информации в эволюционном поиске ....................................156
5.5.1. Популяция .............................................................................................157
5.5.2. Коэффициент мутации .........................................................................157
5.5.3. Ландшафт отбора ..................................................................................158
5.6. Ступенчатая информация и переходная функциональная  
жизнеспособность ..............................................................................................160

Содержание  7

5.6.1. Детские шаги .........................................................................................162
5.6.2. Сохранение функциональности развития и неснижаемая  
сложность ........................................................................................................162
5.7. Коэволюция ...................................................................................................167
5.8. Поиск поиска ................................................................................................171
5.8.1. Пример ...................................................................................................171
5.8.2. Проблема поиска для поисков .............................................................172
5.8.3. Математические доказательства .........................................................174
5.9. Заключение ...................................................................................................179
Источники ...........................................................................................................179

Глава 6. Анализ моделей биологической эволюции ......................185
6.1. EV: программная модель эволюции ...........................................................186
6.1.1. Структура EV ..........................................................................................186
6.1.2. Устройство программы EV ....................................................................189
6.1.3. Внутренние источники информации в EV ..........................................192
6.1.4. Поиск ......................................................................................................195
6.1.5. Интерфейс EV Ware ...............................................................................197
6.1.6. Диагноз ..................................................................................................200
6.2. Avida: ступенчатый поиск и логика NAND .................................................202
6.2.1. Булева логика ........................................................................................202
6.2.2. Логика NAND .........................................................................................203
6.2.3. Организм Avida и его здоровье ............................................................208
6.2.4. Анализ Avida с точки зрения информации .........................................212
6.2.5. Наличие замысла в программе Avida ..................................................221
6.2.6. Движения мертвого организма ............................................................223
6.3. Метабиология ...............................................................................................223
6.3.1. Проблема остановки .............................................................................225
6.3.2. Проблема поиска ...................................................................................226
6.3.3. Математический базис метабиологии ................................................227
6.3.4. Ресурсы ..................................................................................................231
6.4. Пора подметать грязный пол? ....................................................................232
6.4.1. Доработка дерева Штейнера ................................................................232
6.4.2. Время для эволюции .............................................................................233
6.4.3. Заключение ............................................................................................234
Источники ...........................................................................................................234

Глава 7. Измерение смысла и алгоритмическая  
заданная сложность ....................................................................................240
7.1. Значимость информации.............................................................................240
7.2. Условная сложность KCS ...............................................................................242
7.3. Определение алгоритмической заданной сложности (ASC) .....................243
7.3.1. Высокая ASC и низкая вероятность ......................................................245

 Содержание

7.4. Примеры ASC ................................................................................................246
7.4.1. Расширенные буквенно-цифровые символы ......................................246
7.4.2. Игра в покер ...........................................................................................249
7.4.3. Снежинки ...............................................................................................250
7.4.4. ASC в игре «Жизнь» ...............................................................................252
7.5. Смысл в глазах смотрящего .........................................................................263
Источники ...........................................................................................................264

Глава 8. Разум и искусственный интеллект .......................................266
8.1. Тьюринг и Лавлейс: сильный и слабый интеллект ....................................267
8.1.1. Ошибка Тьюринга .................................................................................267
8.1.2. Тест Лавлейс ..........................................................................................269
8.1.3. Озарение гения .....................................................................................270
8.2. Интеллект и непознаваемое ........................................................................271
8.3. Заключение ...................................................................................................272
Источники ...........................................................................................................272

Предметный указатель ..............................................................................274

Вступительное слово 
от издательства

Отзывы и пОжелания

Мы всегда рады отзывам наших читателей. Расскажите нам, что вы думаете об 
этой книге – что понравилось или, может быть, не понравилось. Отзывы важны 
для нас, чтобы выпус кать книги, которые будут для вас максимально полезны.
Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на 
страницу книги и оставив комментарий в разделе «Отзывы и рецензии». Также можно послать письмо главному редактору по адресу dmkpress@gmail.com; 
при этом укажите название книги в теме письма. 
Если вы являетесь экспертом в какой-либо области и заинтересованы в написании новой книги, заполните форму на нашем сайте по адресу http://dmkpress.com/authors/publish_book/ или напишите в издательство по адресу dmkpress@gmail.com.

СпиСОк ОпечатОк

Хотя мы приняли все возможные меры для того, чтобы обеспечить высокое 
качество наших текстов, ошибки все равно случаются. Если вы найдете ошибку 
в одной из наших книг – возможно, ошибку в основном тексте или программном коде, – мы будем очень благодарны, если вы сообщите нам о ней. Сделав 
это, вы избавите других читателей от недопонимания и поможете нам улучшить последующие издания этой книги. 
Если вы найдете какие-либо ошибки в коде, пожалуйста, сообщите о них 
главному редактору по адресу dmkpress@gmail.com, и мы исправим это в следующих тиражах.

нарушение автОрСких прав

Пиратство в интернете по-прежнему остается насущной проблемой. Издательства «ДМК Пресс» и World Scientific очень серь езно относятся к вопросам 
защиты авторских прав и лицензирования. Если вы столкнетесь в интернете 
с незаконной публикацией какой-либо из наших книг, пожалуйста, пришлите 
нам ссылку на интернет-ресурс, чтобы мы могли применить санкции.
Ссылку на подозрительные материалы можно прислать по адресу электронной поч ты dmkpress@gmail.com.
Мы высоко ценим любую помощь по защите наших авторов, благодаря которой мы можем предоставлять вам качественные материалы.

Предисловие

Наука добилась больших успехов в моделировании пространства, времени, 
массы и энергии, но слишком мало сделала, для того чтобы создать модель 
информации, заполняющей нашу Вселенную. Сегодня теория информации 
используется для измерения емкости диска Blu-ray или для описания пропускной способности соединения Wi-Fi. Тем не менее наука не рассматривает 
трудности, связанные с созданием содержимого Blu-ray и смыслом данных, передаваемых через соединение Wi-Fi. Новые достижения теории информации 
позволяют оценить роль информации в эволюционных процессах и под новым 
углом взглянуть на само понятие информации и ее роль в картине мироздания. 
В самом деле, все современные модели требуют для работы информацию от 
внешнего источника. Иными словами, все современные эволюционные модели просто не работают без подключения к внешнему источнику информации. 
В объяснении основ захватывающей теории информации на доступном уровне 
и заключается назначение книги «Введение в эволюционную информатику».

первОиСтОчники

Содержание этой монографии вытекает из оригинальных работ одного из ваших скромных соавторов, Уильяма А. Дембски (William A. Dembski) [1], и последующих отредактированных трудов [2]. Авторы написали множество статей 
и глав книг, в которых содержится основополагающий материал для этой монографии [3]. Ссылки на многие из этих документов доступны на нашем сайте EvoInfo.org. В данной монографии мы приводим рисунки и текст из этих 
работ, иногда дословно. Во всех случаях мы старались дать прямую ссылку на 
источник, но, возможно, что-то упустили.
Вне всяких сомнений, у материала этой монографии прочная основа. Цитируемые статьи тем не менее написаны на уровне, который понятен только 
фанатичным ученым. Данная монография служит двум целям. Во-первых, это 
объяснение эволюционной информатики на уровне, доступном для хорошо 
эрудированного читателя. Во-вторых, мы убеждены, что данная работа достаточно полно раскрывает различные точки зрения на теорию эволюционного 
моделирования.

МатеМатика и СиМвОл ⍟

Хотя в этой книге мы попытались свести к минимуму обращения к математике, иногда без нее не обойтись. В таких случаях мы выделяем математический 
материал символом ⍟ и даем максимально четкое объяснение основополагающих рассуждений.

Краткое содержание глав  11

Математический материал может быть понят с начальным знанием:
 
 простых логарифмов;
 
 элементарной теории вероятностей;
 
 элементарной статистики, такой как средние значения (или среднее по 
выборке);
 
 представления чисел в двоичном формате (по основанию 2);
 
 простых операций булевой алгебры, таких как И (AND), ИЛИ (OR), НЕ 
(NOT), И-НЕ (NAND), ИЛИ-НЕ (NOR), ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR) и т. д.
Чтобы помочь тем, кто хочет быстрее прочитать книгу или не интересуется 
математическими подробностями, мы пометили символом ⍟ разделы, которые можно пропустить. Некоторые математические дополнения даны в сносках и также помечены символом ⍟.

ССылки и СнОСки

Как правило, в конце глав перечислены источники и дополнительная литература, в то время как в сносках содержатся пояснения и дополнения к материа лу 
главы. Ссылки на источники обозначены числом в квадратных скобках, сноски 
обозначены надстрочным числом. При быстром или обзорном чтении сноски 
можно пропустить.

краткОе СОдержание глав

Глава 1. Введение
Ученые и философы часто возводят теорию или идеологию на трон, словно королеву, а инженеры заставляют королеву сойти с трона и вымыть пол. И если 
она не работает, ее прогоняют прочь.
Ученые надеялись, что быстрые компьютеры позволят построить универсальную модель ненаправленной эволюции, основанную исключительно на 
случайных мутациях. Однако пока это не удалось. Если опираться только на 
теорию вероятностей, вы непременно сталкиваетесь с законом Бореля (Borel’s 
law), который гласит, что события, описанные с достаточно малой (стремящейся к нулю) вероятностью, являются невозможными событиями. Например, существует ненулевая вероятность того, что вы испытаете квантовое туннелирование через стул, на котором сидите. Однако вероятность настолько мала, что 
мы можем классифицировать событие как невозможное.

Глава 2. Информация: что это такое?
Информация – это не материя и не энергия. Она выступает как самостоятельный компонент природы.
Термин «информация», как правило, не очень хорошо определен, используется ли он в повседневной беседе или в журнальной статье. Теория информации Шеннона (Shannon) является, пожалуй, самой известной математической 

 Предисловие

моделью информации. Шеннон отметил очевидное: его модель информации 
ограничена и не применима к широкому кругу возможных определений информации.
Теория информации Колмогорова–Хайтина–Соломонова (Kolmogorov–Chaitin–Solomonov, KCS), также известная как алгоритмическая теория информации, является еще одной популярной моделью информации. Однако и модели 
Шеннона, и KCS не способны моделировать информацию в части измерения 
смысла или значимости, относящихся к объекту.

Глава 3. Эволюционный поиск и требования к информации
Инженерное проектирование – это всегда итеративный поиск, основанный на 
компетенции разработчика. Для создания WD-40 понадобилось 40 испытаний, 
а Formula 409 потребовала 409 попыток. Так эти продукты получили числовую 
часть своих названий.
Анатомия поиска иллюстрируется на примере того, как шеф-повар разрабатывает хороший рецепт блинов. Выделены важные аспекты разработки, в том 
числе роль отраслевого эксперта и проклятие размерности, которое может 
быст ро сделать невозможным априорно-неинформированный проект.
Анализ разработанной с использованием эволюционного поиска антенны 
NASA показывает, что в области эволюционного проектирования накоплены 
достаточно обширные познания, и проблема поиска была не такой уж сложной.
При разработке чего угодно невозможно обойтись без компромиссов. Разработка недорогого и безопасного автомобиля требует определенного баланса 
критериев. Дешевые машины небезопасны, а безопасные машины недешевы. Более того, глобальная оптимальность требует частичной оптимальности 
(субоптимальности) составляющих частей. Плохо обоснованные критические 
утверж дения о неоптимальном устройстве биологических систем объясняются 
наличием компромиссов, присущих любой сложной системе.

Глава 4. Детерминизм в случайности
Это может звучать как оксюморон, но в случайности есть элементы детерминизма. Например, если монету многократно подбрасывают тысячи раз, количество выпавших орлов всегда будет стремиться к детерминированному значению 
50 % от числа подбрасываний. Аналогичным образом многие программы, целью 
которых является демонстрация ненаправленной эволюции, неизменно пишутся так, чтобы в большинстве случаев сходиться к конкретному детерминированному результату. Как и в случае со стальным шариком в автомате для игры 
в пинбол, в каждом испытании можно выбрать разные пути, но стальной шарик 
всегда заканчивает тем, что падает в маленькое отверстие под лопатками.
Принцип недостаточного обоснования Бернулли (Principle Of Insufficient Reason, PrOIR), несмотря на сложное название, просто говорит о том, что вероятность выиграть в лотерею с тысячей билетов – один шанс из тысячи, если вы 
купили только один билет. Каждому возможному исходу в розыгрыше присва

Краткое содержание глав  13

ивается равная вероятность. PrOIR Бернулли используется для моделирования 
случайного слепого поиска.
Потолок Бейснера (Basener’s ceiling) накладывает строгое ограничение на 
любой эволюционный процесс. Он гласит, что эволюционный компьютерный 
поиск достигает точки, когда дальнейшее улучшение невозможно. Здравый 
смысл подсказывает, что эволюционная программа, написанная для проектирования антенны, не будет продолжать развиваться до такой степени, что, например, самопроизвольно научится играть в шахматы. Теория, лежащая в основе этого ограничения эволюционных процессов, основывается на понятии 
потолка Бейснера.

Глава 5. Сохранение информации в компьютерном поиске
Теперь у нас есть инструменты, необходимые для представления закона сохранения информации (Information Conservation Law, ICL), как показано в теореме об отсутствии бесплатных завтраков (No Free Lunch theorem, NFL). Теорема гласит, что при итеративном поиске произвольной цели один алгоритм 
в среднем так же хорош, как и любой другой, если у разработчика нет никаких 
априорных экспертных знаний в предметной области. Теорема, опубликованная в 1997 году Вольпертом (Wolpert) и Макреди (Macready), вызвала удивление 
у сообщества машинного интеллекта, которое часто противопоставляло один 
алгоритм поиска другому, чтобы определить, какой из них лучше. Получается, 
что результаты такого конкурса ничего не говорят о тотальном преимуществе 
одного алгоритма поиска над другим. Они лишь показывают, что определенный алгоритм поиска лучше подходит к исследуемой проблеме, и это преимущество не действует для других проблем.
Теорема об отсутствии бесплатных завтраков также послужила источником 
вдохновения для книги Уильяма Дембски с аналогичным названием.
Если нет априорных экспертных знаний о предметной области, мы ожидаем, что слепой поиск будет работать так же хорошо, как и любой другой метод. 
Проблема в том, что во многих случаях обращение к одной лишь случайности 
быстро заводит в экспоненциальный тупик бесконечного числа вариантов. 
Эффективная эволюция требует наличия информации.
Эволюционный поиск можно сделать лучше, чем в среднем, с помощью экспертизы предметной области. В этом случае для успешного поиска требуется 
меньше итераций. Активная информация измеряет степень, в которой экспертиза предметной области помогает в поиске. Суть активной информации иллюстрируют легко понятные примеры, такие как головоломка Cracker Barrel 
и игровое шоу «Давайте договоримся».
Утверждают, что теорема об отсутствии бесплатных завтраков была нарушена так называемым процессом коэволюции. Мы аргументированно показываем, что это не так.
Наконец, мы затрагиваем тему поиска поисков (метапоиска). Если все поисковые процедуры в среднем работают одинаково, разве у нас не может быть 

 Предисловие

компьютерного поиска для выявления поиска, который в определенной ситуации работает лучше среднего? Ответ оказывается решительным НЕТ! Показано, что метапоиск экспоненциально сложнее, чем сам поиск.

Глава 6. Анализ моделей биологической эволюции

Существует ряд компьютерных программ, предназначенных для демонстрации ненаправленной дарвиновской эволюции. Наиболее известной является 
программа моделирования эволюции Avida, которой даже довелось участвовать в судебном процессе между сторонниками и противниками теории ненаправленной эволюции.
Поскольку Avida пытается решить относительно сложную задачу, разработчик программы, очевидно, внедрил в код программы знания предметной области. Мы определяем источники и измеряем внесенную активную информацию. Показано, что Avida содержит много хаотичной информации, снижающей 
производительность. Когда беспорядок устранен, программа сходится к решению быстрее.
Другая эволюционная программа, исследованная на предмет выявления 
и измерения активной информации, называется EV.
Когда в эволюционной программе выявлен внешний источник знаний, соответствующая активная информация может быть добыта иными способами 
с помощью других поисковых программ. Как для Avida, так и для EV показаны 
альтернативные программы поиска, которые дают те же результаты, что и эволюционный поиск, но с меньшей вычислительной нагрузкой.
На EvoInfo.org мы разработали интерактивные графические интерфейсы, 
чтобы проиллюстрировать производительность как Avida, так и EV. Имеется 
также графический интерфейс для экспериментального исследования алгоритма поиска Ричарда Докинза (Richard Dawkins), известного как алгоритм 
«Ласка» (WEASEL algorithm). Устройство и использование этих графических 
интерфейсов достаточно просты, так что читатель может выйти в интернет 
и провести эксперимент самостоятельно.
Наконец, анализируется модель, предложенная Грегори Хайтиным (Gregory 
Chaitin) в его книге «Доказывая Дарвина: математическая биология», изданной 
в 2013 году. Модель Хайтина, построенная в красивом и сюрреалистическом 
мире алгоритмической теории информации, оказывается переполненной активной информацией. К сожалению, как и другие компьютерные программы, 
написанные для демонстрации ненаправленной дарвиновской эволюции, она 
не является всеохватывающей.

Глава 7. Измерение смысла  
и алгоритмическая заданная сложность

Заданная сложность (specified complexity) рассматривается как оценка степени значимости исходной или экспертной информации при создании объекта.