Discovering the suitability of optimisation algorithms by learning from evolved instances

DOI10.1007/s10472-011-9230-5zbMath1236.49008OpenAlexW2054706389WikidataQ62033379 ScholiaQ62033379MaRDI QIDQ408979

Kate A. Smith-Miles, Jano I. van Hemert

Publication date: 12 April 2012

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-011-9230-5

zbMATH Keywords

combinatorial optimizationphase transitiontravelling salesman problemalgorithm selectionhardness predictioninstance difficulty

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Combinatorial optimization (90C27) Operations research and management science (90B99) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Software, source code, etc. for problems pertaining to calculus of variations and optimal control (49-04) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (14)

Online over time processing of combinatorial problems ⋮ Towards objective measures of algorithm performance across instance space ⋮ Auto-selection mechanism of differential evolution algorithm variants and its application ⋮ Generating new test instances by evolving in instance space ⋮ New summary measures and datasets for the multi-project scheduling problem ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ A data-driven \textit{meta}-learning recommendation model for multi-mode resource constrained project scheduling problem ⋮ Instance spaces for machine learning classification ⋮ What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO ⋮ Algorithm runtime prediction: methods \& evaluation ⋮ Generalization of machine learning for problem reduction: a case study on travelling salesman problems ⋮ A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem ⋮ Measuring instance difficulty for combinatorial optimization problems ⋮ Evolving test instances of the Hamiltonian completion problem

Uses Software

• Hyperheuristics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Objective function features providing barriers to rapid global optimization
• A review of metrics on permutations for search landscape analysis
• What makes an optimization problem hard?.
• Landscapes, operators and heuristic search
• The TSP phase transition
• Measuring instance difficulty for combinatorial optimization problems
• Chained Lin-Kernighan for Large Traveling Salesman Problems
• Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures
• Empirical hardness models
• Determining Whether a Problem Characteristic Affects Heuristic Performance
• Hyper-Heuristics: An Emerging Direction in Modern Search Technology
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Evolutionary Computation in Combinatorial Optimization
• Principles and Practice of Constraint Programming – CP 2004
• The landscape of the traveling salesman problem

This page was built for publication: Discovering the suitability of optimisation algorithms by learning from evolved instances