Список метаэвристики на основе метафор - List of metaphor-based metaheuristics

Это хронологически упорядоченный список метаэвристических алгоритмов на основе метафор и разведки роя .

Алгоритмы

Имитация отжига (Киркпатрик и др., 1983)

Имитация отжига (SA) - это вероятностный метод, вдохновленный методом термической обработки в металлургии . Он часто используется, когда пространство поиска дискретно (например, все туры, которые посещают заданный набор городов). Для задач, где нахождение точного глобального оптимума менее важно, чем нахождение приемлемого локального оптимума за фиксированный промежуток времени, имитация отжига может быть предпочтительнее альтернатив, таких как градиентный спуск .

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

Оптимизация колонии муравьев (Дориго, 1992)

Алгоритм оптимизации муравьиной колонии (ACO) - это вероятностный метод решения вычислительных задач, который можно свести к поиску хороших путей через графы . Первоначально предложенный Марко Дориго в 1992 году в его докторской диссертации, первый алгоритм был нацелен на поиск оптимального пути в графе, основанный на поведении муравьев, ищущих путь между своей колонией и источником пищи. Первоначальная идея с тех пор изменилась, чтобы решить более широкий класс численных задач, и в результате возникло несколько проблем, основанных на различных аспектах поведения муравьев. В более широком плане ACO выполняет поиск на основе модели и имеет некоторые общие черты с алгоритмами оценки распределения .

Оптимизация роя частиц (Кеннеди и Эберхарт, 1995)

Оптимизация роя частиц (PSO) - это вычислительный метод, который оптимизирует проблему, итеративно пытаясь улучшить возможное решение с учетом заданного показателя качества. Он решает проблему, имея совокупность возможных решений, здесь названных частиц , и перемещая эти частицы в пространстве поиска в соответствии с простыми математическими формулами относительно положения и скорости частицы . На движение каждой частицы влияет ее местное наиболее известное положение, но оно также направляется к наиболее известным позициям в пространстве поиска, которые обновляются по мере того, как другие частицы находят лучшие позиции. Ожидается, что это подтолкнет рой к лучшим решениям.

Первоначально ПСО приписывают Кеннеди , Эберхарту и Ши и сначала предназначались для моделирования социального поведения как стилизованное представление движения организмов в стае птиц или косяке рыб . Алгоритм был упрощен, и было замечено, что он выполняет оптимизацию. Книга Кеннеди и Эберхарта описывает многие философские аспекты PSO и интеллекта роя . Poli проводит обширный обзор приложений PSO . Недавно Боньяди и Михалевич опубликовали исчерпывающий обзор теоретических и экспериментальных работ по PSO.

Поиск гармонии (Джем, Ким и Логанатан, 2001)

Поиск гармонии - это метаэвристика, имитирующая феномен, введенная в 2001 году Зонг У Гимом, Джун Хун Кимом и Дж. В. Логанатаном. Поиск гармонии вдохновлен процессом импровизации джазовых музыкантов. В одном документе утверждалось, что поиск гармонии оказался частным случаем алгоритма Evolution Strategies . Однако в недавней статье утверждается, что структура стратегий эволюции отличается от структуры поиска гармонии.

Поиск гармонии (HS) - это относительно простой, но эффективный эволюционный алгоритм. В алгоритме HS случайным образом генерируется набор возможных решений (называемый памятью гармонии). Новое решение создается с использованием всех решений в памяти Harmony (а не только двух, как в GA), и если это новое решение лучше, чем худшее решение в памяти Harmony, худшее решение заменяется этим новым решением. Эффективность и преимущества HS были продемонстрированы в различных приложениях, таких как проектирование муниципальных водопроводных сетей, структурное проектирование, задача распределения нагрузки в электротехнике, многоцелевая оптимизация, задачи составления списков, кластеризация, а также классификация и выбор характеристик. Подробный обзор приложений HS можно найти в, а приложения HS в интеллектуальном анализе данных можно найти в.

Алгоритм искусственной пчелиной семьи (Карабога, 2005)

Алгоритм искусственного пчелиного поселения - это метаэвристический алгоритм, представленный Карабогой в 2005 году и имитирующий поведение медоносных пчел в поисках пищи. Алгоритм ABC состоит из трех этапов: используемая пчела, пчела-наблюдатель и пчела-разведчик. В фазах использованной пчелы и фазы пчелы-наблюдателя пчелы используют источники путем локального поиска в окрестностях решений, выбранных на основе детерминированного выбора в фазе используемой пчелы и вероятностного выбора в фазе пчелы-наблюдателя. На этапе разведки пчел, который является аналогом отказа от истощенных источников пищи в процессе поиска пищи, отбрасываются решения, которые больше не являются полезными для прогресса поиска, и вместо них вставляются новые решения для исследования новых регионов в пространстве поиска. Алгоритм имеет хорошо сбалансированную способность исследования и эксплуатации.

