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