Iterated Local Search From Scratch in Python

Iterated Local Search is a stochastic global optimization algorithm.

It involves the repeated application of a local search algorithm to modified versions of a good solution found previously. In this way, it is like a clever version of the stochastic hill climbing with random restarts algorithm.

The intuition behind the algorithm is that random restarts can help to locate many local optima in a problem and that better local optima are often close to other local optima. Therefore modest perturbations to existing local optima may locate better or even best solutions to an optimization problem.

In this tutorial, you will discover how to implement the iterated local search algorithm from scratch.

After completing this tutorial, you will know:

• Iterated local search is a stochastic global search optimization algorithm that is a smarter version of stochastic hill climbing with random restarts.
• How to implement stochastic hill climbing with random restarts from scratch.
• How to implement and apply the iterated local search algorithm to a nonlinear objective function.

Kick-start your project with my new book Optimization for Machine Learning, including step-by-step tutorials and the Python source code files for all examples.

Iterated Local Search From Scratch in Python
Photo by Susanne Nilsson, some rights reserved.

Tutorial Overview

This tutorial is divided into five parts; they are:

1. What Is Iterated Local Search
2. Ackley Objective Function
3. Stochastic Hill Climbing Algorithm
4. Stochastic Hill Climbing With Random Restarts
5. Iterated Local Search Algorithm

What Is Iterated Local Search

Iterated Local Search, or ILS for short, is a stochastic global search optimization algorithm.

It is related to or an extension of stochastic hill climbing and stochastic hill climbing with random starts.

It’s essentially a more clever version of Hill-Climbing with Random Restarts.

— Page 26, Essentials of Metaheuristics, 2011.

Stochastic hill climbing is a local search algorithm that involves making random modifications to an existing solution and accepting the modification only if it results in better results than the current working solution.

Local search algorithms in general can get stuck in local optima. One approach to address this problem is to restart the search from a new randomly selected starting point. The restart procedure can be performed many times and may be triggered after a fixed number of function evaluations or if no further improvement is seen for a given number of algorithm iterations. This algorithm is called stochastic hill climbing with random restarts.

The simplest possibility to improve upon a cost found by LocalSearch is to repeat the search from another starting point.

— Page 132, Handbook of Metaheuristics, 3rd edition 2019.

Iterated local search is similar to stochastic hill climbing with random restarts, except rather than selecting a random starting point for each restart, a point is selected based on a modified version of the best point found so far during the broader search.

The perturbation of the best solution so far is like a large jump in the search space to a new region, whereas the perturbations made by the stochastic hill climbing algorithm are much smaller, confined to a specific region of the search space.

The heuristic here is that you can often find better local optima near to the one you’re presently in, and walking from local optimum to local optimum in this way often outperforms just trying new locations entirely at random.

— Page 26, Essentials of Metaheuristics, 2011.

This allows the search to be performed at two levels. The hill climbing algorithm is the local search for getting the most out of a specific candidate solution or region of the search space, and the restart approach allows different regions of the search space to be explored.

In this way, the algorithm Iterated Local Search explores multiple local optima in the search space, increasing the likelihood of locating the global optima.

The Iterated Local Search was proposed for combinatorial optimization problems, such as the traveling salesman problem (TSP), although it can be applied to continuous function optimization by using different step sizes in the search space: smaller steps for the hill climbing and larger steps for the random restart.

Now that we are familiar with the Iterated Local Search algorithm, let’s explore how to implement the algorithm from scratch.

Ackley Objective Function

First, let’s define a channeling optimization problem as the basis for implementing the Iterated Local Search algorithm.

The Ackley function is an example of a multimodal objective function that has a single global optima and multiple local optima in which a local search might get stuck.

As such, a global optimization technique is required. It is a two-dimensional objective function that has a global optima at [0,0], which evaluates to 0.0.

The example below implements the Ackley and creates a three-dimensional surface plot showing the global optima and multiple local optima.

Running the example creates the surface plot of the Ackley function showing the vast number of local optima.

3D Surface Plot of the Ackley Multimodal Function

We will use this as the basis for implementing and comparing a simple stochastic hill climbing algorithm, stochastic hill climbing with random restarts, and finally iterated local search.

We would expect a stochastic hill climbing algorithm to get stuck easily in local minima. We would expect stochastic hill climbing with restarts to find many local minima, and we would expect iterated local search to perform better than either method on this problem if configured appropriately.

Stochastic Hill Climbing Algorithm

Core to the Iterated Local Search algorithm is a local search, and in this tutorial, we will use the Stochastic Hill Climbing algorithm for this purpose.

The Stochastic Hill Climbing algorithm involves first generating a random starting point and current working solution, then generating perturbed versions of the current working solution and accepting them if they are better than the current working solution.

Given that we are working on a continuous optimization problem, a solution is a vector of values to be evaluated by the objective function, in this case, a point in a two-dimensional space bounded by -5 and 5.

We can generate a random point by sampling the search space with a uniform probability distribution. For example:

We can generate perturbed versions of a currently working solution using a Gaussian probability distribution with the mean of the current values in the solution and a standard deviation controlled by a hyperparameter that controls how far the search is allowed to explore from the current working solution.

We will refer to this hyperparameter as “step_size“, for example:

Importantly, we must check that generated solutions are within the search space.

This can be achieved with a custom function named in_bounds() that takes a candidate solution and the bounds of the search space and returns True if the point is in the search space, False otherwise.

This function can then be called during the hill climb to confirm that new points are in the bounds of the search space, and if not, new points can be generated.

Tying this together, the function hillclimbing() below implements the stochastic hill climbing local search algorithm. It takes the name of the objective function, bounds of the problem, number of iterations, and steps size as arguments and returns the best solution and its evaluation.

We can test this algorithm on the Ackley function.

We will fix the seed for the pseudorandom number generator to ensure we get the same results each time the code is run.

The algorithm will be run for 1,000 iterations and a step size of 0.05 units will be used; both hyperparameters were chosen after a little trial and error.

At the end of the run, we will report the best solution found.

Tying this together, the complete example of applying the stochastic hill climbing algorithm to the Ackley objective function is listed below.

Running the example performs the stochastic hill climbing search on the objective function. Each improvement found during the search is reported and the best solution is then reported at the end of the search.

Note: Your results may vary given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.

In this case, we can see about 13 improvements during the search and a final solution of about f(-0.981, 1.965), resulting in an evaluation of about 5.381, which is far from f(0.0, 0.0) = 0.

Next, we will modify the algorithm to perform random restarts and see if we can achieve better results.

Stochastic Hill Climbing With Random Restarts

The Stochastic Hill Climbing With Random Restarts algorithm involves the repeated running of the Stochastic Hill Climbing algorithm and keeping track of the best solution found.

First, let’s modify the hillclimbing() function to take the starting point of the search rather than generating it randomly. This will help later when we implement the Iterated Local Search algorithm later.

Next, we can implement the random restart algorithm by repeatedly calling the hillclimbing() function a fixed number of times.

Each call, we will generate a new randomly selected starting point for the hill climbing search.

We can then inspect the result and keep it if it is better than any result of the search we have seen so far.

Tying this together, the random_restarts() function implemented the stochastic hill climbing algorithm with random restarts.

We can then apply this algorithm to the Ackley objective function. In this case, we will limit the number of random restarts to 30, chosen arbitrarily.

The complete example is listed below.

Running the example will perform a stochastic hill climbing with random restarts search for the Ackley objective function. Each time an improved overall solution is discovered, it is reported and the final best solution found by the search is summarized.

Note: Your results may vary given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.

In this case, we can see three improvements during the search and that the best solution found was approximately f(0.002, 0.002), which evaluated to about 0.009, which is much better than a single run of the hill climbing algorithm.

Next, let’s look at how we can implement the iterated local search algorithm.

Iterated Local Search Algorithm

The Iterated Local Search algorithm is a modified version of the stochastic hill climbing with random restarts algorithm.

The important difference is that the starting point for each application of the stochastic hill climbing algorithm is a perturbed version of the best point found so far.

We can implement this algorithm by using the random_restarts() function as a starting point. Each restart iteration, we can generate a modified version of the best solution found so far instead of a random starting point.

This can be achieved by using a step size hyperparameter, much like is used in the stochastic hill climber. In this case, a larger step size value will be used given the need for larger perturbations in the search space.

Tying this together, the iterated_local_search() function is defined below.

We can then apply the algorithm to the Ackley objective function. In this case, we will use a larger step size value of 1.0 for the random restarts, chosen after a little trial and error.

The complete example is listed below.

Running the example will perform an Iterated Local Search of the Ackley objective function.

Each time an improved overall solution is discovered, it is reported and the final best solution found by the search is summarized at the end of the run.

Note: Your results may vary given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.

In this case, we can see four improvements during the search and that the best solution found was two very small inputs that are close to zero, which evaluated to about 0.0003, which is better than either a single run of the hill climber or the hill climber with restarts.

Further Reading

This section provides more resources on the topic if you are looking to go deeper.

Books

• Essentials of Metaheuristics, 2011.
• Handbook of Metaheuristics, 3rd edition 2019.

Articles

• Hill climbing, Wikipedia.
• Iterated local search, Wikipedia.

Summary

In this tutorial, you discovered how to implement the iterated local search algorithm from scratch.

Specifically, you learned:

• Iterated local search is a stochastic global search optimization algorithm that is a smarter version of stochastic hill climbing with random restarts.
• How to implement stochastic hill climbing with random restarts from scratch.
• How to implement and apply the iterated local search algorithm to a nonlinear objective function.

Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.

Get a Handle on Modern Optimization Algorithms!

Develop Your Understanding of Optimization

...with just a few lines of python code

Discover how in my new Ebook:
Optimization for Machine Learning

It provides self-study tutorials with full working code on:
Gradient Descent, Genetic Algorithms, Hill Climbing, Curve Fitting, RMSProp, Adam, and much more...

Bring Modern Optimization Algorithms to
Your Machine Learning Projects

See What's Inside