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

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

Метафора

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

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

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

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

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

Алгоритм

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

0) Define objective function:  $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 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

См. также

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

Ссылки

^ Jump up to: ^а ^б ^с Аташпаз-Гаргари, Э.; Лукас, К. (2007). «Империалистический конкурентный алгоритм: алгоритм оптимизации, вдохновленный империалистической конкуренцией» (PDF) . Конгресс IEEE по эволюционным вычислениям . Том. 7. С. 4661–4666. ^{[ мертвая ссылка ]}
^ Jump up to: ^а ^б Хоссейни, С.; Аль Халед, А. (2014). «Обзор метаэвристики империалистического конкурентного алгоритма: реализация в инженерной области и направления будущих исследований». Прикладные мягкие вычисления . 24 : 1078–1094. дои : 10.1016/j.asoc.2014.08.024 .
^ Jump up to: ^а ^б Назари-Ширкуи, С.; Эйвази, Х.; Годси, Р.; Резаи, К.; Аташпаз-Гаргари, Э. (2010). «Решение проблемы аутсорсинга интегрированного ассортимента продукции с помощью нового метаэвристического алгоритма: империалистического конкурентного алгоритма». Экспертные системы с приложениями . 37 (12): 7615–7626. дои : 10.1016/j.eswa.2010.04.081 .

[ica_en_2007_cnf_atashpaz_ica_ica-1] Jump up to: ^а ^б ^с Аташпаз-Гаргари, Э.; Лукас, К. (2007). «Империалистический конкурентный алгоритм: алгоритм оптимизации, вдохновленный империалистической конкуренцией» (PDF) . Конгресс IEEE по эволюционным вычислениям . Том. 7. С. 4661–4666. ^{[ мертвая ссылка ]}

[ICA_2014_Survey-2] Jump up to: ^а ^б Хоссейни, С.; Аль Халед, А. (2014). «Обзор метаэвристики империалистического конкурентного алгоритма: реализация в инженерной области и направления будущих исследований». Прикладные мягкие вычисления . 24 : 1078–1094. дои : 10.1016/j.asoc.2014.08.024 .

[ica_en_2010_jnl_nazari_integrated_product_mix_outsourcing-3] Jump up to: ^а ^б Назари-Ширкуи, С.; Эйвази, Х.; Годси, Р.; Резаи, К.; Аташпаз-Гаргари, Э. (2010). «Решение проблемы аутсорсинга интегрированного ассортимента продукции с помощью нового метаэвристического алгоритма: империалистического конкурентного алгоритма». Экспертные системы с приложениями . 37 (12): 7615–7626. дои : 10.1016/j.eswa.2010.04.081 .

[1]

[2]

[3]