Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья про алгоритм поиска. Для алгоритма хеширования см. Хеширование с кукушкой .

В исследовании операций , поиск кукушки является оптимизация алгоритмом , разработанная Xin-она Ян и Suash Деб в 2009 году [1] [2] Он был вдохновлен облигатным расплод паразитизмом некоторых кукушки видов, откладывая свои яйца в гнездах другого хоста птицы (других видов). Некоторые птицы-хозяева могут вступать в прямой конфликт с вторгающимися кукушками. Например, если птица-хозяин обнаруживает, что яйца не принадлежат ей, она либо выбросит эти инопланетные яйца, либо просто покинет свое гнездо и построит новое гнездо в другом месте. Некоторые виды кукушек, такие как паразитические выводки Tapera из Нового Света.эволюционировали таким образом, что самки кукушек-паразитов часто очень специализированы в мимикрии окраски и рисунка яиц нескольких выбранных видов хозяев. [3] Поиск с кукушкой идеализировал такое поведение при размножении и, таким образом, может применяться для решения различных задач оптимизации.

Метафора [ править ]

Cuckoo search (CS) использует следующие представления:

Каждое яйцо в гнезде представляет собой раствор, а яйцо кукушки представляет собой новый раствор. Цель состоит в том, чтобы использовать новые и потенциально лучшие решения (кукушки), чтобы заменить не очень хорошее решение в гнездах. В простейшем виде в каждом гнезде по одному яйцу. Алгоритм может быть расширен на более сложные случаи, когда в каждом гнезде есть несколько яиц, представляющих набор решений.

CS основан на трех идеализированных правилах:

  1. Каждая кукушка откладывает по одному яйцу за раз и сбрасывает свое яйцо в случайно выбранное гнездо;
  2. Лучшие гнезда с высоким качеством яиц переходят в следующее поколение;
  3. Количество доступных гнезд хозяев фиксировано, и яйцо, снесенное кукушкой, с вероятностью обнаруживается птицей-хозяином . В этом случае птица-хозяин может выбросить яйцо / покинуть гнездо и построить совершенно новое гнездо.

Вдобавок Ян и Деб обнаружили, что поиск в стиле случайного блуждания лучше выполняется рейсами Леви , чем простым случайным блужданием .

Алгоритм [ править ]

Псевдокод можно резюмировать следующим образом:

Целевая функция:
создание начальной популяции гнезд хозяев;Пока (t <MaxGeneration) или (критерий остановки) Получить кукушку наугад (скажем, i) и заменить ее решение полетами Леви; Оцените его качество / пригодность [для максимизации ]; Случайно выбрать гнездо среди n (скажем, j); если ( ), Заменить j новым решением; конец, если Часть ( ) худших гнезд покидают и строят новые; Сохраните лучшие решения / гнезда; Ранжируйте решения / гнезда и найдите лучшие на данный момент; Передача текущих лучших решений следующему поколению;конец пока

Важным преимуществом этого алгоритма является его простота. Фактически, по сравнению с другими метаэвристическими алгоритмами, основанными на популяциях или агентах , такими как оптимизация роя частиц и поиск гармонии , в CS, по сути, есть только один параметр (помимо размера популяции ). Поэтому реализовать его очень просто.

Случайные прогулки и размер шага [ править ]

Важным вопросом является применение полетов Леви и случайных блужданий в общем уравнении для генерации новых решений.

где взято из стандартного нормального распределения с нулевым средним и единичным стандартным отклонением для случайных блужданий или получено из распределения Леви для полетов Леви . Очевидно, случайные блуждания также могут быть связаны со сходством между яйцом кукушки и яйцом хозяина, что может быть непросто в реализации. Здесь размер шага определяет, как далеко может пройти случайный человек за фиксированное количество итераций. Генерация размера шага Леви часто бывает сложной, и сравнение трех алгоритмов (включая алгоритм Мантеньи [4] ) было выполнено Леккарди [5], который обнаружил, что реализация подхода Чемберса и др. [6] является наиболее вычислительной. эффективен из-за небольшого количества требуемых случайных чисел.

Если s слишком велико, то новое сгенерированное решение будет слишком далеко от старого решения (или даже выйдет за границы). Тогда такой ход вряд ли будет принят. Если s слишком мало, изменение слишком мало, чтобы быть значительным, и, следовательно, такой поиск неэффективен. Поэтому правильный размер шага важен для обеспечения максимальной эффективности поиска.

Например, для простых изотропных случайных блужданий мы знаем, что среднее расстояние, пройденное в пространстве размерности d, равно

где - эффективный коэффициент диффузии. Вот размер шага или расстояние, пройденное при каждом прыжке, и время, затраченное на каждый прыжок. Из приведенного выше уравнения следует, что [7]

