Discovering the suitability of optimisation algorithms by learning from evolved instances |
| |
Authors: | Kate Smith-Miles Jano van Hemert |
| |
Affiliation: | 1.School of Mathematical Sciences,Monash University,Victoria,Australia;2.School of Informatics,University of Edinburgh,Edinburgh,UK |
| |
Abstract: | The suitability of an optimisation algorithm selected from within an algorithm portfolio depends upon the features of the
particular instance to be solved. Understanding the relative strengths and weaknesses of different algorithms in the portfolio
is crucial for effective performance prediction, automated algorithm selection, and to generate knowledge about the ideal
conditions for each algorithm to influence better algorithm design. Relying on well-studied benchmark instances, or randomly
generated instances, limits our ability to truly challenge each of the algorithms in a portfolio and determine these ideal
conditions. Instead we use an evolutionary algorithm to evolve instances that are uniquely easy or hard for each algorithm,
thus providing a more direct method for studying the relative strengths and weaknesses of each algorithm. The proposed methodology
ensures that the meta-data is sufficient to be able to learn the features of the instances that uniquely characterise the
ideal conditions for each algorithm. A case study is presented based on a comprehensive study of the performance of two heuristics
on the Travelling Salesman Problem. The results show that prediction of search effort as well as the best performing algorithm
for a given instance can be achieved with high accuracy. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|