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

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

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

Алгоритъмът се инициализира с генериране на множество от случайни кандидат-решения в съответното пространство на търсене на дадената оптимизационна задача. Генерираните случайни точки се наричат начални Държави. Държавите в този алгоритъм са аналози на хромозомите в генетичните алгоритми и на частиците в оптимизацията на частици в рояк (Particle Swarm Optimization, 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) Край

Източници[редактиране | редактиране на кода]

↑ ^а ^б ^в Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition // IEEE Congress on Evolutionary Computation. Т. 7. 2007, 4661–4666 с.
↑ ^а ^б Hosseini, S. и др. A survey on the Imperialist Competitive Algorithm metaheuristic: Implementation in engineering domain and directions for future research // Applied Soft Computing 24. 2014. с. 1078–1094.
↑ ^а ^б Nazari-Shirkouhi, S. и др. Solving the Integrated Product Mix-Outsourcing Problem by a Novel Meta-Heuristic Algorithm: Imperialist Competitive Algorithm // Expert Systems with Applications 37 (12). 2010. DOI:10.1016/j.eswa.2010.04.081. с. 7615–7626.

Тази страница частично или изцяло представлява превод на страницата List_of_metaphor-based_metaheuristics#Imperialist_competitive_algorithm_.28Atashpaz-Gargari_.26_Lucas_2007.29 в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[ica_en_2007_cnf_atashpaz_ica_ica-1] а ^б ^в Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition // IEEE Congress on Evolutionary Computation. Т. 7. 2007, 4661–4666 с.

[ICA_2014_Survey-2] а ^б Hosseini, S. и др. A survey on the Imperialist Competitive Algorithm metaheuristic: Implementation in engineering domain and directions for future research // Applied Soft Computing 24. 2014. с. 1078–1094.

[ica_en_2010_jnl_nazari_integrated_product_mix_outsourcing-3] а ^б Nazari-Shirkouhi, S. и др. Solving the Integrated Product Mix-Outsourcing Problem by a Novel Meta-Heuristic Algorithm: Imperialist Competitive Algorithm // Expert Systems with Applications 37 (12). 2010. DOI:10.1016/j.eswa.2010.04.081. с. 7615–7626.

[1]

[2]

[3]