Генетические алгоритмы на Python. Применение генетических алгоритмов к решению задач глубокого обучения и искусственного интеллекта

Эйял Вирсански
Генетические алгоритмы  
на Python

Hands-On Genetic 
Algorithms with Python
Applying genetic algorithms to solve 
real-world deep learning and artificial 
intelligence problems
Eyal Wirsansky
BIRMINGHAM – MUMBAI

Генетические алгоритмы  
на Python
Применение генетических алгоритмов  
к решению задач глубокого обучения  
и искусственного интеллекта
Эйял Вирсански
Москва, 2020

УДК 004.421
ББК 32.811
В52
Вирсански Э.
В52 
Генетические алгоритмы на Python / пер. с англ. А. А. Слинкина. – М.: 
ДМК Пресс, 2020. – 286 с.: ил. 
ISBN 978-5-97060-857-9
Там, где традиционные алгоритмы бесполезны или не дают результата за обозримое время, на помощь могут прийти генетические алгоритмы. Они позволяют 
решить целый комплекс сложных задач, в том числе связанных с искусственным 
интеллектом, упростить оптимизацию непрерывных функций, выполнять реконструкцию изображений и многое другое.
Книга поможет программистам, специалистам по обработке данных и энтузиастам ИИ, интересующимся генетическими алгоритмами, подступиться к стоящим 
перед ними задачам, связанным с обучением, поиском и оптимизацией, а также 
повысить качество и точность результатов в уже имеющихся приложениях.
Для изучения материала книги требуются владение языком Python на рабочем 
уровне и базовые знания математики и информатики.
УДК  004.421
ББК  32.811
First published in the English language under the title ‘Hands-On Genetic Algorithms with 
Python’. Russian language edition copyright © 2020 by DMK Press. All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения 
владельцев авторских прав.
ISBN 978-1-83855-774-4 (англ.) 
Copyright © Packt Publishing, 2020
ISBN 978-5-97060-857-9 (рус.) 
©  Оформление, издание, перевод, 
ДМК Пресс, 2020

Моей любимой жене Джеки  
за любовь, терпение и поддержку 
Моим детям, Даниэлле и Лиарне,  
чья творческая натура и артистические таланты  
подвигли меня на написание этой книги

Содержание
Об авторе............................................................................................................13
О рецензенте.....................................................................................................14
Предисловие.....................................................................................................15
Часть I. ОСНОВЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ....................19
Глава 1. Введение в генетические алгоритмы....................................20
Что такое генетические алгоритмы?...................................................................20
Дарвиновская эволюция...................................................................................21
Аналогия с генетическими алгоритмами........................................................21
Генотип......................................................................................................22
Популяция.................................................................................................22
Функция приспособленности...................................................................23
Отбор..........................................................................................................23
Скрещивание.............................................................................................23
Мутация.....................................................................................................24
Теоретические основы генетических алгоритмов..............................................24
Теорема о схемах...............................................................................................25
Отличия от традиционных алгоритмов...............................................................26
Популяция как основа алгоритма....................................................................27
Генетическое представление............................................................................27
Функция приспособленности...........................................................................27
Вероятностное поведение................................................................................27
Преимущества генетических алгоритмов...........................................................28
Глобальная оптимизация..................................................................................28
Применимость к сложным задачам.................................................................29
Применимость к задачам, не имеющим математического  
представления...................................................................................................30
Устойчивость к шуму.........................................................................................30
Распараллеливание...........................................................................................30
Непрерывное обучение.....................................................................................31
Ограничения генетических алгоритмов.............................................................31
Специальные определения...............................................................................31
Настройка гиперпараметров............................................................................31
Большой объем счетных операций..................................................................32
Преждевременная сходимость.........................................................................32
Отсутствие гарантированного решения..........................................................32
Сценарии применения генетических алгоритмов.............................................32
Резюме...................................................................................................................33
Для дальнейшего чтения......................................................................................33

