Алгоритъм на империалистическата конкуренция () е вид метаевристичен алгоритъм, използван за решаване на различни оптимизационни задачи. Като повечето методи в областта на еволюционните изчисления, алгоритъмът не се нуждае от градиент на функция, по който да извършва оптимизационния процес. В определен смисъл, алгоритъмът на империалистическата конкуренция може да бъде мислен като социален аналог на генетичните алгоритми; той е математически модел и симулация на социалната еволюция при хората, както генетичните алгоритми симулират биологичната еволюция на видовете.
Алгоритъмът се инициализира с генериране на множество от случайни кандидат-решения в съответното пространство на търсене на дадената оптимизационна задача. Генерираните случайни точки се наричат начални Държави. Държавите в този алгоритъм са аналози на хромозомите в генетичните алгоритми и на частиците в оптимизацията на частици в рояк (Particle Swarm Optimization, PSO), т.е. масив от стойности на кандидат-решението на оптимизационната задача. Целевата функция (фитнес функция, ценова функция) на оптимизационната задача определя силата на всяка от държавите. В зависимост от силата им, някои от най-добрите начални държави стават Империалисти и започват да завземат контрола над други държави, наречени Колонии, и така започват да формират началните Империи.
Двата основни оператора в този вид метаевристика са Асимилация и Революция. Операторът Асимилация прави колониите на всяка империя да се доближават до завладелия ги Империалист в пространството на социополитическите характеристики (пространството на търсене в оптимизационната задача). Операторът Революция въвежда случайни внезапни промени в позицията на някои държави спрямо други (аналог на оператора мутация в генетичните алгоритми). Чрез асимилация и революция, Колонията може да постигне по-добро положение и има възможност да получи контрол над цялата Империя и да измести държавата, която текущо владее Империята.
Империалистическата конкуренция е друга част от алгоритъма. Всички империи се опитват да спечелят играта и да завладеят колониите на останалите империи. На всяка стъпка от алгоритъма, в зависимост от тяхната сила, всички империи имат шанс да завземат контрола над една или повече от колониите на най-слабата империя.
Алгоритъмът продължава със споменатите стъпки (Асимилация, Революция, Конкуренция) докато не бъде удовлетворено определено условие за край.
Горните стъпки могат да се обобщят във вида на следния псевдокод.
0) Дефиниране на целевата функция: 1) Инициализация на алгоритъма. Генериране на някакви случайни решения в пространството на търсене и създаване на началните империи. 2) Асимилация: Колониите се придвижват към Империалистическите държави в различни посоки. 3) Революция: Настъпват случайни промени в характеристиките на някои държави (решения). 4) Смяна на местата на Колония и Империалист. Колония с по-добри характеристики от Империалиста има шанс да завземе контрола над империята, като измести текущия Империалист. 5) Империалистическа конкуренция: Всички империалисти се конкурират в отнемането на колонии една от друга. 6) Елиминация на слабите империи. Слабите империи постепенно губят мощта си и в последна сметка биват елиминирани. 7) Ако е изпълнено условие за край, Край, в противен случай, връщане в точка 2). 8) Край
Източници
Категория:Метаевристични алгоритми