КулЛиб электронная библиотека
Всего книг - 570390 томов
Объем библиотеки - 849 Гб.
Всего авторов - 229123
Пользователей - 105731

Впечатления

zaraza2 про Chigis: Замерзшее блюдо (Детективная фантастика)

Хорошая книга, жаль коротка. Автор молодец!

Рейтинг: +1 ( 1 за, 0 против).
Stribog73 про Хоменко: Справочник по теплозащите зданий (Справочники)

Уважаемые читатели! Качайте научно-техническую литературу именно у нас. У нас самое лучшее качество книг. Я лично очень много работаю над этим вопросом.
Надеюсь, пройдет совсем немного времени и мы станем одной из ведущих библиотек по научно-технической литературе. И хоть и не по количеству, но по качеству книг мы даем другим библиотекам большую фору.

Рейтинг: +5 ( 5 за, 0 против).
Arikchess про Веселовский: Введение в генетику (Биология)

Генетика, лженаука?

Рейтинг: 0 ( 0 за, 0 против).
SubMarinka про Эппле: Неудобное прошлое. Память о государственных преступлениях в России и других странах (Публицистика)

Печальный вывод из этой книги — мы живём в "стране невыученных уроков"... Обратите внимание, что книга издана в 2020 г., то есть написана ещё раньше!
Тем, кто заинтересуется этим историко-философским произведением, очень рекомендую посмотреть интервью Николая Эппле на канале "Скажи Гордеевой"
https://youtu.be/T7UEcXDZiWU

Рейтинг: +2 ( 2 за, 0 против).
Stribog73 про Слюсарев: Биология с общей генетикой (Биология)

В книге отсутствуют 4 страницы.

Рейтинг: +2 ( 2 за, 0 против).
Stribog73 про Веселовский: Введение в генетику (Биология)

Как видите, уважаемые мухолюбы-человеконенавистники, я и о вас не забываю. Книги по вашей лженауке у меня еще есть и я буду продолжать их периодически выкладывать.
Качайте и изучайте.

2 Arikchess
Да я же шучу. Вы что - шутку юмора не понимаете?

- Вот приедет Сталин,
Сталин нас рассудит.
Почти Некрасов

Рейтинг: +2 ( 2 за, 0 против).
Stribog73 про Асланян: Большой практикум по генетике животных и растений (Биология)

И еще одну книгу для мухолюбов-человеконенавистников выкладываю.

Рейтинг: +2 ( 2 за, 0 против).

Генетические алгоритмы на Python [Эйял Вирсански] (pdf) читать онлайн

-  Генетические алгоритмы на Python  (пер. А. А. Слинкин) 9.3 Мб (скачать pdf) (скачать pdf+fbd)  (читать)  (читать постранично) - Эйял Вирсански

Книга в формате pdf! Изображения и текст могут не отображаться!


Настройки текста:



После обзора генетических алгоритмов и описания принципов автор рассказывает об их отличиях от традиционных алгоритмов и о типах задач, к которым
они применимы, как то: планирование, составление расписаний, игры и анализ функций. Вы также узнаете о том, как генетические алгоритмы позволяют
повысить качество моделей машинного и глубокого обучения, решать задачи
обучения с подкреплением и выполнять реконструкцию изображений. Наконец,
будет упомянуто о некоторых родственных технологиях, открывающих новые
возможности для будущих приложений.

Краткое содержание книги:
• применение современных средств на языке Python к созданию генетических алгоритмов;
• использование генетических алгоритмов для оптимизации функций
и решения задач планирования и составления расписаний;
• повышение качества моделей машинного обучения и оптимизация
архитектуры сети глубокого обучения;
• применение генетических алгоритмов к задачам обучения с подкреплением с использованием библиотеки OpenAI Gym;
• реконструкция изображений с помощью набора полупрозрачных
фигур;
• другие бионические методы, в т. ч. генетическое программирование
и оптимизация методом роя частиц.
Книга адресована программистам, специалистам по обработке данных и энтузиастам ИИ, желающим применить генетические алгоритмы в решении
практических задач. Требуются владение языком Python на рабочем уровне и
базовые знания математики и информатики.
ISBN 978-5-97060-857-9

Интернет-магазин:
www.dmkpress.com
Оптовая продажа:
КТК “Галактика”
books@alians-kniga.ru

www.дмк.рф

9 785970 608579

Эйял Вирсански

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

Генетические алгоритмы — это семейство алгоритмов поиска, оптимизации и
обучения, черпающее идеи из естественной эволюции. Благодаря имитации
эволюционных процессов генетические алгоритмы способы преодолевать
трудности, присущие традиционным алгоритмам поиска, и находить высококачественные решения в самых разных задачах. Эта книга поможет освоить мощный, но в то же время простой подход к применению генетических алгоритмов,
написанных на языке Python, и познакомиться с последними достижениями в
области искусственного интеллекта.

Генетические
алгоритмы
на 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 (англ.)
ISBN 978-5-97060-857-9 (рус.)

Copyright © Packt Publishing, 2020
© Оформление, издание, перевод,
ДМК Пресс, 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

Содержание  11

Оптимизация архитектуры классификатора на основе глубокой сети...........209
Набор данных Iris............................................................................................209
Представление конфигурации скрытого слоя...............................................210
Оценка верности классификатора.................................................................211
Оптимизация архитектуры МСП с помощью генетического
алгоритма.........................................................................................................212
Объединение оптимизации архитектуры с настройкой
гиперпараметров.................................................................................................215
Представление решения.................................................................................215
Вычисление верности классификатора.........................................................216
Оптимизация объединенной конфигурации МСП с помощью
генетического алгоритма................................................................................217
Резюме..................................................................................................................218
Для дальнейшего чтения.....................................................................................218

Глава 10. Генетические алгоритмы и обучение
с подкреплением...........................................................................................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  Содержание
Измерение степени различия двух изображений.........................................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
Резюме..................................................................................................................279
Для дальнейшего чтения.....................................................................................280

Предметный указатель...............................................................................281

Об авторе
Эйял Вирсански – старший инженер-программист, лидер технического
сообщества, исследователь и энтузиаст искусственного интеллекта. Начал
карье­ру как один из первопроходцев в области передачи голоса по IP-сетям
и теперь может похвастаться более чем 20-летним опытом создания самых
разных высокопроизводительных корпоративных решений. Еще будучи
студентом, проявил интерес к генетическим алгоритмам и нейронным сетям. Одним из результатов его исследований стал новый алгоритм обучения
с учителем, объединяющий достоинства обоих подходов.
Эйял возглавляет группу пользователей Java в Джексонвилле, а также виртуальную группу пользователей по теме «Искусственный интеллект в корпоративных приложениях» и ведет блог по искусственному интеллекту ai4java,
ориентированный на разработчиков.
Я хочу поблагодарить свою семью и близких друзей за терпение, поддержку
и ободрение на протяжении длительного процесса написания книги. Отдельное спасибо группе пользователей Python в Джексонвилле (PyJax) за
отзывы и поддержку.

О рецензенте
Лайза Бэнг окончила бакалавриат по биологии моря в Калифорнийском
университете в Санта-Крус и магистратуру по биоинформатике в Сеульском
университете Сонсиль под руководством д-ра Кван Хви Чо. Магистерская
диссертация была посвящена методу создания воспроизводимых моделей
QSAR (поиск количественных соотношений структура–свойство) с применением блокнота Jupyter, одним из компонентов которого был генетический
алгоритм, позволяющий уменьшить пространство поиска. В настоящее время ведется работа по его переводу на каркас DEAP-VS для совместимости
с Python 3. Она также работала в системе здравоохранения Гейсингера, входящей в состав Института биомедицинской и трансляционной информатики,
где применяла данные следующего поколения о секвенировании и электронные медицинские карты пациентов для анализа исходов раковых и других
заболеваний. Сейчас работает в компании Ultragenyx Pharmaceutical, где занимается доклиническими испытаниями и использует методы биоинформатики и хемоинформатики для анализа редких наследственных болезней.
Спасибо моей семье, учителям и наставникам!

Предисловие
Берущие начало в эволюционной теории Дарвина, генетические алгоритмы
являются одним из самых удивительных методов решения задач поиска,
оптимизации и обучения. Они могут привести к успеху там, где традиционные алгоритмы не способны дать адекватные результаты за приемлемое
время.
Данная книга покажет вам путь к овладению этим чрезвычайно мощным
и вместе с тем простым подходом к разнообразным задачам, венцом которых станут приложения ИИ.
Вы узнаете, как работают генетические алгоритмы и когда имеет смысл их
использовать. А заодно получите практический опыт их применения в разных областях с по­мощью популярного языка программирования Python.

Предполагаемая аудитория
Эта книга призвана помочь программистам, специалистам по обработке
данных и энтузиастам ИИ, интересующимся генетическими алгоритмами,
подступиться к стоящим перед ними задачам, связанным с обучением, поиском и оптимизацией, а также повысить качество и точность результатов
в уже имеющихся приложениях.
Книга адресована также всем, кто сталкивался в своей практике с трудными задачами, в которых традиционные алгоритмы вообще бесполезны
или не дают результата за обозримое время. Показано, как использовать
генетические алгоритмы в качестве эффективного и в то же время простого
подхода к решению сложных задач.

Структура книги
В главе 1 «Введение в генетические алгоритмы» приводится краткое введение в теорию и принципы работы генетических алгоритмов. Рассматриваются также различия между генетическими алгоритмами и традиционными
методами, и описываются сценарии, в которых имеет смысл применять генетические алгоритмы.
В главе 2 «Основные компоненты генетических алгоритмов» более глубоко описываются основные компоненты и детали реализации генетических
алгоритмов. Познакомившись с потоком управления, вы затем узнаете о различных компонентах и их реализациях.
В главе 3 «Каркас DEAP» дается введение в DEAP – мощный и гибкий каркас эволюционных вычислений, позволяющий решать практические задачи
с по­мощью генетических алгоритмов. Мы продемонстрируем его использо-