Содержание    7
Глава 2. Основные компоненты генетических алгоритмов...........34
Базовая структура генетического алгоритма......................................................34
Создание начальной популяции......................................................................36
Вычисление приспособленности.....................................................................36
Применение операторов отбора, скрещивания и мутации...........................36
Проверка условий остановки...........................................................................37
Методы отбора.......................................................................................................37
Правило рулетки................................................................................................38
Стохастическая универсальная выборка.........................................................39
Ранжированный отбор......................................................................................40
Масштабирование приспособленности...........................................................41
Турнирный отбор..............................................................................................42
Методы скрещивания...........................................................................................43
Одноточечное скрещивание.............................................................................43
Двухточечное и k-точечное скрещивание.......................................................44
Равномерное скрещивание..............................................................................45
Скрещивание для упорядоченных списков....................................................45
Упорядоченное скрещивание...................................................................46
Методы мутации...................................................................................................47
Инвертирование бита.......................................................................................48
Мутация обменом.............................................................................................48
Мутация обращением.......................................................................................48
Мутация перетасовкой......................................................................................49
Генетические алгоритмы с вещественным кодированием................................49
Скрещивание смешением................................................................................50
Имитация двоичного скрещивания.................................................................51
Вещественная мутация.....................................................................................53
Элитизм..................................................................................................................53
Образование ниш и разделение...........................................................................54
Последовательное и параллельное образование ниш....................................56
Искусство решения задач с помощью генетических алгоритмов.....................57
Резюме...................................................................................................................58
Для дальнейшего чтения......................................................................................58
Часть  II. РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ  
ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ..........................................................59
Глава 3. Каркас DEAP.....................................................................................60
Технические требования.......................................................................................60
Введение в DEAP....................................................................................................61
Использование модуля creator.............................................................................62
Создание класса Fitness....................................................................................62
Определение стратегии приспособления................................................62
Хранение значения приспособленности.................................................63
Создание класса Individual...............................................................................64
Использование класса Toolbox.............................................................................64

8    Содержание
Создание генетических операторов................................................................65
Создание популяции.........................................................................................66
Вычисление приспособленности.....................................................................66
Задача OneMax.......................................................................................................67
Решение задачи OneMax с помощью DEAP.........................................................67
Выбор хромосомы.............................................................................................67
Вычисление приспособленности.....................................................................68
Выбор генетических операторов.....................................................................68
Задание условия остановки..............................................................................68
Реализация средствами DEAP..........................................................................69
Подготовка.................................................................................................69
Эволюция решения...................................................................................72
Выполнение программы...........................................................................75
Использование встроенных алгоритмов.............................................................76
Объект Statistics.................................................................................................77
Алгоритм............................................................................................................77
Объект logbook...................................................................................................77
Выполнение программы...................................................................................78
Зал славы............................................................................................................79
Эксперименты с параметрами алгоритма..........................................................81
Размер популяции и количество поколений...................................................81
Оператор скрещивания....................................................................................83
Оператор мутации............................................................................................84
Оператор отбора................................................................................................87
Размер турнира и его связь с вероятностью мутации............................88
Отбор по правилу рулетки........................................................................92
Резюме...................................................................................................................93
Для дальнейшего чтения......................................................................................94
Глава 4. Комбинаторная оптимизация...................................................95
Технические требования.......................................................................................95
Поисковые задачи и комбинаторная оптимизация...........................................96
Решение задачи о рюкзаке...................................................................................96
Задача о рюкзаке 0-1 с сайта Rosetta Code......................................................97
Представление решения...................................................................................98
Представление задачи на Python.....................................................................98
Решение с помощью генетического алгоритма..............................................99
Решение задачи коммивояжера.........................................................................102
Файлы эталонных данных TSPLIB..................................................................103
Представление решения.................................................................................104
Представление задачи на Python...................................................................104
Решение с помощью генетического алгоритма............................................106
Улучшение результатов благодаря дополнительному исследованию  
и элитизму.......................................................................................................109
Решение задачи о маршрутизации транспорта................................................114
Представление решения.................................................................................115
Представление задачи на Python...................................................................116

