Automatic algorithm selection for the quadratic assignment problem using meta-learning principles and fitness landscape measures

Abstract

Resumo: Algoritmos meta-heurísticos são usados para obter boas soluções em tempo factível para vários problems de busca NP-difícil. Entretanto, o desempenho dos algoritmos depende fortemente das características do problema, o que significa que não há um único método capaz de obter as melhores soluções em todos os cenários. Portanto, estudar formas de realizar seleção automática de algoritmo para problemas de otimização é um crescente tópico de pesquisa nos últimos anos. Esse tipo de tarefa pode ser abordado através de conceitos de metaaprendizagem, oriundos da comunidade de aprendizagem de máquina, cujo objetivo é mapear as características das instâncias do problema ao desempenho de um conjunto de algoritmos. Um aspecto fundamental de meta-aprendizagem é a caracterização das instâncias, o que é feito pelas meta-características e que, por sua vez, devem ser propriedades informativas que afetam o desempenho dos algoritmos. Algumas pesquisas propõem o uso de medidas baseadas em Análise de Superfície de Aptidão (ASA) para representar as instâncias. Esse tipo de métrica caracteriza as formas das superfícies geradas por um operador heurístico, e são tradicionalmente usadas para relacionar a dificuldade que um determinado problema oferece à uma meta-heurística. Neste trabalho, foi conduzida de forma progressiva uma série de estudos relacionados à seleção de algoritmos com meta-aprendizagem e medidas de ASA para o Problema Quadrático de Alocação (PQA). O PQA é um clássico problema de busca NP-difícil e é conhecido por ser um dos mais desafiadores para algoritmos de otimização. As principais contribuições deste trabalho são os experimentos de meta-aprendizagem realizados usando medidas de ASA conhecidas na literatura e alguns dos algoritmos meta-heurísticos do estado-da-arte. Diversos aspectos da abordagem são evidenciadas ao longo dos estudos, como desempenho de classificação, esforço de aplicação e consumo de tempo.

Abstract: Meta-heuristic algorithms have been used to obtain good solutions in feasible time for many NP-hard search problems. However, the performance of the algorithms heavily depends on the features of the problem, meaning that it does not exist a single method able to achieve the best solutions in all scenarios. Therefore, studying ways to perform automatic algorithm selection for optimization problems is an increasing research topic in the past recent years. This type of task can be addressed by using meta-learning concepts, from the machine learning community, which aims at mapping the characteristics of problem instances to the performance of a set of algorithms. A key aspect of meta-learning is the characterization of the instances, which is done by the meta-features that, in turn, must be informative properties that affect the performance of the algorithms. Some researches have proposed the use of features based on Fitness Landscape Analysis (FLA) to characterize the instances. This type of measures characterizes the landscape shapes generated by a heuristic operator, and are traditionally used to relate the difficulty in which a problem imposes to a meta-heuristic. In this work, a series of studies were progressively conducted regarding algorithm selection with meta-learning and FLA features for the Quadratic Assignment Problem (QAP). The QAP is a classical NP-hard search problem that is known for being one of the most challenging for optimization algorithms. The main contributions of this work are the meta-learning experiments performed using well known sets of FLA measures from the literature and some of the state-of-the-art meta-heuristic algorithms. Several aspects of the approach are highlighted along the studies, such as the performance of classification, application effort and time consumption.