Iterated local search

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Iterated local search kicks a solution out from a local optimum

Iterated Local Search[1][2] (ILS) 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 can get stuck in a local minimum, where no improving neighbors are available.

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:

  1. perturbing the current local minimum;
  2. 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.

The method has been applied to several Combinatorial Optimization Problems including the Job-Shop Scheduling Problems,[3][4] Flow-Shop Problems,[5] Vehicle Routing Problems [6] as well as many others.

References[edit]

  1. ^ Lourenço, H.R.; Martin O. and Stützle T. (2010). "Iterated Local Search: Framework and Applications". Handbook of Metaheuristics, 2nd. Edition. Kluwer Academic Publishers, International Series in Operations Research & Management Science 146: 363–397. doi:10.1007/978-1-4419-1665-5_12. 
  2. ^ Lourenço, H.R.; Martin O. and Stützle T. (2003). "Iterated Local Search". Handbook of Metaheuristics. Kluwer Academic Publishers, International Series in Operations Research & Management Science 57: 321–353. 
  3. ^ Lourenço, H.R.; Zwijnenburg M. (1996). "Combining the large-step optimization with tabu-search: application to the job-shop scheduling problem". Meta-Heuristics: Theory and Applications. Kluwer Academic Publishers: 219–236. 
  4. ^ Lourenço, H.R. (1995). "Job-Shop Scheduling: computational study of local search and large-step optimization methods". European Journal of Operational Research 83 (2): 347–364. doi:10.1016/0377-2217(95)00012-F. 
  5. ^ Juan, A.A.; Lourenço, H.; Mateo, M.; Luo, R.; Castella, Q. (in press). "Using Iterated Local Search for solving the Flow-Shop Problem: parametrization, randomization and parallelization issues". International Transactions in Operational Research.  Check date values in: |date= (help)
  6. ^ Penna, Puca H.V..; Satori Ochi L. Subramanian A. (2013). "An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem". Journal of Heuristics 19 (2): 201–232. doi:10.1007/s10732-011-9186-y.