Алгоритм пчел (Pham, 2005)

Алгоритм пчел в его базовой формулировке был создан Фамом и его сотрудниками в 2005 году и в последующие годы был усовершенствован. Алгоритм, созданный на основе поведения медоносных пчел при поиске пищи , сочетает в себе глобальный исследовательский поиск с локальным эксплуатационным поиском. Небольшое количество искусственных пчел (разведчиков) случайным образом исследует пространство решений (среду) для решений высокой пригодности (высокодоходные источники пищи), в то время как основная часть населения ищет (собирает урожай) окрестности наиболее приспособленных решений в поисках оптимальной приспособленности. . Детерминированная процедура набора, которая имитирует виляющий танец биологических пчел, используется для передачи результатов разведчиков сборщикам и распределения сборщиков в зависимости от пригодности районов, выбранных для местного поиска. Как только поиск в окрестности решения прекращается, считается, что локальный оптимум пригодности найден, и сайт покидает. Таким образом, алгоритм пчел одновременно выполняет поиск наиболее перспективных областей пространства решений, при этом непрерывно отбирая образцы в поисках новых благоприятных регионов.

Оптимизация роя светлячков (Кришнананд и Гхоз, 2005)

Оптимизация роя светлячков - это алгоритм оптимизации интеллекта роя , разработанный на основе поведения светлячков (также известных как светлячки или молнии). Алгоритм GSO был разработан и представлен К. Н. Кришнанандом и Дебасишем Гхосом в 2005 году в лаборатории систем наведения, управления и принятия решений Департамента аэрокосмической техники Индийского института науки , Бангалор , Индия .

Образец поведения светлячков, который используется для этого алгоритма, представляет собой очевидную способность светлячков изменять интенсивность излучения люциферина и, таким образом, кажется, что они светятся с разной интенсивностью.

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

Часть 2 алгоритма отличает его от других эволюционных алгоритмов мультимодальной оптимизации . Именно на этом этапе рои светлячков автоматически разделяются на подгруппы, которые затем могут сходиться к нескольким локальным оптимумам одновременно. Это свойство алгоритма позволяет использовать его для идентификации нескольких пиков мультимодальной функции и делает его частью семейство эволюционных алгоритмов мультимодальной оптимизации.

Алгоритм перетасованного лягушачьего прыжка (Eusuff, Lansey & Pasha, 2006)

Алгоритм перетасованного лягушачьего прыжка - это алгоритм оптимизации, используемый в искусственном интеллекте . Это сравнимо с генетическим алгоритмом .

Оптимизация роя кошек (Чу, Цай и Пан, 2006)

Алгоритм оптимизации кошачьего роя, который решает проблемы оптимизации и основан на поведении кошек. Он похож на другие алгоритмы оптимизации роя, такие как алгоритмы оптимизации муравьиной колонии или оптимизации роя частиц. Поиск и отслеживание, два общих поведения кошек, составляют две подмодели алгоритма. Seeking Mode основан на поведении отдыхающей кошки, которая ищет, куда двигаться дальше. В режиме поиска он выбирает несколько точек-кандидатов, а затем выбирает одну для случайного перемещения, увеличивая вероятность выбора точек с более высоким значением пригодности. Режим отслеживания вдохновлен кошкой, выслеживающей какую-то цель. В этом режиме кошка будет пытаться перейти в позицию с наилучшим показателем пригодности. Кошки будут продолжать движение в режиме поиска и отслеживания до тех пор, пока не будет выполнено условие завершения.

Империалистический конкурентный алгоритм (Аташпаз-Гаргари и Лукас, 2007)

Империалистический конкурентный алгоритм - это вычислительный метод, который используется для решения задач оптимизации различных типов. Как и большинство методов в области эволюционных вычислений , ICA не требует градиента функции в процессе оптимизации. С определенной точки зрения, ICA можно рассматривать как социальный аналог генетических алгоритмов (ГА). ICA - это математическая модель и компьютерное моделирование социальной эволюции человека , в то время как GA основаны на биологической эволюции видов.

Этот алгоритм начинается с генерации набора случайных возможных решений в пространстве поиска задачи оптимизации. Сгенерированные случайные точки называются исходными странами . Страны в этом алгоритме являются аналогом хромосом в GA и частиц в оптимизации роя частиц (PSO) и представляют собой массив значений возможного решения проблемы оптимизации. Функция стоимости задачи оптимизации определяет мощь каждой страны. Основываясь на своей мощи, некоторые из лучших начальных стран (страны с наименьшим значением функции затрат) становятся империалистами и начинают брать под свой контроль другие страны (называемые колониями ) и формируют начальные империи .

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

