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

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

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

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. В данной монографии мы приводим рисунки и текст из этих 
работ, иногда дословно. Во всех случаях мы старались дать прямую ссылку на 
источник, но, возможно, что-то упустили.
Вне всяких сомнений, у материала этой монографии прочная основа. Цитируемые статьи тем не менее написаны на уровне, который понятен только 
фанатичным ученым. Данная монография служит двум целям. Во-первых, это 
объяснение эволюционной информатики на уровне, доступном для хорошо 
эрудированного читателя. Во-вторых, мы убеждены, что данная работа достаточно полно раскрывает различные точки зрения на теорию эволюционного 
моделирования.

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

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