Поиск рыбы косяк - Fish School Search

Поиск рыбных косяков (FSS), предложенный Бастосом Филью и Лимой Нето в 2007 году, в своей базовой версии^[1] алгоритм унимодальной оптимизации, вдохновленный коллективным поведением косяков рыб. Механизмы кормления и согласованного движения послужили источником вдохновения для создания поисковых операторов. Основная идея состоит в том, чтобы заставить рыб «плыть» к положительному градиенту, чтобы «съесть» и «набрать вес». В совокупности более тяжелые рыбы имеют большее влияние на процесс поиска в целом, что заставляет барицентр косяка рыб перемещаться в лучшие места в пространстве поиска на итерациях.^[2]

ФСС использует следующие принципы:^[3]

1. Простые вычисления для всех индивидуумов (например, рыб)
2. Различные способы хранения информации (например, вес рыбы и школьный барицентр)
3. Локальные вычисления (т.е. плавание состоит из отдельных компонентов)
4. Низкая коммуникация между соседними особями (т.е. рыбы должны думать как местные, но также быть социально осведомленными)
5. Минимальный централизованный контроль (в основном для самоконтроля школьного радиуса)
6. Некоторые отчетливые механизмы разнообразия (чтобы избежать нежелательного поведения стая)
7. Масштабируемость (по сложности задач оптимизации / поиска)
8. Автономность (т.е. способность к самоконтролю)

Алгоритм

FSS - это алгоритм поиска на основе популяции, основанный на поведении плавающих рыб, которые расширяются и сжимаются в поисках пищи. Каждая рыба ${\displaystyle n}$-размерное расположение представляет собой возможное решение проблемы оптимизации. Алгоритм использует веса для всех рыб, что представляет собой совокупный счет того, насколько успешным был поиск каждой рыбы в косяке. FSS состоит из операторов подачи и перемещения, которые делятся на три подкомпонента, а именно:^[4]

Индивидуальная составляющая движения

Каждая рыба в косяке выполняет локальный поиск в поисках перспективных регионов в пространстве поиска. Это делается, как показано ниже:

${\displaystyle x_{i}(t+1)=x_{i}(t)+rand(-1,1)step_{ind},}$

куда ${\displaystyle x_{i}(t)}$ и ${\displaystyle x_{i}(t+1)}$ представлять положение рыбы ${\displaystyle i}$ до и после индивидуального перемещения оператора соответственно. ${\displaystyle rand(-1,1)}$ - равномерно распределенное случайное число от -1 до 1 и ${\displaystyle step_{ind}}$ - параметр, определяющий максимальное смещение для этого движения. Новая должность ${\displaystyle x_{i}(t+1)}$ принимается только в том случае, если приспособленность рыбы улучшается с изменением положения. Если это не так, рыба остается в том же положении и ${\displaystyle x_{i}(t+1)=x_{i}(t)}$.

Коллективно-инстинктивная составляющая движения

Среднее значение отдельных перемещений рассчитывается на основе следующего:

${\displaystyle I={\frac {\sum _{i=1}^{N}\Delta x_{i}\Delta f_{i}}{\sum _{i=1}^{N}\Delta f_{i}}}.}$

Вектор ${\displaystyle I}$ представляет собой средневзвешенное значение перемещений каждой рыбы. Это означает, что рыбы, у которых было более высокое улучшение, будут привлекать рыб на свою позицию. ${\displaystyle I}$ вычислений, каждая рыба будет двигаться в соответствии с:

${\displaystyle x_{i}(t+1)=x_{i}(t)+I.}$

Коллективно-волевая составляющая движения

Этот оператор используется для регулирования возможностей школы по разведке / эксплуатации в процессе поиска. Прежде всего, барицентр ${\displaystyle B}$ школы рассчитывается исходя из должности ${\displaystyle x_{i}}$ и вес ${\displaystyle W_{i}}$ каждой рыбы:

${\displaystyle B(t)={\frac {\sum _{i=1}^{N}x_{i}(t)W_{i}(t)}{\sum _{i=1}^{N}W_{i}(t)}},}$

а затем, если общий вес школы ${\displaystyle \sum _{i=1}^{N}W_{i}}$ увеличился от последней к текущей итерации, рыбы привлекаются к барицентру в соответствии с уравнением A. Если общий вес косяка не улучшился, рыбы отводятся от барицентра в соответствии с уравнением B:

