Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Биологически обусловленные и популяционно-ориентированные подходы к компьютерному интеллекту
Покупка
Артикул: 739785.02.99
Доступ онлайн
1 999 ₽
В корзину
В данной книге рассматриваются история, теоретические основы, математический аппарат и программирование алгоритмов эволюционной оптимизации. Рассмотренные алгоритмы включают в себя генетические алгоритмы, генетическое программирование, оптимизацию на основе муравьиной кучи, оптимизацию на основе роя частиц, дифференциальную эволюцию, биогеографическую оптимизацию и многие другие. Издание будет полезно студентам старших курсов, программистам, инженерам, а также всем специалистам, кто интересуется принципами построения различных алгоритмов.
Саймон, Д. Алгоритмы эволюционной оптимизации : практическое руководство / Д. Саймон ; пер. с англ. А. В. Логунова. - Москва : ДМК Пресс, 2020. - 1002 с. - ISBN 978-5-97060-707-7. - Текст : электронный. - URL: https://znanium.com/catalog/product/1210621 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Дэн Саймон

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

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

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

Оглавление  11

13.1.2. Вычисление статистических показателей .................................................................... 437

13.2. Алгоритмы оценивания вероятностных распределений на основе 
статистических показателей первого порядка .........................................................438
13.2.1. Алгоритм одномерного маржинального распределения (UMDA) ...................... 438
13.2.2. Компактный генетический алгоритм (cGA) .................................................................. 441
13.2.3. Популяционное инкрементное самообучение (PBIL) ............................................. 445

13.3. Алгоритмы оценивания вероятностных распределений на основе 
статистических показателей второго порядка ..........................................................449
13.3.1. Максимизация взаимной информации для кластеризации входных  
данных (MIMIC) .......................................................................................................................... 450

13.3.2. Объединение оптимизаторов с деревьями взаимной информации  
(COMIT) ......................................................................................................................................... 456

13.3.3. Алгоритм двумерного маржинального распределения (BMDA)  ........................ 463

13.4. Алгоритмы оценивания многомерных вероятностных распределений ...... 467

13.4.1. Расширенный компактный генетический алгоритм (ECGA) .................................. 467
13.4.2. Другие алгоритмы оценивания многомерных вероятностных  
распределений .......................................................................................................................... 471

13.5. Алгоритмы оценивания непрерывных вероятностных распределений ......471

13.5.1. Алгоритм одномерного маржинального непрерывного распределения ........ 473
13.5.2. Непрерывное популяционное инкрементное самообучение ............................. 474

13.6. Заключение ...........................................................................................................................478
Задачи ................................................................................................................................................481

Письменные упражнения.................................................................................................................. 481
Компьютерные упражнения ............................................................................................................. 482

Глава 14. Биогеографическая оптимизация ..................................................................484

Краткий обзор главы ...................................................................................................................485
14.1. Биогеография .......................................................................................................................485

Математическая модель биогеографии ...................................................................................... 488

14.2. Биогеография как процесс оптимизации .................................................................492
14.3. Биогеографическая оптимизация ................................................................................495
14.4. Расширения алгоритма биогеографической оптимизации...............................500

14.4.1. Миграционные кривые ........................................................................................................ 501
14.4.2. Смешанная миграция ........................................................................................................... 503
14.4.3. Другие подходы к биогеографической оптимизации............................................. 505
14.4.4. Алгоритм биогеографической оптимизации и генетические алгоритмы ....... 508

14.5. Заключение ...........................................................................................................................510
Задачи ................................................................................................................................................516

Письменные упражнения.................................................................................................................. 516
Компьютерные упражнения ............................................................................................................. 517

Глава 15. Культурные алгоритмы ....................................................................................519

Краткий обзор главы ...................................................................................................................520

 Оглавление

15.1. Сотрудничество и конкуренция ....................................................................................521

Бар «Эль Фароль» ................................................................................................................................. 522
Другие примеры ................................................................................................................................... 523

15.2. Пространства убеждений в культурных алгоритмах ...........................................525
15.3. Культурно-эволюционное программирование ......................................................529
15.4. Адаптивно-культурная модель ......................................................................................532
15.5. Заключение ...........................................................................................................................541
Задачи ................................................................................................................................................542