Империалистическая конкуренция - еще одна часть этого алгоритма. Все империи пытаются выиграть эту игру и завладеть колониями других империй. На каждом этапе алгоритма, в зависимости от своей мощи, все империи имеют шанс взять под контроль одну или несколько колоний самой слабой империи.

Алгоритм продолжается с упомянутых шагов (Ассимиляция, Революция, Соревнование) до тех пор, пока не будет выполнено условие остановки.

Вышеупомянутые шаги можно резюмировать как приведенный ниже псевдокод .

0) Define objective function: ${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}$
1) Initialization of the algorithm. Generate some random solution in the search space and create initial empires.
    2) Assimilation: Colonies move towards imperialist states in different in directions.
    3) Revolution: Random changes occur in the characteristics of some countries.
    4) Position exchange between a colony and Imperialist. A colony with a better position than the imperialist,
       has the chance to take the control of empire by replacing the existing imperialist.
    5) Imperialistic competition: All imperialists compete to take possession of colonies of each other.
    6) Eliminate the powerless empires. Weak empires lose their power gradually and they will finally be eliminated.
    7) If the stop condition is satisfied, stop, if not go to 2.
8) End

Динамика формирования рек (Rabanal, Rodríguez & Rubio, 2007)

Динамика формирования рек основана на имитации того, как вода формирует реки, размывая землю и осаждая отложения (капли действуют как рой). После того, как капли преобразуют ландшафт, увеличивая / уменьшая высоту мест, решения даются в виде путей уменьшения высоты. Создаются убывающие градиенты, и за этими градиентами следуют последующие падения, чтобы составить новые градиенты и усилить лучшие. Этот метод эвристической оптимизации был впервые представлен в 2007 году Rabanal et al. Применимость RFD к другим NP-полным задачам была изучена, и алгоритм был применен к таким областям, как маршрутизация и навигация роботов. Основные области применения RFD можно найти в подробном обзоре.

Интеллектуальный алгоритм капель воды (Шах-Хоссейни, 2007)

Интеллектуальный алгоритм капель воды содержит несколько основных элементов естественных капель воды, а также действий и реакций, которые происходят между дном реки и текущими каплями воды. IWD был впервые представлен для задачи коммивояжера в 2007 году.

Практически каждый алгоритм IWD состоит из двух частей: графа, который играет роль распределенной памяти, на которой сохраняются почвы разных краев, и подвижной части алгоритма IWD, которая представляет собой несколько интеллектуальных капель воды. Эти интеллектуальные капли воды (IWD) одновременно соревнуются и сотрудничают, чтобы найти лучшие решения, и, изменяя почвы на графике, пути к лучшим решениям становятся более доступными. Упоминается, что для работы алгоритмов на основе IWD требуется как минимум два IWD.

Алгоритм IWD имеет два типа параметров: статические и динамические параметры. Статические параметры постоянны в процессе работы алгоритма IWD. Динамические параметры повторно инициализируются после каждой итерации алгоритма IWD. Псевдокод алгоритма на основе IWD может быть определен в восемь шагов:

1) Инициализация статических параметров

а) Представление задачи в виде графа

б) Установка значений статических параметров

2) Инициализация динамических параметров: грунт и скорость IWD.

3) Распределение IWD на графе задачи

4) Построение решения с помощью IWD вместе с обновлением почвы и скорости

а) Местное обновление почвы на графике

б) Обновление почвы и скорости на IWD

5) Локальный поиск по каждому решению IWD (необязательно)

6) Глобальное обновление почвы

7) Обновление Total-Best решения

8) Переходите к шагу 2, если не выполняется условие завершения.

Алгоритм гравитационного поиска (Rashedi, Nezamabadi-pour & Saryazdi, 2009)

Алгоритм гравитационного поиска основан на законе гравитации и понятии массовых взаимодействий. Алгоритм GSA использует теорию ньютоновской физики, а его поисковые агенты представляют собой совокупность масс. В GSA существует изолированная система масс. Используя силу тяжести, каждая масса в системе может видеть положение других масс. Таким образом, гравитационная сила - это способ передачи информации между разными массами (Рашеди, Незамабади-пуре и Сарьязди, 2009). В GSA агенты рассматриваются как объекты, и их производительность измеряется их массой. Все эти объекты притягивают друг друга силой тяжести , и эта сила вызывает движение всех объектов к объектам с более тяжелыми массами. Более тяжелые массы соответствуют лучшим решениям проблемы. Положение агента соответствует решению этой проблемы, а ее масса определяется с помощью функции пригодности. По прошествии времени массы притягиваются самой тяжелой массой, которая в идеале представляет собой оптимальное решение в пространстве поиска. GSA можно рассматривать как изолированную систему масс. Это похоже на небольшой искусственный мир масс, подчиняющийся законам тяготения и движения Ньютона. Многоцелевой вариант GSA, названный MOGSA, был впервые предложен Hassanzadeh et al. в 2010.

