Investigating Gradient Ascent and Hill-Climbing Algorithms for Optimisation Problems

In this resit, I am asking you to use the gradient ascent / hill-climbing example of the first coursework as a starting point to investigate one of the following problems:

1. How to improve gradient descent convergence?

2. What are pros and cons of different algorithms (e.g., different solvers)?

3. What happens on landscapes with different properties (beyond those included in the first assignment, e.g., consider published benchmark optimisation tasks)?

4. Methods of mutation for hill-climbing and, e.g., error thresholds

5. Comparison with a genetic algorithm (GA)

6. Effect of noise in the function evaluation (as in robot experiments).

Your investigation may include analytical work, simulations, numerical experimentations, etc.

Assessment is not based on mathematical complexity, but rather on demonstrating the process of investigation and showing that you have critically engaged with your chosen topic. A good way of doing this is to imagine that you are explaining your subject and findings to someone else (me in this case – although please avoid producing a tutorial). Show me why the topic is interesting (introduction), briefly explain the techniques you have used (methods) and discuss what helped you gain an understanding (results).

Your submission should consist of:

• A report in PDF of length 3 pages at most, with minimum font size of 11, including references and figures.

• Your source code (provided as a zip if there are multiple files).

With respect to the three variables in the gradient ascent algorithm, we will initially:

1. use a constant learning rate of 0.1;

2. stop after a maximum of 50 iterations of the algorithm;

3. as we know the functions we will be optimising, the exact gradient will be used.

1. What do you notice about the 2 algorithms in terms of the height they get to and the time it takes them to get there? To test this, change the hill climbing and gradient ascent functions so that they return 2 parameters: a 1 or 0 specifying whether the global optimum was reached together with how many iterations the algorithm performed. NB: to stop the algorithm after the maximum has been reached, use an if statement to test whether the maximum height has been reached, then use the function break to break out of the for loop.

2. Now test the algorithms systematically by starting from a grid of points covering the landscape. You will have to replace the line generating a random starting position with some suitable code. NB: commenting out plotting commands makes the program run faster. Calculate how many starting points lead to the maximum, then calculate the mean number of iterations it takes those that reached the maximum to get there. You will find the function pcolor to be useful to summarise your results visually. To get a scale bar, use colorbar. Experiment with shading and colormap to see their effects. Document your results in the form of  a small report with figures, figure captions and explanations.

3. Explain any differences in results between the 2 algorithms. Experiment with changing the learning rate and range of mutation to see what happens.