Письменные упражнения.................................................................................................................. 542
Компьютерные упражнения ............................................................................................................. 543

Глава 16. Оппозиционное самообучение .......................................................................544

Краткий обзор главы ...................................................................................................................545
16.1. Определения и идеи оппозиции ..................................................................................545

16.1.1. Отраженные противоположности и противоположности по модулю .............. 545
16.1.2. Частичные противоположности ....................................................................................... 547
16.1.3. Противоположности 1-го рода и противоположности 2-го рода ...................... 548
16.1.4. Квазипротивоположности и сверхпротивоположности ........................................ 550

16.2. Алгоритмы оппозиционной эволюции ......................................................................551
16.3. Оппозиционные вероятности ........................................................................................558
16.4. Коэффициент перескока ..................................................................................................563
16.5. Оппозиционная комбинаторная оптимизация.......................................................565
16.6. Дуальное самообучение ..................................................................................................569
16.7. Заключение ...........................................................................................................................571
Задачи ................................................................................................................................................572

Письменные упражнения.................................................................................................................. 572
Компьютерные упражнения ............................................................................................................. 573

Глава 17. Другие эволюционные алгоритмы .................................................................574

17.1. Табуированный поиск .......................................................................................................575
17.2. Алгоритм искусственного косяка рыб ........................................................................576

17.2.1. Случайное поведение ........................................................................................................... 577
17.2.2. Поведение преследования ................................................................................................. 578
17.2.3. Роевое поведение .................................................................................................................. 578
17.2.4. Поисковое поведение .......................................................................................................... 579
17.2.5. Скачущее поведение ............................................................................................................. 579
17.2.6. Резюме алгоритма искусственного косяка рыб ......................................................... 580

17.3. Оптимизатор на основе группового поиска ............................................................581
17.4 . Алгоритм перемешанных лягушачьих прыжков ...................................................585
17.5. Светлячковый алгоритм .................................................................................................... 587
17.6. Оптимизация на основе бактериальной кормодобычи ......................................589
17.7. Алгоритм искусственной пчелиной семьи .................................................................593

Оглавление  13

17.8. Алгоритм гравитационного поиска ..............................................................................596
17.9. Поиск гармонии ...................................................................................................................598
17.10. Оптимизация по принципу учитель–ученик .........................................................601
17.11. Заключение .........................................................................................................................605
Задачи ................................................................................................................................................ 607

Письменные упражнения.................................................................................................................. 607
Компьютерные упражнения ............................................................................................................. 608

Часть IV. Специальные типы оптимизационных задач ...........................................609

Глава 18. Комбинаторная оптимизация .........................................................................610

Краткий обзор главы ...................................................................................................................611
18.1. Задача коммивояжера ......................................................................................................612
18.2. Инициализация задачи коммивояжера ....................................................................614

18.2.1. Инициализация на основе ближайшего соседа ........................................................ 614
18.2.2. Инициализация на основе кратчайшего ребра ........................................................ 616
18.2.3. Инициализации на основе вставки ................................................................................ 618
18.2.4. Стохастическая инициализация ....................................................................................... 620

18.3. Представления задачи коммивояжера и скрещивание .....................................621

18.3.1. Представление в виде пути ............................................................................................... 621
18.3.2. Представление в виде смежности .................................................................................. 626
18.3.3. Порядковое представление ............................................................................................... 630
18.3.4. Матричное представление ................................................................................................. 631

18.4. Мутация в задаче коммивояжера ................................................................................635

18.4.1. Инверсия ................................................................................................................................... 635
18.4.2. Вставка ....................................................................................................................................... 635
18.4.3. Перенесение ............................................................................................................................ 636
18.4.4. Взаимообмен ........................................................................................................................... 636

18.5. Эволюционный алгоритм для задачи коммивояжера .........................................636
18.6. Задача раскраски графа ..................................................................................................643
18.7. Заключение ...........................................................................................................................648
Задачи ................................................................................................................................................650

Письменные упражнения.................................................................................................................. 650
Компьютерные упражнения ............................................................................................................. 651

Глава 19. Ограниченная оптимизация ............................................................................652

Краткий обзор главы ...................................................................................................................653
19.1. Подходы на основе штрафной функции ..................................................................654

19.1.1. Методы внутренней точки .................................................................................................. 655
19.1.2. Внешние методы .................................................................................................................... 657

