A cross-domain multi-armed bandit hyper-heuristic

Abstract

Resumo: Muitos problemas de otimização do mundo real são complexos e possuem muitas variáveis e restrições. Por esta causa, o uso de meta-heurísticas tornou-se a principal maneira de resolver problemas com essas características. Uma das principais desvantagens do uso de meta-heurísticas e que são geralmente desenvolvidas utilizando características do domínio fazendo com que sejam atreladas a ele dificultando sua utilização em outros problemas. Em buscas de algoritmos mais adaptáveis o conceito de hiper-heurísticas surgiu. Hiper- heurísticas são métodos de busca que visam solucionar problemas de otimização selecionando ou gerando heurísticas. Hiper-heurísticas de seleção escolhem uma boa heurística para ser aplicada a partir de um conjunto de heurísticas. O método de seleção e a principal peca de uma hiper-heurística de seleção tendo impacto fundamental em sua performance. Apesar de existirem vários trabalhos sobre hiper-heurísticas de seleção, ainda não existe consenso sobre como uma boa estratégia de seleção deve ser definida. Em busca de uma estratégia de seleção, algoritmos inspirados nos conceitos do problema Multi-Armed Bandit (MAB) serão estudados. Estes algoritmos foram aplicados ao contexto da Seleção Adaptativa de Operadores obtendo resultados promissores. Entretanto, ainda existem poucas abordagens para o contexto de hiper-heurísticas. Nesta dissertação propomos uma hiper-heurística que utiliza algoritmos MAB como sua estratégia de seleção. A abordagem proposta e desenvolvida utilizando o framework HyFlex, que foi proposto para facilitar a implementação e comparação de novas Hiper- heurísticas. Os parâmetros foram configurados através de um estudo empírico, e a melhor configuração encontrada foi comparada com os 10 primeiros colocados da competição CHeSC 2011. Os resultados obtidos foram bons e comparáveis com os das melhores abordagens da literatura. O algoritmo proposto alcançou a quarta colocação. Apesar dos bons resultados, os experimentos demonstram que a abordagem proposta sofre grande influencia dos parâmetros. Trabalhos futuros irão investigar formas de amenizar esta influência.

Abstract: Many real word optimization problems are very complex with many variables and constraints, and cannot be solved by exact methods in a reasonable computational time. As an alternative, meta-heuristics emerged as an efficient way to solve this type of problems even though they cannot ensure optimal values. The main issue of meta-heuristics is that they are built using domain-specific knowledge, therefore they require a great effort to be used in a new domain. In order to solve this problem, the concept of Hyper-heuristics were proposed. Hyper-heuristics are search methods that aim to solve optimization problems by selecting or generating heuristics. Selection hyper-heuristics choose from a pool of heuristics a good one to be applied at the current stage of the optimization process. The selection mechanism is the main part of a selection hyper-heuristic and has a great impact on its performance. Although there are several works focused on selection hyperheuristics, there is no unanimity about which is the best way to define a selection strategy. In this dissertation, a deterministic selection strategy based on the concepts of the MultiArmed Bandit (MAB) problem is proposed to cross-domain optimization. Multi-armed bandit approaches define a selection function with two components, the first is based on the performance of an operator and the second based on the number of times that the operator was used. These approaches had showed a promising performance over the Adaptive Operator Selection context. However, there are few works on literature that aim the hyper-heuristic context, as proposed here. The proposed approach is integrated into the HyFlex framework, that was developed to facilitate the implementation and comparison of hyper-heuristics. An empirical parameter configuration was performed and the best setup was compared to the top ten CHeSC 2011 algorithms using the same methodology adopted during the competition. The results obtained were good comparable to those attained by the literature. Moreover, it was concluded that the behavior of MAB selection is heavily affected by its parameters. As this is not a desirable behavior to hyper-heuristics, future research will investigate ways to better deal with the parameter setting.