16  Предисловие
вание на примере программы на Python, которая решает задачу OneMax –
что-то вроде «Hello World» в мире генетических алгоритмов.
В главе 4 «Комбинаторная оптимизация» рассматриваются такие проблемы, как упаковка рюкзака, задача коммивояжера и задача маршрутизации
транспорта, а также программы на Python для их решения с по­мощью генетических алгоритмов и каркаса DEAP.
Глава 5 «Задачи с ограничениями» представляет собой введение в задачи
с ограничениями, например: задача об N ферзях, составление графика дежурства медсестер, задача о раскраске графа. Объясняется, как решить их на
Python с по­мощью генетических алгоритмов и каркаса DEAP.
В главе 6 «Оптимизация непрерывных функций» обсуждаются задачи непрерывной оптимизации и их решения с по­мощью генетических алгоритмов. В качестве примеров приводятся функция Eggholder, функции Химмельблау и Симионеску. Попутно мы изучим концепции образования ниш,
разделения и обработки ограничений.
В главе 7 «Дополнение моделей машинного обучения методами выделения
признаков» речь пойдет о моделях машинного обучения с учителем. Объясняется, как генетические алгоритмы позволяют повысить качество этих
моделей за счет выделения наилучшего подмножества признаков из представленных входных данных.
В главе 8 «Настройка гиперпараметров моделей машинного обучения»
показано, как использовать генетические алгоритмы для улучшения качест­
ва моделей машинного обучения с учителем путем применения поиска на
сетке, управляемого генетическим алгоритмом, или прямого генетического
поиска.
В главе 9 «Оптимизация архитектуры сетей глубокого обучения» рассмат­
риваются искусственные нейронные сети и описывается, как генетические
алгоритмы позволяют улучшить модель, основанную на нейронной сети,
путем оптимизации архитектуры последней. Вы узнаете, как сочетать оптимизацию архитектуры сети с настройкой гиперпараметров.
Глава 10 «Генетические алгоритмы и обучение с подкреплением» посвящена обучению с подкреплением. Применение генетических алгоритмов
иллюстрируется на примере двух тестовых окружающих сред – MountainCar
(машина на горе) и CartPole (балансировка стержня) – из библиотеки OpenAI
Gym.
В главе 11 «Генетическая реконструкция изображений» описываются
эксперименты по реконструкции одного хорошо известного изображения
с по­мощью множества полупрозрачных многоугольников на основе генетических алгоритмов. Попутно вы приобретете полезный опыт обработки
изображений и научитесь работать с соответствующими библиотеками на
Python.
Глава 12 «Другие эволюционные и бионические методы вычислений»
расширяет горизонты и знакомит еще с несколькими пришедшими из биологии приемами решения задач. Два из них – генетическое программирование и метод роя частиц – будут реализованы с по­мощью Python и каркаса
DEAP.

Обозначения и графические выделения  17

Что необходимо для чтения этой книги
Чтобы получить максимум пользы от чтения книги, необходимо владеть
языком Python на рабочем уровне и иметь базовые знания по математике
и информатике. Знакомство с фундаментальными понятиями машинного обучения желательно, но не обязательно, поскольку в книге приводится
крат­кое изложение всего необходимого.
Для выполнения приведенных в книге примеров понадобится версия 3.7
или более поздняя, а также несколько Python-пакетов (все они здесь же
и описываются). Рекомендуется, хотя это и необязательно, установить какую-нибудь интегрированную среду разработки на Python (IDE), например
PyCharm или Visual Studio Code.

Скачивание исходного кода
Скачать файлы с дополнительной информацией для книг издательства «ДМК
Пресс» можно на сайте www.dmkpress.com на странице с описанием соответст­
вую­щей книги.

Обозначения и графические выделения
В этой книге применяется ряд соглашений о наборе текста.
CodeInText: код в тексте, имена таблиц базы данных, папок и файлов, расширения имен файлов, пути к файлам, URL-адреса, данные, вводимые пользователем, и адреса в Твиттере. Например: «Метод класса __init__() создает
набор данных».
Отдельно стоящие фрагменты кода набраны так:
self.X, self.y = datasets.make_friedman1(n_samples=self.numSamples,
n_features=self.numFeatures,
noise=self.NOISE,
random_state=self.randomSeed)

Желая привлечь внимание к какой-то части кода, мы выделяем ее полужирным шрифтом, например:
self.regressor = GradientBoostingRegressor(random_state=self.randomSeed)

Команды операционной системы и результаты их работы выделяются так:
pip install deap

Полужирный: новые термины и важные слова, а также части пользовательского интерфейса. Так выделяются команды меню и текст в диалоговых
окнах, например: «Выберите команду System info на панели Administration».

18  Предисловие
Предупреждения и важные замечания выглядят так.
Советы и рекомендации выглядят так.

Отзывы и пожелания
Мы всегда рады отзывам наших читателей. Расскажите нам, что вы думаете
об этой книге – что понравилось или, может быть, не понравилось. Отзывы
важны для нас, чтобы выпускать книги, которые будут для вас максимально
полезны.
Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на
страницу книги и оставив комментарий в разделе «Отзывы и рецензии». Также можно послать письмо главному редактору по адресу dmkpress@gmail.com;
при этом укажите название книги в теме письма.
Если вы являетесь экспертом в какой-либо области и заинтересованы в написании новой книги, заполните форму на нашем сайте по адресу http://
dmkpress.com/authors/publish_book/ или напишите в издательство по адресу
dmkpress@gmail.com.

Список опечаток
Хотя мы приняли все возможные меры для того, чтобы обеспечить высокое
качество наших текстов, ошибки все равно случаются. Если вы найдете ошибку
в одной из наших книг – возможно, ошибку в основном тексте или программном коде, – мы будем очень благодарны, если вы сообщите нам о ней. Сделав
это, вы избавите других читателей от недопонимания и поможете нам улучшить последующие издания этой книги.
Если вы найдете какие-либо ошибки в коде, пожалуйста, сообщите о них
главному редактору по адресу dmkpress@gmail.com, и мы исправим это в следующих тиражах.

Нарушение авторских прав
Пиратство в интернете по-прежнему остается насущной проблемой. Издательства «ДМК Пресс» и Packt очень серьезно относятся к вопросам защиты
авторских прав и лицензирования. Если вы столкнетесь в интернете с незаконной публикацией какой-либо из наших книг, пожалуйста, пришлите нам
ссылку на интернет-ресурс, чтобы мы могли применить санкции.
Ссылку на подозрительные материалы можно прислать по адресу элект­
ронной почты dmkpress@gmail.com.
Мы высоко ценим любую помощь по защите наших авторов, благодаря
которой мы можем предоставлять вам качественные материалы.

ЧАСТЬ

I
ОСНОВЫ
ГЕНЕТИЧЕСКИХ
АЛГОРИТМОВ

В этой части мы познакомимся с основными концепциями
генетических алгоритмов и способами их применения

Глава

1
Введение
в генетические
алгоритмы

Позаимствовавший идею у теории эволюции Чарльза Дарвина, один из самых удивительных методов решения задач заслуженно получил название
«эволюционные вычисления». Самыми известными и широко распространенными представителями этого семейства являются генетические
алгоритмы. В этой главе мы начнем путешествие в мир этих чрезвычайно
мощных и вместе с тем очень простых методов.
Мы познакомимся с генетическими алгоритмами, проведем аналогию
между ними и дарвиновской эволюцией и опишем как теорию, так и базовые
принципы их работы. Затем поговорим о различиях между генетическими
и традиционными алгоритмами, раскроем их преимущества и ограничения,
опишем области применения. И завершим примерами задач, в которых генетические алгоритмы могут оказаться полезными.
В этой вводной главе рассматриваются следующие вопросы:
  что такое генетические алгоритмы;
  теоретические основы генетических алгоритмов;
  различия между генетическими и традиционными алгоритмами;
  преимущества и ограничения генетических алгоритмов;
  когда имеет смысл использовать генетические алгоритмы.

Что такое генетические алгоритмы?
Генетические алгоритмы – это семейство поисковых алгоритмов, идеи которых подсказаны принципами эволюции в природе. Имитируя процессы ес­
тественного отбора и воспроизводства, генетические алгоритмы могут находить высококачественные решения задач, включающих поиск, оптимизацию
и обучение. В то же время аналогия с естественным отбором позволяет этим
алгоритмам преодолевать некоторые препятствия, встающие на пути тради-

Что такое генетические алгоритмы?  21

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

Дарвиновская эволюция
Генетические алгоритмы реализуют упрощенный вариант дарвиновской эволюции. Ниже перечислены принципы эволюционной теории Дарвина.
  Изменчивость. Признаки (атрибуты) отдельных особей, входящих
в состав популяции, могут изменяться. Поэтому особи отличаются друг
от друга, например по внешнему виду или поведению.
  Наследственность. Некоторые свойства устойчиво передаются от особи к ее потомкам. Поэтому потомки похожи на своих родителей больше, чем на других особей, не связанных с ними родством.
  Естественный отбор. Обычно популяции борются за ресурсы, имеющиеся в окружающей их среде. Особи, обладающие свойствами, лучше
приспособленными к окружающей среде, более успешны в борьбе за
выживание и привносят больше потомков в следующее поколение.
Иными словами, эволюция сохраняет популяцию особей, отличающихся друг от друга. Те, кто лучше приспособлен к окружающей среде, имеют
больше шансов на выживание, размножение и передачу своих признаков
следующему поколению. Так популяция от поколения к поколению становится все более приспособленной к окружающей среде и встающим на ее
пути трудностям.
Важным механизмом эволюции является скрещивание, или рекомбинация, – когда потомок приобретает комбинацию признаков своих родителей.
Скрещивание помогает поддерживать разнообразие популяции и со временем закреплять лучшие признаки. Кроме того, важную роль в эволюции
играют мутации – случайные вариации признаков, – поскольку они вносят
изменения, благодаря которым популяция время от времени совершает скачок в развитии.

Аналогия с генетическими алгоритмами
Цель генетических алгоритмов – найти оптимальное решение некоторой задачи. Если дарвиновская эволюция развивает популяцию отдельных особей,
то генетические алгоритмы развивают популяцию потенциальных решений данной задачи, называемых индивидуумами. Эти решения итеративно
оцениваются и используются для создания нового поколения решений. Те,
что лучше проявили себя при решении задачи, имеют больше шансов пройти
отбор и передать свои качества следующему поколению. Так постепенно потенциальные решения совершенствуются в решении поставленной задачи.
В следующих разделах описываются различные компоненты генетических
алгоритмов, поддерживающие эту аналогию с дарвиновской эволюцией.

22  Введение в генетические алгоритмы

Генотип
В природе скрещивание, воспроизводство и мутация реализуются посредством генотипа – набора генов, сгруппированных в хромосомы. Когда две
особи скрещиваются и производят потомство, каждая хромосома потомка
несет комбинацию генов родителей.
В случае генетических алгоритмов каждому индивидууму соответствует хромосома, представляющая набор генов. Например, хромосому можно
представить двоичной строкой, в которой каждый бит соответствует одному
гену:

Простое двоичное кодирование хромосомы

На рисунке выше показан пример такой двоично-кодированной хромосомы, представляющей одного индивидуума.

Популяция
В любой момент времени генетический алгоритм хранит популяцию индивидуумов – набор потенциальных решений поставленной задачи. Поскольку
каждый индивидуум представлен некоторой хромосомой, эту популяцию
можно рассматривать как коллекцию хромосом:

Популяция индивидуумов,
представленных двоично-кодированными хромосомами

Популяция всегда представляет текущее поколение и эволюционирует со
временем, когда текущее поколение заменяется новым.

Что такое генетические алгоритмы?  23

Функция приспособленности
На каждой итерации алгоритма индивидуумы оцениваются с по­мощью
функции приспособленности (или целевой функции). Это функция, которую мы стремимся оптимизировать, или задача, которую пытаемся решить.
Индивидуумы, для которых функция приспособленности дает наилучшую
оценку, представляют лучшие решения и с большей вероятностью будут отобраны для воспроизводства и представлены в следующем поколении. Со
временем качество решений повышается, значения функции приспособленности растут, а когда будет найдено удовлетворительное значение, процесс
можно остановить.

Отбор
После того как вычислены приспособленности всех индивидуумов в популяции, начинается процесс отбора, который определяет, какие индивидуумы
будут оставлены для воспроизводства, т. е. создания потомков, образующих
следующее поколение.
Процесс отбора основан на оценке приспособленности индивидуумов. Те,
чья оценка выше, имеют больше шансов передать свой генетический материал следующему поколению.
Плохо приспособленные индивидуумы все равно могут быть отобраны,
но с меньшей вероятностью. Таким образом, их генетический материал не
полностью исключен.

Скрещивание
Для создания пары новых индивидуумов родители обычно выбираются из
текущего поколения, а части их хромосом меняются местами (скрещиваются), в результате чего создаются две новые хромосомы, представляющие
потомков. Эта операция называется скрещиванием, или рекомбинацией.

Операция скрещивания двух двоично-кодированных хромосом
Источник: https://commons.wikimedia.org/wiki/File:Computational.science.Genetic.
algorithm.Crossover.One.Point.svg.Image, автор Yearofthedragon.
Публикуется по лицензии Creative Commons CC BY-SA 3.0:
https://creativecommons.org/licenses/by-sa/3.0/deed.en

24  Введение в генетические алгоритмы
На рисунке выше показана операция скрещивания с созданием двух потомков родителей.

Мутация
Цель оператора мутации – периодически случайным образом обновлять популяцию, т. е. вносить новые сочетания генов в хромосомы, стимулируя тем
самым поиск в неисследованных областях пространства решений.
Мутация может проявляться как случайное изменение гена. Мутации реализуются с по­мощью внесения случайных изменений в значения хромосом,
например инвертирования одного бита в двоичной строке.

Применение оператора мутации
к двоично-кодированной хромосоме

На рисунке выше приведен пример операции мутации.
Далее мы рассмотрим теорию, стоящую за генетическими алгоритмами.

Теоретические основы
генетических алгоритмов
Гипотеза структурных элементов, лежащая в основе генетических алгоритмов, заключается в том, что оптимальное решение задачи может быть собрано из небольших структурных элементов, и чем их больше, тем ближе мы
подходим к оптимальному решению.
Индивидуумам, которые содержат некоторые из желательных структурных элементов, назначается более высокая оценка. Повторные операции
отбора и скрещивания приводят к появлению все лучших индивидуумов,
передающих эти структурные элементы следующему поколению, возможно,
в сочетании с другими успешными структурными элементами. Тем самым
создается генетическое давление, направляющее популяцию в сторону появления все большего числа индивидуумов, обладающих структурными элементами, образующими оптимальное решение.
В результате каждое поколение оказывается лучше предыдущего и содержит больше индивидуумов, близких к оптимальному решению.

Теоретические основы генетических алгоритмов  25

Например, если имеется популяция четырехзначных двоичных строк
и требуется найти строки с максимальной суммой цифр, то цифра 1 в любой
из четырех позиций является хорошим структурным элементом. В процессе
работы алгоритм будет определять решения, содержащие такие структурные
элементы, и объединять их. В каждом поколении будет больше индивидуумов, содержащих 1 в различных позициях, а в конечном итоге получится
строка 1111, объединяющая все четыре желательных структурных элемента.
Это показано на рисунке ниже.

Демонстрация операции скрещивания –
структурные элементы оптимального решения собираются вместе

Здесь мы видим, как два индивидуума, представляющих хорошие решения
задачи (в каждом три бита равны 1), порождают потомка, дающего наилучшее решение (четыре единичных бита), после того как операция скрещивания объединяет желательные элементы обоих родителей.

Теорема о схемах
Формальное выражение гипотезы о структурных элементах является содержанием теоремы Холланда о схемах, или основной теоремы генетических алгоритмов.
Эта теорема говорит о схемах, т. е. паттернах (или закономерностях), обнаруживаемых в хромосомах. Каждая схема представляет подмножество хромосом, обладающих определенным сходством.
Например, если набор хромосом представлен двоичными строками длины 4, то схема 1*01 представляет все хромосомы, у которых в крайней левой
позиции находится 1, в двух крайних справа – 01, а во второй слева позиции
может находиться как 1, так и 0, поскольку * – это метасимвол, сопоставляемый с любым конкретным символом.
Для каждой схемы можно определить две характеристики:
  порядок: количество фиксированных цифр (не метасимволов);
  определяющая длина: расстояние между крайними фиксированными цифрами.

26  Введение в генетические алгоритмы
В таблице ниже приведены примеры четырехзначных двоичных схем и их
характеристик:
Схема
1101
1*01
*101
*1*1
**01
1***
****

Порядок
4
3
3
2
2
1
0

Определяющая длина
3
3
2
2
1
0
0

Каждая хромосома в популяции соответствует нескольким схемам – точно
так же, как заданная строка соответствует разным регулярным выражениям.
Например, хромосома 1101 соответствует любой из перечисленных в таблице
схем. Если оценка этой хромосомы высока, то она с большей вероятностью
успешно пройдет отбор вместе со всеми схемами, которые представляет.
После скрещивания с другой хромосомой или мутации некоторые схемы выживут, а остальные исчезнут. Больше шансов на выживание у схем низкого
порядка с малым определяющим расстоянием.
Теорема о схемах утверждает, что частота схем низкого порядка с малым
определяющим расстоянием и приспособленностью выше средней экспоненциально возрастает в последующих поколениях. Иными словами, генетический алгоритм увеличивает частоту в популяции небольших и простых
структурных элементов, представляющих атрибуты, благодаря которым решение становится лучше.

Отличия от традиционных алгоритмов
Между генетическими и традиционными алгоритмами поиска и оптимизации имеется несколько важных различий.
Перечислим основные характеристики генетических алгоритмов, отли­
чающие их от традиционных:
  поддержание популяции решений:
  использование генетического представления решений;
  использование функции приспособленности;
  вероятностное поведение.
В следующих разделах эти факторы описываются более подробно.

Отличия от традиционных алгоритмов  27

Популяция как основа алгоритма
Целью генетического поиска является популяция потенциальных решений
(индивидуумов), а не единственное решение. В любой точке поиска алгоритм
сохраняет множество индивидуумов, образующих текущее поколение. На
каждой итерации генетического алгоритма создается следующее поколение
индивидуумов.
С другой стороны, в большинстве других алгоритмов поиска хранится
единственное решение, которое итеративно улучшается. Например, алгоритм градиентного спуска итеративно сдвигает текущее решение в направлении наискорейшего спуска, которое определяется антиградиентом
заданной функции.

Генетическое представление
Генетические алгоритмы работают не с самими потенциальными решениями, а с их кодированными представлениями, которые часто называют
хромосомами. Простым примером хромосомы является двоичная строка
фиксированной длины.
Хромосомы позволяют определить генетические операции скрещивания
и мутации. Скрещивание реализуется обменом частей родительских хромосом, а мутация – изменением частей хромосом.
Побочный эффект генетического представления – отделение поиска от исходной предметной области. Генетические алгоритмы не знают, что именно
представляют хромосомы, и не пытаются их интерпретировать.

Функция приспособленности
Функция приспособленности представляет проблему, которую мы пытаемся
решить. Цель генетического алгоритма – найти индивидуумов, для которых
оценка, вычисляемая функцией приспособленности, максимальна.
В отличие от традиционных алгоритмов поиска, генетические алгоритмы
анализируют только значение, возвращенное функцией приспособленности, их не интересует ни производная, ни какая-либо другая информация.
Поэтому они могут работать с функциями, которые трудно или невозможно
продифференцировать.

Вероятностное поведение
Многие традиционные алгоритмы по природе своей детерминированы, тогда как правила, применяемые генетическими алгоритмами для перехода от
предыдущего поколения к следующему, вероятностные.

28  Введение в генетические алгоритмы
Например, вероятность отбора индивидуума для создания следующего
поколения тем выше, чем больше значение функции приспособленности,
но элемент случайности все равно присутствует. Слабо приспособленные
индивидуумы могут быть отобраны, хотя вероятность этого ниже.
Мутации тоже имеют вероятностный характер, обычно их вероятность
мала, а изменению подвергаются случайные позиции в хромосоме.
Случайность присутствует и в операторе скрещивания. В некоторых генетических алгоритмах скрещивание происходит лишь с некоторой вероятностью. Если скрещивания не было, то оба родителя дублируются в следующем
поколении вообще без изменений.
Несмотря на вероятностную природу процесса, поиск, основанный на генетическом алгоритме, нельзя назвать случайным; случайность используется, чтобы направить поиск в сторону тех областей пространства поиска,
где выше шансы улучшить результаты. Теперь рассмотрим преимущества
генетических алгоритмов.

Преимущества генетических алгоритмов
Особенности генетических алгоритмов, рассмотренные в предыдущих разделах, определяют их преимущества по сравнению с традиционными алгоритмами поиска.
Ниже перечислены основные преимущества генетических алгоритмов:
  способность выполнять глобальную оптимизацию;
  применимость к задачам со сложным математическим представле­
нием;
  применимость к задачам, не имеющим математического представ­
ления;
  устойчивость к шуму;
  поддержка распараллеливания и распределенной обработки;
  пригодность к непрерывному обучению.
Мы рассмотрим их поочередно в следующих разделах.

Глобальная оптимизация
Во многих задачах оптимизации имеются точки локального максимума
и минимума, которые представляют решения, лучшие, чем те, что находятся
поблизости, но необязательно лучшие в глобальном смысле.
На рисунке ниже показаны различия между локальными и глобальными
минимумами и максимумами.

Преимущества генетических алгоритмов  29

Глобальный максимум
Локальный максимум

Локальный минимум
Глобальный минимум

Локальные и глобальные максимумы и минимумы функции
Источник: https://commons.wikimedia.org/wiki/File:Computational.science.
Genetic.algorithm.Crossover.One.Point.svg. Автор KSmrq.
Публикуется по лицензии Creative Commons CC BY-SA 3.0:
https://creativecommons.org/licenses/by-sa/3.0/