19.2. Популярные методы обработки ограничений ........................................................660

19.2.1. Статические штрафные методы ....................................................................................... 660

 Оглавление

19.2.2. Превосходство допустимых точек .................................................................................. 660
19.2.3. Эклектичный эволюционный алгоритм ........................................................................ 661
19.2.4. Коэволюционные штрафы .................................................................................................. 662
19.2.5. Динамические штрафные методы .................................................................................. 664
19.2.6. Адаптивные штрафные методы ........................................................................................ 667
19.2.7. Сегрегированный генетический алгоритм ................................................................... 668
19.2.8. Самоадаптивная формулировка приспособленности ............................................ 668
19.2.9. Самоадаптивная штрафная функция ............................................................................. 670
19.2.10. Адаптивная сегрегационная обработка ограничений ......................................... 672
19.2.11. Поведенческая память ...................................................................................................... 673
19.2.12. Стохастическое ранжирование ...................................................................................... 675
19.2.13. Нишевой штрафной метод .............................................................................................. 676

19.3. Специальные представления и специальные операторы ................................. 677

19.3.1. Специальные представления ............................................................................................ 678
19.3.2. Специальные операторы .................................................................................................... 681
19.3.3. Алгоритм Genocop .................................................................................................................. 683
19.3.4. Алгоритм Genocop II .............................................................................................................. 684
19.3.5. Алгоритм Genocop III ............................................................................................................ 684

19.4. Другие подходы к ограниченной оптимизации ....................................................686

19.4.1. Культурные алгоритмы ........................................................................................................ 687
19.4.2. Многокритериальная оптимизация ................................................................................ 687

19.5. Ранжирование кандидатных решений ......................................................................688

19.5.1. Ранжирование по максимальному нарушению ограничений ............................. 689
19.5.2. Ранжирование по порядку следования ограничений ............................................. 689
19.5.3. Метод сравнений 𝝐-уровня ................................................................................................ 690

19.6. Сравнение методов обработки ограничений .........................................................691
19.7. Заключение ...........................................................................................................................695
Задачи ................................................................................................................................................699

Письменные упражнения.................................................................................................................. 699
Компьютерные упражнения ............................................................................................................. 701

Глава 20. Многокритериальная оптимизация ...............................................................703

Краткий обзор главы ...................................................................................................................705
20.1. Оптимальность по Парето ...............................................................................................705
20.2. Цели многокритериальной оптимизации .................................................................711

20.2.1. Гиперобъем ............................................................................................................................... 715
20.2.2. Относительный охват ........................................................................................................... 718

20.3. Непаретоориентированные эволюционные алгоритмы ....................................719

20.3.1. Методы агрегирования ........................................................................................................ 719
20.3.2. Генетический алгоритм с векторным оцениванием (VEGA) ................................. 722
20.3.3. Лексикографическое упорядочение .............................................................................. 724
20.3.4. Метод 𝝐-ограничений ........................................................................................................... 724
20.3.5. Гендерные подходы .............................................................................................................. 726

Оглавление  15

20.4. Паретоориентированные эволюционные алгоритмы .........................................728

20.4.1. Эволюционные многокритериальные оптимизаторы ............................................. 729
20.4.2. 𝝐-ориентированный многокритериальный эволюционный  
алгоритм (𝝐-MOEA) ................................................................................................................... 731

20.4.3. Генетический алгоритм с сортировкой по уровню  
недоминирования (NSGA) ..................................................................................................... 734

20.4.4. Многокритериальный генетический алгоритм (MOGA) .......................................... 737
20.4.5. Генетический алгоритм с нишированием по Парето (NPGA) ............................... 739
20.4.6. Эволюционный алгоритм с расчетом силы Парето (SPEA) ................................... 740
20.4.7. Эволюционная стратегия с архивированием по Парето (PAES) ......................... 749

20.5. Многокритериальная биогеографическая оптимизация ...................................750

20.5.1. Биогеографическая оптимизация с векторным оцениванием ............................ 750
20.5.2. Алгоритм BBO с сортировкой по уровню недоминирования .............................. 751
20.5.3. Алгоритм ВВО с нишированием по Парето ................................................................ 752
20.5.4. Алгоритм ВВО с расчетом силы Парето ........................................................................ 754
20.5.5. Симуляции многокритериальной биогеографической оптимизации .............. 755