Для типичного масштаба длины L интересующего измерения локальный поиск обычно ограничивается областью . Для и t = от 100 до 1000 мы имеем для d = 1 и для d = 10. Следовательно, для большинства задач мы можем использовать s / L = 0,001–0,01. Хотя для точного вывода может потребоваться подробный анализ поведения полетов Леви. [8]

Анализ алгоритмов и сходимости будет плодотворным, потому что есть много открытых проблем, связанных с метаэвристикой [9]

Теоретический анализ [ править ]

Для повышения производительности алгоритмов на основе CS требуются значительные усилия, теоретический анализ: [10]

  1. Теоретический анализ сходимости алгоритмов на основе CS
  2. Обеспечение достаточных и необходимых условий для настройки параметров управления
  3. Использование неоднородных правил поиска для улучшения классического алгоритма CS

Улучшенные алгоритмы поиска кукушки [ править ]

Сходимость алгоритма поиска кукушки может быть существенно улучшена путем генетической замены заброшенных гнезд (вместо использования случайных замен из исходного метода). [11] В алгоритм также были внесены изменения путем дополнительного скрещивания лучших (высококачественных) гнезд [12], и этот подход был успешно применен к ряду задач промышленной оптимизации. [13] [14]

Ссылки [ править ]

  1. ^ X.-S. Ян; С. Деб (декабрь 2009 г.). Кукушка поиск по рейсам Леви . Всемирный конгресс по природе и биологическим вычислениям (NaBIC 2009). Публикации IEEE. С. 210–214. arXiv : 1003.1594v1 .
  2. ^ Inderscience (27 мая 2010). «Кукушка конструирует весну» . Alphagalileo.org . Проверено 27 мая 2010 .
  3. ^ RB Payne, MD Sorenson, и К. Klitz, кукушки, Oxford University Press (2005).
  4. ^ RN Mantegna, Быстрый и точный алгоритм для численного моделирования устойчивых случайных процессов Леви , Physical Review E, Vol.49, 4677-4683 (1994).
  5. ^ М. Леккарди, Сравнение трех алгоритмов генерации шума Леви , Труды пятой конференции EUROMECH по нелинейной динамике (2005).
  6. ^ Чемберс, JM; Мальвы, CL; Застрявший, BW (1976). «Метод моделирования стабильных случайных величин». Журнал Американской статистической ассоциации . 71 : 340–344. DOI : 10.1080 / 01621459.1976.10480344 .
  7. ^ X.-S. Ян, Природные метаэвристические алгоритмы , 2-е издание, Luniver Press, (2010).
  8. ^ М. Гутовски, Полеты Леви как основной механизм для алгоритмов глобальной оптимизации , ArXiv Mathematical Physics e-Prints, июнь (2001).
  9. ^ XS Ян, Метаэвристическая оптимизация: анализ алгоритмов и открытые проблемы , в: Experimental Algorithms (SEA2011), Eds (PM Pardalos and S. Rebennack), LNCS 6630, pp.21-32 (2011).
  10. ^ Cheung, Нью-Джерси; Дин, X .; Шен, Х. (21 января 2016 г.). «Неоднородный алгоритм поиска кукушки на основе квантового механизма для оптимизации реальных параметров» . IEEE Transactions по кибернетике . 47 (2): 391–402. DOI : 10.1109 / TCYB.2016.2517140 .
  11. ^ де Оливейра, Виктория YM; де Оливейра, Родриго М.С.; Аффонсо, Каролина М. (31.07.2018). «Подход Cuckoo Search, усиленный генетической заменой заброшенных гнезд, применяемый для оптимального размещения единиц распределенного поколения» . Генерация, передача и распределение ИЭПП . 12 (13): 3353–3362. DOI : 10,1049 / МТВ-gtd.2017.1992 . ISSN 1751-8687 . 
  12. ^ Уолтон, S .; Hassan, O .; Morgan, K .; Браун, MR (2011-09-01). «Модифицированный поиск кукушки: новый алгоритм оптимизации без градиента» . Хаос, солитоны и фракталы . 44 (9): 710–718. DOI : 10.1016 / j.chaos.2011.06.004 . ISSN 0960-0779 . 
  13. ^ «Новая реализация вычислительной оптимизации аэродинамической формы с использованием модифицированного поиска кукушки» . Прикладное математическое моделирование . 40 (7–8): 4543–4559. 2016-04-01. DOI : 10.1016 / j.apm.2015.11.023 . ISSN 0307-904X . 
  14. ^ Чжао, J .; Liu, S .; Чжоу, М .; Guo, X .; Ци, Л. (июль 2018 г.). «Модифицированный алгоритм поиска кукушки для решения задач оптимизации диспетчеризации экономической энергии» . IEEE / CAA Journal of Automatica Sinica . 5 (4): 794–806. DOI : 10,1109 / JAS.2018.7511138 . ISSN 2329-9274 .