Большинство традиционных алгоритмов поиска и оптимизации, а особенно те, что основаны на вычислении градиента, могут застревать в локальном
максимуме, вместо того чтобы найти глобальный. Это связано с тем, что
в окрестности локального максимума всякое небольшое изменение решения
ухудшает оценку.
Генетические алгоритмы менее подвержены этой напасти и имеют больше шансов отыскать глобальный максимум. Объясняется это тем, что используется популяция потенциальных решений, а не единственное решение,
а операции скрещивания и мутации зачастую порождают решения, далеко
отстоящие от ранее рассмотренных. Это остается справедливым при условии,
что мы поддерживаем разнообразие популяции и избегаем преждевременной сходимости, о чем поговорим в следующем разделе.

Применимость к сложным задачам
Поскольку генетическим алгоритмам нужно знать только значение функции приспособленности каждого индивидуума, а все остальные ее свойства,
в частности производные, несущественны, их можно применять к задачам со
сложным математическим представлением, включающим функции, которые
трудно или невозможно продифференцировать.
К сложным случаям, когда достоинства генетических алгоритмов раскрываются во всем блеске, относятся также задачи с большим числом парамет­
ров или со смешанными параметрами, например непрерывными и дискретными.

30  Введение в генетические алгоритмы

Применимость к задачам, не имеющим
математического представления
Генетические алгоритмы применимы и к задачам, вообще не имеющим математического представления. Один из таких случаев, представляющий особый интерес, – когда оценка приспособленности основана на мнении человека. Пусть, например, требуется найти наиболее привлекательную цветовую
палитру для веб-сайта. Мы можем попробовать разные комбинации цветов
и попросить пользователей оценить привлекательность сайта. А затем применить генетический алгоритм, чтобы найти лучшую комбинацию, используя функцию приспособленности, основанную на оценках пользователей.
Алгоритм будет работать, несмотря на то что никакого математического
представления нет и невозможно вычислить оценку заданной комбинации
непосредственно.
В следующей главе мы увидим, что генетические алгоритмы справляются
даже со случаями, когда нельзя получить оценку каждого индивидуума, при
условии что имеется возможность сравнить двух индивидуумов и определить, какой из них лучше. Примером может служить алгоритм машинного
обучения, который управляет автомобилем в имитации гонок. Поиск на основе генетического алгоритма может оптимизировать и настроить алгоритм
машинного обучения, организовав состязание различных вариантов алгоритма между собой, чтобы определить, какой лучше.

Устойчивость к шуму
Для некоторых задач характерно присутствие шума. Это означает, что даже
при близких истинных значениях входных параметров результаты их измерений могут довольно сильно различаться. Например, так бывает, когда
данные считываются с датчиков или когда оценка основана на мнении человека, как было описано в предыдущем разделе.
Подобное поведение может сделать непригодными многие традиционные
алгоритмы поиска, но генетические алгоритмы в общем случае устойчивы
к нему благодаря повторяющимся операциям сборки и оценивания индивидуумов.

Распараллеливание
Генетические алгоритмы хорошо поддаются распараллеливанию и распределенной обработке. Функция приспособленности независимо вычисляется
для каждого индивидуума, а это значит, что все индивидуумы в популяции
могут обрабатываться одновременно.
Кроме того, операции отбора, скрещивания и мутации могут одновременно выполняться для индивидуумов и пар индивидуумов.
Поэтому подход, основанный на генетических алгоритмах, естественно
адаптируется к распределенным и облачным реализациям.

Ограничения генетических алгоритмов  31

Непрерывное обучение
В природе эволюция никогда не прекращается. Если окружающие условия
изменяются, популяция приспосабливается к ним. Так и генетические алгоритмы могут непрерывно работать в постоянно изменяющихся условиях,
и мы всегда можем получить и использовать лучшее на данный момент
решение.
Но это возможно, только если окружающая среда изменяется медленно по
сравнению со скоростью смены поколений в генетическом алгоритме. Итак,
преимущества мы обсудили, теперь перейдем к ограничениям генетических
алгоритмов.

Ограничения генетических алгоритмов
Чтобы получить максимум пользы от генетических алгоритмов, мы должны
знать об их ограничениях и потенциальных подвохах.
Ниже перечислены ограничения генетических алгоритмов:
  необходимы специальные определения;
  необходима настройка гиперпараметров;
  большой объем счетных операций;
  опасность преждевременной сходимости;
  отсутствие гарантированного решения.

Специальные определения
Пытаясь применить генетические алгоритмы к некоторой задаче, мы должны создать подходящее представление – определить функцию приспособ­
ленности и структуру хромосом, а также операторы отбора, скрещивания
и мутации. Зачастую это совсем не просто и занимает много времени.
По счастью, генетические алгоритмы уже бессчетное число раз применялись к самым разным задачам, так что многие определения стандартизованы. В этой книге рассматриваются многочисленные примеры реальных
задач и способы их решения с по­мощью генетических алгоритмов. Можете
использовать ее как руководство, когда столкнетесь с новой задачей.

Настройка гиперпараметров
Поведение генетических алгоритмов контролируется набором гиперпара­
метров, например размером популяции и скоростью мутации. Точных правил для выбора значений гиперпараметров не существует.
Однако так обстоит дело практически со всеми алгоритмами поиска и оптимизации. Проработав примеры в книге и поэкспериментировав самостоятельно, вы научитесь подбирать разумные значения гиперпараметров.

32  Введение в генетические алгоритмы

Большой объем счетных операций
Работа с потенциально большими популяциями и итеративный характер генетических алгоритмов обусловливают большой объем вычислений, поэтому
на получение приемлемого результата может уйти много времени.
Проблему можно сгладить за счет хорошего выбора гиперпараметров,
распараллеливания и в некоторых случаях кеширования промежуточных
результатов.

Преждевременная сходимость
Если приспособленность какого-то индивидуума гораздо больше, чем у всей
остальной популяции, то не исключено, что он продублируется так много
раз, что в конечном счете, кроме него, в популяции ничего не останется.
В результате генетический алгоритм может застрять в локальном максимуме
и не найдет глобального.
Чтобы предотвратить такое развитие событий, важно поддерживать разнообразие популяции. В следующей главе мы рассмотрим различные способы достижения этой цели.

Отсутствие гарантированного решения
Использование генетических алгоритмов не гарантирует нахождения глобального максимума.
Однако это типично для всех алгоритмов поиска и оптимизации, если
только у задачи не существует аналитического решения.
Но, вообще говоря, при правильном применении генетические алгоритмы
находят хорошие решения на разумное время. Далее мы рассмотрим несколько ситуаций, в которых применение генетических алгоритмов оправдано.

Сценарии применения
генетических алгоритмов
Резюмируя изложенное в предыдущих разделах, можно сказать, что генетические алгоритмы лучше применять для решения следующих задач.
  Задачи со сложным математическим представлением. Поскольку
генетическим алгоритмам нужно знать только значение функции приспособленности, их можно использовать для решения задач, в которых
целевую функцию трудно или невозможно продифференцировать, задач с большим количеством параметров и задач с параметрами разных
типов.
  Задачи, не имеющие математического представления. Генетические алгоритмы не требуют математического представления задачи,

Для дальнейшего чтения  33

коль скоро можно получить значение оценки или существует метод
сравнения двух решений.
  Задачи с зашумленной окружающей средой. Генетические алгоритмы устойчивы к зашумленным данным, например прочитанным
с датчика или основанным на оценках, сделанных человеком.
  Задачи, в которых окружающая среда изменяется во времени.
Генетические алгоритмы могут адаптироваться к медленным изменениям окружающей среды, поскольку постоянно создают новые поколения, приспосабливающиеся к изменениям.
С другой стороны, если для задачи известен специализированный способ
решения традиционным или аналитическим методом, то вполне вероятно,
что он окажется эффективнее.

Резюме
Мы начали эту главу со знакомства с генетическими алгоритмами, с аналогии между ними и дарвиновской эволюцией и с основных принципов их
работы: использования популяции, генотипа, функции приспособленности
и операторов отбора, скрещивания и мутации.
Затем рассмотрели теорию, лежащую в основе генетических алгоритмов, –
гипотезу структурных элементов и теорему о схемах – и показали, как генетические алгоритмы работают, собирая наилучшие решения из небольших
структурных элементов, обладающих превосходными качествами.
Далее мы разобрали различия между генетическими и традиционными
алгоритмами, в т. ч. поддержание популяции решений и использование генетического представления решений.
После этого мы обсудили сильные стороны генетических алгоритмов,
включая возможность глобальной оптимизации, применимость к задачам со
сложным математическим представлением или вообще без такового и устойчивость к шуму. Мы также поговорили о недостатках: необходимости специальных определений и настройки гиперпараметров, опасности преждевременной сходимости.
В заключение перечислили ситуации, когда применение генетических алгоритмов может дать выигрыш: математически сложные задачи, оптимизация в зашумленной или постоянно изменяющейся среде.
В главе 2 мы более подробно рассмотрим ключевые компоненты и детали
реализации генетических алгоритмов. Это станет подготовкой к последующим главам, где мы приведем код решения различных задач.

Для дальнейшего чтения
Дополнительный материал, относящийся к этой главе, можно найти в главе
«Введение в генетические алгоритмы» книги Amita Kapoor «Hands-On Artificial Intelligence for IoT» (январь 2019), опубликованной по адресу https://subscription.packtpub.com/book/big_data_and_business_intelligence/9781788836067.

Глава

2

Основные компоненты
генетических
алгоритмов
В этой главе мы подробнее рассмотрим основные компоненты и детали реализации генетических алгоритмов. Это станет подготовкой к чтению последующих глав, посвященных использованию таких алгоритмов для решения
различных задач.
Прежде всего опишем базовую структуру генетического алгоритма, а затем выделим в ней отдельные компоненты и продемонстрируем различные реализации методов отбора, скрещивания и мутации. Затем мы познакомимся с генетическими алгоритмами с вещественными хромосомами
для организации поиска в непрерывном пространстве параметров. За этим
последует увлекательное введение в вопросы элитизма, образования ниш
и разделения в генетических алгоритмах. Наконец, мы займемся искусством
решения задач с по­мощью генетических алгоритмов.
Прочитав эту главу, вы будете:
  знать об основных компонентах генетических алгоритмов;
  понимать, из каких этапов состоит поток управления в генетическом
алгоритме;
  знать, что такое генетические операторы и какие у них есть варианты;
  знать о различных видах условий остановки;
  понимать, как нужно модифицировать базовый генетический алгоритм, чтобы он мог работать с вещественными числами;
  понимать механизм элитизма;
  понимать идею и реализацию механизмов образования ниш и разделения;
  знать, с чего начинать при решении новой задачи.