20.6. Заключение ........................................................................................................................... 757
Задачи ................................................................................................................................................761

Письменные упражнения.................................................................................................................. 761
Компьютерные упражнения ............................................................................................................. 763

Глава 21. Дорогостоящие, шумные и динамические функции  
приспособленности ...........................................................................................................765

Краткий обзор главы ...................................................................................................................766
21.1. Дорогостоящие функции приспособленности........................................................ 767

21.1.1. Аппроксимирование функции приспособленности................................................. 770
21.1.2. Аппроксимирование трансформированных функций ............................................ 783
21.1.3. Как применять аппроксимации приспособленности в эволюционных 
алгоритмах .................................................................................................................................. 785

21.1.4. Множественные модели ...................................................................................................... 789
21.1.5. Переподгонка .......................................................................................................................... 792
21.1.6. Оценивание аппроксимационных методов ................................................................ 793

21.2. Динамические функции приспособленности .........................................................796

21.2.1. Предсказательный эволюционный алгоритм ............................................................. 799
21.2.2. Иммигрантские схемы ......................................................................................................... 801
21.2.3. Подходы на основе памяти ............................................................................................... 807
21.2.4. Оценивание результативности динамической оптимизации .............................. 809

21.3. Шумные функции приспособленности ......................................................................810

21.3.1. Многократное взятие проб ................................................................................................ 812
21.3.2. Оценивание приспособленности .................................................................................... 816
21.3.3. Эволюционный алгоритм на основе фильтра Калмана ......................................... 816

21.4. Заключение ...........................................................................................................................819
Задачи ................................................................................................................................................822

 Оглавление

Письменные упражнения.................................................................................................................. 822
Компьютерные упражнения ............................................................................................................. 824

Часть V. Приложения .....................................................................................................825

Приложение А. Несколько практических советов ........................................................826

A.1. Проверка на наличие ошибок .........................................................................................826
A.2. Эволюционные алгоритмы являются стохастическими ........................................ 827
А.3. Небольшие изменения могут иметь большой эффект ..........................................828
A.4. Большие изменения могут иметь малый эффект ....................................................828
A.5. Популяции имеют много информации ........................................................................829
A.6. Поощрение многообразия ................................................................................................829
A.7. Использование специфичной на конкретной задаче информации ................830
A.8. Сохраняйте свои результаты как можно чаще .........................................................830
A.9. Понимание статистической значимости .....................................................................830
A.10. Пишите хорошо ...................................................................................................................831
A.11. Акцент на теории ................................................................................................................831
A.12. Акцент на практике............................................................................................................832

Приложение B. Теорема об отсутствии бесплатных обедов и тестирование 
результативности ...............................................................................................................833

B.1. Теорема об отсутствии бесплатных обедов ...............................................................834
B.2. Тестирование результативности .....................................................................................844

B.2.1. Преувеличения на основе результатов симуляций .................................................... 845
B.2.2. Как отчитываться (и как не отчитываться) о результатах симулирования ....... 848
B.2.3. Случайные числа ....................................................................................................................... 856
В.2.4. t-тесты ............................................................................................................................................ 859
B.2.5. F-тесты ........................................................................................................................................... 866

B.3. Заключение .............................................................................................................................872

Приложение C. Эталонные оптимизационные функции .............................................873

С.1. Неограниченные эталоны .................................................................................................874

С.1.1. Сферическая функция ............................................................................................................ 874
С.1.2. Функция Экли  ........................................................................................................................... 875
С.1.3. Тестовая функция Экли .......................................................................................................... 876
С.1.4. Функция Розенброка ............................................................................................................... 876
C.1.5. Функция Флетчера ................................................................................................................... 877
С.1.6. Функция Гриванка .................................................................................................................... 878
C.1.7. Штрафная функция #1 ............................................................................................................ 879
C.1.8. Штрафная функция #2 ............................................................................................................ 879
С. 1.9. Квартичная функция .............................................................................................................. 880
C.1.10. Десятистепенная функция .................................................................................................. 881
С.1.11. Функция Растригина ............................................................................................................. 882

Оглавление  17

С.1.12. Функция двойной суммы Швефеля ................................................................................ 883
С.1.13. Функция max Швефеля ........................................................................................................ 883
С.1.14. Функция Швефеля абсолютной величины .................................................................. 884
С.1.15. Синусоидальная функция Швефеля ............................................................................... 885
С.1.16. Ступенчатая функция ............................................................................................................ 885
С.1.17. Функция абсолютной величины ....................................................................................... 886
C.1.18. Функция лисьей норы Шекеля ......................................................................................... 887
С.1.19. Функция Михалевича ........................................................................................................... 887
С.1.20. Функция синусоидальной огибающей .......................................................................... 888
С.1.21. Функция в форме упаковки для яиц .............................................................................. 889
C.1.22. Функция Вейерштрасса ....................................................................................................... 889

С.2. Ограниченные эталоны ......................................................................................................890

С.2.1. Функция С01 ............................................................................................................................... 891
С.2.2. Функция С02 ............................................................................................................................... 891
С.2.3. Функция С03 ............................................................................................................................... 892
С.2.4. Функция С04   ............................................................................................................................ 892
С.2.5. Функция С05 ............................................................................................................................... 892
С.2.6. Функция С06 ............................................................................................................................... 893
С.2.7. Функция С07 ................................................................................................................................ 893
С.2.8. Функция С08 ............................................................................................................................... 893
С.2.9. Функция С09 ............................................................................................................................... 894
С.2.10. Функция С10 ............................................................................................................................ 894
С.2.11. Функция C11 ............................................................................................................................ 894
С.2.12. Функция С12 ............................................................................................................................ 895
С.2.13. Функция С13 ............................................................................................................................ 895
С.2.14. Функция С14 ............................................................................................................................ 895
С.2.15. Функция С15 ............................................................................................................................ 896
С.2.16. Функция С16 ............................................................................................................................ 896
С.2.17. Функция С17 ............................................................................................................................. 897
С.2.18. Функция С18 ............................................................................................................................ 897
C.2.19. Резюме ограниченных эталонов ..................................................................................... 897

C.3. Многокритериальные эталоны ........................................................................................898

C.3.1. Неограниченная многокритериальная оптимизационная задача 1 ................... 899
C.3.2. Неограниченная многокритериальная оптимизационная задача 2 ................... 900
C.3.3. Неограниченная многокритериальная оптимизационная задача 3  .................. 901
C.3.4. Неограниченная многокритериальная оптимизационная задача 4 ................... 901
C.3.5. Неограниченная многокритериальная оптимизационная задача 5 ................... 902
C.3.6. Неограниченная многокритериальная оптимизационная задача 6 ................... 903
C.3.7. Неограниченная многокритериальная оптимизационная задача 7 .................... 904
C.3.8. Неограниченная многокритериальная оптимизационная задача 8 ................... 904
C.3.9. Неограниченная многокритериальная оптимизационная задача 9 ................... 905
C.3.10. Неограниченная многокритериальная оптимизационная задача 10 .............. 906

С.4. Динамические эталоны ...................................................................................................... 907

 Оглавление

C.4.1. Полное описание динамического эталона .................................................................... 907
C.4.2. Упрощенное описание динамического эталона .......................................................... 914

С.5. Шумные эталоны ...................................................................................................................915
C.6. Задачи коммивояжера ........................................................................................................915
С.7. Устранение смещения в поисковом пространстве ..................................................919

С.7.1. Сдвиги ............................................................................................................................................ 919
C.7.2. Матрицы поворота ................................................................................................................... 921

Список литературы ............................................................................................................925

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

Благодарности

