Кукушка поиск - Cuckoo search

эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью от добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: "Кукушка поиск"  – Новости  · газеты  · книги  · ученый  · JSTOR (Июнь 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Метафора

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

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

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

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

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

Алгоритм

В псевдокод можно резюмировать как:

Целевая функция: ${ displaystyle f ( mathbf {x}),  quad  mathbf {x} = (x_ {1}, x_ {2},  dots, x_ {d}); ,}$Создайте начальную популяцию ${ displaystyle n}$ хозяйские гнезда; Пока (t ${ displaystyle F_ {i}}$         [Для максимизации ${ Displaystyle F_ {я}  propto f ( mathbf {x} _ {я})}$ ]; Случайно выбрать гнездо среди n (скажем, j); если (${ displaystyle F_ {i}> F_ {j}}$), Заменим j новым решением; конец, если A дробь (${ displaystyle p_ {a}}$) из худших гнезд бросают и строят новые; Сохраните лучшие решения / гнезда; Ранжируйте решения / гнезда и найдите лучшие на данный момент; Передача текущих лучших решений следующему поколению; конец, пока

Важным преимуществом этого алгоритма является его простота. Фактически, по сравнению с другими популяциями или агентами метаэвристический такие алгоритмы как оптимизация роя частиц и поиск гармонии, по сути, есть только один параметр ${ displaystyle p_ {a}}$ в CS (не считая численности населения ${ displaystyle n}$). Поэтому реализовать его очень просто.

Случайные прогулки и размер шага

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

${ displaystyle mathbf {x} _ {t + 1} = mathbf {x} _ {t} + sE_ {t},}$

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

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

Например, для простых изотропных случайных блужданий мы знаем, что среднее расстояние ${ displaystyle r}$ путешествовал в d-мерном пространстве

${ displaystyle r ^ {2} = 2dDt,}$

где ${ Displaystyle D = s ^ {2} / 2 тау}$ - эффективный коэффициент диффузии. Вот ${ displaystyle s}$ - размер шага или расстояние, пройденное при каждом прыжке, и ${ Displaystyle тау}$ время, затрачиваемое на каждый прыжок. Из приведенного выше уравнения следует, что^[7]

${ displaystyle s ^ {2} = { frac { tau ; r ^ {2}} {t ; d}}.}$

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

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

Теоретический анализ

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

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

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

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

использованная литература