Поиск кукушки (Янг и Деб, 2009)

В исследовании операций , поиск кукушка является оптимизация алгоритма , разработанная Xin-она Ян и Suash Деб в 2009 году был вдохновлен облигатными расплода паразитизма некоторых кукушкой видов, откладывая свои яйца в гнезда других птиц - хозяев (других видов) . Если птица-хозяин обнаруживает, что яйца ей не принадлежат, она выбрасывает их из гнезда или бросает гнездо и строит новое. Принцип поиска с кукушкой заключается в размещении «яиц» (вновь найденных решений) в «гнездах» и сохранении лучших в качестве кандидатов для следующего поколения. Новые растворы могут быть выброшены случайным образом («яйца» выбрасываются из «гнезда»).

Алгоритм летучей мыши (Ян, 2010)

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

Алгоритм спиральной оптимизации (SPO) (Тамура и Ясуда, 2011, 2016-2017)

Спиральный алгоритм оптимизация (SPO) является несложной концепцией поиска вдохновленной спиральными явлений в природе. Мотивация к сосредоточению внимания на спиральных явлениях была связана с пониманием того, что динамика, порождающая логарифмические спирали, разделяет поведение диверсификации и интенсификации. Поведение диверсификации может работать для глобального поиска (исследования), а поведение интенсификации позволяет проводить интенсивный поиск вокруг текущего найденного хорошего решения (эксплуатации). Алгоритм SPO - это алгоритм многоточечного поиска, не имеющий градиента целевой функции, который использует несколько спиральных моделей, которые можно описать как детерминированные динамические системы. Поскольку точки поиска следуют по логарифмическим спиральным траекториям к общему центру, определяемому как текущая лучшая точка, могут быть найдены лучшие решения и общий центр может быть обновлен.

Алгоритм опыления цветов (Ян, 2012)

Алгоритм опыления цветов - это метаэвристический алгоритм , разработанный Xin-She Yang , основанный на процессе опыления цветущих растений .

В этом алгоритме есть 4 правила или предположения:

1. Биотическое и перекрестное опыление рассматривается как глобальный процесс опыления, когда опылители, несущие пыльцу, выполняют полеты Леви .
2. Абиотическое опыление и самоопыление рассматриваются как местное опыление.
3. Постоянство цветка можно рассматривать, поскольку вероятность воспроизводства пропорциональна сходству двух задействованных цветов.
4. Местное и глобальное опыление контролируется вероятностью переключения . Из-за физической близости и других факторов, таких как ветер, местное опыление может составлять значительную долю q в общей активности опыления.${\ displaystyle p \ in [0,1]}$

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

${\ displaystyle x_ {i} ^ {t + 1} = x_ {i} ^ {t} + L (x_ {i} ^ {t} -g _ {*})}$

${\ displaystyle x_ {i} ^ {t + 1} = x_ {i} ^ {t} + \ epsilon (x_ {i} ^ {t} -x_ {k} ^ {t})}$

где - вектор решения, а - текущий лучший результат, найденный на данный момент во время итерации. Вероятность переключения между двумя уравнениями во время итераций составляет . Кроме того, это случайное число, полученное из равномерного распределения. - размер шага, взятый из распределения Леви. ${\ displaystyle x_ {i} ^ {t}}$${\ displaystyle g _ {*}}$${\ displaystyle p}$${\ displaystyle \ epsilon}$${\ displaystyle L}$

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

${\ displaystyle L \ sim {\ frac {1} {s ^ {1+ \ beta}}},}$

где - показатель Леви. Правильно нарисовать шаги Леви может оказаться сложной задачей, и простой способ создания полетов Леви состоит в использовании двух нормальных распределений и преобразования ${\ displaystyle \ beta}$${\ displaystyle s}$${\ displaystyle u}$${\ displaystyle v}$

${\ displaystyle s = {\ frac {u} {| v | ^ {1+ \ beta}}},}$

с участием

${\ displaystyle u \ sim N (0, \ sigma ^ {2}), \ quad v \ sim N (0,1),}$

где - функция от . ${\ displaystyle \ sigma}$${\ displaystyle \ beta}$

Алгоритм гетерогенных распределенных пчел (Ткач и др., 2013)