Хотелось бы поблагодарить всех тех, кто оказывал финансовую поддержку моих исследований по эволюционной оптимизации два десятилетия, в течение которых я участвую в этой увлекательной области 
исследования: Хоссни Эль-Шарифа из группы по системной интеграции компании TRW, Дорин Драготониу из подразделения по системам 
безопасности на транспорте компании TRW, Санджай Гарга и Дональда 
Саймона из подразделения управления и динамики имени Джона Гленна в НАСА, Димитра Филева из  Форд Мотор Компани, Брайана Дэвиса 
и Уильяма Смита из Кливленд Клиник, Национальный научный фонд и 
государственный университет Кливленда. Хотел бы также поблагодарить студентов и коллег, которые работали со мной и публиковали статьи по проблематике эволюционных алгоритмов: Джеффа Абеля, Тавой 
Ду, Мехмета Эргецера, Брент Гарднер, Бориса Игельника, Пола Лозового, Хайпинг Ма, Берни Монтавона, Мирелу Оврейю, Рик Рарика, Ганса 
Рихтера, Дэвида Сейди, Сергея Саморезова, Нину Шайдеггер, Арпита 
Шаха, Стива Затмари, Джорджа Томаса, Оливера Тибра, Тона ван ден 
Богерта, Аруна Венкатесана и Тима Уилмота. Наконец, хотел бы поблагодарить всех тех, кто читал предварительные проекты этого материала 
и сделал ряд полезных предложений для его улучшения: Эмиль Аартс, 
Дэна Эшлока, Форреста Беннета, Ханса-Георга Байера, Мориса Клера, 
Карлоса Коэльо Коэльо, Калянмоя Деба, Гаца Эйбена, Цзинь Хао Као, 
Яосю Джин, Педро Ларранага, Махамеда Омрана, Кеннета В. Прайса, 
Ханса-Пола Швефеля, Томаса Штюцле, Хамида Тизуша, Даррелла Уитли, а также трех анонимных рецензентов оригинального предложения 
данной книги. Эти рецензенты не обязательно одобряют данную книгу, 
но она стала намного лучше благодаря их предложениям и комментариям.

Дэн Саймон

Предисловие от издательства

Отзывы и пожелания

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

Список опечаток

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

Нарушение авторских прав

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

Аббревиатуры

ABC
artificial bee colony
искуственная пчелиная семья

ACM
adaptive cultural model
адаптивная культурная модель

ACO
ant colony optimization
оптимизация на основе муравьиной 
кучи

ACR
acronym
аббревиатура

ACS
ant colony system
система муравьиной кучи

ADF
automatically defined 
function
автоматически определяемая функция

AFSA
artificial fish swarm 
algorithm
алгоритм по методу искусственного 
косяка рыб

ANTS
approximated nondeterministic tree search
аппроксимированный недетерменированный древовидный поиск

AS
ant system
муравьиная система

ASCHEA
adaptive segregational 
constraint handling 
evolutionary algorithm

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

BBO
biogeography-based 
optimization
биогеографическая оптимизация

BFOA
bacterial foraging 
optimization algorithm
алгоритм оптимизации на основе 
бактериальной кормодобычи 

BMDA
bivariate marginal 
distribution algorithm
алгоритм двумерного маржинального распределения

BOA
Bayesian optimization 
algorithm
алгоритм байесовой оптимизации

CA
cultural algorithm
культурный алгоритм

CAEP
cultural algorithm-influenced 
evolutionary programming
эволюционное программирование в 
условиях культурного алгоритма

CE
cross entropy
перекрестная энтропия

CEC
Congress on Evolutionary 
Computation
Конгресс по эволюционным вычислениям

CDF 
cumulative distribution 
function
кумулятивная функция распределения

cGA 
compact genetic algorithm
компактный генетический алгоритм

 Аббревиатуры

CMA-ES 
covariance matrix 
adaptation evolution 
strategy

ковариационно-матричная 
адаптивная эволюционная стратегия

CMSA-ES 
covariance matrix selfadaptive evolution strategy
ковариационно-матричная самоадаптивная эволюционная стратегия

COMIT 
combining optimizers with 
mutual information trees
объединение оптимизаторов с деревьями взаимной информации

CX 
cycle crossover
цикличное скрещивание

DACE 
design and analysis of 
computer experiments
проектирование и анализ компьютерных экспериментов

DAFHEA 
dynamic approximate fitness 
based hybrid evolutionary 
algorithm

гибридный эвалюционный алгоритм на основе динамической приближенной приспособленнос ти

DE 
differential evolution
дифференциальная эволюция

DEMO 
diversity evolutionary multiobjective optimizer
диверсифицирующий эволюционный 
многокритериальный оптимизатор 

-MOEA 
-based multi-objective 
evolutionary algorithm
-ориентированный многокритериальный эволюционный алгоритм

EA 
evolutionary algorithm
эволюционный алгоритм

EBNA 
estimation of Bayesian 
networks algorithm
алгоритм оценивания байесовой 
сети

