Iterated local search
Encyclopedia
Iterated local search is a term in applied mathematics
and computer science
defining a modification of local search
or hill climbing
methods for solving discrete optimization problems.
Local search methods build a trajectory in configuration
space which leads from an initial solution to a local optimum
, where local search stops
(no improving neighbors are available).
If local optima deliver sub-optimal solutions, local search needs to be modified
to continue the search beyond local optimality.
A simple modification consists of iterating calls to the local search routine,
each time starting from a different initial configuration. This is called repeated local search,
and implies that the knowledge obtained during the previous local search phases
is not used.
Learning implies that the previous history, for example the memory about the previously found local minima,
is mined to produce better and better starting points for local search.
The implicit assumption is that of a clustered distribution of local minima
:
when minimizing a function, determining good local minima is easier when starting from a local minimum with a
low value than when starting from a random point.
The only caveat is to
avoid confinement in a given attraction basin, so that the kick to transform
a local minimizer into the starting point for the next run has to be appropriately strong,
but not too strong to avoid reverting to memory-less random restarts.
Iterated Local Search is based on building a sequence of locally optimal solutions by:
The perturbation strength has to be sufficient to lead the trajectory to a different
attraction basin leading to a different local optimum
.
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
defining a modification of local search
Local search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
or hill climbing
Hill climbing
In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution...
methods for solving discrete optimization problems.
Local search methods build a trajectory in configuration
space which leads from an initial solution to a local optimum
Local optimum
Local optimum is a term in applied mathematics and computer science.A local optimum of a combinatorial optimization problem is a solution that is optimal within a neighboring set of solutions...
, where local search stops
(no improving neighbors are available).
If local optima deliver sub-optimal solutions, local search needs to be modified
to continue the search beyond local optimality.
A simple modification consists of iterating calls to the local search routine,
each time starting from a different initial configuration. This is called repeated local search,
and implies that the knowledge obtained during the previous local search phases
is not used.
Learning implies that the previous history, for example the memory about the previously found local minima,
is mined to produce better and better starting points for local search.
The implicit assumption is that of a clustered distribution of local minima
Local optimum
Local optimum is a term in applied mathematics and computer science.A local optimum of a combinatorial optimization problem is a solution that is optimal within a neighboring set of solutions...
:
when minimizing a function, determining good local minima is easier when starting from a local minimum with a
low value than when starting from a random point.
The only caveat is to
avoid confinement in a given attraction basin, so that the kick to transform
a local minimizer into the starting point for the next run has to be appropriately strong,
but not too strong to avoid reverting to memory-less random restarts.
Iterated Local Search is based on building a sequence of locally optimal solutions by:
- perturbing the current local minimum;
- applying local search after starting from the modified solution.
The perturbation strength has to be sufficient to lead the trajectory to a different
attraction basin leading to a different local optimum
Local optimum
Local optimum is a term in applied mathematics and computer science.A local optimum of a combinatorial optimization problem is a solution that is optimal within a neighboring set of solutions...
.