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

Вычислительный метод, используемый для решения задач оптимизации разных типов

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

Метафора

Рисунок 1: Блок-схема империалистического конкурентного алгоритма (ICA)

На рисунке 1 показана блок-схема Империалистического конкурентного алгоритма. Этот алгоритм начинается с генерации набора кандидатов случайных решений в поисковом пространстве задачи оптимизации. Сгенерированные случайные точки называются начальными странами . Страны в этом алгоритме являются аналогом хромосом в ГА и частиц в оптимизации роя частиц (PSO), и это массив значений кандидата решения задачи оптимизации. Функция стоимости задачи оптимизации определяет силу каждой страны. Основываясь на своей силе, некоторые из лучших начальных стран (страны с наименьшим значением функции стоимости) становятся империалистами и начинают захватывать другие страны (называемые колониями ) и формировать начальные империи . ^[1]

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

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

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

Алгоритм

Вышеуказанные шаги можно суммировать в виде следующего псевдокода . ^[2]^[3]

0) Определим целевую функцию: $f(\mathbf {x}),\quad \mathbf {x} =(x_{1},x_{2},\dots,x_{d});\,$ 1) Инициализация алгоритма. Генерируем случайное решение в пространстве поиска и создаем начальные империи. 2) Ассимиляция: колонии движутся к империалистическим государствам в разных направлениях. 3) Революция: в характеристиках некоторых стран происходят случайные изменения. 4) Обмен позициями между колонией и империалистом. Колония с лучшей позицией, чем империалист, имеет шанс взять под контроль империю, заменив существующего империалиста. 5) Империалистическая конкуренция: Все империалисты конкурируют за обладание колониями друг друга. 6) Уничтожить бессильные империи. Слабые империи постепенно теряют свою силу и в конце концов будут уничтожены. 7) Если условие остановки выполнено, остановиться, если нет, перейти к пункту 2.8) Конец

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

Список метаэвристик, основанных на метафорах

Ссылки

^ abc Atashpaz-Gargari, E.; Lucas, C (2007). «Империалистический конкурентный алгоритм: алгоритм оптимизации, вдохновленный империалистической конкуренцией» (PDF) . IEEE Congress on Evolutionary Computation . Vol. 7. pp. 4661– 4666.^{[ мертвая ссылка ‍ ]}
^ ab Hosseini, S.; Al Khaled, A. (2014). «Обзор метаэвристики империалистического конкурентного алгоритма: реализация в инженерной области и направления будущих исследований». Applied Soft Computing . 24 : 1078– 1094. doi :10.1016/j.asoc.2014.08.024.
^ ab Nazari-Shirkouhi, S.; Eivazy, H.; Ghodsi, R.; Rezaie, K.; Atashpaz-Gargari, E. (2010). «Решение проблемы аутсорсинга интегрированного ассортимента продукции с помощью нового метаэвристического алгоритма: империалистический конкурентный алгоритм». Expert Systems with Applications . 37 (12): 7615– 7626. doi :10.1016/j.eswa.2010.04.081.

[ica_en_2007_cnf_atashpaz_ica_ica-1] Atashpaz-Gargari, E.; Lucas, C (2007). «Империалистический конкурентный алгоритм: алгоритм оптимизации, вдохновленный империалистической конкуренцией» (PDF) . IEEE Congress on Evolutionary Computation . Vol. 7. pp. 4661– 4666.^{[ мертвая ссылка ‍ ]}

[ICA_2014_Survey-2] Hosseini, S.; Al Khaled, A. (2014). «Обзор метаэвристики империалистического конкурентного алгоритма: реализация в инженерной области и направления будущих исследований». Applied Soft Computing . 24 : 1078– 1094. doi :10.1016/j.asoc.2014.08.024.

[ica_en_2010_jnl_nazari_integrated_product_mix_outsourcing-3] Nazari-Shirkouhi, S.; Eivazy, H.; Ghodsi, R.; Rezaie, K.; Atashpaz-Gargari, E. (2010). «Решение проблемы аутсорсинга интегрированного ассортимента продукции с помощью нового метаэвристического алгоритма: империалистический конкурентный алгоритм». Expert Systems with Applications . 37 (12): 7615– 7626. doi :10.1016/j.eswa.2010.04.081.