Алгоритмы эволюционной оптимизации

Дэн Саймон
Алгоритмы 
эволюционной 
оптимизации
Биологически обусловленные  
и популяционно-ориентированные подходы  
к компьютерному интеллекту

EVOLUTIONARY
OPTIMIZATION
ALGORITHMS
Biologically-Inspired  
and Population-Based Approaches  
to Computer Intelligence
Dan Simon
Cleveland State University

Москва, 2020
Дэн Саймон
Перевод с английского Логунов А. В.
АЛГОРИТМЫ 
ЭВОЛЮЦИОННОЙ 
ОПТИМИЗАЦИИ 
Биологически обусловленные  
и популяционно-ориентированные подходы  
к компьютерному интеллекту

УДК   004.421
ББК   32.811
С12
С12   Дэн Саймон
Алгоритмы эволюционной оптимизации / пер. с англ. А. В. Логунова. – 
М.: ДМК Пресс, 2020. – 1002 с.: ил.
            ISBN 978-5-97060-707-7
В данной книге рассматриваются история, теоретические основы, 
мате-матический аппарат и программирование алгоритмов эволюционной оптимизации. Рассмотренные алгоритмы включают в себя генетические алгоритмы, генетическое программирование, оптимизацию на 
основе муравьиной кучи, оптимизацию на основе роя частиц, дифференциальную эволюцию, биогеографическую оптимизацию и многие 
другие.
Издание будет полезно студентам старших курсов, программистам, 
инженерам, а также всем специалистам, кто интересуется принципами 
построения различных алгоритмов.
	
	
	
	
	
	
	
	
      УДК  004.421
	
	
	
	
	
	
	
	
       ББК  32.811
Original English language edition published by John Wiley & Sons, Inc. Copyright 
©  2013 by John Wiley & Sons, Inc. All rights reserved. Russian-language edition 
copyright © 2019 by DMK Press. All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в 
какой бы то ни было форме и какими бы то ни было средствами без письменного 
разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку 
вероятность технических ошибок все равно существует, издательство не может 
гарантировать абсолютную точность и правильность приводимых сведений. В 
связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.
ISBN 978-0-470-93741-9 (англ.)                 © John Wiley & Sons, Inc. All rights reserved, 2013
ISBN 978-5-97060-707-7 (рус.)                   © Оформление, перевод на русский язык,
	
              издание, ДМК Пресс, 2020

Оглавление
Благодарности.......................................................................................................................19
Предисловие от издательства............................................................................................20
Аббревиатуры........................................................................................................................21
Часть I. Введение в эволюционную оптимизацию......................................................27
Глава 1. Введение..................................................................................................................28
Обзор главы........................................................................................................................................28
1.1. Терминология..............................................................................................................................29
1.2. Зачем нужна еще одна книга по эволюционным алгоритмам?............................32
1.3. Предварительные условия....................................................................................................34
1.4. Домашние задания...................................................................................................................35
1.5. Обозначения...............................................................................................................................35
1.6. План изложения.........................................................................................................................38
1.7. Учебный курс на основе данной книги............................................................................39
Глава 2. Оптимизация...........................................................................................................41
Краткий обзор главы.......................................................................................................................41
2.1. Неограниченная оптимизация............................................................................................42
2.2. Ограниченная оптимизация.................................................................................................46
2.3. Многокритериальная оптимизация...................................................................................48
2.4. Мультимодальная оптимизация..........................................................................................51
2.5. Комбинаторная оптимизация..............................................................................................52
2.6. Восхождение к вершине холма..........................................................................................54
2.6.1. Смещенные оптимизационные алгоритмы.......................................................................59
2.6.2. Важность симуляций Монте-Карло.......................................................................................60
2.7. Интеллект......................................................................................................................................60
2.7.1. Приспособляемость......................................................................................................................61
2.7.2. Случайность.....................................................................................................................................61
2.7.3. Общение...........................................................................................................................................62
2.7.4. Обратная связь...............................................................................................................................63
2.7.5. Разведывание и эксплуатация.................................................................................................64
2.8. Заключение.................................................................................................................................65
Задачи....................................................................................................................................................66
Письменные упражнения.....................................................................................................................66
Компьютерные упражнения.................................................................................................................68

