Алгоритъм на империалистическата конкуренция

Алгоритъм на империалистическата конкуренция (на английски: Imperialist Competitive Algorithm, ICA) е вид метаевристичен алгоритъм, използван за решаване на различни оптимизационни задачи.^{[1] [2]} Като повечето методи в областта на еволюционните изчисления, алгоритъмът не се нуждае от градиент на функция, по който да извършва оптимизационния процес. В определен смисъл, алгоритъмът на империалистическата конкуренция може да бъде мислен като социален аналог на генетичните алгоритми; той е математически модел и симулация на социалната еволюция при хората, както генетичните алгоритми симулират биологичната еволюция на видовете.

Блоксхема на алгоритъма на империалистическата конкуренция

Алгоритъмът се инициализира с генериране на множество от случайни кандидат-решения в съответното пространство на търсене на дадената оптимизационна задача. Генерираните случайни точки се наричат начални Държави. Държавите в този алгоритъм са аналози на хромозомите в генетичните алгоритми и на частиците в оптимизацията на частици в рояк (Particle Swarm Optimization, PSO), т.е. масив от стойности на кандидат-решението на оптимизационната задача. Целевата функция (фитнес функция, ценова функция) на оптимизационната задача определя силата на всяка от държавите. В зависимост от силата им, някои от най-добрите начални държави стават Империалисти и започват да завземат контрола над други държави, наречени Колонии, и така започват да формират началните Империи.^[1]

Двата основни оператора в този вид метаевристика са Асимилация и Революция. Операторът Асимилация прави колониите на всяка империя да се доближават до завладелия ги Империалист в пространството на социополитическите характеристики (пространството на търсене в оптимизационната задача). Операторът Революция въвежда случайни внезапни промени в позицията на някои държави спрямо други (аналог на оператора мутация в генетичните алгоритми). Чрез асимилация и революция, Колонията може да постигне по-добро положение и има възможност да получи контрол над цялата Империя и да измести държавата, която текущо владее Империята.^[3]

Империалистическата конкуренция е друга част от алгоритъма. Всички империи се опитват да спечелят играта и да завладеят колониите на останалите империи. На всяка стъпка от алгоритъма, в зависимост от тяхната сила, всички империи имат шанс да завземат контрола над една или повече от колониите на най-слабата империя.^[1]

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

Горните стъпки могат да се обобщят във вида на следния псевдокод.^[2][3]

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