Базовая структура генетического алгоритма
На следующей блок-схеме показаны основные этапы типичного генетического алгоритма.

Базовая структура генетического алгоритма  35

Начало

Создать
начальную популяцию
(«поколение 0»)

Вычислить
приспособленность каждого
индивидуума в популяции

Отбор

Скрещивание

Мутация

Вычислить пригодность
каждого индивидуума
в популяции

Нет

Условия
остановки
выполнены?

Да
Выбрать индивидуума
с максимальной
приспособленностью

Конец

Базовая структура генетического алгоритма

36  Основные компоненты генетических алгоритмов
В следующих разделах эти этапы описаны более подробно.

Создание начальной популяции
Начальная популяция состоит из случайным образом выбранных потенциальных решений (индивидуумов). Поскольку в генетических алгоритмах индивидуумы представлены хромосомами, начальная популяция – это, по сути
дела, набор хромосом. Формат хромосом должен соответствовать принятым
для решаемой задачи правилам, например это могут быть двоичные строки
определенной длины.

Вычисление приспособленности
Для каждого индивидуума вычисляется функция приспособленности. Это
делается один раз для начальной популяции, а затем для каждого нового поколения после применения операторов отбора, скрещивания и мутации. Поскольку приспособленность любого индивидуума не зависит от всех
остальных, эти вычисления можно производить параллельно.
Так как на этапе отбора, следующем за вычислением приспособленности,
более приспособленные индивидуумы обычно считаются лучшими решениями, генетические алгоритмы естественно «заточены» под нахождение
максимумов функции приспособленности. Если в какой-то задаче нужен
минимум, то при вычислении приспособленности следует инвертировать
найденное значение, например умножив его на –1.

Применение операторов отбора, скрещивания
и мутации
Применение генетических операторов к популяции приводит к созданию
новой популяции, основанной на лучших индивидуумах из текущей.
Оператор отбора отвечает за отбор индивидуумов из текущей популяции
таким образом, что предпочтение отдается лучшим. Примеры операторов
отбора приведены в разделе «Методы отбора».
Оператор скрещивания (или рекомбинации) создает потомка выбранных индивидуумов. Обычно для этого берутся два индивидуума, и части их
хромосом меняются местами, в результате чего создаются две новые хромосомы, представляющие двух потомков. Примеры операторов скрещивания
приведены в разделе «Методы скрещивания».
Оператор мутации вносит случайные изменения в один или несколько генов хромосомы вновь созданного индивидуума. Обычно вероятность
мутации очень мала. Примеры операторов мутации приведены в разделе
«Методы мутации».

Методы отбора  37

Проверка условий остановки
Может существовать несколько условий, при выполнении которых процесс
останавливается. Сначала отметим два самых распространенных:
  достигнуто максимальное количество поколений. Это условие заодно
позволяет ограничить время работы алгоритма и потребление им ресурсов системы;
  на протяжении нескольких последних поколений не наблюдается заметных улучшений. Это можно реализовать путем запоминания наилучшей приспособленности, достигнутой в каждом поколении, и сравнения наилучшего текущего значения со значениями в нескольких
предыдущих поколениях. Если разница меньше заранее заданного порога, то алгоритм можно останавливать.
Перечислим также другие возможные условия:
  с момента начала прошло заранее определенное время;
  превышен некоторый лимит затрат, например процессорного времени
или памяти;
  наилучшее решение заняло часть популяции, большую заранее заданного порога.
Резюмируем. Генетический алгоритм начинается с популяции случайно
выбранных потенциальных решений (индивидуумов), для которых вычисляется функция приспособленности. Алгоритм выполняет цикл, в котором
последовательно применяются операторы отбора, скрещивания и мутации,
после чего приспособленность индивидуумов пересчитывается. Цикл продолжается, пока не выполнено условие остановки, после чего лучший индивидуум в текущей популяции считается решением. Теперь рассмотрим
методы отбора.

Методы отбора
Отбор выполняется в начале каждой итерации цикла генетического алгоритма, чтобы выбрать из текущей популяции тех индивидуумов, которые
станут родителями индивидуумов в следующем поколении. Отбор носит
вероятностный характер, причем вероятность выбора индивидуума зависит
от его приспособленности, так что у более приспособленных индивидуумов
шансы отобраться выше.
Ниже описаны некоторые из распространенных методов отбора и их характеристики.

38  Основные компоненты генетических алгоритмов

Правило рулетки
Метод отбора по правилу рулетки, или отбор пропорционально приспособленности (fitness proportionate selection – FPS), устроен так, что вероятность отбора индивидуума прямо пропорциональна его приспособленности.
Тут можно провести аналогию с вращением колеса рулетки, где каждому индивидууму соответствует сектор, стоимость которого равна приспособленности индивидуума. Шансы, что шарик остановится в секторе индивидуума,
пропорциональны размеру этого сектора.
Пусть, например, имеется популяция из шести индивидуумов с такими
значениями приспособленности, как в таблице ниже. По этим значениям
вычисляются доли, занимаемые секторами каждого индивидуума.
Индивидуум
A
B
С
D
E
F

Приспособленность
8
12
27
4
45
17

Относительная доля
7%
11 %
24 %
3%
40 %
15 %

На рисунке ниже изображена соответствующая рулетка.

A

15 %

B

C

D

E

F

7%
11 %

Точка
отбора

Направление
вращения
рулетки

24 %
40 %

3%

Пример отбора по правилу рулетки

Методы отбора  39

После каждого запуска рулетки отбор индивидуума из популяции производится в точке отбора. Затем рулетка запускается еще раз для выбора
следующего индивидуума, и так до тех пор, пока не наберется достаточно
индивидуумов для образования следующего поколения. В результате один
и тот же индивидуум может быть выбран несколько раз.

Стохастическая универсальная выборка
Стохастическая универсальная выборка (stochastic universal sampling – SUS) –
немного модифицированный вариант правила рулетки. Используется та же
рулетка с такими же секторами, но вместо одной точки отбора и многократного запуска рулетки мы вращаем колесо только один раз, а отбор индивидуумов производим в нескольких точках, равномерно расставленных по
окружности. Тем самым все индивидуумы выбираются одновременно, как
показано на рисунке ниже.

A B C D E F

Точка
отбора

Точка
отбора

7%
15 %
11 %

Точка
отбора

Точка
отбора

Направление
вращения
рулетки

24 %
40 %

3%
Точка
отбора

Точка
отбора

Пример стохастической универсальной выборки

Этот метод отбора не дает индивидуумам с особенно высокой приспособленностью заполнить все следующее поколение в результате повторного
выбора. Поэтому более слабым индивидуумам предоставляется шанс, а несправедливость чистого правила рулетки в какой-то мере сглаживается.

40  Основные компоненты генетических алгоритмов

Ранжированный отбор
Метод ранжированного отбора похож на правило рулетки, но значения приспособленности используются не для вычисления вероятностей выбора,
а просто для сортировки индивидуумов. После сортировки каждому индивидууму назначается ранг, соответствующий его позиции в списке, а вероятности секторов рулетки вычисляются на основе этих рангов.
Возьмем ту же самую популяцию из шести индивидуумов, что и раньше.
И добавим в таблицу столбец с рангом индивидуума. Поскольку размер популяции равен 6, наивысший возможный ранг тоже равен 6, следующий по
порядку – 5 и т. д. Каждому индивидууму сопоставляется сектор рулетки,
вычисленный по этим рангам, а не по значениям функции приспособленности.
Индивидуум
A
B
С
D
E
F

Приспособленность
8
12
27
4
45
17

Ранг
2
3
5
1
6
4

Относительная доля
9%
14 %
24 %
5%
29 %
19 %

На рисунке ниже изображена соответствующая рулетка.
A

B

C

D

E

F

9%
19 %
14 %
Точка
отбора

Направление
вращения
рулетки

29 %
24 %

5%

Пример ранжированного отбора

Методы отбора  41

Ранжированный отбор полезен, когда есть несколько индивидуумов, гораздо лучше приспособленных, чем все остальные. Использование ранга
вместо самой приспособленности мешает этим индивидуумам захватить всю
популяцию в следующем поколении, поскольку ранжирование сглаживает
значительные различия.
Кроме того, когда все индивидуумы обладают почти одинаковой приспособленностью, ранжированный отбор позволяет разделить их, отдавая преимущество лучшим, даже когда различия малы.

Масштабирование приспособленности
Если при ранжированном отборе приспособленности заменяются рангами,
то в случае масштабирования приспособленности к исходным значениям
приспособленности применяется линейное преобразование, которое переводит их в желательный диапазон:
масштабированная приспособленность = a × (исходная
приспособленность) + b,
где a и b – постоянные, выбираемые по нашему усмотрению.
Например, в предыдущих примерах значения приспособленности лежали
в диапазоне от 4 (у индивидуума D) до 45 (у индивидуума E). Допустим, мы хотим перевести их в диапазон от 50 до 100. Тогда a и b вычисляются из уравнений
  50 = a × 4 + b (наименьшая приспособленность);
  100 = a × 45 + b (наибольшая приспособленность).
Решая эту систему двух линейных уравнений, получаем следующие параметры масштабирования:
a = 1.22, b = 45.12.
Таким образом, масштабированные значения приспособленности вычисляются по формуле
масштабированная приспособленность = 1.22 × (исходная
приспособленность) + 45.12.
Добавив в таблицу столбец, содержащий значения масштабированной
приспособленности, убеждаемся, что все они действительно попадают в диапазон от 50 до 100.
Индивидуум

Приспособленность

A
B
С
D
E
F

8
12
27
4
45
17

Масштабированная
приспособленность
55
60
78
50
100
66

Относительная доля
13 %
15 %
19 %
12 %
25 %
16 %

42  Основные компоненты генетических алгоритмов
На рисунке ниже изображена соответствующая рулетка.
A

B

C

D

E

F

13 %

16 %

15 %

Точка
отбора

Направление
вращения
рулетки

25 %

19 %
12 %

Пример колеса рулетки после масштабирования приспособленности

Как видно по рисунку, переход к новому диапазону дает гораздо более
равномерное разбиение рулетки на сектора по сравнению с исходным. Вероятность отбора лучшего индивидуума (с масштабированной приспособленностью 100) теперь всего в два раза выше, чем худшего (с масштабированной
приспособленностью 50), а не в 11 раз, как первоначально.

Турнирный отбор
В каждом раунде турнирного отбора из популяции выбираются два или более
индивидуумов, и тот, у кого приспособленность больше, выигрывает и отбирается в следующее поколение.
Рассмотрим тех же индивидуумов с такими же приспособленностями, что
и выше. На следующем рисунке показан результат случайного выбора трех из
них (A, B и F) с последующим объявлением F победителем, поскольку у него
приспособленность максимальная из трех (17).