Алгоритм гетерогенных распределенных пчел (HDBA), также известный как модифицированный распределенный алгоритм пчел (MDBA), представляет собой многоагентный метаэвристический алгоритм, впервые представленный Ткачем и его сотрудниками в 2013 году и разработанный в рамках его докторской диссертации. HDBA использует вероятностную технику, вдохновленную поведением пчел при кормлении. Это позволяет решать задачи комбинаторной оптимизации с несколькими разнородными агентами, которые обладают разными возможностями и производительностью. Окончательный механизм принятия решений использует правило выбора колеса, где каждый агент имеет вероятность, с которой он выбирает решение. Впервые он был применен для случая неоднородных датчиков в задаче распознавания целей для улучшения производительности системы путем сопоставления функции полезности датчиков со значением их характеристик. Впоследствии это было успешно применено к другим проблемам, включая проблему распределения полицейских агентов по преступлениям и выработку почти оптимальных решений проблемы коммивояжера.

Алгоритм искусственной экосистемы (Baczyński, 2013)

Алгоритм искусственной экосистемы (AEA) - это вероятностный метод оптимизации, основанный на некоторых явлениях, происходящих в естественных экосистемах. Отношения между людьми моделируются как их взаимоотношениями внутри одной группы, так и отношениями между людьми, принадлежащими к разным группам, сосуществующими как часть экологической системы. Есть три основных типа организмов: растения, травоядные и хищники. Все типы организмов воспроизводятся (переходят и видоизменяются) внутри своего собственного вида. В качестве метода он включает некоторые эволюционные алгоритмы и элементы PSO с дополнительными расширениями. Это довольно сложный метод, но он доказал свою способность решать задачи как непрерывной, так и комбинаторной оптимизации.

Кооперативная оптимизация группы (2014)

Система кооперативной групповой оптимизации (CGO) - это метаэвристическая структура для реализации экземпляров алгоритмов путем интеграции преимуществ кооперативной группы и низкоуровневого проектирования портфеля алгоритмов. Следуя вдохновленной природой парадигме кооперативной группы, агенты не только исследуют параллельно своей индивидуальной памяти, но также сотрудничают со своими сверстниками через групповую память. Каждый агент имеет портфель (разнородных) встроенных эвристик поиска (ESH), в котором каждый ESH может перевести группу в автономный CGO-кейс, а гибридные CGO-кейсы в алгоритмическом пространстве могут быть определены с помощью низкоуровневого кооперативного поиска среди портфель алгоритмов (ESH) посредством настраиваемого совместного использования памяти. Пассивный лидер группы может также облегчить процесс оптимизации за счет кодирования знаний в среде поиска. Он был применен как к задачам численной, так и к комбинаторной оптимизации.

Искусственный интеллект роя (Розенберг, 2014)

Под искусственным роевым интеллектом понимается замкнутая система в реальном времени, состоящая из людей-пользователей, подключенных через Интернет и структурированная в рамках, смоделированных по образцу естественных роей, таким образом, что она вызывает коллективную мудрость группы как единый возникающий интеллект. Таким образом, стаи людей могут отвечать на вопросы, делать прогнозы, принимать решения и решать проблемы, коллективно исследуя разнообразные варианты и синхронно находя предпочтительные решения. Изобретенная доктором Луи Розенбергом в 2014 году методология ASI стала известной благодаря своей способности делать точные коллективные прогнозы, превосходящие по эффективности отдельных членов роя. В 2016 году репортер бросил вызов искусственному интеллекту роя от Unanimous AI , чтобы предсказать победителей Кентукки Дерби , и успешно выбрал первых четырех лошадей по порядку, превзойдя шансы 540 к 1.

Оптимизация сталкивающихся тел (Кавех и Махдави, 2014)

Алгоритм оптимизации сталкивающихся тел (CBO) был создан Каве и Махдави в 2014 году на основе законов импульса и энергии. Этот алгоритм не зависит от каких-либо внутренних параметров, а также чрезвычайно прост в реализации, использовании и использовании в различных типах инженерных задач.

Алгоритм дуэлянта (Биянто, 2016)

Алгоритм дуэлянта относится к алгоритму оптимизации на основе генов, аналогичному генетическим алгоритмам . Алгоритм дуэлянтов начинается с первоначального набора дуэлянтов. Поединок заключается в определении победителя и проигравшего. Проигравший учится у победителя, а победитель пробует свои новые навыки или приемы, которые могут улучшить их боевые способности. Несколько дуэлянтов с высокими боевыми способностями называются чемпионом. Чемпион тренирует нового дуэлянта, исходя из своих возможностей. Новый дуэлянт присоединится к турниру как представитель каждого чемпиона. Все дуэлянты переоцениваются, а дуэлянты с худшими боевыми способностями удаляются, чтобы сохранить количество дуэлянтов.

Оптимизация Харриса ястреба (Heidari et al., 2019)

