Iterated Local Search (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:
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.
Finding the perturbation algorithm for ILS is not an easy task. The main aim is not to get stuck at the same local minimum and in order to ensure this property, the undo operation is forbidden. Despite this, a good permutation has to consider a lot of values, since there exist two kind of bad permutations:
too weak: fall back to the same local minimum
too strong: random restart
The procedure consists in fixing a number of values for the perturbation such that these values are significant for the instance: on average probability and not rare.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
This course covers numerous powerful algorithmic techniques (greedy, local search, linear programming, multiplicative weight update, ...). The concepts are studied in clean and simple settings so as t
Introduction aux techniques de l'Intelligence Artificielle, complémentée par des exercices de programmation qui montrent les algorithmes et des exemples de leur application à des problèmes pratiques.
In computer science, local search is a heuristic 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. Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.
Tabu search (TS) is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989. Local (neighborhood) searches take a potential solution to a problem and check its immediate neighbors (that is, solutions that are similar except for very few minor details) in the hope of finding an improved solution. Local search methods have a tendency to become stuck in suboptimal regions or on plateaus where many solutions are equally fit.
In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to pl ...
Transit priority based in exclusive right-of-way is a low-cost way of improving transit service by minimizing delays caused by interaction with other vehicles. This effect can increase the share of public transit against private cars in the mode preference ...
Decreasing defects, waste time, meeting customer demand and being adaptable are the goals of a Zero Defect Manufacturing (ZDM) strategy. Scheduling is an important tool to perform that. It should take in account buffer size allocation. In this study, a met ...