Содержание    9
Решение с помощью генетического алгоритма............................................118
Резюме.................................................................................................................122
Для дальнейшего чтения....................................................................................123
Глава 5. Задачи с ограничениями...........................................................124
Технические требования.....................................................................................124
Соблюдение ограничений в поисковых задачах...........................................125
Решение задачи об N ферзях..............................................................................125
Представление решения.................................................................................126
Представление задачи на Python...................................................................128
Решение с помощью генетического алгоритма............................................129
Решение задачи о составлении графика дежурств медсестер.........................133
Представление решения.................................................................................133
Жесткие и мягкие ограничения.....................................................................134
Представление задачи на Python...................................................................135
Решение на основе генетического алгоритма..............................................137
Решение задачи о раскраске графа....................................................................140
Представление решения.................................................................................142
Жесткие и мягкие ограничения в задаче о раскраске графа.......................143
Представление задачи на Python...................................................................143
Решение с помощью генетического алгоритма............................................145
Резюме.................................................................................................................149
Для дальнейшего чтения....................................................................................150
Глава 6. Оптимизация непрерывных функций.................................151
Технические требования.....................................................................................151
Хромосомы и генетические операторы для задач с вещественными  
числами................................................................................................................152
Использование DEAP совместно с непрерывными функциями......................153
Оптимизация функции Eggholder......................................................................154
Оптимизация функции Eggholder с помощью генетического  
алгоритма........................................................................................................155
Повышение скорости сходимости посредством увеличения частоты  
мутаций............................................................................................................158
Оптимизация функции Химмельблау...............................................................159
Оптимизация функции Химмельблау с помощью генетического  
алгоритма........................................................................................................161
Использование ниш и разделения для отыскания нескольких  
решений...........................................................................................................165
Функция Симионеску и условная оптимизация...............................................168
Условная оптимизация с помощью генетического алгоритма....................170
Оптимизация функции Симионеску с помощью генетического  
алгоритма........................................................................................................171
Использование ограничений для нахождения нескольких решений.........172
Резюме.................................................................................................................173
Для дальнейшего чтения....................................................................................173

10    Содержание
Часть III. ПРИЛОЖЕНИЯ ГЕНЕТИЧЕСКИХ  
АЛГОРИТМОВ В ИСКУССТВЕННОМ ИНТЕЛЛЕКТЕ...............174
Глава 7. Дополнение моделей машинного обучения  
методами выделения признаков...........................................................175
Технические требования.....................................................................................176
Машинное обучение с учителем........................................................................176
Классификация................................................................................................177
Регрессия..........................................................................................................179
Алгоритмы обучения с учителем...................................................................180
Выделение признаков в обучении с учителем..................................................180
Выделение признаков для задачи регрессии Фридмана-1..............................181
Представление решения.................................................................................182
Представление решения на Python................................................................182
Решение с помощью генетического алгоритма............................................184
Выделение признаков для классификации набора данных Zoo......................186
Представление задачи на Python...................................................................187
Решение с помощью генетического алгоритма............................................189
Резюме.................................................................................................................191
Для дальнейшего чтения....................................................................................191
Глава 8. Настройка гиперпараметров моделей  
машинного обучения...................................................................................192
Технические требования.....................................................................................193
Гиперпараметры в машинном обучении..........................................................193
Настройка гиперпараметров..........................................................................194
Набор данных Wine.........................................................................................195
Классификатор на основе адаптивного усиления........................................195
Настройка гиперпараметров с помощью генетического поиска на сетке......196
Тестирование качества классификатора с параметрами по умолчанию.....198
Результаты традиционного поиска на сетке.................................................198
Результаты генетического поиска на сетке...................................................198
Прямой генетический подход к настройке гиперпараметров.........................199
Представление гиперпараметров..................................................................200
Оценка верности классификатора.................................................................200
Настройка гиперпараметров с помощью генетического алгоритма..........201
Резюме.................................................................................................................204
Для дальнейшего чтения....................................................................................204
Глава 9. Оптимизация архитектуры сетей глубокого  
обучения...........................................................................................................205
Технические требования.....................................................................................205
Искусственные нейронные сети и глубокое обучение.....................................206
Многослойный перцептрон............................................................................207
Глубокое обучение и сверточные нейронные сети.......................................208