6    Оглавление
Часть II. Классические эволюционные алгоритмы.....................................................71
Глава 3. Генетические алгоритмы.......................................................................................72
Краткий обзор главы.......................................................................................................................73
3.1. История генетики......................................................................................................................74
3.1.1. Чарльз Дарвин...............................................................................................................................74
3.1.2. Грегор Мендель..............................................................................................................................77
3.2. Генетика........................................................................................................................................79
3.3. История генетических алгоритмов....................................................................................81
3.4. Простой бинарный генетический алгоритм...................................................................85
3.4.1. Генетический алгоритм для проектирования роботов.................................................85
3.4.2. Отбор и скрещивание.................................................................................................................88
3.4.3. Мутации............................................................................................................................................91
3.4.4.  Краткая формулировка генетического алгоритма........................................................93
3.4.5. Регулировочные параметры и примеры генетического алгоритма........................93
3.5. Простой непрерывный генетический алгоритм........................................................100
3.6. Заключение..............................................................................................................................105
Задачи.................................................................................................................................................106
Письменные упражнения.................................................................................................................. 106
Компьютерные упражнения.............................................................................................................. 109
Глава 4. Математические модели генетических алгоритмов......................................111
Краткий обзор главы....................................................................................................................111
4.1. Теория схем..............................................................................................................................112
4.2. Цепи Маркова..........................................................................................................................118
4.3. Обозначения марковской модели для эволюционных алгоритмов.................124
4.4. Марковские модели генетических алгоритмов.........................................................129
4.4.1. Отбор.............................................................................................................................................. 129
4.4.2. Мутации......................................................................................................................................... 130
4.4.3. Скрещивание............................................................................................................................... 132
4.5. Системно-динамические модели генетических алгоритмов............................... 137
4.5.1. Отбор.............................................................................................................................................. 138
4.5.2. Мутации......................................................................................................................................... 140
4.5.3. Скрещивание............................................................................................................................... 143
4.6. Заключение..............................................................................................................................149
Задачи.................................................................................................................................................150
Письменные упражнения.................................................................................................................. 150
Компьютерные упражнения.............................................................................................................. 151
Глава 5. Эволюционное программирование..................................................................153
Краткий обзор главы....................................................................................................................153
5.1. Непрерывное эволюционное программирование..................................................154
5.2. Конечно-автоматная оптимизация.................................................................................159

Оглавление    7
5.3. Дискретное эволюционное программирование.......................................................163
5.4. Дилемма заключенного.......................................................................................................165
5.5. Задача искусственного муравья......................................................................................171
5.6. Заключение..............................................................................................................................176
Задачи................................................................................................................................................. 177
Письменные упражнения.................................................................................................................. 177
Компьютерные упражнения.............................................................................................................. 178
Глава 6. Эволюционные стратегии...................................................................................180
Краткий обзор главы....................................................................................................................181
6.1. Эволюционная стратегия (1 + 1)......................................................................................181
6.2. Правило 1/5: деривация..................................................................................................... 187
6.3. Эволюционная стратегия (μ + 1) .....................................................................................191
6.4. Эволюционные стратегии (μ + 𝝀) и (μ, 𝝀)......................................................................194
Эволюционная стратегия (μ, 𝜿, 𝝀, 𝝆)............................................................................................... 198
6.5. Самоадаптивные эволюционные стратегии...............................................................198
6.6. Заключение..............................................................................................................................205
Задачи.................................................................................................................................................206
Письменные упражнения.................................................................................................................. 206
Компьютерные упражнения.............................................................................................................. 207
Глава 7. Генетическое программирование......................................................................209
Ранние результаты генетического программирования..................................................211
Краткий обзор главы....................................................................................................................212
7.1. Lisp: язык генетического программирования.............................................................213
7.2. Основы генетического программирования.................................................................219
7.2.1. Мера приспособленности....................................................................................................... 220
7.2.2. Критерии останова ................................................................................................................... 221
7.2.3. Множество терминальных символов................................................................................. 221
7.2.4. Множество функций.................................................................................................................. 223
7.2.5. Инициализация........................................................................................................................... 225
7.2.6. Параметры генетической программы............................................................................... 228
7.3. Генетическое программирование: управление объектом за минимальное 
время...........................................................................................................................................233
7.4. Раздувание генетической программы...........................................................................240
7.5. Эволюционирующие сущности помимо компьютерных программ...................243
7.6. Математический анализ генетического программирования...............................246
7.6.1. Определения и обозначения................................................................................................. 247
7.6.2. Отбор и скрещивание.............................................................................................................. 248
7.6.3. Мутация и конечные результаты......................................................................................... 253
7.7. Заключение...............................................................................................................................255
Задачи.................................................................................................................................................258