Оптимизатор ястребов Харриса (HHO) вдохновляет охотничьи стратегии Харриса на ястребов и способы побега кроликов в природе .

Алгоритм касаток (Биянто, 2016)

Killer Whale Algorithm - это алгоритм, вдохновленный жизнью косаток. Философия алгоритма - это модели движения косаток при охоте на добычу и социальная структура косаток. Новизна этого алгоритма заключается в том, что в алгоритм включена « способность запоминания » касатки.

Алгоритм дождевой воды (Biyanto, 2017)

« Физические движения капель дождя с использованием движения закона Ньютона » вдохновили авторов на создание этого алгоритма. Каждая капля дождя представляет собой случайные значения оптимизированных переменных, которые различаются по массе и высоте. Он упадет на землю, следуя " свободному падению " со скоростью, равной квадратному корню из времени ускорения свободного падения . Следующее движение - « равномерно ускоренное движение » по пути капли дождя, чтобы достичь самого низкого места на земле. Самое низкое место в земле - целевая функция этого алгоритма.

Алгоритм баланса массы и энергии (Biyanto, 2018)

Баланс массы и энергии - это фундаментальный « закон физики », который гласит, что масса не может быть ни произведена, ни разрушена. Это только законсервировано. Не менее фундаментальным является закон сохранения энергии. Хотя энергия может меняться по форме, она также не может быть создана или уничтожена. Прелесть этого алгоритма заключается в возможности достичь глобального оптимального решения, одновременно работая « методом минимизации и максимизации ».

Алгоритм гидрологического цикла (Wedyan et al., 2017)

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

Колония императорских пингвинов (Харифи и др., 2019)

Этот алгоритм представляет собой новый метаэвристический алгоритм, вдохновленный поведением императорских пингвинов, обитающих в Антарктиде. EPC контролируется тепловым излучением тела пингвинов и их спиралевидным движением в своей колонии. Императорские пингвины в колонии стремятся создать соответствующее тепло и регулировать температуру своего тела, и это тепло полностью координируется и контролируется движением пингвинов.

Алгоритм Momentum Balance (MBA) (Biyanto et al., 2019)

Баланс импульса - это один из трех фундаментальных «законов физики», согласно которому масса, энергия и импульс только сохраняются. Использование баланса импульса было предложено во многих приложениях.

В этом исследовании был принят баланс импульса, чтобы получить идеально упругое столкновение. В идеальном, идеально упругом столкновении нет потерь кинетической энергии на другие формы, такие как потенциальная энергия, тепло и шум. Красота этого алгоритма так же проста, как и детерминированные алгоритмы оптимизации, однако алгоритм баланса импульса имеет возможность достичь глобального оптимального решения.

Алгоритм оптимизации Shuffled Shepherd (SSOA) (Kaveh and Zaerreza, 2020)

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

Алгоритм оптимизации поденок (MA) (Zervoudakis & Tsafarakis, 2020)

Алгоритм оптимизации поденок был разработан для решения как задач непрерывной, так и дискретной оптимизации и основан на поведении поденок и процессе спаривания поденок. Процессы брачного танца и случайного полета улучшают баланс между исследовательскими и эксплуатационными свойствами алгоритма и помогают ему выйти из локальных оптимумов. По производительности алгоритм поденок превосходит другие популярные метаэвристики, такие как PSO, DE, GA и FA, с точки зрения скорости сходимости и скорости сходимости.

Политический оптимизатор (ПО) (Камар Аскари, Ирфан Юнас и Мехрин Саид, 2020 г.)

Политический оптимизатор (PO) - это алгоритм, основанный на социальном поведении человека, вдохновленный многопартийной политической системой. Источник вдохновения сформулирован как набор из 5 этапов: формирование партии и распределение избирательных округов, смена партии, избирательная кампания, межпартийные выборы и парламентские дела. У PO есть две уникальные особенности: логическое разделение совокупности для присвоения двойной роли каждому возможному решению и стратегия обновления позиции на основе недавнего прошлого (RPPUS). PO демонстрирует отличную производительность против 15 хорошо известных метаэвристик для 50 унимодальных и мультимодальных тестовых функций и 4 инженерных задач.

Оптимизатор на основе кучи (HBO) (Камар Аскари, Мехрин Саид, Ирфан Юнас, 2020 г.)

HBO - это метаэвристика, основанная на социальном поведении человека, вдохновленная корпоративной иерархией рангов и взаимодействием между сотрудниками, организованными в иерархию. Уникальность HBO заключается в использовании структуры данных кучи для моделирования иерархического расположения сотрудников и введении параметра (γ) для альтернативного включения исследования и эксплуатации. Более того, три уравнения, выведенные для трех фаз HBO, вероятностно объединены, чтобы уравновесить разведку и разработку. HBO демонстрирует потрясающую производительность в 97 тестах и ​​3 задачах машиностроения.