Уравнение А:

${\displaystyle x_{i}(t+1)=x_{i}(t)-step_{vol}rand(0,1){\frac {x_{i}(t)-B(t)}{distance(x_{i}(t),B(t))}},}$

Уравнение B:

${\displaystyle x_{i}(t+1)=x_{i}(t)+step_{vol}rand(0,1){\frac {x_{i}(t)-B(t)}{distance(x_{i}(t),B(t))}},}$

куда ${\displaystyle step_{vol}}$ определяет размер максимального смещения, выполняемого с использованием этого оператора. ${\displaystyle distance(x_{i}(t),B(t))}$ это евклидово расстояние между рыбками ${\displaystyle i}$ положение и школьный барицентр. ${\displaystyle rand(0,1)}$ - равномерно распределенное случайное число от 0 до 1.

Помимо операторов перемещения, был также определен оператор кормления, используемый для обновления веса каждой рыбы в соответствии с:

${\displaystyle W_{i}(t+1)=W_{i}(t)+{\frac {\Delta f_{i}}{max(|\Delta f_{i}|)}},}$

куда ${\displaystyle W_{i}(t)}$ параметр веса для рыбы ${\displaystyle i}$, ${\displaystyle \Delta f_{i}}$ изменение пригодности между последним и новым положением, и ${\displaystyle max(|\Delta f_{i}|)}$ представляет собой максимальное абсолютное значение вариации приспособленности среди всех рыб в стае.${\displaystyle W}$ может изменяться только от 1 до ${\displaystyle W_{scale}/2}$, который является определяемым пользователем атрибутом. Вес всех рыб инициализируется значением ${\displaystyle W_{scale}/2}$.

Псевдокод для ФСС

1. Инициализировать параметры пользователя
2. Инициализировать позиции рыб в случайном порядке
3. пока не выполняется условие остановки, сделайте
4. Рассчитайте приспособленность для каждой рыбы
5. Выполните индивидуальные движения оператора
6. Рассчитайте приспособленность для каждой рыбы
7. Оператор запуска подачи
8. Выполнить коллективно-инстинктивное движение оператора
9. Выполнить коллективно-волевое движение оператора
10. конец пока

Параметры ${\displaystyle step_{ind}}$ и ${\displaystyle step_{vol}}$ линейно распадаются по:

${\displaystyle step_{ind}(t+1)=step_{ind}(t)-{\frac {step_{ind}(initial)}{It_{max}}},}$

и аналогично:

${\displaystyle step_{vol}(t+1)=step_{vol}(t)-{\frac {step_{vol}(initial)}{It_{max}}},}$

куда ${\displaystyle step_{ind}(initial)}$ и ${\displaystyle step_{vol}(initial)}$ - определенные пользователем начальные значения для ${\displaystyle step_{ind}}$ и ${\displaystyle step_{vol}}$, соответственно. ${\displaystyle It_{max}}$ - максимальное количество итераций, разрешенных в процессе поиска.

Варианты FSS

dFSS (поиск косяков рыбы на основе плотности)

Эта версия отлично подходит для мультимодальных гипермерных функций. Он включает изменения в предыдущих операторах: Кормление и Плавание, а также новые: Операторы Памяти и Разделения. Последние два были введены для учета разделения основной школы на подгруппы. Некоторые изменения были также внесены в условия остановки, которые теперь также должны учитывать подпогрев.^[5]

wFSS (поиск косяка рыбы на основе веса)

wFSS - это версия FSS на основе весовых коэффициентов, предназначенная для создания нескольких решений. Стратегия ничинга основана на новом операторе, называемом форматором ссылок. Этот оператор используется для определения лидеров для рыб, чтобы сформировать подшколы.^[6]

FSS-SAR (Обычный поиск косяков рыбы с предотвращением застоя)

В исходной версии алгоритма отдельному компоненту движения разрешено перемещать рыбу только в том случае, если это улучшает приспособленность. Однако в очень гладком пространстве поиска будет много движущихся испытаний без успеха, и алгоритм может не сойтись. Для решения этих проблем был введен параметр X, для которого 0 <= X <= 1 в отдельном компоненте Движение. X убывает экспоненциально вместе с итерациями и измеряет вероятность ухудшения допуска для каждой рыбы. Это означает, что каждый раз, когда рыба пытается переместиться в положение, которое не улучшает ее приспособленность, выбирается случайное число, и если оно меньше X, движение разрешается.^[7]

