Генетические алгоритмы на Python (5000,00 руб.)

Стр.5

Стр.7

Стр.8

Стр.9

Стр.10

Стр.11

Стр.12

Стр.13

УДК 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 (англ.) ISBN 978-5-97060-857-9 (рус.) Copyright © Packt Publishing, 2020 © Оформление, издание, перевод, ДМК Пресс, 2020

Стр.5

Содержание Об авторе ...........................................................................................................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

Содержание  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

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

Содержание  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 Глава 6. Оптимизация непрерывных функций ................................151 Технические требования ....................................................................................151 Хромосомы и генетические операторы для задач с вещественными числами ...............................................................................................................152 Использование DEAP совместно с непрерывными функциями .....................153 Оптимизация функции Eggholder .....................................................................154 Оптимизация функции Eggholder с помощью генетического алгоритма ........................................................................................................155 Повышение скорости сходимости посредством увеличения частоты мутаций ...........................................................................................................158 Оптимизация функции Химмельблау ..............................................................159 Оптимизация функции Химмельблау с помощью генетического алгоритма ........................................................................................................161 Использование ниш и разделения для отыскания нескольких решений ..........................................................................................................165 Функция Симионеску и условная оптимизация ..............................................168 Условная оптимизация с помощью генетического алгоритма ...................170 Оптимизация функции Симионеску с помощью генетического алгоритма ........................................................................................................171 Использование ограничений для нахождения нескольких решений ........172 Резюме .................................................................................................................173 Для дальнейшего чтения ....................................................................................173 Резюме .................................................................................................................149 Для дальнейшего чтения ....................................................................................150

Стр.10

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 Глава 9. Оптимизация архитектуры сетей глубокого Резюме .................................................................................................................204 Для дальнейшего чтения ....................................................................................204 обучения ..........................................................................................................205 Технические требования ....................................................................................205 Искусственные нейронные сети и глубокое обучение ....................................206 Многослойный перцептрон ...........................................................................207 Глубокое обучение и сверточные нейронные сети ......................................208

Стр.11

Содержание  11 Оптимизация архитектуры классификатора на основе глубокой сети ..........209 Набор данных Iris ...........................................................................................209 Представление конфигурации скрытого слоя ..............................................210 Оценка верности классификатора ................................................................211 Оптимизация архитектуры МСП с помощью генетического алгоритма ........................................................................................................212 Объединение оптимизации архитектуры с настройкой гиперпараметров ................................................................................................215 Представление решения ................................................................................215 Вычисление верности классификатора ........................................................216 Оптимизация объединенной конфигурации МСП с помощью генетического алгоритма ...............................................................................217 Глава 10. Генетические алгоритмы и обучение Резюме .................................................................................................................218 Для дальнейшего чтения ....................................................................................218 с подкреплением ..........................................................................................219 Технические требования ....................................................................................219 Обучение с подкреплением ...............................................................................220 Генетические алгоритмы и обучение с подкреплением .............................221 OpenAI Gym .........................................................................................................221 Интерфейс env ................................................................................................222 Решение окружающей среды MountainCar .......................................................223 Представление решения ................................................................................225 Оценивание решения .....................................................................................225 Представление задачи на Python ..................................................................226 Решение с помощью генетического алгоритма ...........................................226 Решение окружающей среды CartPole ..............................................................229 Управление средой CartPole с помощью нейронной сети ...........................230 Представление и оценивание решения ........................................................231 Представление задачи на Python ..................................................................232 Решение с помощью генетического алгоритма ...........................................233 Резюме .................................................................................................................236 Для дальнейшего чтения ....................................................................................237 Часть IV. РОДСТВЕННЫЕ ТЕХНОЛОГИИ .......................................238 Глава 11. Генетическая реконструкция изображений ...................239 Технические требования ....................................................................................239 Реконструкция изображений из многоугольников ..........................................240 Обработка изображений на Python ...................................................................240 Библиотеки обработки изображений на Python ..........................................240 Библиотека Pillow ...................................................................................241 Библиотека scikit-image .........................................................................241 Библиотека opencv-python .....................................................................241 Рисование с помощью многоугольников .....................................................242

Стр.12

12  Содержание Измерение степени различия двух изображений ........................................243 Попиксельная среднеквадратическая ошибка .....................................243 Структурное сходство (SSIM) .................................................................244 Применение генетических алгоритмов для реконструкции изображений .......................................................................................................244 Представление и оценивание решения ........................................................245 Представление задачи на Python ..................................................................246 Реализация генетического алгоритма ..........................................................246 Добавление функции обратного вызова в код генетического алгоритма ................................................................................................249 Результаты реконструкции изображения .....................................................250 Применение попиксельной среднеквадратической ошибки ..............251 Применение индекса структурного сходства .......................................253 Другие эксперименты ............................................................................256 Резюме .................................................................................................................257 Для дальнейшего чтения ....................................................................................258 Глава 12. Другие эволюционные и бионические методы вычислений .....................................................................................................259 Технические требования ....................................................................................259 Эволюционные и бионические вычисления ....................................................260 Генетическое программирование .....................................................................260 Пример генетического программирования – контроль по четности .........262 Реализация с помощью генетического программирования .......................264 Упрощение решения ..............................................................................269 Оптимизация методом роя частиц ...................................................................271 Пример применения PSO – оптимизация функции ....................................272 Реализация оптимизации методом роя частиц ...........................................273 Другие родственные методы .............................................................................277 Эволюционные стратегии ..............................................................................277 Дифференциальная эволюция ......................................................................278 Муравьиный алгоритм оптимизации ...........................................................278 Искусственные иммунные системы ..............................................................278 Искусственная жизнь .....................................................................................279 Предметный указатель ..............................................................................281 Резюме .................................................................................................................279 Для дальнейшего чтения ....................................................................................280

Стр.13