Методы скрещивания  43

Индивидуум

Приспособленность

А

8

В

12

С

27

D

4

E

45

F

17

F

Пример турнирного отбора на турнире с тремя участниками

Количество индивидуумов, участвующих в каждом раунде турнирного отбора (в нашем примере – три), называется размером турнира. Чем больше
размер турнира, тем выше шансы, что в раундах будут участвовать лучшие
индивидуумы, и тем меньше шансов у слабых участников победить в турнире
и отобраться.
У этого метода отбора есть интересная особенность: если мы умеем сравнивать любых двух индивидуумов и определять, какой из них лучше, то сами
значения функции приспособленности и не нужны.

Методы скрещивания
Оператор скрещивания (или рекомбинации) соответствует биологическому
скрещиванию при половом размножении. Он используется для комбинирования генетической информации двух индивидуумов, выступающих в роли
родителей, в процессе порождения потомков (обычно двух).
Как правило, оператор скрещивания применяется не всегда, а с некоторой
(высокой) вероятностью. Если скрещивание не применяется, то копии обоих
родителей переходят в следующее поколение без изменения.
В следующих разделах описываются некоторые методы скрещивания и типичные примеры их применения. Впрочем, в некоторых ситуациях приходится придумывать специальный метод, соответствующий конкретной
задаче.

Одноточечное скрещивание
В этом случае позиция в хромосомах обоих родителей выбирается случайным
образом. Эта позиция называется точкой скрещивания, или точкой разреза.
Гены одной хромосомы, расположенные справа от этой точки, обмениваются
с точно так же расположенными генами другой хромосомы. В результате мы
получаем двух потомков, несущих генетическую информацию обоих родителей.

44  Основные компоненты генетических алгоритмов
На рисунке ниже показано одноточечное скрещивание пары двоичных хромосом, когда точка скрещивания находится между пятым и шестым геном.

Пример одноточечного скрещивания
Источник: https://commons.wikimedia.org/wiki/File:Computational.science.
Genetic.algorithm.Crossover.One.Point.svg. Автор: Yearofthedragon.
Публикуется по лицензии Creative Commons CC BY-SA 3.0:
https://creativecommons.org/licenses/by-sa/3.0/deed.en

Двухточечное и k-точечное скрещивание
При двухточечном скрещивании случайным образом выбираются по две точки скрещивания в каждой хромосоме. Гены одной хромосомы, расположенные между этими точками, обмениваются с точно так же расположенными
генами другой хромосомы.
На рисунке ниже показано двухточечное скрещивание пары двоичных
хромосом, когда первая точка скрещивания находится между третьим и четвертым геном, а вторая – между седьмым и восьмым.

Пример двухточечного скрещивания
Источник: https://commons.wikimedia.org/wiki/File:Computational.science.
Genetic.algorithm.Crossover.Two.Point.svg. Автор: Yearofthedragon.
Публикуется по лицензии Creative Commons CC BY-SA 3.0:
https://creativecommons.org/licenses/by-sa/3.0/deed.en

Методы скрещивания  45

Метод двухточечного скрещивания можно реализовать с по­мощью двух
одноточечных скрещиваний с разными точками скрещивания. Его обобщением является метод k-точечного скрещивания, где k – целое положительное
число.

Равномерное скрещивание
При равномерном скрещивании каждый ген обоих родителей определяется
независимо путем случайного выбора с равномерным распределением. Когда выбирается 50 % генов, оба родителя имеют одинаковые шансы повлиять
на потомков.

Пример равномерного скрещивания

Заметим, что в этом примере гены обоих потомков меняются местами, но
в принципе потомков можно создавать и независимо.
В этом примере использовались целочисленные хромосомы, но метод точно так
же работает для двоичных.

Поскольку в этом методе не производится обмен целых участков хромосом, потенциально он может повысить разнообразие потомков.

Скрещивание для упорядоченных списков
В предыдущем примере мы видели результаты операции скрещивания двух
целочисленных хромосом. В обоих родителях каждая цифра от 0 до 9 встречалась ровно один раз, но в потомках некоторые цифры встречаются более
одного раза (например, 2 в верхнем потомке и 1 в нижнем), тогда как другие
отсутствуют вовсе (например, 4 в верхнем потомке и 5 в нижнем).

46  Основные компоненты генетических алгоритмов
Но бывают задачи, в которых целочисленные хромосомы представляют
индексы упорядоченного списка. Пусть, например, имеется несколько городов, известны попарные расстояния между ними и требуется найти кратчайший путь, проходящий через все города. Это так называемая задача коммивояжера, которую мы подробно рассмотрим в последующих главах.
Если городов четыре, то возможное решение задачи удобно представить
четырехзначной целочисленной хромосомой, описывающей порядок посещения городов, например (1,2,3,4) или (3,4,2,1). Хромосома, в которой
некоторые значения повторяются или, наоборот, отсутствуют, не является
допустимым решением.
Для таких случаев были придуманы альтернативные методы скрещивания,
гарантирующие, что всегда создается допустимый потомок. Один из таких
методов, упорядоченное скрещивание, рассматривается в следующем разделе.

Упорядоченное скрещивание
Метод упорядоченного скрещивания (OX1) стремится по возможности сохранить относительный порядок родительских генов. Мы продемонстрируем
его на примере хромосом длины шесть.
На первом шаге мы выполняем двухточечное скрещивание со случайно
выбранными точками разреза, как показано на рисунке ниже (родители изображены слева):

Пример упорядоченного скрещивания – шаг 1

Затем начинаем заполнять оставшиеся гены в каждом потомке, для чего
обходим гены родителя в их исходном порядке, начиная со следующего за
второй точкой разреза. В первом родителе в этой позиции находится 6, но
это число уже присутствует в потомке, поэтому мы переходим к следующей
позиции (с возвратом в начало), в которой находится 1. Это число также уже
имеется. Следующим является число 2. Поскольку его еще нет в потомке, добавляем его, как показано на рисунке ниже. Для второй пары родитель–потомок мы начинаем с позиции, в которой находится 5. Поскольку это число
уже присутствует в потомке, переходим к числу 4. Оно тоже присутствует, поэтому идем дальше и заканчиваем в позиции, где находится число 2, которое
мы добавляем в потомка. Результат также показан на рисунке.

Методы мутации  47

Пример упорядоченного скрещивания – шаг 2

Следующим числом для первого родителя будет 3 (оно уже присутствует
в потомке), а за ним 4, которое добавляется к потомку. Для второго родителя
следующим идет ген 6. Поскольку его еще нет в потомке, добавляем. Результат показан на рисунке ниже.

Пример упорядоченного скрещивания – шаг 3

Продолжая таким же манером, мы заполним все свободные позиции в потомках и придем к окончательным хромосомам-потомкам:

Пример упорядоченного скрещивания – шаг 4

Существуют и другие методы скрещивания, некоторые из них встретятся
нам позже. Но благодаря гибкости генетических алгоритмов вы можете придумать и свои методы. А мы перейдем к методам мутации.

Методы мутации
Мутация – последний генетический оператор, применяемый при создании
нового поколения. Он применяется к потомку, созданному в результате операций отбора и скрещивания.

48  Основные компоненты генетических алгоритмов
Операция мутации вероятностная, обычно она выполняется изредка,
с очень низкой вероятностью, поскольку может ухудшить качество индивидуума, к которому применена. В некоторых вариантах генетических алгоритмов вероятность мутации постепенно увеличивается, чтобы предотвратить стагнацию и повысить разнообразие популяции. С другой стороны,
если частота мутации слишком велика, то генетический алгоритм выродится
в случайный поиск.
В следующих разделах описываются некоторые методы мутации и типичные примеры их применения. Но не забывайте, что вы всегда можете придумать свой собственный метод, отвечающий специфике конкретной задачи.

Инвертирование бита
Для двоичной хромосомы мы можем случайным образом выбрать ген и инвертировать его (взять двоичное дополнение), как показано на рисунке ниже.

Пример мутации инвертированием бита

Можно пойти дальше и инвертировать не один, а сразу несколько генов.

Мутация обменом
Этот метод применим как к двоичным, так и к целочисленным хромосомам:
случайно выбираются два гена, и их значения меняются местами, как показано на рисунке ниже.

Пример мутации обменом

Такая операция мутации годится для хромосом, представляющих упорядоченные списки, поскольку набор генов в новой хромосоме такой же, как
в исходной.

Мутация обращением
При применении этого метода к двоичной или целочисленной хромосоме
выбирается случайная последовательность генов, и порядок генов в ней меняется на противоположный, как показано на рисунке ниже.

Генетические алгоритмы с вещественным кодированием  49

Пример мутации обращением

Как и мутация обменом, мутация обращением годится для хромосом,
представляющих упорядоченные списки.

Мутация перетасовкой
Еще один оператор мутации, подходящий для хромосом, представляющих
упорядоченные списки, – мутация перетасовкой. В этом случае выбирается
случайная последовательность генов, и порядок генов в ней изменяется случайным образом (тасуется), как показано на рисунке ниже.

Пример мутации перетасовкой

В следующем разделе мы рассмотрим другие типы специализированных
операторов, встречающиеся в генетических алгоритмах с вещественным кодированием.

Генетические алгоритмы
с вещественным кодированием
До сих пор мы рассматривали хромосомы, представляющие двоичные или
целочисленные параметры. И генетические операторы были приспособлены
для работы с такими хромосомами. Но зачастую встречаются задачи с непрерывным пространством решений, когда индивидуумы описываются вещест­
венными числами с плавающей точкой.
Исторически в генетических алгоритмах применялись двоичные строки
для представления целых чисел, но для вещественных чисел это не годится.
Точность вещественного числа, представленного двоичной строкой, ограничена длиной строки (количеством бит). Поскольку эту длину нужно задать
заранее, может получиться, что строки слишком короткие, поэтому точность
недостаточна, или, наоборот, чересчур длинные.
Кроме того, в двоичной строке значение бита зависит от его позиции –
наиболее значимые биты находятся слева. Это может стать причиной дисбаланса схем – паттернов, встречающихся в хромосомах; например, схема
1**** (все пятизначные двоичные строки, начинающиеся с 1) и схема ****1

