Алгоритмы эволюционной оптимизации
Биологически обусловленные и популяционно-ориентированные подходы к компьютерному интеллекту
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Саймон Ден
Перевод:
Логунов А. В.
Год издания: 2020
Кол-во страниц: 1002
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-97060-707-7
Артикул: 739785.02.99
В данной книге рассматриваются история, теоретические основы, математический аппарат и программирование алгоритмов эволюционной оптимизации. Рассмотренные алгоритмы включают в себя генетические алгоритмы, генетическое программирование, оптимизацию на основе муравьиной кучи, оптимизацию на основе роя частиц, дифференциальную эволюцию, биогеографическую оптимизацию и многие другие.
Издание будет полезно студентам старших курсов, программистам, инженерам, а также всем специалистам, кто интересуется принципами построения различных алгоритмов.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
- 09.03.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Алгоритмы эволюционной оптимизации Алгоритмы эволюционной оптимизации Дэн Саймон
Дэн Саймон Алгоритмы эволюционной оптимизации Биологически обусловленные и популяционно-ориентированные подходы к компьютерному интеллекту
EVOLUTIONARY OPTIMIZATION ALGORITHMS Biologically-Inspired and Population-Based Approaches to Computer Intelligence Dan Simon Cleveland State University
Москва, 2020 Дэн Саймон Перевод с английского Логунов А. В. АЛГОРИТМЫ ЭВОЛЮЦИОННОЙ ОПТИМИЗАЦИИ Биологически обусловленные и популяционно-ориентированные подходы к компьютерному интеллекту
УДК 004.421
ББК 32.811
С12
С12 Дэн Саймон
Алгоритмы эволюционной оптимизации / пер. с англ. А. В. Логунова. –
М.: ДМК Пресс, 2020. – 1002 с.: ил.
ISBN 978-5-97060-707-7
В данной книге рассматриваются история, теоретические основы,
мате-матический аппарат и программирование алгоритмов эволюционной оптимизации. Рассмотренные алгоритмы включают в себя генетические алгоритмы, генетическое программирование, оптимизацию на
основе муравьиной кучи, оптимизацию на основе роя частиц, дифференциальную эволюцию, биогеографическую оптимизацию и многие
другие.
Издание будет полезно студентам старших курсов, программистам,
инженерам, а также всем специалистам, кто интересуется принципами
построения различных алгоритмов.
УДК 004.421
ББК 32.811
Original English language edition published by John Wiley & Sons, Inc. Copyright
© 2013 by John Wiley & Sons, Inc. All rights reserved. Russian-language edition
copyright © 2019 by DMK Press. All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в
какой бы то ни было форме и какими бы то ни было средствами без письменного
разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку
вероятность технических ошибок все равно существует, издательство не может
гарантировать абсолютную точность и правильность приводимых сведений. В
связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.
ISBN 978-0-470-93741-9 (англ.) © John Wiley & Sons, Inc. All rights reserved, 2013
ISBN 978-5-97060-707-7 (рус.) © Оформление, перевод на русский язык,
издание, ДМК Пресс, 2020
Оглавление Благодарности.......................................................................................................................19 Предисловие от издательства............................................................................................20 Аббревиатуры........................................................................................................................21 Часть I. Введение в эволюционную оптимизацию......................................................27 Глава 1. Введение..................................................................................................................28 Обзор главы........................................................................................................................................28 1.1. Терминология..............................................................................................................................29 1.2. Зачем нужна еще одна книга по эволюционным алгоритмам?............................32 1.3. Предварительные условия....................................................................................................34 1.4. Домашние задания...................................................................................................................35 1.5. Обозначения...............................................................................................................................35 1.6. План изложения.........................................................................................................................38 1.7. Учебный курс на основе данной книги............................................................................39 Глава 2. Оптимизация...........................................................................................................41 Краткий обзор главы.......................................................................................................................41 2.1. Неограниченная оптимизация............................................................................................42 2.2. Ограниченная оптимизация.................................................................................................46 2.3. Многокритериальная оптимизация...................................................................................48 2.4. Мультимодальная оптимизация..........................................................................................51 2.5. Комбинаторная оптимизация..............................................................................................52 2.6. Восхождение к вершине холма..........................................................................................54 2.6.1. Смещенные оптимизационные алгоритмы.......................................................................59 2.6.2. Важность симуляций Монте-Карло.......................................................................................60 2.7. Интеллект......................................................................................................................................60 2.7.1. Приспособляемость......................................................................................................................61 2.7.2. Случайность.....................................................................................................................................61 2.7.3. Общение...........................................................................................................................................62 2.7.4. Обратная связь...............................................................................................................................63 2.7.5. Разведывание и эксплуатация.................................................................................................64 2.8. Заключение.................................................................................................................................65 Задачи....................................................................................................................................................66 Письменные упражнения.....................................................................................................................66 Компьютерные упражнения.................................................................................................................68
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