bFSS (поиск косяков двоичных рыб)

BFSS призван справиться с преждевременной конвергенцией. Предлагается использовать схему двоичного кодирования для внутренних механизмов поиска косяка рыб. Он объединил FSS с нечетким моделированием в подходе оболочки для выбора функций.^[8]

MOFSS (многоцелевой поиск косяков рыбы)

В MOFSS операторы адаптированы для решения многоцелевых задач. Алгоритм развертывает внешний архив для хранения лучших недоминируемых решений, найденных в процессе поиска. Этот подход широко использовался для различных оптимизаторов, основанных на биологии и многоцелевых целях.^[9][10] Кроме того, решения из внешнего архива используются для управления перемещениями рыбы в версии предложения.^[11]

Смотрите также

• Алгоритмы оптимизации муравьиной колонии
• Алгоритм искусственной пчелиной колонии
• Оптимизация роя частиц

внешняя ссылка

• http://www.fbln.pro.br/fss/

Рекомендации

1. С. Дж. А. Б. Филхо., Ф. Б. де Лима Нето, А. Дж. К. С. Линс, А. И. С. Насименто. И М. П. Лима "Новый алгоритм поиска, основанный на поведении косяков рыб., "Системы, человек и кибернетика, SMC 2008. Международная конференция IEEE, 2008 г., стр. 2646-2651.
2. де Лима Нето, Фернандо Буарк и Марсело Гомеш Перейра де Ласерда. "Алгоритмы мультимодального поиска косяков рыб на основе локальной информации для разделения косяков. »Конгресс БРИКС по вычислительному интеллекту 2013 г. и 11-й Бразильский конгресс по вычислительному интеллекту. IEEE, 2013 г.
3. http://www.fbln.pro.br/fss/
4. Дж. Б. Монтейро, И. М. К. Альбукерке, Ф. Б. Л. Нето и Ф. В. С. Феррейра, «Оптимизация функций нескольких плато с помощью FSS-SAR (программа предотвращения застоя), ”Представлено на серии симпозиумов IEEE по вычислительному интеллекту, 2016 г.
5. Мадейро, С. С., де Лима-Нето, Ф. Б., Бастос-Филью, К. Дж. А., и Насименту Фигейредо, Э. М. (2011, июнь). Плотность как механизм сегрегации в поиске косяков для задач мультимодальной оптимизации. В Международной конференции по разведке роя (стр. 563-572). Springer Berlin Heidelberg.
6. Ф. Буарке Де Лима Нето и М. Гомеш Перейра де Ласерда, «Поиск косяка рыбы по весу, ”В Системах, Человеке и Кибернетике (SMC), Международная конференция IEEE 2014 г. IEEE, 2014, стр. 270–277.
7. Дж. Б. Монтейро, И. М. К. Альбукерке, Ф. Б. Л. Нето и Ф. В. С. Феррейра, «Оптимизация функций нескольких плато с помощью FSS-SAR (программа предотвращения застоя), ”Представлено на серии симпозиумов IEEE по вычислительному интеллекту, 2016 г.
8. Сарго, Жоао А.Г. и др. "Функция поиска Binary Fish School Search применяется к выбору функции: Заявление в реадмиссию ICU. »Международная конференция IEEE по нечетким системам (FUZZ-IEEE), 2014 г. IEEE, 2014.
9. Деб К., Тиле Л., Лауманнс М. и Цитцлер Э. (2002) Задачи масштабируемой многоцелевой оптимизации, В: Конгресс IEEE по эволюционным вычислениям (стр. 825–830).
10. Небро, А. Дж., Дурилло, Дж. Дж., Гарса-Ньето, Дж., Коэлло Коэльо, К. А., Луна, Ф. и Альба, Э. (2009) SMPSO: новая метаэвристика на основе PSO для многоцелевой оптимизации, В: Симпозиум IEEE по вычислительному интеллекту в многокритериальном принятии решений (стр. 66–73). DOI: 10.1109 / MCDM.2009.4938830
11. Бастос-Филью, Кармело Х.А. и Аугусто С.С. Гимарайнш. "Многоцелевой поиск косяков рыбы. »Международный журнал исследований разведки роя (IJSIR) 6.1 (2015): 23-40.