Grasp - Procedimento de busca guloso, aleatório adaptativo
871 palavras
4 páginas
GRASPSilas dos S. Silva
Definição
A metodologia Grasp foi desenvolvida por Feo e Resende em 1989, foi idealizada combinando uma heurística construtiva e uma busca local, seu foco está nas possíveis soluções de problemas relacionados à otimização combinatória, onde há a presença de uma aleatoriedade para encontrar soluções tão ótimas quanto possível para problemas. Definição
● Greedy Randomized Adaptive Search Procedure.
● Procedimento de busca guloso, aleatório adaptativo.
● Aplica a busca local a partir de soluções construídas com um algoritmo guloso aleatório.
● Melhor ótimo local dentre todas as combinações analisadas é retornado como solução.
Ótimo Local
Imagem extraída de: http://www.blopig.com/blog/category/groupmeetings/
Grasp
● Não garante um ótimo global, mas pode encontrá lo.
● Algoritmo
estocástico
(restrições
ou
parâmetros
dependem de variáveis aleatórias).
● A melhor solução local encontrada pode variar de um determinado problema para outro.
Grasp
● Processo iterativo.
● Consiste em duas fases, realizadas a cada iteração.
● Fase de construção e fase de busca local.
● A solução que se mostrar a melhor durante as iterações será mantida como resultado.
Fase de Construção
● Produzir uma possível solução, também de forma iterativa.
● A escolha do próximo elemento a ser adicionado à solução é determinada pela ordenação de todos os elementos candidatos, com base em uma função
g:C
R, onde g é
uma função adaptativa gulosa, a entrada C é uma lista de candidatos e R uma solução real.
Lista de Candidatos
● Na fase de construção, uma solução é iterativamente construída, elemento por elemento. A cada iteração dessa fase, os próximos elementos candidatos a serem incluídos na solução são colocados em uma lista C de candidatos. Aleatória
● A exemplo, imaginemos um certo parâmetro α para ser nosso coeficiente de aleatoriedade (controlar o nível de gulosidade e aleatoriedade na fase de construção).
● α = 0 poderia fazer gerar soluções