GRASP

GRASP (Greedy Randomized Adaptive Search Procedures) é uma meta-heurística para problemas de otimização combinatória. Meta-heurística basicamente é uma heurística que resolve problemas genéricos, com algumas pequenas adaptações. Esse método foi originalmente desenvolvido pelo brasileiro Maurício Resende, que hoje é pesquisador no AT&T.

De maneira geral, o algoritmo consiste de duas fases: construção e busca local. Na fase de construção tenta-se construir uma solução viável com um método que é um pouco guloso e um pouco aleatório. A busca local consiste em explorar vizinhos de uma solução até encontrar uma solução ótima local. Essas duas fases são repetidas por um certo número de iterações. Intuitivamente, o algoritmo sorteia pontos no espaço de soluções, quase que aleatoriamente (não é totalmente aleatório devido ao fator guloso, que tende a sortear soluções de melhor custo). Aí a busca local faz o trabalho de achar o ótimo local a partir de cada um desses pontos. Observe que as iterações são independentes entre si.

Construção da solução inicial

Para ficar mais claro, vamos considerar o problema de encontrar o caminho Hamiltoniano de custo mínimo, ou seja, dado um conjunto de cidades, encontrar a ordem em que se deve visitá-las de forma a minimizar o custo total de se viajar de uma cidade para outra. Podemos enxergar esse problema como o problema de encontrar a permutação de menor custo de elementos. O custo de uma permutação é a soma das distâncias entre dois elementos adjacentes nela.

O algoritmo é basicamente o seguinte: fazemos n iterações. Na i-ésima iteração, decidimos qual elemento ocupará a i-ésima posição do vetor representando a permutação. Para cada i,

  1. Construímos uma lista restrita de candidatos (Restricted Candidate List RCL)
  2. Selecionamos um elemento ‘s’ da RLC aleatoriamente e inserimos ele na posição i
  3. Remova ‘s’ da lista de candidatos

A construção da RCL é a parte principal dessa fase. Primeiramente calculamos o aumento no custo que cada elemento da lista de candidatos causará se for inserido na i-ésima posição. No nosso caso isso é basicamente sua distância para o elemento (i-1). Salvamos qual foi o maior e o menor custo desses elementos, cmin e cmax, respectivamente. Aí inserimos na RCL apenas os elementos cujo custo c(e) satisfizerem

Onde é um parâmetro de controle. Se , só o elemento de menor custo será inserido na RCL enquanto que se , todos os elementos o serão. Observe que como o elemento da RCL é escolhido aleatoriamente, se só houver um elemento, não há espaço para aleatoriedade e o algoritmo fica puramente guloso. Por outro lado, se todos os elementos estão na RCL, qualquer elemento é igualmente possível de ser escolhido, o que torna o algoritmo puramente aleatorio. Assim, fornece um controle sobre o quão guloso ou aleatorio é essa construção.

Busca Local

Após construída a solução inicial, realizamos a busca local que consiste em andar por soluções adjacentes que melhorem o custo da solução. A escolha da vizinhança é crucial para a eficácia do algoritmo. No nosso problema, uma possível vizinhaça seria as soluções obtidas trocando-se dois elementos de posição.

Há duas estratégias para “caminhar” em uma busca local: o First Improving e o Best Improving. Na primeira, logo que encontramos uma solução vizinha que seja melhor do que a solução atual, damos o passo. Já na segunda, exploramos todos os possíveis vizinhos e damos o passo na direção daquele de melhor custo.

Busca local termina em ótimos locais.

Path Relinking

Uma técnica para complementar o algoritmo GRASP é chamada de Path Relinking. Ela consiste em guardar um conjunto limitado de soluções — de baixo custo e suficientemente diferentes entre si — encontradas no decorrer do GRASP, e é chamado de soluções de elite. Ao chegar no ótimo local após a busca, consideramos os caminhos para sair dessa solução e chegar até cada uma das soluções de elite. A esperança é de que existam boas soluções no meio desses caminhos.

Bibliografia

[1] Greedy Randomized Adaptive Search Procedures: Advances and Applications – Resende, Mauricio e Ribeiro, Celso. Handbook of Metaheuristics 2008.

Os comentários estão fechados.

%d bloggers like this: