Although different, these terms are indistinguishably used in many works. What are their similarities and differences? On which cases should each of them be used?
Dear Antonio,
1) exploitation consists of probing a limited (but promising) region of the search space with the hope of improving a promising solution S that we already have at hand. This operation amounts then to intensifying (refining) the search in the vicinity of S. By doing so, we would be doing, de facto, a local search.
2) exploration, on the other hand, consists of probing a much larger portion of the search space with the hope of finding other promising solutions that are yet to be refined. This operation amounts then to diversifying the search in order to avoid getting trapped in a local optimum. By doing so, we would be doing, de facto, a global search.
From what is described above, it seems that we could use "intensification" to mean "exploitation" and "diversification" to mean "exploration". However, "intensification" and "diversification" are being used mostly in conjunction with population-based optimization techniques, whereas exploitation and exploration are being used in a more general context.
Can we use global-exploration-diversification interchangeably? I would say no because a "global" technique strives to make a delicate balance between BOTH operations (1) and (2) described above and is thus not limited to (2) only. Usually (as mentioned by @Omar) this balance is insured by favoring (2) at the beginning of the search and (1) at the end.
Can we use local-exploitation-intensification interchangeably? Perhaps yes but not always because although a "local" technique is based solely on (1), we can nonetheless use it repeatedly, restarting each time from a different initial solution, forcing it in a way to do (2) also.
Exploration is related to global search as well as exploitation is related to local search. In the first one, we are interested in exploring the search space looking for good solutions, whereas in the second one we want to refine the solution and try to avoid big jumps on the search space.
Diversification is how different are the individuals within a population. In this context, it is desirable to have a good diversification in our population in order to explore the search space properly. A low level of diversification means a genetic convergence, where, in theory, the algorithm is close to the final solution. Thus, it is desirable to have a high level of diversification in the beginning of the algorithm and a lower one at the end. Therefore, a low level of diversification in the beginning leads to a premature convergence which is a bad thing. Also, when the diversification is high we intensify the exploration, otherwise we intensify the local search.
Dear Antonio,
1) exploitation consists of probing a limited (but promising) region of the search space with the hope of improving a promising solution S that we already have at hand. This operation amounts then to intensifying (refining) the search in the vicinity of S. By doing so, we would be doing, de facto, a local search.
2) exploration, on the other hand, consists of probing a much larger portion of the search space with the hope of finding other promising solutions that are yet to be refined. This operation amounts then to diversifying the search in order to avoid getting trapped in a local optimum. By doing so, we would be doing, de facto, a global search.
From what is described above, it seems that we could use "intensification" to mean "exploitation" and "diversification" to mean "exploration". However, "intensification" and "diversification" are being used mostly in conjunction with population-based optimization techniques, whereas exploitation and exploration are being used in a more general context.
Can we use global-exploration-diversification interchangeably? I would say no because a "global" technique strives to make a delicate balance between BOTH operations (1) and (2) described above and is thus not limited to (2) only. Usually (as mentioned by @Omar) this balance is insured by favoring (2) at the beginning of the search and (1) at the end.
Can we use local-exploitation-intensification interchangeably? Perhaps yes but not always because although a "local" technique is based solely on (1), we can nonetheless use it repeatedly, restarting each time from a different initial solution, forcing it in a way to do (2) also.
I forgot to answer the second question, but @Lehtihet did it very well. :)
Dear Dr. Antonio José Bolufé Röhler,
"Exploration" is mission targeted activity. "Exploitation", uses the result for to get benefit or advantage.
"Intensification" effect is concentrated or centralized. "Diversification" is beyond the structure or boundary.
"Global search" is aimed to search among-st complete possible domain. "Local search" is a search process from a subset of complete possible domain.
Both are contradictory criteria.
1. exploration of the search space is diversification and
2. exploitation of the best solutions found is intensification.
In intensification, the promising regions are explored more thoroughly
in the hope to find better solutions. In diversification, nonexplored regions must be visited to be sure that all regions of the search space are evenly explored and
that the search is not confined to only a reduced number of regions.
Over the last decades metaheuristics have become a substantial area within optimization with various applications. An intelligent interplay of intensification
and diversification (such as ideas from POPMUSIC), and the connection
to powerful exact algorithms as subroutines for handable subproblems and
other means of hybridization (like in MATHEURISTICS) are avenues to be followed.
The basic idea of POPMUSIC (Partial OPtimization Metaheuristic Under
Special Intensification Conditions) is to locally optimize subparts
of a solution, a posteriori, once a solution to the problem is available.
These local optimizations are repeated until a local optimum is found. Therefore,
POPMUSIC may be viewed as a local search working with a special,
large neighborhood.
Kindly have a look at the folllowing Version for some more detail: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.8451
Let's give it a try Antonio, and let's split that question into three parts? No harm done with that, beacuse they are rather unrelated.
1) What is the difference between "exploration" vs. "exploitation"?
2) What is the difference between "intensification" vs. "diversification"?
3) What is the difference between"global search" vs. "local search"?
On 1). Exploration is the act of searching for the purpose of discovery of information or resources. Exploration occurs in all non-sessile animal species, including humans. In human history, its most dramatic rise is arguably seen during the Age of Discovery when European explorers sailed and charted much of the rest of the world, largely in a pursuit of material wealth. Since then, major explorations after the Age of Discovery have occurred for reasons more aimed at information discovery. In scientific research, exploration is one of three purposes of empirical research (the other two being description and explanation). The term is also commonly used metaphorically. For example, an individual may speak of exploring the internet, sexuality, etc. See also
List of explorations; List of explorers; List of maritime explorers; List of Russian explorers; Early human migrations; Adventure; Chronology of European exploration of Asia; European exploration of Africa; Explorers Grand Slam; History of Antarctica; Timeline of European exploration.
And on 1) Exploitation is the use of someone or something in an unjust or cruel manner. Most often, the word exploitation is used to refer to economic exploitation; that is, the act of using another person's labor without offering them an adequate compensation. There are two major perspectives on economic exploitation: Organizational or "micro-level" exploitation: most theories of exploitation center on the market power of economic organizations within a market setting. Some neoclassical theory points to exploitation not based on market power. Structural or "macro-level" exploitation: focuses on exploitation by large sections of society even (or especially) in the context of free markets. Marxist theory points to the entire capitalist class as an exploitative entity, and to capitalism as a system based on exploitation. See Also: Abuse, Capital accumulation, Exploitation film, Fair trade, Marx's theory of alienation,Overexploitation, Rate of exploitation, Surplus labour, Surplus product, Surplus value.
On 2)
If you have a fear of flying, there might be an intensification of this feeling as you board the plane, and again when you take off. That is, your feelings of fear might increase or "intensify." An intensification is an increase in strength or magnitude (or intensity). Agricultural intensification is an increase of productivity per acre. The intensification of a conflict, as in a war, usually means an increase in fighting. Gender intensification is an increasing preference by boys for "boy things" and by girls for "girl things.".
And on 2)
Diversification may refer to: Diversification (in finance) involves spreading investments. Diversification (marketing strategy) as a corporate strategy to increase market penetration. Agricultural diversification involves the re-allocation of some of a farm's resources to new products or non-agricultural activities. Diversified technique, a chiropractic method.
On (3) Global search (engine) Academic databases and search engines designed to accelerate scientific discovery and progress. Swarm intelligence (section Gravitational search algorithm) SDS is both an efficient and robust global search and optimisation algorithm, which has been extensively mathematically described.
And on local search. Local search may refer to: Local search (optimization), a method for problem solving in optimization. Local search (Internet), web searching ...
In computer science , local search is a metaheuristic method for solving computationally hard optimization problems. Local search is the use of specialized Internet search engines that allow users to submit geographically constrained searches. In constraint satisfaction , local search is an incomplete method for finding a solution to a problem . Metaheuristic (partial search algorithm ) that may provide a sufficiently good solution to an improvement on simple local search algorithms.In optimization , 2-opt is a simple local search algorithm first proposed by Croes in 1958 for solving the traveling salesman problem
And there is a lot more,...
Cheers,
Frank
Hi Antonio,
In artificial intelligence, genetic programming (GP) is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. Essentially GP is a set of instructions and a fitness function to measure how well a computer has performed a task. It is a specialization of genetic algorithms (GA) where each individual is a computer program. It is a machine learning technique used to optimize a population of computer programs according to a fitness landscape determined by a program's ability to perform a given computational task.
n 1954, GP began with the evolutionary algorithms first used by Nils Aall Barricelli applied to evolutionary simulations. In the 1960s and early 1970s, evolutionary algorithms became widely recognized as optimization methods. Ingo Rechenberg and his group were able to solve complex engineering problems through evolution strategies as documented in his 1971 PhD thesis and the resulting 1973 book. John Holland was highly influential during the 1970s.
In 1964, Lawrence J. Fogel, one of the earliest practitioners of the GP methodology, applied evolutionary algorithms to the problem of discovering finite-state automata. Later GP-related work grew out of the learning classifier system community, which developed sets of sparse rules describing optimal policies for Markov decision processes. The first statement of modern "tree-based" genetic programming (that is, procedural languages organized in tree-based structures and operated on by suitably defined GA-operators) was given by Nichael L. Cramer (1985).[1] This work was later greatly expanded by John R. Koza, a main proponent of GP who has pioneered the application of genetic programming in various complex optimization and search problems.[2] Gianna Giavelli, a student of Koza's, later pionered the use of genetic programming as a technique to model DNA expression.[3]
In the 1990s, GP was mainly used to solve relatively simple problems because it is very computationally intensive. Recently GP has produced many novel and outstanding results in areas such as quantum computing, electronic design, game playing, sorting, and searching, due to improvements in GP technology and the exponential growth in CPU power.[4] These results include the replication or development of several post-year-2000 inventions. GP has also been applied to evolvable hardware as well as computer programs.
Developing a theory for GP has been very difficult and so in the 1990s GP was considered a sort of outcast among search techniques.
The basic ideas of genetic programming have been modified and extended in a variety of ways:
Extended Compact Genetic Programming (ECGP)
Embedded Cartesian Genetic Programming (ECGP)
Probabilistic Incremental Program Evolution (PIPE)
GP evolves computer programs, traditionally represented in memory as tree structures.[5] Trees can be easily evaluated in a recursive manner. Every tree node has an operator function and every terminal node has an operand, making mathematical expressions easy to evolve and evaluate. Thus traditionally GP favors the use of programming languages that naturally embody tree structures (for example, Lisp; other functional programming languages are also suitable).
Non-tree representations have been suggested and successfully implemented, such as linear genetic programming which suits the more traditional imperative languages [see, for example, Banzhaf et al. (1998)]. The commercial GP software Discipulus uses automatic induction of binary machine code ("AIM")[6] to achieve better performance. µGP uses directed multigraphs to generate programs that fully exploit the syntax of a given assembly language.
I am not sure which is the most popular one. There are a lot varain,ts in GP so?
Cheers,
Frank
Hi,
In a local search algorithm, you start from a first solution (usually computed by a simple greedy heuristic into a Monte Carlo Scheme) and you move among the neighbourhood of solutions you defined.
The word "exploration" came from the expression "neighbourhood exploration". Every moves of this exploration are made at each iteration of the local search main loop.
Thanks to everyone for all the answers. You have actually provided a very “diversified” set of answers :)
Some comments and doubts about your answers….
Omar, I agree with you that “exploration is related to global search as well as exploitation is related to local search”. My question seeks to determine exactly the relationship between these concepts. Do they mean exactly the same (i.e. “exploration=global search” and “exploitation=local search”)?
As for “diversification vs. intensification”, I don’t mean diversification as keeping a diversified population. But more as independent search processes "employed [within tabu search] to achieve regional intensification and global diversification". See Fred Glover’s seminal work on Tabu Search (Tabu Search – Part I). Actually, there is no population in Tabu Search.
Lehtihet, I like your points (1) and (2). There you clearly describe the strong similarities between the “exploration”-“global search”-“diversification” and “exploitation”-“local search”-“intensification” concepts. But as you state later, they shouldn’t be interchangeably used. Let me take your example of a local search method with restarts. In such a case would this be a global or local search technique? Does it actually make sense to talk, in general, about “local techniques” and “global techniques”? I believe few search methods could be categorically be classified as such. Or would it be more convenient to talk about local and search mechanisms inside a given algorithm?
Afaq Ahmad, your attempt of providing clear and concise definitions for these concepts is one the aims of this question. However, some of the terms you use puzzle me. What exactly do you mean by “mission targeted activity” and “beyond the structure or boundary”?
Dear Antonio,
Thanks for your feedback.
Concerning the question you have raised in your last post, I believe it is more convenient to view "exploitation / exploration" as being search mechanisms inside a given optimization algorithm.
In fact, as pointed out earlier in this thread by @Stefan, powerful algorithms can be built based on "an intelligent interplay" of these mechanisms, coupled with "exact algorithms" whenever possible and "other means of hybridization".
PS: in my opinion the contribution by @Stefan is very interesting and I am surprised to see that someone had down-voted it without providing any explanation.
In support of what @Stefan wrote, my students and myself have proposed a few years ago a hybrid Master/Slave optimization technique to handle a difficult optimal-control problem. The Slave routine is a deterministic algorithm (which, sometimes, can be exact depending on the problem setup), whereas the Master routine is a corridor-constrained meta-heuristic, which can be based either on Simulated Annealing or on Differential Evolution.
Well, exploration is about finding basins of attractions (as much as possible) and exploitation is the act of digging down in these basins, that's all. Diversification and intensification I agree with others.
Now, the difference between global search and local search is tricky: these two terms are very very vague. They might refer to "algorithms", say for example an algorithm is a global search algorithm and another is local search algorithm, it means that there is a guarantee that the first algorithm can converge to the global optimum of the search space (and that is for all search spaces) after infinite number of iterations almost surely (i.e. with probability one). However, if the algorithm is a local search, it converges to a local optimum of the search space almost surely. Note that, it is easy to have a global search algorithm: a random search is a global search. But, the story becomes to another concept called "first hitting time". Ask me if you were interested about first hitting time. Also, note that it is not easy to prove evolutionary methods are locally convergent (or globally convergent) and surprisingly, some of them are not. In fact, the term "GA is a global search method" is very wrong and harmful. There are two reasons for being wrong: the term global search is not a well-defined term, and GA (in its original form) is not even a local optimizer (local minimizer, or local search). And it is harmful because it is not true while people still saying we have a method that is global optimizer (operations research or math) while it is far beyond achievement in other research fields, and when they look at it, they can easily see that the algorithm is not even a local search.
In the context of combinatorial optimization, some times local search just means improving the solutions you have found with some refining procedures (a simple heuristic). Anyway, it is going too far :-). I hope you find it helpful.
The above discussions gives a good insight into the topics.
Ultimately in my view all these boil down to the reproduction operators of crossover and mutation.
Crossover takes two individuals from the exixting population and tries to create two new individuals which are more similar to the parents.
While mutation takes a single individual solution and changes it into a new individual which may or may not be present in the current population.
Thus crossover operation enables intense search and hence exploitation of the solution space and enables local search.
While mutation operator is used to create diverse solutions enabling global search and explore new possible solutions.
The rate and type of crossover and mutation can be chosen according to the problem at hand.
In short:
exploitation:- searching in the neighborhood of the current solution to improve the quality with a small perturbation.
exploration:- search different regions of the solution space, good to escape being trapped in local solutions
Hello Colleagues,
In my point of view:
Exploration is related with dynamic features and long run: finding, experimenting and researching to gain new options or innovations.
Exploitation is corresponding with static features and short run: refining existing procedures, investigating the efficiency and implementation.
Regards,
Hello Prof. Dr. Cortes,
Great day!
I have great pleasure for same opinion.
So, for Sustainability, we may prefer Exploration.
Thank you so much.
Regards,
Exploration allows a search algorithm to come close to the global minimum or good local minimum.
Exploitation helps locate the global minimum accurately.
Most often, the word exploitation is used to refer to economic exploitation; that is, the act of using another person's labor without offering them an adequate compensation. There are two major perspectives on economic exploitation: Organizational or "micro-level" exploitation: most theories of exploitation center on the market power of economic organizations within a market setting. Some neoclassical theory points to exploitation not based on market power. Structural or "macro-level" exploitation: focuses on exploitation by large sections of society even (or especially) in the context of free markets. Marxist theory points to the entire capitalist class as an exploitative entity, and to capitalism as a system based on exploitation. See Also: Abuse, Capital accumulation, Exploitation film, Fair trade, Marx's theory of alienation,Overexploitation, Rate of exploitation, Surplus labour, Surplus product, Surplus value.
hi?
Intensification" effect is concentrated or centralized. "Diversification" is beyond the structure or boundary.
exploitation: caring for quality performance on the actual domain
exploration: looking for a new territory candidate to be part of the work area
intensification: build subdomains to generate performance improvements against specific targets
diversification: build subdomains to generate performance improvements against the primary target of each domain
global search: searches on all levels above it
local search: perform a search on all levels below it
Good article about the concepts and differences between exploration and exploitation.
Who can help me get ?
Hi Antonio Bolufé-Röhler !
Exploration is directly related to Global search and we use this explore the whole search space of our solutions for searching good solution globally.
Exploitation is directly related to local search, we use this after defining the boundary of our local minima to limit the search space.
Diversification indicates the diversity of individuals in the population which is desirable to make the solution more global to get new best solutions. But near the termination criteria this must be minimum which is indication of your best solution and intensification of the solutions.
From a research context, let us consider a literature review method. I would call this as exploitation as the scope of search space gets defined before the review. However you can explore new ideas/gaps within the scope without any defined criteria beforehand. A case study with no a priori hypothesis could be an example of exploratory research as there is no hypothesis defined beforehand.
So in general, we can say that when a defined logic is set before the knowledge creation process this is exploitation (exploitation of the defined logic in the knowledge space). When no logic is defined beforehand on the knowledge space then the process of knowledge creation is called exploration.
Striking the balance between the two is the real-time practice to knowledge.
Such concept are close related. Exploration is the proces of seeking new positions in the search space. Explotation is the process of refining a good solution, already found. Exploration ---> Diversification.
Exploitation-----> intensification
Exploration is a type of global search, whereas exploitation is a local search
In Geo-sciences, the term EXPLORATION is used when one undertakes a reconnaissance survey of a terrain to look for deposits of natural resources.
When it is proven that, that natural resource is there, and in a large enough quantity, you go through the process of EXPLOITATION to harness the resource.
EXPLORATION - Initial Environmental Evaluation.
EXPLOITATION - Final process of harnessing the resource.
Explanation out of science:
Take a research institute as an example, exploration is to recruit post-docs and exploitation is to convert post-docs as staff.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms