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

Дэн Саймон

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

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

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

 Оглавление

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

 Оглавление

Письменные упражнения.................................................................................................................. 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.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