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

'''Алгоритъм на империалистическата конкуренция''' ({{lang|en|Imperialist Competitive Algorithm, ICA}}) е вид [[метаевристичен алгоритъм]], използван за решаване на различни [[математическа оптимизация|оптимизационни]] задачи.<ref name=ica_en_2007_cnf_atashpaz_ica_ica>{{cite conference
|last1= Atashpaz-Gargari
|first1= E.
|last2= Lucas
|first2= C
|title= Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition
|booktitle= IEEE Congress on Evolutionary Computation
|year= 2007
|volume= 7
|pages= 4661–4666
}}</ref>
<ref name=ICA_2014_Survey>{{cite journal
|last1= Hosseini
|first1=S.
|last2=Al Khaled
|first2=A.
|title=A survey on the Imperialist Competitive Algorithm metaheuristic: Implementation in engineering domain and directions for future research
|journal=Applied Soft Computing
|year=2014
|volume=24
|pages=1078–1094
}}</ref> Като повечето методи в областта на [[еволюционни изчисления|еволюционните изчисления]], алгоритъмът не се нуждае от градиент на функция, по който да извършва оптимизационния процес. В определен смисъл, алгоритъмът на империалистическата конкуренция може да бъде мислен като социален аналог на [[генетични алгоритми|генетичните алгоритми]]; той е [[математически модел]] и симулация на [[социална еволюция|социалната еволюция]] при хората, както генетичните алгоритми симулират [[еволюция|биологичната еволюция]] на [[вид (биология)|видовете]].

[[Файл:Imperialist-competitive-algorithm-flowchart-bg.png|дясно|мини|600px|Блоксхема на алгоритъма на империалистическата конкуренция]]
Алгоритъмът се инициализира с генериране на множество от случайни [[кандидат-решение|кандидат-решения]] в съответното пространство на търсене на дадената оптимизационна задача. Генерираните случайни точки се наричат начални ''Държави''. Държавите в този алгоритъм са аналози на хромозомите в генетичните алгоритми и на частиците в [[оптимизация на частици в рояк|оптимизацията на частици в рояк]] (''Particle Swarm Optimization, PSO''), т.е. масив от стойности на кандидат-решението на оптимизационната задача. Целевата функция ([[фитнес функция]], ценова функция) на оптимизационната задача определя силата на всяка от държавите. В зависимост от силата им, някои от най-добрите начални държави стават ''Империалисти'' и започват да завземат контрола над други държави, наречени ''Колонии'', и така започват да формират началните ''Империи''.<ref name=ica_en_2007_cnf_atashpaz_ica_ica />

Двата основни оператора в този вид метаевристика са Асимилация и Революция. Операторът ''Асимилация'' прави колониите на всяка империя да се доближават до завладелия ги Империалист в пространството на социополитическите характеристики (пространството на търсене в оптимизационната задача). Операторът ''Революция'' въвежда случайни внезапни промени в позицията на някои държави спрямо други (аналог на [[мутация (генетичен оператор)|оператора мутация]] в генетичните алгоритми). Чрез асимилация и революция, Колонията може да постигне по-добро положение и има възможност да получи контрол над цялата Империя и да измести държавата, която текущо владее Империята.<ref name=ica_en_2010_jnl_nazari_integrated_product_mix_outsourcing>{{cite journal
|last1= Nazari-Shirkouhi
|first1= S.
|last2= Eivazy
|first2= H.
|last3= Ghodsi
|first3= R.
|last4= Rezaie
|first4= K.
|last5= Atashpaz-Gargari
|first5= E.
|title= Solving the Integrated Product Mix-Outsourcing Problem by a Novel Meta-Heuristic Algorithm: Imperialist Competitive Algorithm
|journal= Expert Systems with Applications
|year= 2010
|volume= 37
|issue= 12
|pages= 7615–7626
|doi=10.1016/j.eswa.2010.04.081
}}</ref>

''Империалистическата конкуренция'' е друга част от алгоритъма. Всички империи се опитват да спечелят играта и да завладеят колониите на останалите империи. На всяка стъпка от алгоритъма, в зависимост от тяхната сила, всички империи имат шанс да завземат контрола над една или повече от колониите на най-слабата империя.<ref name=ica_en_2007_cnf_atashpaz_ica_ica />

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

Горните стъпки могат да се обобщят във вида на следния [[псевдокод]].<ref name=ICA_2014_Survey /><ref name=ica_en_2010_jnl_nazari_integrated_product_mix_outsourcing />

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

== Източници ==
<references />

{{превод от|en|List_of_metaphor-based_metaheuristics#Imperialist_competitive_algorithm_.28Atashpaz-Gargari_.26_Lucas_2007.29|774553874}}

[[Категория:Метаевристични алгоритми]]