ECGA 
extended compact genetic 
algorithm
расширенный компактный генетический алгоритм

EDA 
estimation of distribution 
algorithm
алгоритм оценивания вероятностного распределения

EGNA 
estimation of Gaussian 
network algorithm
алгоритм оценивания гауссовой 
сети

EMNA 
estimation of multivariate 
normal algorithm
алгоритм оценивания многомерных 
нормальных величин

EP 
evolutionary programming
эволюционное программирование 

ES 
evolution strategy
эволюционная стратегия 

FDA 
factorized distribution 
algorithm
алгоритм факторизованного распределения

FIPS 
fully informed particle 
swarm
частично информированный рой 
частиц

Аббревиатуры  23

FSM 
finite state machine
конечный автомат, или машина с 
конечным числом состояний

GA 
genetic algorithm
генетический алгоритм

GENOCOP genetic algorithm for 
numerical optimization of 
constrained problems

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

GOM 
generalized other model
обобщенная другая модель

GP 
genetic programming, or 
genetic program
генетическое программирование 
или генетическая программа

GSA 
gravitational search 
algorithm
гравитационный поисковый алгоритм

GSO 
group search optimizer
оптимизатор на основе группового 
поиска

GSO 
Glowworm search 
optimization
светлячковая поисковая оптимизация

HBA 
honey bee algorithm
алгоритм на основе медоносной 
пчелы

hBOA 
hierarchical Bayesian 
optimization algorithm
иерархический байесовский оптимизационный алгоритм

HCwL 
hill climbing with learning
восхождение к вершине холма с 
самообучением

HLGA 
Hajela-Lin genetic algorithm
генетический алгоритм Хаджела-Лин

HS 
harmony search
поиск гармонии

HSI 
habitat suitability index
индекс пригодности естественной 
среды обитания

IDEA
iterated density estimation 
algorithm
алгоритм итерированного оценивания плотности верояности

IDEA 
infeasibility driven 
evolutionary algorithm
эволюционный алгоритм, управляемый невыполнимостью

IUMDA 
incremental univariate 
marginal distribution 
algorithm

инкрементный алгоритм одномерного маржинального распределения

MMAS 
max-min ant system
минимаксная муравьиная система 

MMES 
multimembered evolution 
strategy
многочленная эволюционная стратегия

 Аббревиатуры

MIMIC 
mutual information 
maximization for input 
clustering

максимизация взаимной информации для кластеризации входных 
данных

MOBBO 
multi-objective 
biogeography-based 
optimization

многокритериальная биогеографическая оптимизация 

MOEA 
multi-objective evolutionary 
algorithm
многокритериальный эволюционный алгоритм

MOGA 
multi-objective genetic 
algorithm
многокритериальный генетичес кий 
алгоритм

MOP 
multi-objective optimization 
problem
задача многокритериальной оптимизации

MPM 
marginal product model
модель маржинального продукта

N(μ, σ2) 
normal PDF with a mean μ 
and a variance σ2
нормальная функция плотности 
вероятности со средним значением 
и дисперсией

N(μ, ∑) 
multidimensional normal 
PDF with mean μ and 
covariance ∑

многомерная нормальная функция 
плотности вероятности со средним 
значением и ковариацией

NFL 
no free lunch
никаких бесплатных обедов

NPBBO 
niched Pareto biogeographybased optimization
алгоритм биогеографической 
оптимизации с нишированием по 
Парето

NPGA 
niched Pareto genetic 
algorithm
генетический алгоритм с нишированием по Парето

NPSO 
negative reinforcement 
particle swarm optimization
оптимизация на основе роя час тиц с 
отрицательным подкреп лением

NSBBO 
nondominated sorting 
biogeography-based 
optimization

алгоритм биогеографической оптимизации с сортировкой по уровню 
недоминирования

NSGA 
nondominated sorting 
genetic algorithm
генетический алгоритм с сортировкой по уровню недоминирования

OBBO 
oppositional biogeographybased optimization
алгоритм оппозиционно-биогеографической оптимизации 

OBL 
opposition-based learning
оппозиционное самообучение

OBX 
order-based crossover
реорганизующее скрещивание 

OX 
order crossover
упорядоченное скрещивание

Доступ онлайн
1 999 ₽
В корзину