Генетические алгоритмы на 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

 Содержание

Создание генетических операторов................................................................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

 Содержание

Часть 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