8    Оглавление
Письменные упражнения.................................................................................................................. 258
Компьютерные упражнения.............................................................................................................. 259
Глава 8. Вариации эволюционных алгоритмов.............................................................263
Краткий обзор главы....................................................................................................................263
8.1. Инициализация.......................................................................................................................264
8.2. Критерии сходимости..........................................................................................................266
8.3. Представление задачи с помощью кода Грея............................................................269
8.4. Элитарность..............................................................................................................................274
8.5. Стационарные и поколенческие алгоритмы...............................................................278
8.6. Популяционное многообразие.........................................................................................279
8.6.1. Дублирующие особи................................................................................................................. 280
8.6.2. Нишевая и видовая рекомбинация................................................................................... 281
8.6.3. Ниширование.............................................................................................................................. 283
8.7. Варианты отбора....................................................................................................................289
8.7.1. Стохастическая универсальная выборка.......................................................................... 290
8.7.2. Избыточный отбор..................................................................................................................... 292
8.7.3. Сигма-шкалирование............................................................................................................... 293
8.7.4. Ранговый отбор........................................................................................................................... 295
8.7.5. Линейное ранжирование........................................................................................................ 297
8.7.6. Турнирный отбор........................................................................................................................ 300
8.7.7. Племенные эволюционные алгоритмы............................................................................. 301
8.8. Рекомбинация.........................................................................................................................303
8.8.1. Одноточечное скрещивание (в бинарных или непрерывных  
эволюционных алгоритмах).................................................................................................. 304
8.8.2. Многоточечное скрещивание (в бинарных или непрерывных  
эволюционных алгоритмах).................................................................................................. 304
8.8.3. Сегментированное скрещивание (в бинарных или непрерывных  
эволюционных алгоритмах).................................................................................................. 304
8.8.4. Равномерное скрещивание (в бинарных или непрерывных  
эволюционных алгоритмах).................................................................................................. 305
8.8.5. Многородительское скрещивание (в бинарных или непрерывных 
эволюционных алгоритмах).................................................................................................. 306
8.8.6. Глобальное однородное скрещивание (в бинарных или непрерывных 
эволюционных алгоритмах).................................................................................................. 306
8.8.7. Перетасованное скрещивание (в бинарных или непрерывных  
эволюционных алгоритмах).................................................................................................. 307
8.8.8. Плоское скрещивание и арифметическое скрещивание (в непрерывных 
эволюционных алгоритмах).................................................................................................. 307
8.8.9. Смешанное скрещивание (в непрерывных эволюционных алгоритмах).......... 308
8.8.10. Линейное скрещивание (в непрерывных эволюционных алгоритмах) .......... 309
8.8.11. Симулированное бинарное скрещивание (в непрерывных эволюционных 
алгоритмах).................................................................................................................................. 309
8.8.12. Резюме......................................................................................................................................... 310

