Skip to content

Latest commit

 

History

History
80 lines (55 loc) · 4.64 KB

README.md

File metadata and controls

80 lines (55 loc) · 4.64 KB
Raw

A nevis-based benchmark framework for optimisers

This repository provides a benchmark whose results are presented in the paper:
"Where’s Ben Nevis? A 2D optimisation benchmark with 957,174 local optima based on Great Britain terrain data", Yuhang Wei, Michael Clerx, Gary R. Mirams, 2024, arXiv, https://doi.org/10.48550/arXiv.2410.02422

This benchmark uses the nevis package which turns Ordnance Survey Terrain 50 data into a linearly interpolated surface for optimisation problems.

Reproducing the figures and tables in the paper

Tested on Ubuntu 22.04.3 LTS with Python 3.10.12.

  1. Use a Python virtual environment: python3 -m venv venv && source venv/bin/activate.
  2. Install the required packages pip install -r requirements.txt. Alternatively, you may run pip install numpy pandas matplotlib seaborn scipy nevis optuna optuna-dashboard pints nlopt jupyter ipython pymongo pybind11 python-dotenv tqdm.
  3. Download the required data for the nevis module by running python3 -c "import nevis; nevis.download_os_terrain_50()", if you haven't done so.
  4. Run the the algorithm of finding local optima and their basin of attraction (as specified in basin-problem/README.md). In other words, you need to run:
cd basin-problem
sudo apt install python3.10-dev g++ inkscape 
python setup.py install

and then run python calculate.py twice. Then cd ... (inkscape is installed because it is needed later for converting SVG to PDF.)

  1. Go to ./basin-problem/ipynb/ and run fig-1.ipynb and table-1.ipynb to produce Figure 1 and Table 1.
  2. Create a directory ./result/ by mkdir result.
  3. Navigate to the src directory by cd src, then run python3 run.py cmaes de da mlsl nm pso. This script will run the hyper-parameter tuning process and save the run results for the best instance for each of the following algorithms: CMA-ES, Differential Evolution, Dual Annealing, MLSL, Nelder-Mead, and PSO (Nelder-Mead does not have hyper-parameters so the tuning process is skipped). To speed up the process, you can run the tuning process for different algorithms concurrently in separate terminals; for example, you could run python3 run.py cmaes nm da in one terminal and python3 run.py pso mlsl de in another. For a full list of available options, use python3 run.py --help.
  4. Go to ./ipynb/plots/ and run all.ipynb. You should then find in ./ipynb/plots/imgs/ three figures: Fig2.pdf, Fig3.pdf and Fig4.pdf, which correspond to Figures 2, 3, 4 in the paper. Tables 5 and 6 are also produced in this notebook.

File structures

./src

Class definitions for the benchmarking framework.

  • ./src/framework contains class definitions for the framework.
  • ./src/algorithms contains algorithms defined using the framework.
  • ./src/tutorial.ipynb is a tutorial for using this framework.

./ipynb

Some Jupyter notebooks.

  • interval_size.ipynb The number of grid points that fall in each height interval.
  • lowest_point.ipynb The lowest point within n meters away from the peaks. Could be useful in selecting height threshold for successful runs.

./ipynb/plots

  • all.ipynb Plot most tables and figures in the paper.
  • de.ipynb Generating plots and animations for Differential Evolution.
  • nelder-mead-multi.ipynb Generating plots and animations for Nelder-Mead.
  • animation This directory contains some sample animations.

./ipynb/legacy

This directory has some notebooks from early trials. Some algorithms used have been re-implemented in the framework.

  • baseline.ipynb Some trials of baseline algorithms on this problem.
  • baseline_grid.ipynb Grid search as a baseline algorithm. The plot methods have been reimplemented in the framework, and the algorithm itself is too inefficient.
  • cmaes.ipynb A run of CMA-ES with plots.
  • DIRECT.ipynb DIRECT algorithms (with different variations implemented in nlopt).
  • fitting-with-shgo.ipynb SHGO algorithm.
  • plot.ipynb Results and plots from earlier experiments.
  • result.ipynb Results and plots from earlier experiments.
  • simulated_annealing.ipynb Simulated annealing and dual annealing.
  • tol-test.ipynb Testing the effect of absolute/relative tolerance on local optimisers.
  • variable-boundary.ipynb An attempt to generate multiple problem instances by setting random boundaries. Aborted.

./basin-problem

Scripts for finding all the local optima and their basin of attraction on the grid.

./img

Images used in documents and Jupyter notebooks.

./doc

Legacy documents and presentation slides about this project.