УДК 004.421
ББК 32.811
С12
С12 Дэн Саймон
Алгоритмы эволюционной оптимизации / пер. с англ. А. В. Логунова. –
М.: ДМК Пресс, 2020. – 940 с.: ил.
ISBN 978-5-97060-812-8
В данной книге рассматриваются история, теоретические основы,
мате матический аппарат и программирование алгоритмов эволюционной
оптимизации. Рассмотренные алгоритмы включают в себя генетические
алгоритмы, генетическое программирование, оптимизацию на
основе муравьиной кучи, оптимизацию на основе роя частиц, дифференциальную
эволюцию, биогеографическую оптимизацию и многие
другие.
инженерам, а также всем специалистам, кто интересуется принципами
построения различных алгоритмов.
УДК 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 (англ.)
ISBN 978-5-97060-812-8 (рус.)
© John Wiley & Sons, Inc. All rights reserved, 2013
© Оформление, перевод на русский язык,
издание, ДМК Пресс, 2020
Стр.5
Оглавление
Благодарности ......................................................................................................................19
Предисловие от издательства ...........................................................................................20
Аббревиатуры .......................................................................................................................21
Часть I. Введение в эволюционную оптимизацию .....................................................27
Глава 1. Введение .................................................................................................................28
Обзор главы .......................................................................................................................................28
1.1. Терминология .............................................................................................................................29
1.2. Зачем нужна еще одна книга по эволюционным алгоритмам? ...........................32
1.3. Предварительные условия ...................................................................................................34
1.4. Домашние задания ..................................................................................................................35
1.5. Обозначения ..............................................................................................................................35
1.6. План изложения ........................................................................................................................38
1.7. Учебный курс на основе данной книги ...........................................................................39
Глава 2. Оптимизация ..........................................................................................................41
Краткий обзор главы ......................................................................................................................41
2.1. Неограниченная оптимизация ...........................................................................................42
2.2. Ограниченная оптимизация ................................................................................................46
2.3. Многокритериальная оптимизация ..................................................................................48
2.4. Мультимодальная оптимизация .........................................................................................51
2.5. Комбинаторная оптимизация .............................................................................................52
2.6. Восхождение к вершине холма .........................................................................................54
2.6.1. Смещенные оптимизационные алгоритмы....................................................................... 59
2.6.2. Важность симуляций Монте-Карло ...................................................................................... 60
2.7. Интеллект .....................................................................................................................................60
2.7.1. Приспособляемость ..................................................................................................................... 61
2.7.2. Случайность .................................................................................................................................... 61
2.7.3. Общение .......................................................................................................................................... 62
2.7.4. Обратная связь .............................................................................................................................. 63
2.7.5. Разведывание и эксплуатация ................................................................................................ 64
2.8. Заключение ................................................................................................................................65
Задачи ...................................................................................................................................................66
Письменные упражнения..................................................................................................................... 66
Компьютерные упражнения ................................................................................................................ 68
Стр.6
6 Оглавление
Часть II. Классические эволюционные алгоритмы ....................................................71
Глава 3. Генетические алгоритмы ......................................................................................72
Краткий обзор главы ......................................................................................................................73
3.1. История генетики .....................................................................................................................74
3.1.1. Чарльз Дарвин .............................................................................................................................. 74
3.1.2. Грегор Мендель ............................................................................................................................. 77
3.2. Генетика .......................................................................................................................................79
3.3. История генетических алгоритмов ...................................................................................81
3.4. Простой бинарный генетический алгоритм ..................................................................85
3.4.1. Генетический алгоритм для проектирования роботов ................................................ 85
3.4.2. Отбор и скрещивание ................................................................................................................ 88
3.4.3. Мутации ........................................................................................................................................... 91
3.4.4. Краткая формулировка генетического алгоритма ....................................................... 93
3.4.5. Регулировочные параметры и примеры генетического алгоритма ....................... 93
3.5. Простой непрерывный генетический алгоритм .......................................................100
3.6. Заключение .............................................................................................................................105
Задачи ................................................................................................................................................106
Письменные упражнения.................................................................................................................. 106
Компьютерные упражнения ............................................................................................................. 109
Глава 4. Математические модели генетических алгоритмов .....................................111
Краткий обзор главы ...................................................................................................................111
4.1. Теория схем .............................................................................................................................112
4.2. Цепи Маркова .........................................................................................................................118
4.3. Обозначения марковской модели для эволюционных алгоритмов ................124
4.4. Марковские модели генетических алгоритмов ........................................................129
4.4.1. Отбор ............................................................................................................................................. 129
4.4.2. Мутации ........................................................................................................................................ 130
4.4.3. Скрещивание .............................................................................................................................. 132
4.5. Системно-динамические модели генетических алгоритмов .............................. 137
4.5.1. Отбор ............................................................................................................................................. 138
4.5.2. Мутации ........................................................................................................................................ 140
4.5.3. Скрещивание .............................................................................................................................. 143
4.6. Заключение .............................................................................................................................149
Задачи ................................................................................................................................................150
Письменные упражнения.................................................................................................................. 150
Компьютерные упражнения ............................................................................................................. 151
Глава 5. Эволюционное программирование .................................................................153
Краткий обзор главы ...................................................................................................................153
5.1. Непрерывное эволюционное программирование .................................................154
5.2. Конечно-автоматная оптимизация ................................................................................159
Стр.7
Оглавление 7
5.3. Дискретное эволюционное программирование ......................................................163
5.4. Дилемма заключенного ......................................................................................................165
5.5. Задача искусственного муравья .....................................................................................171
5.6. Заключение .............................................................................................................................176
Задачи ................................................................................................................................................ 177
Письменные упражнения.................................................................................................................. 177
Компьютерные упражнения ............................................................................................................. 178
Глава 6. Эволюционные стратегии ..................................................................................180
Краткий обзор главы ...................................................................................................................181
6.1. Эволюционная стратегия (1 + 1) .....................................................................................181
6.2. Правило 1/5: деривация .................................................................................................... 187
6.3. Эволюционная стратегия (μ + 1) ....................................................................................191
6.4. Эволюционные стратегии (μ + 𝝀) и (μ, 𝝀) .....................................................................194
Эволюционная стратегия (μ, 𝜿, 𝝀, 𝝆) .............................................................................................. 198
6.5. Самоадаптивные эволюционные стратегии ..............................................................198
6.6. Заключение .............................................................................................................................205
Задачи ................................................................................................................................................206
Письменные упражнения.................................................................................................................. 206
Компьютерные упражнения ............................................................................................................. 207
Глава 7. Генетическое программирование .....................................................................209
Ранние результаты генетического программирования .................................................211
Краткий обзор главы ...................................................................................................................212
7.1. Lisp: язык генетического программирования ............................................................213
7.2. Основы генетического программирования ................................................................219
7.2.1. Мера приспособленности ...................................................................................................... 220
7.2.2. Критерии останова .................................................................................................................. 221
7.2.3. Множество терминальных символов ................................................................................ 221
7.2.4. Множество функций ................................................................................................................. 223
7.2.5. Инициализация .......................................................................................................................... 225
7.2.6. Параметры генетической программы .............................................................................. 228
7.3. Генетическое программирование: управление объектом за минимальное
время ..........................................................................................................................................233
7.4. Раздувание генетической программы ..........................................................................240
7.5. Эволюционирующие сущности помимо компьютерных программ ..................243
7.6. Математический анализ генетического программирования ..............................246
7.6.1. Определения и обозначения ................................................................................................ 247
7.6.2. Отбор и скрещивание ............................................................................................................. 248
7.6.3. Мутация и конечные результаты ........................................................................................ 253
7.7. Заключение ..............................................................................................................................255
Задачи ................................................................................................................................................258
Стр.8
8 Оглавление
Письменные упражнения.................................................................................................................. 258
Компьютерные упражнения ............................................................................................................. 259
Глава 8. Вариации эволюционных алгоритмов ............................................................263
Краткий обзор главы ...................................................................................................................263
8.1. Инициализация ......................................................................................................................264
8.2. Критерии сходимости .........................................................................................................266
8.3. Представление задачи с помощью кода Грея ...........................................................269
8.4. Элитарность .............................................................................................................................274
8.5. Стационарные и поколенческие алгоритмы ..............................................................278
8.6. Популяционное многообразие ........................................................................................279
8.6.1. Дублирующие особи ................................................................................................................ 280
8.6.2. Нишевая и видовая рекомбинация................................................................................... 281
8.6.3. Ниширование ............................................................................................................................. 283
8.7. Варианты отбора ...................................................................................................................289
8.7.1. Стохастическая универсальная выборка ......................................................................... 290
8.7.2. Избыточный отбор .................................................................................................................... 292
8.7.3. Сигма-шкалирование .............................................................................................................. 293
8.7.4. Ранговый отбор .......................................................................................................................... 295
8.7.5. Линейное ранжирование ....................................................................................................... 297
8.7.6. Турнирный отбор ....................................................................................................................... 300
8.7.7. Племенные эволюционные алгоритмы ............................................................................ 301
8.8. Рекомбинация.........................................................................................................................303
8.8.1. Одноточечное скрещивание (в бинарных или непрерывных
эволюционных алгоритмах) ................................................................................................. 304
8.8.2. Многоточечное скрещивание (в бинарных или непрерывных
эволюционных алгоритмах) ................................................................................................. 304
8.8.3. Сегментированное скрещивание (в бинарных или непрерывных
эволюционных алгоритмах) ................................................................................................. 304
8.8.4. Равномерное скрещивание (в бинарных или непрерывных
эволюционных алгоритмах) ................................................................................................. 305
8.8.5. Многородительское скрещивание (в бинарных или непрерывных
эволюционных алгоритмах) ................................................................................................. 306
8.8.6. Глобальное однородное скрещивание (в бинарных или непрерывных
эволюционных алгоритмах) ................................................................................................. 306
8.8.7. Перетасованное скрещивание (в бинарных или непрерывных
эволюционных алгоритмах) ................................................................................................. 307
8.8.8. Плоское скрещивание и арифметическое скрещивание (в непрерывных
эволюционных алгоритмах) ................................................................................................. 307
8.8.9. Смешанное скрещивание (в непрерывных эволюционных алгоритмах) ......... 308
8.8.10. Линейное скрещивание (в непрерывных эволюционных алгоритмах) ......... 309
8.8.11. Симулированное бинарное скрещивание (в непрерывных эволюционных
алгоритмах) ................................................................................................................................. 309
8.8.12. Резюме ........................................................................................................................................ 310
Стр.9
Оглавление 9
8.9. Мутация .....................................................................................................................................310
8.9.1. Равномерная мутация с центром в xi
(k) .......................................................................... 310
(k) .................................................................................... 311
8.9.2. Равномерная мутация с центром в середине поисковой области....................... 311
8.9.3. Гауссова мутация с центром в xi
8.9.4. Гауссова мутация с центром в середине поисковой области ................................ 312
8.10. Заключение ...........................................................................................................................312
Задачи ................................................................................................................................................313
Письменные упражнения.................................................................................................................. 313
Компьютерные упражнения ............................................................................................................. 316
Часть III. Более поздние эволюционные алгоритмы ..............................................319
Глава 9. Симулированное закаливание ..........................................................................320
Краткий обзор главы ...................................................................................................................321
9.1. Закалка в природе ................................................................................................................321
9.2. Простой алгоритм симулированного закаливания .................................................323
9.3. Режимы охлаждения ............................................................................................................326
9.3.1. Линейное охлаждение ........................................................................................................... 326
9.3.2. Экспоненциальное охлаждение ......................................................................................... 327
9.3.3. Обратное охлаждение ............................................................................................................ 327
9.3.4. Логарифмическое охлаждение........................................................................................... 330
9.3.5. Обратное линейное охлаждение ....................................................................................... 332
9.3.6. Размерно-зависимое охлаждение .................................................................................... 334
9.4. Вопросы реализации ...........................................................................................................338
9.4.1. Генерирование кандидатного решения .......................................................................... 338
9.4.2. Реинициализация ..................................................................................................................... 338
9.4.3. Отслеживание лучшего кандидатного решения .......................................................... 339
9.5. Заключение .............................................................................................................................339
Задачи ................................................................................................................................................340
Письменные упражнения.................................................................................................................. 340
Компьютерные упражнения ............................................................................................................. 341
Глава 10. Оптимизация на основе муравьиной кучи ...................................................343
Краткий обзор главы ...................................................................................................................346
10.1. Модели феромона ..............................................................................................................346
10.2. Муравьиная система .........................................................................................................350
10.3. Непрерывная оптимизация ............................................................................................356
10.4. Другие муравьиные системы .........................................................................................360
10.4.1. Минимаксная муравьиная система ................................................................................ 360
10.4.2. Система муравьиной кучи .................................................................................................. 362
10.4.3. Еще больше муравьиных систем ..................................................................................... 366
10.5. Теоретические результаты ..............................................................................................368
Стр.10
10 Оглавление
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
Оглавление 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
Стр.12
12 Оглавление
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
Оглавление 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
Стр.14
14 Оглавление
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
Оглавление 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
Стр.16
16 Оглавление
Письменные упражнения.................................................................................................................. 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
Оглавление 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
Стр.18
18 Оглавление
C.4.1. Полное описание динамического эталона .................................................................... 907
C.4.2. Упрощенное описание динамического эталона .......................................................... 914
С.5. Шумные эталоны ...................................................................................................................915
C.6. Задачи коммивояжера ........................................................................................................915
С.7. Устранение смещения в поисковом пространстве ..................................................919
С.7.1. Сдвиги ............................................................................................................................................ 919
C.7.2. Матрицы поворота ................................................................................................................... 921
Предметный указатель .....................................................................................................925
Стр.19