Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 638984)
Контекстум
Электро-2024

Алгоритмы эволюционной оптимизации. Биологически обусловленные и популяционно-ориентированные подходы к компьютерному интеллекту (6000,00 руб.)

0   0
Первый авторСаймон
ИздательствоМ.: ДМК Пресс
Страниц942
ID794745
АннотацияВ данной книге рассматриваются история, теоретические основы, математический аппарат и программирование алгоритмов эволюционной оптимизации. Рассмотренные алгоритмы включают в себя генетические алгоритмы, генетическое программирование, оптимизацию на основе муравьиной кучи, оптимизацию на основе роя частиц, дифференциальную эволюцию, биогеографическую оптимизацию и многие другие. Издание будет полезно студентам старших курсов, программистам, инженерам, а также всем специалистам, кто интересуется принципами построения различных алгоритмов.
ISBN978-5-97060-812-8
УДК4.421
ББК32.811
Саймон, Д. Алгоритмы эволюционной оптимизации. Биологически обусловленные и популяционно-ориентированные подходы к компьютерному интеллекту / Д. Саймон .— Москва : ДМК Пресс, 2020 .— 942 с. — ISBN 978-5-97060-812-8 .— URL: https://rucont.ru/efd/794745 (дата обращения: 15.06.2024)

Предпросмотр (выдержки из произведения)

Алгоритмы_эволюционной_оптимизации._Биологически_обусловленные_и_популяционно-ориентированные_подходы_к_компьютерному_интеллекту.pdf
УДК 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

Облако ключевых слов *


* - вычисляется автоматически
Периодика по подписке
Антиплагиат система Руконтекст