Поиск косяка рыбы

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

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

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

Алгоритм

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

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

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

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

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

Коллективно-инстинктивный компонент движения

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

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

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

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

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

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

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

и тогда, если общий школьный вес $\sum _{i=1}^{N}W_{i}$ увеличился по сравнению с последней итерацией к текущей, рыбы притягиваются к барицентру согласно уравнению А. Если общий вес косяка не увеличился, рыбы расходятся от барицентра согласно уравнению Б:

уравнение А:

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

уравнение Б:

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

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

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

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

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

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

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

Параметры $step_{ind}$ и $step_{vol}$ линейно затухают по закону:

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

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

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

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

Вариации ФСС

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

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

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

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

FSS-SAR (Регулярный поиск косяков рыбы во избежание застоя)

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

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

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

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

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

См. также

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

Внешние ссылки

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