50  Основные компоненты генетических алгоритмов
(все пятизначные двоичные строки, заканчивающиеся на 1) имеет порядок 1
и определяющую длину 0, однако первая гораздо более значима, чем вторая.
Поэтому вместо двоичных строк используются массивы вещественных
чисел – это проще и удобнее. Так, в задаче с тремя вещественными парамет­
рами хромосомы будут иметь вид [x1, x2, x3], где x1, x2, x3 – вещественные
числа, например: [1.23, 7.2134, –25.309] или [–30.10, 100.2, 42.424].
Все методы отбора, описанные выше в этой главе, будут работать точно
так же для вещественных хромосом, поскольку они зависят только от приспособленности индивидуумов, а не от их представления.
Однако рассмотренные выше методы скрещивания и мутации для ве­
щественных хромосом не годятся, поэтому нужны специальные методы.
Важно помнить, что эти операции скрещивания и мутации применяются по
отдельности к каждой позиции массивов, представляющих вещественные
хромосомы. Например, если родителями в операции скрещивания являются
хромосомы [1.23, 7.213, –25.39] и [–30.10, 100.2, 42.42], то скрещивание производится отдельно для следующих пар:
  1.23 и –30.10 (первая позиция);
  7.213 и 100.2 (вторая позиция);
  –25.39 и 42.42 (третья позиция).
Это показано на рисунке ниже.

Пример скрещивания вещественных хромосом

Все сказанное относится и к оператору мутации вещественных хромосом.
Ниже описано несколько методов скрещивания и мутации в вещественном случае. А в главе 6 мы увидим, как они применяются на практике.

Скрещивание смешением
В случае скрещивания смешением (blend crossover – BLX) каждый потомок случайным образом выбирается из следующего интервала, созданного
родителями parent1 и parent2:
[parent1 – α(parent2 – parent1), parent2 + α(parent2 – parent1)].

Параметр α – постоянная от 0 до 1. Чем больше α, тем шире интервал. Например, если значения родителей равны 1.33 и 5.72, то:
  при α = 0 получается интервал [1.33, 5.72] (такой же, как между родителями);

Генетические алгоритмы с вещественным кодированием  51

  при α = 0.5 получается интервал [–0.865, 7.915] (в два раза шире, чем
между родителями);
  при α = 1.0 получается интервал [–3.06, 10.11] (в три раза шире, чем
между родителями).
Эти примеры показаны на рисунке ниже, где родители обозначены p1 и p2,
а интервал скрещивания изображен желтым цветом:

Пример скрещивания смешением

При использовании этого метода скрещивания обычно полагают α = 0.5.

Имитация двоичного скрещивания

Идея имитации двоичного скрещивания (simulated binary crossover –
SBX) – имитировать свойства одноточечного скрещивания, часто применяемого для двоичных хромосом. Одно из свойств заключается в том, что
среднее значений родителей равно среднему значений потомков.
В случае метода SBX два потомка создаются из родителей по следующей
формуле:
offsping1 = ½ [(1 + β]parent1 + (1 – β)parent2]);
offsping2 = ½ [(1 – β]parent1 + (1 + β)parent2]),

где β – случайное число, называемое коэффициентом распределения.
Эта формула обладает следующими свойствами:
  среднее потомков равно среднему родителей независимо от значений β;
  если β = 1, потомки являются копиями родителей;

52  Основные компоненты генетических алгоритмов
  когда β < 1, потомки располагаются ближе друг к другу, чем родители;
  когда β > 1, потомки располагаются дальше друг от друга, чем родители.
Например, если значения родителей равны 1.33 и 5.72, то имеем:
  при β = 0.8 получаются потомки 1.769 и 5.281;
  при β = 1.0 получаются потомки 1.33 и 5.72;
  при β = 1.2 получаются потомки 0.891 и 6.159.
Все три случая показаны на следующем рисунке, где родители обозначены
p1 и p2, а потомки – o1 и o2.

Пример имитации двоичного скрещивания

В каждом из этих случаев среднее значение потомков равно 3.525, т. е. совпадает со средним родителей.
У двоичного одноточечного скрещивания есть еще одно свойство: мы
стремимся сохранить сходство между потомком и родителями. Чтобы имитировать его, нужно выбирать β из случайного распределения. Плотность
вероятности β должна быть гораздо выше в окрестности 1, где потомки похожи на родителей. Для этого β вычисляется с по­мощью еще одной случайной
величины, обозначаемой u, которая равномерно распределена в интервале
[0, 1]. Ели значение u выбрано, то β вычисляется следующим образом:
  если u ≤ 0.5:

  иначе:
Параметр η в этих формулах – постоянная, называемая индексом распределения. Чем больше значение η, тем сильнее потомок похож на своих
родителей. Обычно выбирают η равным 10 или 20.

Элитизм  53

Вещественная мутация
Один из способов применения мутации в генетических алгоритмах с вещественным кодированием – заменить любое вещественное значение совершенно новым, случайно сгенерированным. Однако при этом может оказаться, что мутировавший индивидуум не имеет ничего общего с исходным.
Другой подход – сгенерировать случайное вещественное число, находящее­
ся рядом с исходным индивидуумом. Примером может служить нормально
распределенная (или гауссова) мутация: случайное число выбирается из
нормального распределения со средним 0 и каким-то заранее заданным
стандартным отклонением, как показано на рисунке ниже.

Пример гауссовой мутации

Далее мы рассмотрим еще два вопроса: элитизм и образование ниш.

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

54  Основные компоненты генетических алгоритмов
Но если мы хотим гарантировать, что лучшие индивидуумы обязательно
переходят в следующее поколение, то можем применить факультативную
стратегию элитизма. Это означает, что n лучших индивидуумов (n – небольшое, заранее заданное число) копируются в следующее поколение, до
того как все места будут заняты потомками, полученными в результате отбора, скрещивания и мутации. Скопированные элитные индивидуумы попрежнему могут использоваться как родители новых индивидуумов.
Иногда элитизм оказывает заметный положительный эффект на качество
алгоритма, поскольку не нужно тратить времени на повторное открытие
хороших решений, потерянных в результате эволюции.
Еще один интересный способ улучшить результаты генетического алгоритма – воспользоваться образованием ниш, как описано в следующем разделе.

Образование ниш и разделение
В природе любая окружающая среда разбивается на несколько меньших сред,
или ниш, занятых различными видами, которые обращают себе на пользу
уникальные ресурсы ниши, например пищу и укрытие. Так, в лесу можно
выделить верхушки деревьев, подлесок, лесную подстилку, корни деревьев
и т. д. В каждой такой нише обитают разные виды, приспособленные к су­
щест­вованию именно в ней.
Если в одной нише обитают несколько разных видов, то они конкурируют
за одни и те же ресурсы, поэтому наблюдается тенденция к поиску новых
свободных ниш и их заселению.
В генетических алгоритмах феномен ниш можно использовать для поддержания разнообразия популяции, а также для поиска нескольких оптимальных решений, каждое из которых считается нишей.
Пусть, например, наш генетический алгоритм должен максимизировать
функцию приспособленности, имеющую несколько пиков разной высоты,
как на графике ниже.

Образование ниш и разделение  55

Ожидаемые результаты генетического алгоритма без образования ниш

Поскольку генетический алгоритм обычно стремится найти глобальный
максимум, можно ожидать, что через некоторое время большая часть популяции сосредоточится в районе верхнего пика. На рисунке это показано
крестиками на графике функции, представляющими индивидуумов в текущем поколении.
Однако иногда нам нужно найти не только глобальный максимум, но и некоторые (или все) другие пики. Для этого мы должны рассматривать каждый
пик как нишу, предлагающую ресурсы в объеме, пропорциональном высоте.
Затем мы ищем способ разделить эти ресурсы между индивидуумами, занимающими нишу. В идеале популяция при этом должна распределиться
соответственно, так что самый высокий пик будет привлекать больше всего
индивидуумов, поскольку предлагает наибольшее вознаграждение, а прочие пики будут заселены не так плотно, потому что вознаграждение в них
меньше.

56  Основные компоненты генетических алгоритмов
Эта идеальная ситуация изображена на рисунке ниже.

Результаты идеального генетического алгоритма с образованием ниш

Проблема теперь в том, как реализовать этот механизм разделения. Один
из вариантов – разделить исходное значение приспособленности каждого
индивидуума на число, равное какой-то функции от комбинации расстояний
до всех остальных индивидуумов. Другой вариант – разделить исходную
приспособленность каждого индивидуума на число других индивидуумов,
отстоящих от него не более чем на некоторое пороговое расстояние.

Последовательное и параллельное
образование ниш
К сожалению, описанную выше идею ниш трудно реализовать, потому что
при этом возрастает сложность вычисления приспособленности. На практике
понадобится также умножить исходный размер популяции на количество
ожидаемых пиков (которое в общем случае неизвестно).
Один из способов преодолеть эти проблемы – искать пики по одному (последовательное образование ниш), а не пытаться найти все сразу (параллельное образование ниш). Для реализации последовательного образования
ниш мы используем генетический алгоритм как обычно и находим лучшее
решение. Затем функция приспособленности изменяется таким образом,
чтобы «сплющить» окрестность точки максимума, после чего генетический
алгоритм выполняется еще раз.

Искусство решения задач с помощью генетических алгоритмов  57

В идеале мы найдем следующий по высоте пик, поскольку исходного пика
больше не существует. Этот процесс можно повторять итеративно, отыскивая
на каждой итерации очередной пик.

Искусство решения задач
с помощью генетических алгоритмов
Генетические алгоритмы дают нам мощный и гибкий инструмент, позволяющий решать широкий спектр задач. Приступая к новой задаче, мы должны
подогнать этот инструмент к ее особенностям. Для этого есть несколько подходов, описанных ниже.
Прежде всего необходимо определить функцию приспособленности. С ее
по­мощью оцениваются все индивидуумы: чем больше приспособленность,
тем лучше индивидуум. Функция необязательно должна быть выражена
в виде математической формулы. Она может быть представлена алгоритмом,
или обращением к внешней службе, или даже являться результатом игры –
и это далеко не все возможности. Главное, чтобы мы могли программно
получить приспособленность любого решения (индивидуума).
Затем нужно выбрать подходящий способ кодирования хромосом.
Он основан на параметрах, передаваемых функции приспособленности.
До сих пор нам встречались такие кодировки: двоичная, целочисленная,
упорядоченный список, вещественная. Но бывают задачи со смешанными типами параметров, а иногда даже приходится создавать собственные
кодировки.
Далее нужно определиться с методом отбора. Большинство методов работают для хромосом любого типа. Если функция приспособленности как таковая недоступна, но мы все-таки можем сказать, какой из двух кандидатов
лучше, то можно воспользоваться турнирным методом отбора.
В предыдущих разделах мы видели, что выбор операторов скрещивания
и мутации зависит от кодировки хромосом. Для двоичных хромосом применяются не такие схемы скрещивания и мутации, как для вещественных.
И в этом случае также можно придумать собственные методы скрещивания
и мутации, отвечающие специфике задачи.
Наконец, следует помнить о гиперпараметрах алгоритма. Вот некоторые
из наиболее распространенных:
  размер популяции;
  частота скрещивания;
  частота мутаций;
  максимальное количество поколений;
  другие условия остановки;
  элитизм (использовать или нет, какого размера).