Алгоритм криминалистического расследования (ФБР) (Дж. С. Чоу и Н. М. Нгуен, 2020 г.)

Основной мотивацией для разработки нового алгоритма является его способность эффективно решать различные задачи оптимизации. Новый метод оптимизации, алгоритм криминалистического расследования (FBI), разработан для определения глобальных решений для непрерывных нелинейных функций с низкими вычислительными затратами и высокой точностью. ФБР вдохновлено процессом полицейских «расследование - местонахождение - преследование». Основные особенности FBI: (1) FBI - алгоритм оптимизации без параметров; (2) ФБР значительно превзошло хорошо известные и недавно разработанные алгоритмы; (3) FBI имеет короткое время вычислений и быстро находит оптимальные решения в решении проблем; (4) ФБР эффективно решает задачи большой размерности (D = 1000); и (5) в структуре ФБР есть две команды, которые хорошо сочетают разведку и разработку.

Подробности можно найти по адресу: Chou JS, Nguyen NM, Метаоптимизация, вдохновленная ФБР, Applied Soft Computing, 2020: 106339, ISSN 1568-4946, https://doi.org/10.1016/j.asoc.2020.106339

Поиск медуз (JS) (JS Chou and DN Truong, 2021)

Оптимизатор Jellyfish Search (JS) вдохновлен поведением медуз в океане. Моделирование поискового поведения медуз включает в себя их следование за океаническим течением, их движения внутри роя медуз (активные движения и пассивные движения), механизм контроля времени для переключения между этими движениями и их схождение в цветение медуз. Новый алгоритм успешно протестирован на тестовых функциях и задачах оптимизации. Примечательно, что JS имеет только два управляющих параметра: размер популяции и количество итераций. Следовательно, JS очень прост в использовании и потенциально является отличным метаэвристическим алгоритмом для решения задач оптимизации.

Оптимизатор Golden Eagle (GEO) (Mohammadi-Balani et al., 2020)

Golden Eagle Optimizer (GEO) - это метаэвристический алгоритм, основанный на популяционном рое и интеллекте, созданный на основе охотничьего поведения беркутов . Алгоритм моделирует это поведение, разделяя вектор скорости беркутов на две составляющие: а) вектор атаки и б) вектор крейсерского полета. Вектор атаки для каждого беркут (поискового агента) начинается с текущей позиции беркут и заканчивается в том месте, где находится жертва в памяти каждого беркут. Добыча каждого беркута - лучшее место, которое он когда-либо посещал. Беркуты кружат вокруг добычи в гипотетических гиперсферах. Крейсерский вектор - это вектор, касательный к гипотетической гиперсфере для каждого беркута. Оригинальная статья содержит как одноцелевые, так и многокритериальные версии алгоритма. Исходный код, набор инструментов и графический пользовательский интерфейс для Golden Eagle Optimizer (GEO) и Multi-Objective Golden Eagle Optimizer (MOGEO) также разработаны для MATLAB.

Критика методологии метафоры

В то время как метаэвристика, вдохновленная отдельными метафорами, дает удивительно эффективные решения конкретных проблем, метаэвристика, вдохновленная метафорами, в целом вызывает критику в исследовательском сообществе за то, что скрывает свою неэффективность или новизну за сложной метафорой. Кеннет Соренсен отметил, что:

В последние годы область комбинаторной оптимизации стала свидетелем настоящего цунами «новых» метаэвристических методов, большинство из которых основано на метафоре некоего естественного или искусственного процесса. Поведение практически любых видов насекомых, поток воды, совместная игра музыкантов - кажется, ни одна идея не является слишком надуманной, чтобы служить вдохновением для запуска еще одной метаэвристики. [Я] буду утверждать, что это направление исследований угрожает увести область метаэвристики от научной строгости.

Соренсен и Гловер заявили, что:

Большое (и постоянно увеличивающееся) количество публикаций посвящено разработке (предположительно) новых метаэвристических структур, основанных на метафорах. Список естественных или антропогенных процессов, который был использован в качестве основы для метаэвристической схемы, теперь включает такие разнообразные процессы, как сбор бактерий, формирование рек , биогеография, совместная игра музыкантов, электромагнетизм, гравитация , колонизация империей , взрывы мин и т. Д. чемпионаты лиги, облака и так далее. Важная подкатегория находится в метаэвристике, основанной на поведении животных. Муравьи , пчелы, летучие мыши , волки, кошки, светлячки , орлы, дельфины, лягушки , лосось, стервятники, термиты, мухи и многие другие - все они были использованы для создания «нового» метаэвристического метода. [...] Как правило, публикация статей по метаэвристике на основе метафор ограничивается журналами и конференциями второго уровня, но из этого правила можно найти некоторые недавние исключения. Соренсен (2013) утверждает, что исследования в этом направлении в корне ошибочны. Наиболее важно то, что автор утверждает, что новизна основной метафоры не делает автоматически получившуюся основу «новой». Напротив, появляется все больше свидетельств того, что очень немногие методы, основанные на метафорах, являются новыми в каком-либо интересном смысле.

