Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой (3000,00 руб.)

Стр.2

Стр.442

Стр.443

Стр.444

Стр.445

Стр.446

УДК 519.6 ББК 22.19 К26 Рецензенты : заведующий кафедрой «Информационные технологии в управлении» Российской академии народного хозяйства и государственной службы при Президенте Российской Федерации, д-р техн. наук, профессор А.Н. Данчул; профессор кафедры физико-математических методов управления МГУ им. М.В. Ломоносова, главный научный сотрудник лаборатории оптимизации управляемых систем ИПУ им. В.А. Трапезникова РАН, д-р техн. наук Н.Б. Филимонов Карпенко, А. П. К26 Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой : учебное пособие / А. П. Карпенко. — 3-е изд., испр. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2021. — 446, [2] с. : ил. ISBN 978-5-7038-5563-8 Рассмотрены современные стохастические популяционные алгоритмы ре - шения однокритериальной задачи глобальной оптимизации. Изложены методы повышения эффективности этих алгоритмов путем их гибридизации и метаоптимизации. Наряду с однокритериальной рассмотрена задача многокритериальной оптимизации и популяционные алгоритмы ее решения. Представлены методы распараллеливания указанных алгоритмов. Содержит большое число примеров решения тестовых и практически значимых задач оптимизации. Для студентов высших учебных заведений, обучающихся по направлению подготовки 09.03.01 «Информатика и вычислительная техника». Может быть полезно для всех студентов, изучающих курс «Методы оптимизации» и близкие по тематике курсы. Материал пособия представляет интерес также для аспирантов и специалистов, использующих в своей работе методы, алгоритмы и программы оптимизации. УДК 519.6 ББК 22.19 ISBN 978-5-7038-5563-8 © Карпенко А.П., 2014 © Карпенко А.П., 2021, с изменениями © Оформление. Издательство МГТУ им. Н.Э. Баумана, 2021

Стр.2

Оглавление Предисловие.......................................................................................................................... 3 Основные обозначения......................................................................................................... 5 Введение................................................................................................................................. 8 Глава 1. Постановка задачи поисковой оптимизации и непопуляционные стохастические алгоритмы ее решения..................................................... 14 1.1. Постановка и классификация алгоритмов решения детерминированной задачи поисковой оптимизации.................................................................................. 14 1.1.1. Постановка задачи............................................................................................ 14 1.1.2. Классификация задач оптимизации................................................................ 16 1.1.3. Классификация алгоритмов оптимизации...................................................... 19 1.2. Локальная безусловная оптимизация......................................................................... 22 1.2.1. Одношаговые алгоритмы................................................................................. 22 1.2.2. Многошаговые алгоритмы............................................................................... 26 1.2.3. Многоточечные алгоритмы.............................................................................. 29 1.3.2. Алгоритмы, не использующие редукцию задачи условной оптимизации к задаче безусловной оптимизации......................................... 42 1.3. Локальная условная оптимизация.............................................................................. 33 1.3.1. Алгоритмы на основе сведения задачи условной оптимизации к задаче безусловной оптимизации................................................................. 34 1.4. Глобальная оптимизация............................................................................................. 46 1.4.1. Алгоритмы одномерной редукции.................................................................. 46 1.4.2. Алгоритмы случайного поиска........................................................................ 53 1.4.3. Поиск с запретами............................................................................................. 62 Вопросыдлясамопроверки................................................................................................. 63 Глава 2. Эволюционные алгоритмы........................................................................... 65 2.1. Биологические предпосылки и общая схема эволюционных алгоритмов............. 66 2.2. Кодирование особей.................................................................................................... 69 2.3. Операторы мутации..................................................................................................... 75 2.3.1. Бинарные мутаторы.......................................................................................... 75 2.3.2. Вещественные мутаторы.................................................................................. 77 2.4. Операторы скрещивания (кроссоверы)...................................................................... 80 2.4.1. Бинарные кроссоверы....................................................................................... 80 2.4.2. Вещественные кроссоверы.............................................................................. 84 2.5. Операторы отбора........................................................................................................ 88 2.5.1. Операторы управления популяцией................................................................ 88 2.5.2. Операторы селекции......................................................................................... 92 2.6. Другие операторы и процедуры................................................................................. 96 2.7. Типовые генетические алгоритмы............................................................................ 102 2.8. Теория шим................................................................................................................. 106 2.9. Эволюционная стратегия........................................................................................... 109 2.10. Эволюционное программирование........................................................................ 112 2.11. Дифференциальная эволюция................................................................................. 114 2.12. Генетический коэволюционный алгоритм............................................................. 117 2.13. Пример применения генетического алгоритма..................................................... 121 Вопросыдлясамопроверки............................................................................................... 125

Стр.442

Оглавление 443 Глава 3. Алгоритмы роя частиц, колонии муравьев и пчелиного роя................... 127 3.1. Оптимизация роем частиц................................................................................ 127 3.1.1. Канонический алгоритм роя частиц....................................................... ...... 127 3.1.2. Модификации канонического алгоритма роя частиц.................................. 133 3.1.3. Топологии соседства частиц.......................................................................... 137 3.1.4. Алгоритмы с динамической топологией соседства частиц........................ 141 3.1.5. Гибридный алгоритм на основе роя частиц и имитации отжига............... 143 3.1.6. Пример решения задачи с использованием алгоритма роя частиц............ 146 3.2. Муравьиная оптимизация......................................................................................... 147 3.2.1. Бионические предпосылки............................................................................. 148 3.2.2. Алгоритм непрерывной оптимизации колонией муравьев......................... 150 3.2.3. Алгоритм непрерывно взаимодействующей колонии муравьев................ 153 3.2.4. Непрерывный ортогональный алгоритм муравьиной колонии.................. 159 3.2.5. Гибридный алгоритм непрерывно взаимодействующей муравьиной колонии....................................................................................... 163 3.2.6. Пример применения модифицированного алгоритма CIAC....................... 170 3.3. Оптимизация пчелиным роем................................................................................... 175 3.3.1. Бионические предпосылки............................................................................. 175 3.3.2. Пчелиный алгоритм........................................................................................ 176 3.3.3. Алгоритм колонии искусственных пчел....................................................... 183 3.3.4. Гибридный алгоритм ..................................................................................... 190 Вопросыдлясамопроверки.............................................................................................. 193 Глава 4. Другие популяционные алгоритмы, вдохновленные живой природой........................................................................................................ 195 4.1. Искусственные иммунные системы......................................................................... 195 4.1.1. Биологические основы................................................................................... 195 4.1.2. Оптимизация с помощью модели иммунной сети....................................... 198 4.1.3. Алгоритм на основе искусственной микроиммунной системы.................. 200 4.1.4. Пример алгоритма искусственной иммунной сети...................................... 201 4.2. Бактериальная оптимизация..................................................................................... 204 4.2.1. Бионические предпосылки............................................................................. 204 4.2.2. Канонический алгоритм бактериальной оптимизации............................... 205 4.2.3. Кооперативная бактериальная оптимизация................................................ 210 4.2.4. Алгоритм, использующий эффект роения бактерий................................... 211 4.2.5. Гибридные бактериальные алгоритмы......................................................... 212 4.3. Алгоритмы, вдохновленные роем светлячков......................................................... 213 4.3.1 Алгоритм светлячков....................................................................................... 213 4.3.2 Алгоритм оптимизации роем светлячков...................................................... 216 4.4. Сорняковый алгоритм................................................................................................ 218 4.4.1. Биологические основы.................................................................................... 218 4.4.2. Схема алгоритма............................................................................................. 219 4.5. Кукушкин поиск......................................................................................................... 221 4.5.1. Биологические предпосылки......................................................................... 221 4.5.2. Схема алгоритма............................................................................................. 222 4.5.3. Эффективность алгоритма............................................................................. 223 4.6. Алгоритмы, вдохновленные поведением обезьян................................................... 227 4.6.1. Обезьяний поиск............................................................................................. 227 4.6.2. Обезьяний алгоритм....................................................................................... 228 4.7. Прочие алгоритмы..................................................................................................... 230

Стр.443