Оглавление    9
8.9. Мутация......................................................................................................................................310
8.9.1. Равномерная мутация с центром в xi(k)........................................................................... 310
8.9.2. Равномерная мутация с центром в середине поисковой области....................... 311
8.9.3. Гауссова мутация с центром в xi(k)..................................................................................... 311
8.9.4. Гауссова мутация с центром в середине поисковой области................................. 312
8.10. Заключение............................................................................................................................312
Задачи.................................................................................................................................................313
Письменные упражнения.................................................................................................................. 313
Компьютерные упражнения.............................................................................................................. 316
Часть III. Более поздние эволюционные алгоритмы...............................................319
Глава 9. Симулированное закаливание...........................................................................320
Краткий обзор главы....................................................................................................................321
9.1. Закалка в природе.................................................................................................................321
9.2. Простой алгоритм симулированного закаливания..................................................323
9.3. Режимы охлаждения.............................................................................................................326
9.3.1. Линейное охлаждение............................................................................................................ 326
9.3.2. Экспоненциальное охлаждение.......................................................................................... 327
9.3.3. Обратное охлаждение............................................................................................................. 327
9.3.4. Логарифмическое охлаждение........................................................................................... 330
9.3.5. Обратное линейное охлаждение........................................................................................ 332
9.3.6. Размерно-зависимое охлаждение..................................................................................... 334
9.4. Вопросы реализации............................................................................................................338
9.4.1. Генерирование кандидатного решения........................................................................... 338
9.4.2. Реинициализация...................................................................................................................... 338
9.4.3. Отслеживание лучшего кандидатного решения........................................................... 339
9.5. Заключение..............................................................................................................................339
Задачи.................................................................................................................................................340
Письменные упражнения.................................................................................................................. 340
Компьютерные упражнения.............................................................................................................. 341
Глава 10. Оптимизация на основе муравьиной кучи....................................................343
Краткий обзор главы....................................................................................................................346
10.1. Модели феромона...............................................................................................................346
10.2. Муравьиная система..........................................................................................................350
10.3. Непрерывная оптимизация.............................................................................................356
10.4. Другие муравьиные системы..........................................................................................360
10.4.1. Минимаксная муравьиная система................................................................................. 360
10.4.2. Система муравьиной кучи................................................................................................... 362
10.4.3. Еще больше муравьиных систем...................................................................................... 366
10.5. Теоретические результаты...............................................................................................368

10    Оглавление
10.6. Заключение............................................................................................................................369
Задачи.................................................................................................................................................371
Письменные упражнения.................................................................................................................. 371
Компьютерные упражнения.............................................................................................................. 373
Глава 11. Оптимизация на основе роя частиц...............................................................374
Краткий обзор главы....................................................................................................................376
11.1. Базовый алгоритм оптимизации на основе роя частиц...................................... 377
Топологии роя частиц.......................................................................................................................... 380
11.2. Ограничение скорости......................................................................................................381
11.3. Коэффициенты инерционного взвешивания и сужения.....................................383
11.3.1. Инерционное взвешивание................................................................................................ 383
11.3.2. Коэффициент сужения.......................................................................................................... 384
11.3.3. Стабильность оптимизации на основе роя частиц.................................................... 387
11.4. Глобальные обновления скорости................................................................................393
11.5. Полноинформированный рой частиц.........................................................................396
11.6. Самообучение на ошибках..............................................................................................400
11.7. Заключение............................................................................................................................403
Задачи.................................................................................................................................................405
Письменные упражнения.................................................................................................................. 405
Компьютерные упражнения.............................................................................................................. 407
Глава 12. Дифференциальная эволюция........................................................................409
Краткий обзор главы....................................................................................................................410
12.1. Базовый алгоритм дифференциальной эволюции................................................410
12.2. Вариации дифференциальной эволюции.................................................................413
12.2.1. Пробные векторы.................................................................................................................... 413
12.2.2. Мутантные векторы................................................................................................................ 416
12.2.3. Корректировка коэффициента шкалирования........................................................... 421
12.3. Дискретная оптимизация.................................................................................................425
12.3.1. Смешанно-целочисленная дифференциальная эволюция................................... 425
12.3.2. Дискретная дифференциальная эволюция.................................................................. 426
12.4. Дифференциальная эволюция и генетические алгоритмы...............................428
12.5. Заключение............................................................................................................................431
Задачи.................................................................................................................................................431
Письменные упражнения.................................................................................................................. 431
Компьютерные упражнения.............................................................................................................. 432
Глава 13. Алгоритмы оценивания вероятностных распределений............................434
Краткий обзор главы....................................................................................................................435
13.1. Алгоритмы оценивания вероятностных распределений: основные  
понятия.......................................................................................................................................436
13.1.1. Простой алгоритм оценивания вероятностного распределения........................ 436