GRASP

A meta-heurística GRASP (Greedy Randomized Adaptive Search Procedure) é um algoritmo comumente aplicado a problemas de otimização combinatória. Como diversos métodos construtivos, a aplicação do GRASP consiste em criar uma solução inicial e depois efetuar uma busca local para melhorar a qualidade da solução. Seu diferencial para outros métodos está na geração dessa solução inicial, baseada nas três primeiras iniciais de sua sigla em inglês: gulosa (Greedy), aleatória (Randomized) e adaptativa (Adaptive).

Filosofia do GRASP

Enquanto outros algoritmos como a busca tabú e os algoritmos genéticos valem-se de estratégias com grande ênfase na busca local, o GRASP é dito construtivo por privilegiar a geração de uma solução inicial de melhor qualidade para utilizar a busca local apenas para pequenas melhorias.

A estratégia de construção de uma solução no GRASP consiste na definição de um critério de avaliação dos elementos que podem ser inseridos em um conjunto que, ao final do processo, será uma solução para o problema de otimização que se pretende resolver. Esse critério adapta-se à solução já construída, de forma que a valoração dos elementos muda durante a construção da solução. Entretanto, esse critério não é tomado como referência absoluta para a decisão do próximo elemento a ser inserido, havendo uma escolha aleatória entre os melhores elementos a cada iteração.

Metodologia

Uma solução para um problema de otimização combinatória é visto no GRASP como um conjunto com elementos que atendam a todas as restrições existentes no problema. Começa-se com um conjunto vazio, e são inseridos elementos nesse conjunto até que ele represente uma solução viável para o problema.

A cada iteração, todos os elementos candidatos são avaliados segundo uma função gulosa que meça o benefício da inserção desse elemento para a construção da solução. A medida desse benefício é dita míope por ser uma avaliação imprecisa de como a inserção de um elemento pode colaborar para a obtenção de uma solução de melhor qualidade, seja em número de elementos necessários, no impacto na função objetivo do problema ou outra métrica qualquer.

Uma vez realizada essa valoração, é construída a RCL (restricted candidate list): uma lista contendo os elementos com melhor valor na função gulosa, podendo seu tamanho ser definido por um parâmetro absoluto como um número de elementos que devam existir na lista, ou por um percentual de tolerância entre o valor do melhor elemento encontrado e o valor de um elemento que pode estar na lista. Dessa lista, escolhe-se um elemento aleatoriamente para ser inserido na solução. Devido a esse misto entre a função gulosa na construção de uma lista e a decisão aleatória sobre qual elemento dessa lista utilizar, diz-se que o GRASP é semi-guloso.

Ao final de cada iteração, todos os elementos candidatos a inserção são reavaliados em decorrência do último elemento inserido, uma vez que elementos muito parecidos com aquele não serão mais tão interessantes quanto eram antes.

Variantes

Muitas variações e especializações foram propostas ao GRASP, como funções de probabilidade de escolha de acordo com o posicionamento dos elementos na RCL, tamanho variável da RCL, entre outros.

Padrão de Implementação

O pseudocódigo abaixo ilustra como funciona uma heurística construtiva:

Enquanto (condição de parada não for satisfeita), faça
  solução = crie aleatoriamente uma solução de forma construtiva();
  solução = busca local(solução);
  se solução é a melhor solução até então conhecida então
    grave(solução);
  fim se
Fim Enquanto

Histórico

GRASP foi inicialmente descrito no trabalho Feo e Resende (1989) para o problema da cobertura de conjuntos. Durante a última década, diversos autores aplicaram o meta-modelo GRASP a diferentes problemas de otimização combinatória atestando sua relevância para a literatura. ^{[carece de fontes]}

Referências

• T.A. Feo and M.G.C. Resende (1989) A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8:67–71, 1989.
• T.A. Feo and M.G.C. Resende (1995) Greedy randomized adaptive search procedures. J. of Global Optimization, 6:109–133, 1995.
• L. Pitsoulis and M.G.C. Resende (2002) Greedy randomized adaptive search procedures. In P.M.Pardalos and M.G.C.Resende, editors, Handbook of Applied Optimization, pp. 168–181, Oxford University Press.
• M.G.C. Resende and C.C. Ribeiro (2003) Greedy randomized adaptive search procedures. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pp. 219–249, Kluwer Academic Publishers, 2003.
• P. Festa and M.G.C. Resende (2002) GRASP: An annotated bibliography. In C.C. Ribeiro and P. Hansen, editors, Essays and Surveys on Metaheuristics, pp. 325–367, Kluwer Academic Publishers, 2002.