Dear Ang,

The answers provided against this question are right. If you are looking more, you may find some interesting answers through the link below.

http://web.maths.unsw.edu.au/~rsw/lgopt.pdf

Thanks,

Sobhan

The distinction between global search and local search can be very subtle. For example, many global search techniques such as PSO can have their parameters adjusted to have them focus more on local search (e.g. higher constriction to limit the speed/movement of particles). Further, local search techniques are often thought of as "greedy", but global search techniques often employ elitism (e.g. pbest positions in PSO, DE, mu+lambda-ES, etc), so global search techniques also display aspects of greediness.

Determinism might be a useful distinction. A search technique which always reaches the same locally optimal solution from the same starting point is probably a local search technique. Equally, the performance of a global search technique should be less dependent on its initial position(s). Whereas a local search technique will target nearby local optima, global search techniques should be able to find (local) optima anywhere in the search space.

This is a tricky problem to describe. From a classification point of view, this differs by the method you use to find the solution. Any method that search in the vicinity of a starting point (incremental methods) and have the potential to get stuck the moment it sees an extrema is a local method.... Gradient descent is the classic example for this. Global methods will usually treat the whole feature space as one when finding the best solution. A very slow and a primitive example would be the exhaustive search.

My colleagues comments described the differences between global and local optima very well. However, I want to add a short remark that is sometime there are NP problems where finding one optimal and definite solution is not possible. We have many examples in real life such as scheduling problems (Exams; Flights..etc). Exhaustive search is not possible to find a solution in this case for several reasons. Another issue is that sometime a heuristic algorithm is known to find a global optimum solution such as Genetic algorithm (GA) but it stuck in the local solution. In this case to slow the fast convergence of GA to local optima it is combined with Hill climbing heuristics process or another process (penalizing process) to slow the convergence and to guarantee the global optimum solution.

Other answers to this question remark very well the differences between a local optima and a global one.

Both search techquines attempt to find a solution that optimizes a cost criterion. Local search algorithms start exploring the state space in a certain point of the state space (this point can be selected using a huge variety of techniques. This technique is highly dependent on the problem domain and the local search algorithm), and iteratively try to find a better solution in terms of the cost function. In general, these algorithms are faster than other global search techniques and they can provide quite good solutions if the initialization step is adequated to the problem. Also, these algorithms are iterative, so you always know the best found solution at the current iteration. This leaves you total freedom to select the stop condition. As other answers point, these algorithms only provide local optimas, which may have a much higher cost than the global one, and which also depend on the initial solution in which you started the exploration

Global search algorithms do not require a initial solution, and their goal is to find the global optima of the cost function. Global search is not applicable to NP problems, but you can discretize your state space with a resolution enough to guarantee the algorithm to be executed in a reasonable time.

Both global and local search techniques may be enhanced using heuristic functions that provide a estimated cost for your solutions. Using this estimated cost you can do a more efficient exploration of the search space, but in local search algorithms this may lead you to local optimas more easily. For this reason the local search techniques are usually enhanced with local optima avoiding techniques.

Ideally speaking, a global searching technique is promising to make sure to find the best global formation but this is achieved most ly at the cost of a long time searching. But then again in reality, they are run and stop when stopping criterion is come across. Examples of this search include, particle swarm optimization. simulated annealing, and genetic algorithm.  Whereas, local search algorithms do not totally focus on search and but it attempts to move from a current formation to a neighboring refining formation. This is much depending on the initial search space and initial formation. An example of local search is hill climbing, which is an iterative algorithm which can start with a random solution and then after the algorithm tries to find a better solution by incrementally altering a solution of single element. If this alteration harvests a better solution, an incremental alteration is made to a new solution, this process can be repeated in anticipation of no more enhancement is identified.

• Local algorithms zoom in on optima based  on known  information

• Global algorithms must also have a component of exploring new regions in design space

• The key to global optimization is therefore  the balance between exploration and exploitation

• Many accomplish that based on population

My opinion on this 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

Dear Ang,

The answers provided against this question are right. If you are looking more, you may find some interesting answers through the link below.

http://web.maths.unsw.edu.au/~rsw/lgopt.pdf

Thanks,

Sobhan

I can say that both are optimization problems (or looking for the best solution posible) where in global search we are able to find the best optimal solution for a given problem. On local search, the problem might be subject to uncertainty where maybe, nobody knows (or can mathematically prove) that there is a best solution, so a local search solution means that there is a (hopefully) nearly-optimal solution to the problem.