УДК 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 (анг.)
ISBN 978-5-97060-725-1 (рус.)
© 2017 by World Scientific Publishing Co. Pte. Ltd.
© Оформление, издание, перевод, ДМК Пресс, 2020
Стр.5
Содержание
Вступительное слово от издательства .....................................................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
Глава 3. Эволюционный поиск и требования к информации ......47
3.1. Эволюция как поиск ......................................................................................47
3.1.1. WD-40TM
3.1.2. Тесла, Эдисон и знания в предметной области .....................................48
и Formula 409TM
.........................................................................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
2.3. Заключение .....................................................................................................44
Источники .............................................................................................................44
3.4. Источники знаний .........................................................................................58
3.4.1. Проектирование антенн с использованием эволюционных
вычислений .......................................................................................................60
Стр.6
6 Содержание
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.4. Заключение ...................................................................................................110
Источники ...........................................................................................................111
Глава 5. Сохранение информации в компьютерном поиске ......114
5.1. Основы ..........................................................................................................114
5.2. Что такое сохранение информации? ..........................................................116
5.2.1. Обманчивые контрпримеры ................................................................118
5.2.2. Взаимосвязь между обучением и поиском .........................................120
5.2.3. Человек в цикле, вносящий активную информацию .........................125
4.3. Потолок Бейснера ........................................................................................105
4.3.1. Tierra ......................................................................................................106
4.3.2. Край эволюции ......................................................................................109
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
Содержание 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
Глава 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
5.9. Заключение ...................................................................................................179
Источники ...........................................................................................................179
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
Стр.8
8 Содержание
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
Стр.9