GRASP (algoritmo)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

A metaheurí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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 aleatóriamente 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]


Wiki letter w.svg Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o. Editor: considere marcar com um esboço mais específico.