Algoritmos

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.
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