MATILDA is an online tool which makes available our new methodology known as Instance Space Analysis. It provides:
- visualisations of the instance space for a problem
- showing the location of benchmark test instances across the instance space
- showing the strengths (“footprints”) and weaknesses of algorithms across the instance space
- summarising the properties of the instances that an algorithm finds easy or hard
- objective (unbiased) metrics of algorithmic power via footprint analysis
- synthetic generation of new test instances at specific locations in the instance space (e.g. real-world-like instances, or instances with controllable properties)
- automated algorithm selection tools to assist deployment of the best algorithm for a given instance.
Our efforts thus far have created instance space analyses for the following problem classes:
- Combinatorial Optimisation Problems
- Graph Colouring
- Travelling Salesman Problem
- Knapsack Problem
- Mathematical Programming
- Linear Programming
- Mixed Integer Programming
- Continuous Optimisation
- Black-box Single Objective
- Black-box Multi-Objective
- Job Shop Scheduling
- Combinatorial Optimisation Problems
- Learning and Model Fitting
- Machine Learning
- Time Series Analysis
- Time Series Forecasting
- Image Analysis
- Facial Age Estimation
- Machine Learning
If you have additional problems you would like to make available in MATILDA, please contact us (firstname.lastname@example.org)
VIDEO TUTORIAL: Introduction to Instance Space Analysis
The engine behind MATILDA is powered by MATLAB code, also available to download and run offline. MATILDA's online platform enables researchers to:
- Download benchmark datasets for various library problems, including existing algorithm performance results, instance features, and our existing instance space visualisations;
- Upload a new algorithm's performance metrics and visualize its comparative strength and weaknesses across our constructed instance space;
- Create instance spaces for new problems to examine the diversity and adequacy of existing benchmarks;
- Generate objective metrics and visualisations of algorithm performance and problem instance distributions across the instance space, to support insightful analysis of algorithmic strengths and weaknesses;
- Use machine learning methods to make recommendations about which algorithm is predicted to perform best in certain regions of the instance space.
VIDEO TUTORIAL: How to Perform an Instance Space Analysis
The methodology used by MATILDA for visualizing and understanding the strengths and weaknesses of different algorithms has been originally described in a series of three papers focusing on graph colouring as a case study:
- Smith-Miles, K. A., and Lopes, L. B., “Measuring Instance Difficulty for Combinatorial Optimization Problems”, Computers & Operations Research, vol. 39, no. 5, pp. 875-889, 2012.
- Smith-Miles, K. A., Baatar, D., Wreford, B. and Lewis, R., “Towards Objective Measures of Algorithm Performance across Instance Space”, Computers & Operations Research, vol. 45, pp. 12-24, 2014.
- Smith-Miles, K. A. and Bowly, S., "Generating New Test Instances by Evolving in Instance Space", Computers & Operations Research, vol. 63, pp. 102-113, 2015.
The early ideas for the instance space analysis methodology are summarised in three earlier papers:
- Smith-Miles, K. A., “Cross-disciplinary perspectives on meta-learning for algorithm selection”, ACM Computing Surveys, vol. 41, no. 1, article 6, 2008.
- Smith-Miles, K. A., "Towards insightful algorithm selection for optimisation using meta-learning concepts", International Joint Conference on Neural Networks, Workshop on Hybrid Systems, Ensembles, and Meta-Learning Algorithms, pp. 4118-4124, 2008.
- Smith-Miles, K.A. “Generalising meta-learning concepts: from machine learning to meta-heuristics”, in Proceedings of the 7th Meta-heuristics International Conference (MIC’07), Montreal, June 25-29th, 2007.
Additional publications from the MATILDA team have applied this methodology to a wide variety of other problem domains, including:
- Guimares, C., Aleti, Al, Grunske, L. and Smith-Miles, K., "Mapping the Effectiveness of Automated Test Suite Generation Techniques", IEEE Transactions on Reliability, vol. 67, no. 3, pp. 771-785, 2018.
- Muñoz, M. A., Villanova, L., Baatar, D. and Smith-Miles, K. A., "Instance Spaces for Machine Learning Classification", Machine Learning, vol. 107, no. 1, pp. 109-147, 2018.
- Kang, Y., Hyndman, R. and Smith-Miles, K., "Visualising Forecasting Algorithm Performance using Time Series Instance Spaces", International Journal of Forecasting, vol. 33, no. 2, pp. 345-358, 2017.
- Muñoz, M. A. and Smith-Miles, K. A., "Performance analysis of continuous black-box optimization algorithms via footprints in instance space", Evolutionary Computation, vol. 25. no. 4, pp. 529-554, 2017.
- Smith-Miles, K. and Tan, T. “Measuring Algorithm Footprints in Instance Space”, in Proceedings of the 2012 IEEE Congress on Evolutionary Computation, pp. 3446-3453, 2012.
- Smith-Miles, K. A., and Lopes, L. B., “Generalising Algorithm Performance in Instance Space: A timetabling case study”, Selected papers of the 5th International Conference on Learning and Intelligent Optimization, Lecture Notes in Computer Science, vol. 6683, pp. 524-539, Springer, 2011.
- Smith-Miles, K. A., van Hemert, J., Lim, Y., “Understanding TSP Difficulty by Learning from Evolved Instances”, Selected papers of the 4th International Conference on Learning and Intelligent Optimization, Lecture Notes in Computer Science, vol. 6073, pp. 266-280, 2010.
- Lopes, L. B. and Smith-Miles, K. A., “Pitfalls in Instance Generation for Udine Timetabling”, Selected papers of the 4th International Conference on Learning and Intelligent Optimization, Lecture Notes in Computer Science, vol. 6073, pp. 299-302, 2010.
- Smith-Miles, K. A., James, R. J. W., Giffin, J. W. and Tu, Y., “A Knowledge Discovery Approach to Understanding Relationships between Scheduling Problem Structure and Heuristic Performance”, Selected papers of the 3rd International Conference on Learning and Intelligent Optimization, Lecture Notes in Computer Science, vol. 5851, pp. 89-103, 2009.