What are the differences ?
What are the main characteristic in the algorithm to use it as local or global search ?
Dear Hayder,
In evolutionary algorithms there is what is called exploitation and exploration.
1. Exploration = global search
Here you make large jumps to find solutions. Often preformed at the beginning of iterations.
2. Exploitation = local search
Here you make small jumps, because you believe the 'best solution' is not far from where you are. Often done towards the end of iterations.
Dear Hayder,
My opinion on this question and the main differences between them: is that global search focuses on exploring the search space, that is trying to cover as much distance as possible within the search space while local search focuses more on obtaining solutions around its present location.
In other words, exploitation and exploration are 2 important properties of an optimization algorithm and there should be a balance between them. the exploration characteristic determines how well an algorithm performs the global search. On the other hand, the exploitation characteristic determines how well it performs a search on local regions and how close it can converge to minimums.
Generally, global search is a process that takes an initial solution and explore a rather vast area of possible solutions - such as a grid search (in which you simply evaluate many, many points on a grid, covering the area in which you want to optimize your objective function). It also refers to tree search, in which you divide the whole space into smaller and smaller segments/areas, in which you try to estimate an optimal value for that area. Having done that over many sub-areas you may "see" which collection of subareas seems to be more profitable than others; in the sub-areas that seem promising you explore a finer grid, while you also may be able to "cut off" subareas that are not interesting (as in probably being worse than a feasible solution that we already have found). This mimics the technique of branch-and-bound in linear integer optimization, but is more general, and therefore has a rather bad "worst-case" complexity. What linear integer optimization has "for free" is the continuous relaxation (leading to a linear program to solve) that one can use in order to obtain lower bounds on the solution in a sub-tree which can help you cut off branches in the tree without evaluating it. In any case, it beats metaheuristics by being globally convergent.
Local search is searching the better solution in vicinity of existing solutions ( exploitation). On the other hand global search(Exploration) refers to generation of new solutions in untested regions of problem search space to escape from local optima and find better solution.
- Badges
- Science topic
- Similar topics
- Computer Science
- Data Mining