Uma hiper-heurística de seleção baseada em decomposição para estabelecer sequências de módulos para o teste de software

Abstract

Resumo: Algoritmos multiobjetivos têm sido amplamente utilizados na busca de soluções de diver-sos problemas da computação, e mais especificamente para resolver problemas de Engenharia de Software na area conhecida como SBSE (Search Based Software Engineering). Contudo, conforme são intensificadas as aplicações destes algoritmos, tem-se a dificuldade de determinar qual algoritmo ou quais operadores são os mais indicados para um dado problema. Neste cenário as hiper-heurísticas são usadas para que o processo de busca seja guiado de forma que o melhor operador para o problema seja escolhido automaticamente. Neste contexto, destaca-se a hiper-heurística chamada HITO (Hyper-heuristic for the Integration and Test Order Problem), proposta para resolver o problema de estabelecer uma sequencia de módulos para o teste de integração (ITO - Integration and Test Order problem ). Em experimentos, a HITO obteve bons resultados, no entanto, existe a dificuldade para utilizar a HITO em conjunto com algoritmos baseados em decomposto, tais como o MOEA/D e MOEA/D-DRA. Estes algoritmos tem se mostrado bastante competitivos na literatura. Tendo este fato como motivação, este trabalho introduz uma hiper-heurística chamada HITO-DA (Hyper-heuristic for the Integration and Test Order Problem using Decomposition Approach) que propõe uma adaptação na HITO para permitir seu uso com algoritmos baseados em decomposto, na busca de soluções para o problema ITO. A HITO-DA foi instanciada com a meta-heurística MOEA/D-DRA usando o algoritmo de seleção FRRMAB (Fitness Rate Rank Multi Armed Bandit), e um novo algoritmo de seleção FRRCF (Fitness Rate Rank with Choice Function), proposto neste trabalho, que combina características do FRRMAB e CF (Choice Function). No estudo empírico conduzido a HITO-DA obteve melhores resultados do que a meta-heurística MOEA/D em todos os casos, e melhor desempenho em sistemas maiores, quando comparada com a HITO.

Abstract: Multi-objective algorithms have been widely applied to find solutions in several problems, more specifically to solve Software Engineering problems, in the field called SBSE (Search Based Software Engineering). However, while these applications are intensified, we find some difficulty to select the most suitable operator for a problem. In this given scenario, hyper-heuristics are used to guide the search process in order to find the most suitable operator for a given problem. In this context, we find a hyper-heuristic, called HITO (Hyper-heuristic for the Integration and Test Order problem), proposed to solve the Integration and Test Order problem (ITO). HITO obtained good results, however, to adapt HITO to work with decomposition based algorithms, such as MOEA/D and MOEA/D-DRA, is a hard task. In the literature, these algorithms have shown competitive results. Based on this motivation, this work introduces a new hyper-heuristic called HITO-DA (Hyper-heuristic for the Integration and Test Order Problem using Decomposition Approach) that adapts HITO to work with decomposition based algorithms and to solve the ITO problem. The HITO-DA was instantiated using the algorithms MOEA/D-DRA, using the selection algorithm FRRMAB (Fitness Rate Rank Multi Armed Bandit) and a new algorithm, introduced in this work, named FRRCF (Fitness Rate Rank with Choice Function). FRRCF combines characteristics of the algorithms FRRMAB and CF (Choice Function). The conducted empirical study shows that HITO-DA obtained better results than MOEA/D in all cases, and obtained better results than HITO, in bigger systems.