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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

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

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

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

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

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

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

  1. а б в Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition. // IEEE Congress on Evolutionary Computation. Т. 7. 2007, 4661–4666 с.
  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.
  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.
Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „List_of_metaphor-based_metaheuristics#Imperialist_competitive_algorithm_.28Atashpaz-Gargari_.26_Lucas_2007.29“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.