444 Оглавление 4.7.1 Тасующий алгоритм прыгающих лягушек.................................................... 230 4.7.2. Алгоритм, инспирированный летучими мышами....................................... 231 4.7.3. Поиск косяком рыб......................................................................................... 234 4.7.4. Алгоритм растущих деревьев........................................................................ 237 Вопросыдлясамопроверки.............................................................................................. 238 Глава 5. Популяционные алгоритмы, инспирированные неживой природой, человеческим обществом, и другие популяционные алгоритмы...... 239 5.1. Гармонический поиск............................................................................................... 239 5.1.1. Канонический алгоритм................................................................................. 240 5.1.2. Некоторые модификации алгоритма гармонического поиска.................... 242 5.1.3. Пример применения модифицированного алгоритма гармонического поиска................................................................................... 243 5.2. Алгоритм гравитационного поиска......................................................................... 246 5.3. Электромагнитный поиск.......................................................................................... 250 5.3.1. Электромагнитный алгоритм......................................................................... 250 5.3.2. Алгоритм поиска системой зарядов.............................................................. 254 5.4. Алгоритм эволюции разума...................................................................................... 255 5.4.1. Простой алгоритм эволюции разума............................................................. 256 5.4.2. Расширенный алгоритм.................................................................................. 257 5.4.3. Улучшенный алгоритм.................................................................................... 259 5.4.4. Хаотический алгоритм эволюции разума..................................................... 260 5.5. Стохастический диффузионный поиск................................................................... 261 5.6. Культурный алгоритм................................................................................................ 263 5.6.1. Общая схема алгоритма.................................................................................. 263 5.6.2. Построение и коррекция пространства убеждений..................................... 265 5.6.3. Культурная модификация генетических операторов................................... 267 5.7. Меметические алгоритмы......................................................................................... 268 5.7.1 Общая схема алгоритма................................................................................... 268 5.7.2. Гиперэвристические мультимемные адаптивные алгоритмы.................... 269 5.7.3. Самоадаптирующиеся мультимемные алгоритмы...................................... 271 5.8. Самоорганизующийся миграционный алгоритм.................................................... 272 5.9. Алгоритмы рассеянного поиска и прокладки путей.............................................. 274 5.9.1. Алгоритм рассеянного поиска....................................................................... 274 5.9.2. Алгоритм прокладки путей............................................................................ 278 Вопросыдлясамопроверки.............................................................................................. 279 Глава 6. Гибридизация популяционных алгоритмов.......................................... 280 6.1. Общие принципы гибридизации................................................................... .......... 280 6.1.1. Одноуровневая классификация Ванга........................................................... 280 6.1.2. Двухуровневая классификация Эль-Абда и Камэла.................................... 282 6.1.3. Четырехуровневая классификация Рейдла................................................... 283 6.2. Вложенные алгоритмы.............................................................................................. 285 6.2.1. Высокоуровневая гибридизация вложением................................................ 285 6.2.2. Низкоуровневая гибридизация вложением................................................... 287 6.4. Коалгоритмы.............................................................................................................. 296 6.4.1. Классификация коэволюционных алгоритмов............................................. 296 6.4.2. Пример коалгоритма....................................................................................... 299 Вопросыдлясамопроверки.............................................................................................. 301 6.3. Гибридизация по схеме препроцессор / постпроцессор........................................ 288 6.3.1. Последовательная гибридизация................................................................... 288 6.3.2. Конвейерная гибридизация............................................................................ 290

Стр.444

Оглавление 445 Глава 7. Метаоптимизация популяционных алгоритмов.................................... 302 7.1. Постановка метазадачи оптимизации...................................................................... 302 7.1.1. Статическая параметрическая метаоптимизация........................................ 302 7.1.2. Динамическая параметрическая метаоптимизация..................................... 304 7.1.3. Структурная метаоптимизация...................................................................... 307 7.1.4. Структурно-параметрическая метаоптимизация......................................... 308 7.2. Классификация методов метаоптимизации............................................................. 309 7.2.1. Классификация Эйбена.................................................................................. 309 7.2.2. Классификация Смита – Фогарти................................................................. 312 7.3. Однократная настройка параметров........................................................................ 313 7.3.1. Статическая параметрическая метаоптимизация........................................ 313 7.3.2. Динамическая параметрическая метаоптимизация..................................... 315 7.4. Перманентная настройка параметров...................................................................... 316 7.4.1. Схема подхода................................................................................................. 316 7.4.2. Задачи кластеризации и собственно метаоптимизации.............................. 317 7.4.3. Особенности программной реализации подхода......................................... 318 7.4.4. Исследование эффективности подхода......................................................... 320 7.5. Адаптивное управление параметрами..................................................................... 324 7.5.1. Гомогенные методы........................................................................................ 325 7.5.2. Гетерогенные методы..................................................................................... 326 7.7. Структурная метаоптимизация................................................................................ 328 Вопросыдлясамопроверки.............................................................................................. 330 7.6. Самоадаптивное управление параметрами............................................................. 327 7.6.1. Расширение вектора варьируемых параметров базовой задачи................. 327 7.6.2. Коэволюция типа соперничества.................................................................. 328 Глава 8. Популяционные алгоритмы многоцелевой оптимизации................... 332 8.1. Задача многоцелевой оптимизации (МЦО-задача) и алгоритмы ее решения................................................................................................................. 332 8.1.1. Постановка задачи.......................................................................................... 333 8.1.2. Классификация алгоритмов решения МЦО-задачи..................................... 336 8.2. Непопуляционные алгоритмы Парето-аппроксимации......................................... 340 8.2.1. Сеточные алгоритмы...................................................................................... 340 8.2.2. Алгоритмы на основе свертки целевых функций........................................ 341 8.3. Популяционные алгоритмы Парето-аппроксимации............................................. 345 8.3.1. Лексикографическая турнирная селекция.................................................... 345 8.3.2. Алгоритмы чередующихся целевых функций............................................. 346 8.3.3. Алгоритмы на основе ранжирования агентов.............................................. 349 8.3.4. Алгоритмы, не использующие ранжирование агентов................................ 353 8.4. Критерии оценки качества Парето-аппроксимации............................................... 357 8.4.1. Унарные критерии.......................................................................................... 358 8.4.2. Бинарные критерии......................................................................................... 360 8.5. Методы обеспечения качества Парето-аппроксимации......................................... 365 8.5.1. Нишевание....................................................................................................... 366 8.5.2. Другие методы................................................................................................. 367 8.6. Примеры Парето-аппроксимации............................................................................ 370 8.6.1. Парето-аппроксимация на основе генетического алгоритма..................... 370 8.6.2. Аппроксимация с помощью алгоритма роя частиц..................................... 373 8.6.3. Аппроксимация на основе алгоритма колонии муравьев........................... 379 8.6.4. Аппроксимация на основе пчелиного алгоритма........................................ 380 Вопросыдлясамопроверки.............................................................................................. 383

Стр.445

446 Оглавление Глава 9. Параллельные популяционные алгоритмы поисковой оптимизации.................................................................................................. 384 9.1. Классификация и основные типы параллельных ЭВМ......................................... 384 9.1.1. Классификация параллельных вычислительных систем............................ 385 9.1.2. Основные типы параллельных ЭВМ............................................................ 389 9.2. Балансировки загрузки параллельной ЭВМ........................................................... 393 9.2.1. Задача оптимального отображения алгоритма на архитектуру параллельной ЭВМ......................................................................................... 393 9.2.2. Постановка задачи балансировки загрузки.................................................. 395 9.2.3. Методы статической балансировки загрузки............................................... 396 9.2.4. Методы динамической балансировки загрузки........................................... 400 9.2.5. Задача согласования алгоритма с архитектурой параллельной ЭВМ....... 403 9.3. Методы распараллеливания популяционных алгоритмов оптимизации............. 404 9.3.1. Глобальная модель параллелизма................................................................. 405 9.3.2. Островная модель параллелизма.................................................................. 407 9.3.3. Диффузная модель параллелизма................................................................. 409 9.3.4. Другие модели параллелизма........................................................................ 409 9.4. Примеры параллельного решения задач оптимизации.......................................... 411 9.4.1. Параллельный алгоритм роя частиц GIPSO................................................. 411 9.4.2. Параллельный алгоритм Парето-аппроксимации роем частиц.................. 417 Вопросыдлясамопроверки.............................................................................................. 419 Литература......................................................................................................................... 420 Приложение А. История разработки популяционных алгоритмов поисковой оптимизации........................................................................................... 422 Приложение В. Тестовые задачи многоцелевой оптимизации................................... 432 Предметный указатель..................................................................................................... 434 Приложение Б. Тестовые функции для одноцелевой задачи глобальной оптимизации.............................................................................................................. 424

Стр.446