Мы можем начать со значений, кажущихся разумными, а затем настроить
их, как поступаем с гиперпараметрами любого другого алгоритма оптимизации и обучения.

58  Основные компоненты генетических алгоритмов
Если все это кажется вам неподъемным, не паникуйте! В следующих главах
мы снова и снова будем проделывать все эти действия для разного рода задач. А дочитав книгу до конца, вы сможете самостоятельно принимать такие
решения.

Резюме
В этой главе мы познакомились с общей структурой генетического алгоритма. Затем мы рассмотрели детали: создание популяции, вычисление функции приспособленности, применение генетических операторов и проверку
условий остановки.
Далее обсудили различные методы отбора, в т. ч. правило рулетки, стохас­
тическую универсальную выборку, ранжированный отбор, масштабирование
приспособленности и турнирный отбор, и рассказали, чем они отличаются
друг от друга.
После этого мы рассмотрели несколько методов скрещивания: одноточечное, двухточечное и k-точечное, а также упорядоченное и смешением.
Мы также познакомились с различными методами мутации: инвертирование бита, обмен, обращение и перетасовка.
Затем были представлены вещественные генетические алгоритмы со
свойственными им специальными способами кодирования хромосом и генетическими операторами скрещивания и мутации.
Мы также поговорили о концепциях элитизма, образования ниш и разделения ресурсов в генетических алгоритмах.
И напоследок перечислили, что нужно сделать, чтобы применить к задаче
генетический алгоритм, эту процедуру мы будем повторять в книге многократно.
В следующей главе начнется интересное – программирование на Python!
Мы познакомимся с каркасом эволюционных вычислений DEAP – эффективным инструментом применения генетических алгоритмов к широкому кругу
задач. DEAP будет использоваться нами при разработке Python-программ
для решения различных проблем.

Для дальнейшего чтения
За дополнительными сведениями обращайтесь к главе 8 «Генетические алгоритмы» книги Prateek Joshi «Artificial Intelligence with Python», доступной
по адресу https://subscription.packtpub.com/book/big_data_and_business_intelligence/9781786464392/8.

ЧАСТЬ

II
РЕШЕНИЕ ЗАДАЧ
С ПО­М ОЩЬЮ
ГЕНЕТИЧЕСКИХ
АЛГОРИТМОВ

В этой части мы займемся применением генетических алгоритмов
на Python к решению различных практических задач

Глава

3
Каркас DEAP

В этой главе, как и было обещано, начнется интересное! Мы познакомимся
с DEAP – мощным и гибким каркасом эволюционных вычислений для
решения практических задач с по­мощью генетических алгоритмов. После
крат­кого введения мы представим два главных модуля – creator и toolbox –
и научимся создавать различные компоненты генетического алгоритма. Затем напишем программу для решения задачи OneMax – своего рода «Hello
World» в мире генетических алгоритмов. После этого мы покажем более короткий вариант той же программы, в котором используются встроенные
в каркас алгоритмы. А под конец главы мы припасли самое увлекательное –
эксперименты с различными настройками созданных генетических алгоритмов и выяснение того, на что они влияют.
К концу главы вы:
  познакомитесь с каркасом DEAP и имеющимися в нем модулями для
генетических алгоритмов;
  будете понимать, как работать с модулями creator и toolbox из каркаса
DEAP;
  сможете перевести простую задачу на язык генетического алгоритма;
  научитесь строить решение в виде генетического алгоритма с по­
мощью каркаса DEAP;
  будете знать, как использовать встроенные в DEAP алгоритмы для создания лаконичного кода;
  решите задачу OneMax с по­мощью генетического алгоритма и каркаса
DEAP;
  научитесь экспериментировать с параметрами генетических алгоритмов и интерпретировать результаты.

Технические требования
Последние версии DEAP можно использовать с Python 2 и 3. В этой книге
применяется Python 3.7. Дистрибутив самого языка Python можно скачать
с сайта Python Software Foundation по адресу https://www.python.org/downloads/. Дополнительные полезные материалы можно найти по адресу https://
realpython.com/installing-python/.
Каркас DEAP рекомендуется устанавливать с по­мощью программ easy_install или pip, например:

Введение в DEAP  61
pip install deap

Дополнительные сведения смотрите в документации по DEAP по адресу
https://deap.readthedocs.io/en/master/installation.html. Дистрибутив для Conda
имеется по адресу https://anaconda.org/conda-forge/deap.
В книге используются и другие Python-пакеты. В частности, в этой главе
понадобятся пакеты:
  NumPy: http://www.numpy.org/;
  Matplotlib: https://matplotlib.org/;
  Seaborn: https://seaborn.pydata.org/.
Итак, мы готовы к работе с DEAP. В следующих двух разделах рассматриваются самые полезные инструменты и утилиты. Но сначала немного познакомимся с DEAP и разберемся, почему мы выбрали именно этот каркас
для изучения генетических алгоритмов.
Код приведенных в этой главе программ можно найти в репозитории книги на GitHub по адресу https://github.com/PacktPublishing/Hands-On-GeneticAlgorithms-with-Python/tree/master/Chapter03. Чтобы увидеть код в действии,
посмотрите видео по адресу http://bit.ly/3aTym1p.

Введение в DEAP
В предыдущих главах мы видели, что основные идеи генетических алгоритмов и их структура довольно просты, как и большинство генетических операторов. Поэтому вполне посильно разработать программу, реализующую
генетический алгоритм решения конкретной задачи, с нуля.
Однако, как часто бывает при разработке программного обеспечения, использование проверенной специализированной библиотеки может облегчить жизнь. Она помогает создавать решения быстрее и с меньшим числом
ошибок, а также предлагает на выбор много отработанных заготовок, вместо
того чтобы изобретать велосипед.
Для работы с генетическими алгоритмами создан целый ряд каркасов
на Python, например GAFT, Pyevolve и PyGMO. Но, рассмотрев различные
варианты, мы решили остановиться на каркасе DEAP, поскольку он прост
в использовании и предлагает широкий набор функций, поддерживает расширяемость и может похвастаться подробной документацией.
DEAP (сокращение от Distributed Evolutionary Algorithms in Python – распределенные эволюционные алгоритмы на Python) поддерживает быструю
разработку решений с применением генетических алгоритмов и других методов эволюционных вычислений. DEAP предлагает различные структуры
данных и инструменты, необходимые для реализации самых разных решений на основе генетических алгоритмов.
Каркас DEAP был разработан в канадском университете Лаваля в 2009 г.
и предлагается на условиях лицензии GNU Lesser General Public License
(LGPL). Исходный код DEAP доступен по адресу https://github.com/DEAP/deap,
а документация размещена по адресу https://deap.readthedocs.io/en/master/.

62  Каркас DEAP

Использование модуля creator
Мы начнем с рассмотрения модуля DEAP creator. Он используется как метафабрика и позволяет расширять существующие классы, добавляя в них новые
атрибуты. Пусть, например, имеется класс Employee. С по­мощью модуля creator мы можем создать из него класс Developer следующим образом:
from deap import creator
creator.create("Developer", Employee, position = "Developer",
programmingLanguages = set)

Первым аргументом функции create() передается имя нового класса, вторым – существующий класс, подлежащий расширению. Все последующие
аргументы определяют атрибуты нового класса. Если значением аргумента
является класс (например, dict или set), то он будет добавлен в новый класс
как атрибут экземпляра, инициализируемый в конструкторе. Если же это не
класс (а, например, литерал), то он добавляется как атрибут класса (статический).
Таким образом, созданный класс Developer расширяет класс Employee и имеет атрибут класса position, равный строке Developer, и атрибут экземпляра
programmingLanguages типа set, который инициализируется в конструкторе.
Следовательно, новый класс эквивалентен такому:
class Developer(Employee):
position = "Developer"
def __init__(self):
self.programmingLanguages = set()
Этот новый класс существует в контексте модуля creator, поэтому ссылаться на
него следует по имени creator.Developer.
Расширение класса numpy.ndarray – особый случай, который будет рассмотрен
ниже.

При работе с DEAP модуль creator обычно служит для создания классов
Fitness и Individual, используемых в генетических алгоритмах.

Создание класса Fitness
При работе с DEAP значения приспособленности инкапсулированы в классе
Fitness. DEAP позволяет распределять приспособленность по нескольким
компонентам (называемым целями), у каждого из которых есть свой вес.
Комбинация весов определяет поведение, или стратегию приспособления
в конкретной задаче.

Определение стратегии приспособления
Для определения стратегии в состав DEAP входит абстрактный класс base.
Fitness, который содержит кортеж weights. Этому кортежу необходимо при-

Использование модуля creator  63

своить значения, чтобы определить стратегию и сделать класс пригодным
для использования. Для этого мы расширяем базовый класс Fitness с по­
мощью модуля creator так же, как делали это ранее с классом Developer:
creator.create("FitnessMax", base.Fitness, weights=(1.0,))

Получается класс creator.FitnessMax, расширяющий класс base.Fitness,
в котором атрибут класса weights инициализирован значением (1.0,).
Обратите внимание на запятую в конце определения weights, которая присутствует, хотя задан всего один вес. Она необходима, потому что weights – кортеж.

Стратегия этого класса FitnessMax – максимизировать приспособленность
индивидуумов с единственной целью. Если бы нам нужно было минимизировать приспособленность в задаче с одной целью, то для задания соответствующей стратегии можно было бы определить такой класс:
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))

Можно также определить класс для оптимизации сразу нескольких целей
различной важности:
creator.create("FitnessCompound", base.Fitness, weights=(1.0, 0.2, -0.5))

В классе creator.FitnessCompound используется три компоненты приспособ­
ленности с весами 1.0, 0.2 и –0.5. Это означает, что первая и вторая компоненты (цели) максимизируются, а третья минимизируется, причем первая
компонента самая важная, следующей по важности является третья, а последней – вторая.

Хранение значения приспособленности
Если кортеж weights определяет стратегию приспособления, то кортеж values
используется для хранения самих значений функции приспособленности
в базовом классе base.Fitness. Эти значения дает отдельно определяемая
функция, которую обычно называют evaluate(); мы опишем ее ниже в этой
главе. Как и weights, кортеж values содержит по одному значению для каждой
компоненты приспособленности (цели).
Третий кортеж, wvalues, содержит взвешенные значения, полученные перемножением элементов кортежа values и соответственных элементов кортежа
weights. Всякий раз, как устанавливаются значения приспособленности, соответствующие взвешенные значения вычисляются и сохраняются в wvalues.
Они используются при сравнении индивидуумов.
Взвешенные приспособленности можно сравнивать лексикографически
с по­мощью следующих операторов:
>, =,