Content deleted Content added
←Redirected page to List of metaphor-based metaheuristics#Imperialist competitive |
|||
Line 1:
In [[computer science]], '''imperialist competitive algorithm''' is a computational method that is used to solve [[optimization problem]]s of different types.<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> Like most of the methods in the area of [[evolutionary computation]], ICA does not need the gradient of the function in its optimization process. From a specific point of view, ICA can be thought of as the social counterpart of [[genetic algorithms]] (GAs). ICA is the mathematical model and the computer simulation of human [[social evolution]], while GAs are based on the [[biological evolution]] of species.
Nature-inspired metaheuristics in general have started to [[List of metaphor-inspired metaheuristics#Criticism of the metaphor methodology|attract criticism in the research community]] for hiding their lack of novelty behind an elaborate metaphor.<ref>{{cite journal|last=Weyland|first=Dennis|title=A Rigorous Analysis of the Harmony Search Algorithm: How the Research Community can be Misled by a "Novel" Methodology|journal=[[International Journal of Applied Metaheuristic Computing]]|volume=1|issue=2|year=2010|pages=50–60|doi=10.4018/jamc.2010040104}}</ref><ref>{{cite journal|first=Kenneth|last=Sörensen|title=Metaheuristics—the metaphor exposed|journal=[[International Transactions in Operational Research]]|doi=10.1111/itor.12001|volume=22|pages=3–18|year=2013|quote=In recent years, the field of combinatorial optimization has witnessed a true tsunami of "novel" metaheuristic methods, most of them based on a metaphor of some natural or man-made process. The behavior of virtually any species of insects, the flow of water, musicians playing together – it seems that no idea is too far-fetched to serve as inspiration to launch yet another metaheuristic. In this paper, we will argue that this line of research is threatening to lead the area of metaheuristics away from scientific rigor.}}</ref><ref>{{scholarpedia|title=Metaheuristics|urlname=Metaheuristics|curator=[[Fred W. Glover|Fred Glover]] and Kenneth Sörensen}} "A large (and increasing) number of publications focuses on the development of (supposedly) new metaheuristic frameworks based on metaphors. The list of natural or man-made processes that has been used as the basis for a metaheuristic framework now includes such diverse processes as bacterial foraging, river formation, biogeography, musicians playing together, electromagnetism, gravity, colonization by an empire, mine blasts, league championships, clouds, and so forth. An important subcategory is found in metaheuristics based on animal behavior. Ants, bees, bats, wolves, cats, fireflies, eagles, vultures, dolphins, frogs, salmon, vultures, termites, flies, and many others, have all been used to inspire a "novel" metaheuristic. [...] As a general rule, publication of papers on metaphor-based metaheuristics has been limited to second-tier journals and conferences, but some recent exceptions to this rule can be found. Sörensen (2013) states that research in this direction is fundamentally flawed. Most importantly, the author contends that the novelty of the underlying metaphor does not automatically render the resulting framework "novel". On the contrary, there is increasing evidence that very few of the metaphor-based methods are new in any interesting sense."</ref><ref>Jerry Swan, Steven Adriaensen, Mohamed Bishr, Edmund K. Burke, John A. Clark, Patrick De Causmaecker, Juanjo Durillo, Kevin Hammond, Emma Hart, Colin G. Johnson, Zoltan A. Kocsis, Ben Kovitz, Krzysztof Krawiec, Simon Martin, J. J. Merelo, Leandro L. Minku, Ender Özcan, Gisele L. Pappa, Erwin Pesch, Pablo Garcáa-Sánchez, Andrea Schaerf, Kevin Sim, Jim E. Smith, Thomas Stützle, Stefan Voß, Stefan Wagner, Xin Yao. [http://www.cs.nott.ac.uk/~exo/docs/publications/research-agenda-metaheuristic.pdf "A Research Agenda for Metaheuristic Standardization"]. "Metaphors often inspire new metaheuristics, but without mathematical rigor, it can be hard to tell if a new metaheuristic is really distinct from a familiar one. For example, mathematically, '[[Harmony search]]' turned out to be a simple variant of '[[Evolution Strategies]]' even though the metaphors that inspired them were quite different. Formally describing state, representation, and operators allows genuine novelty to be distinguished from minor variation."</ref><ref>Alexander Brownlee and John R. Woodward (2015). [http://theconversation.com/why-we-fell-out-of-love-with-algorithms-inspired-by-nature-42718 "Why we fell out of love with algorithms inspired by nature"]. ''[[The Conversation (website)|The Conversation]]''.</ref> In response, [[Springer Science+Business Media|Springer]]'s ''Journal of Heuristics'' has updated their editorial policy to state that:<ref>[http://www.springer.com/cda/content/document/cda_downloaddocument/Journal+of+Heuristic+Policies+on+Heuristic+Search.pdf?SGWID=0-0-45-1483502-p35487524 Journal of Heuristic Policies on Heuristic Search Research]. Springer. "Proposing new paradigms is only acceptable if they contain innovative basic ideas, such as those that are embedded in classical frameworks like [[genetic algorithm]]s, [[tabu search]], and [[simulated annealing]]. The Journal of Heuristics avoids the publication of articles that repackage and embed old ideas in methods that are claimed to be based on metaphors of natural or manmade systems and processes. These so-called "novel" methods employ analogies that range from intelligent water drops, musicians playing jazz, imperialist societies, leapfrogs, kangaroos, all types of swarms and insects and even mine blast processes (Sörensen, 2013). If a researcher uses a metaphor to stimulate his or her own ideas about a new method, the method must nevertheless be translated into metaphor-free language, so that the strategies employed can be clearly understood, and their novelty is made clearly visible. (See items 2 and 3 below.) Metaphors are cheap and easy to come by. Their use to "window dress" a method is not acceptable."</ref>
<blockquote>
Implementations should be explained by employing standard optimization terminology, where a solution is called a "solution" and not something else related to some obscure metaphor (e.g., [[harmony search|harmony]], [[firefly algorithm|flies]], [[bat algorithm|bats]], countries, etc.).
</blockquote>
== Metaphor ==
[[File:Imperialist-competitive-algorithm-flowchart.jpg|thumb|420px|Figure 1: Flowchart of Imperialist Competitive Algorithm (ICA)]]
Figure 1 shows the flowchart of the Imperialist Competitive Algorithm. This algorithm starts by generating a set of candidate random solutions in the search space of the optimization problem. The generated random points are called the initial ''Countries''. Countries in this algorithm are the counterpart of ''Chromosome''s in GAs and ''Particle''s in [[Particle Swarm Optimization]] (PSO) and it is an array of values of a candidate solution of optimization problem. The [[Loss function|cost function]] of the optimization problem determines the power of each country. Based on their power, some of the best initial countries (the countries with the least cost function value), become ''Imperialists'' and start taking control of other countries (called ''colonies'') and form the initial ''Empires''.<ref name=ica_en_2007_cnf_atashpaz_ica_ica />
Two main operators of this algorithm are ''Assimilation'' and ''Revolution''. Assimilation makes the colonies of each empire get closer to the imperialist state in the space of socio-political characteristics (optimization search space). Revolution brings about sudden random changes in the position of some of the countries in the search space. During assimilation and revolution a colony might reach a better position and has the chance to take the control of the entire empire and replace the current imperialist state of the empire.<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>
''Imperialistic Competition'' is another part of this algorithm. All the empires try to win this game and take possession of colonies of other empires. In each step of the algorithm, based on their power, all the empires have a chance to take control of one or more of the colonies of the weakest empire.<ref name=ica_en_2007_cnf_atashpaz_ica_ica />
Algorithm continues with the mentioned steps (Assimilation, Revolution, Competition) until a stop condition is satisfied.
== Algorithm ==
The above steps can be summarized as the below [[pseudocode]].<ref name=ICA_2014_Survey /><ref name=ica_en_2010_jnl_nazari_integrated_product_mix_outsourcing />
0) Define objective function: <math>f(\mathbf{x}), \quad \mathbf{x}=(x_1,x_2,\dots,x_d); \, </math>
1) Initialization of the algorithm. Generate some random solution in the search space and create initial empires.
2) Assimilation: Colonies move towards imperialist states in different in directions.
3) Revolution: Random changes occur in the characteristics of some countries.
4) Position exchange between a colony and Imperialist. A colony with a better position than the imperialist,
has the chance to take the control of empire by replacing the existing imperialist.
5) Imperialistic competition: All imperialists compete to take possession of colonies of each other.
6) Eliminate the powerless empires. Weak empires lose their power gradually and they will finally be eliminated.
7) If the stop condition is satisfied, stop, if not go to 2.
8) End
== References ==
{{Reflist|30em}}
[[Category:Nature-inspired metaheuristics]]
| |||