В ответ на это издание Springer 's Journal of Heuristics обновило свою редакционную политику, заявив, что:

Предложение новых парадигм допустимо только в том случае, если они содержат новаторские базовые идеи, такие как те, которые встроены в классические структуры, такие как генетические алгоритмы , запретный поиск и моделирование отжига . Журнал эвристики избегает публикации статей, которые переупаковывают и внедряют старые идеи в методы, которые, как утверждается, основаны на метафорах естественных или созданных руками человека систем и процессов. В этих так называемых «новых» методах используются аналогии, которые варьируются от разумных капель воды , музыкантов, играющих джаз, до империалистических обществ , чехарды , кенгуру, всех типов стаей и насекомых и даже процессов взрыва мин (Sörensen, 2013). Если исследователь использует метафору, чтобы стимулировать свои собственные идеи о новом методе, метод, тем не менее, должен быть переведен на язык, свободный от метафор, чтобы используемые стратегии можно было четко понять, а их новизна была ясно видна. (См. Пункты 2 и 3 ниже.) Метафоры дешевы, и их легко найти. Их использование для «демонстрации» метода неприемлемо ».

[...] Реализации следует объяснять, используя стандартную терминологию оптимизации, где решение называется «решением», а не что-то еще, связанное с какой-то неясной метафорой (например, гармония, мухи , летучие мыши , страны и т. Д.).

[...] Журнал эвристики полностью поддерживает точку зрения Соренсена о том, что метафорические «новые» методы не должны публиковаться, если они не могут продемонстрировать вклад в свою область. Переименование существующих концепций не считается вкладом. Несмотря на то, что эти методы часто называют «новыми», многие из них не представляют новых идей, за исключением случайных маргинальных вариантов уже существующей методологии. Эти методы не должны занимать пространство журнала для действительно инновационных идей и исследований. Поскольку они не используют стандартный словарь оптимизации, их излишне трудно понять.

Политика Springer журнала «s 4- или - Ежеквартальный журнал исследования операций утверждает , что:

Акцент на научную строгость и инновации подразумевает, в частности, что журнал не публикует статьи, которые просто предлагают замаскированные варианты известных методов без надлежащей проверки (например, метаэвристика, которая считается «эффективной» только на основе метафорических сравнений. с естественными или искусственными системами и процессами). Новые методы должны быть представлены языком без метафор, устанавливая их связь с классическими парадигмами. Их свойства должны быть установлены на основе убедительных с научной точки зрения аргументов: математических доказательств, контролируемых экспериментов, объективных сравнений и т. Д.

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

• Концептуальная метафора
• Метафора научного сообщества

Примечания

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

• Соренсен, Кеннет; Сево, Марк; Гловер, Фред (2017-01-16). «История метаэвристики» (PDF) . В Марти, Рафаэль; Панос, Пардалос; Ресенде, Маурисио (ред.). Справочник по эвристике . Springer. ISBN 978-3-319-07123-7.
• Соренсен, Кеннет (2015). «Метаэвристика - метафора разоблачения». Международные операции в операционных исследованиях . 22 : 3–18. CiteSeerX  10.1.1.470.3422 . DOI : 10.1111 / itor.12001 .
• Одинокий, Майкл А. (2014). «Метаэвристика в алгоритмах, вдохновленных природой». Труды спутника конференции 2014 года по генетическим и эволюционным вычислениям, спутника - GECCO Comp '14 . С. 1419–22. CiteSeerX  10.1.1.699.1825 . DOI : 10.1145 / 2598394.2609841 . ISBN 9781450328814. S2CID  14997975 .
• Фистер, Изток; Ян, Синь-Шэ; Фистер, Изток; Брест, Янез; Фистер, Душан (2013). «Краткий обзор вдохновленных природой алгоритмов оптимизации». Электротехники Вестник . arXiv : 1307.4186 .

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

• Бестиарий эволюционных вычислений  - ироничный отчет обо всей странной, даже причудливой метаэвристике, основанной на метафорах, в широком мире академических публикаций.
•  Список метаэвристических алгоритмов Science Matrix - полный список метаэвристических алгоритмов. Список может быть легко отфильтрован по имени, автору или году и содержит ссылку на основную публикацию каждого алгоритма.