GRASP
Greedy Randomized Adaptative
Search Procedure
GRASP




Método de otimização combinatorial;
Desenvolvido por Feo e Resende (1989, 1995);
É um processo iterativo, no qual a cada iteração
uma nova solução inicial é gerada aleatoriamente;
Cada iteração consiste em 2 fases:


Construtiva: Geração Gulosa,Randômica e Adaptativa;
Busca local: gera alguma melhoria na solução
corrente, através de uma busca local na vizinhança
para encontrar o ótimo local.
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Algoritmo
Construção da
Solução inicial
S
Retorna a
melhor solução
Critério de parada
atingido?
N
Busca Local
Memoriza
melhores soluções
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Fase Construtiva





Demanda maior esforço computacional;
Constrói soluções, iterativamente, inserindo-se na
solução, um elemento de cada vez;
A cada iteração, a escolha do próximo elemento a
ser adicionado é determinado pela ordenação de
todos os elementos candidatos, em uma lista de
candidatos;
Essa ordenação é feita mediante a avaliação de cada
elemento, conforme a função “gulosa”;
Essa função seleciona, sequencialmente, o elemento
que minimiza o custo de incremento da solução
parcial, atualizando o benefício a outros elementos a
cada iteração (heurística adaptativa).
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Componente Probabilística




A componente probabilística é caracterizada pela
escolha aleatória de um dos melhores candidatos da
lista L, mas não necessariamente o melhor.
A lista resultante com os melhores resultados é
chamada de Lista Restrita de Candidatos (LRC).
Através da aleatoriedade, não é certa a obtenção da
melhor solução, porém permite-se uma melhor
diversificação.
Esta fase é dita dinâmica, pois o valor da função
gulosa varia a cada adição de um novo elemento, o
que difere da estática que fixa o valor de cada
elemento, antes do início desta fase.
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Lista Restritiva de Candidatos




Um fator importante do GRASP é a qualidade dos
elementos da lista restrita de candidatos.
Essa lista pode ser limitada por um número de
elementos ou pela qualidade dos elementos que a
compõem.
Se a lista for limitada a um elemento, a solução
encontrada será a única solução e não haverá uma
diversificação da solução.
Se a lista for ampla, serão geradas várias soluções
diferentes produzindo uma maior variação.
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Algoritmo de construção
Procedimento Construção(s)
S{}
Enquanto solução não completa faça:
LCR = {c ϵ C / g(c) ≤ s1 + a(s2 – s1)}
c= selec_elem_aleat(LRC)
S=S U {c}
Fim enquanto
Fim Construção
s1 = min{ g(t), t ϵ C}
s2 = max{ g(t), t ϵ C},
a ϵ (0,1).
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Parâmetro

De acordo com Feo e Resende (1995), a escolha do
parâmetro produz construções diferentes:
 Para a = 0, t = s1 + a(s2 – s1)} t = s1
(construção gulosa)
 Para a = 1, t = s1 + a(s2 – s1)} t = s2
(construção aleatória)
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Fase de Busca Local

Procedimento de busca local para melhoria da solução;

A busca é realizada na estrutura de vizinhança (viz(s));

Trocando a solução corrente, sempre que uma solução melhor foi
encontrada;
O procedimento termina quando nenhuma solução melhor e
encontrada;
Procedimento Buscalocal(s, viz(s))
Enquanto solução não ótima faça:
Encontrar uma melhor solução v ϵ viz(s);
s  v;
Fim enquanto
Retorna(s);
Fim Buscalocal

Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Estratégias de Busca Local


Best-improving - todos os vizinhos são analisados
e o melhor entre eles é selecionado;
First-improving - é adotada a primeira solução
cujo valor da função é menor que da solução
atual;



First-improving - requer um menor tempo
computacional;
Best-improving - converge prematuramente para
um ótimo local (Yamamoto, 2007).
Podem ser utilizados: Hill Climbing e Simulated
Annealing e Busca Tabu.
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
GRASP - PCV
Solução_Inicial = Primeira_Cidade;
Parâmetro a;
Adiciona Elemento Solução;
Seleciona Elemento;
Lista Candidatos (LC);
Lista Candidatos Restrita (LCR);
Parâmetro a
Aleatório/Guloso;
Até Solução Completa;
Solução Completa para Busca Local;
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Grasp para o problema das p-medianas
di mede a variação na função objetivo ao designar o
ponto i para o conjunto de medianas.
min{Cij  Ci ,a (i ) } se Cij  Ci ,a (i )
di  
caso contrário
0

Função de benefício para cada mediana
 j (S)  iN S i

Na fase construtiva do algoritmo GRASP selecionase uma nova mediana, aleatoriamente, entre os
elementos de uma Lista Restrita de Candidatos
(LRC), que contém os índices das medianas cujo
valor correspondente é menor ou igual a certo valor
calculado da seguinte forma:
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Grasp para o problema das p-medianas



RCL= j  J \ S :  j (S )   min  a ( max   min )
 min  min jJ \ S { j }
 max  max jJ \ S { j }

O parâmetro a define a fase de construção como
gulosa (se a = 0) ou aleatória (se a porcentagem de
aceitação).
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Fase de Melhoria



Utiliza-se um procedimento de busca local.
Estrutura de vizinhança, onde o conjunto de
soluções é formado por soluções vizinhas.
Soluções vizinhas são todas aquelas que substituem
uma mediana selecionada por uma mediana não
selecionada , e os demais pontos são novamente
designados à sua melhor mediana.
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
PCV - GRASP



Considerar o depósito inicial: D
1ª Fase: Construção
Repita

Escolha os candidatos da lista LRC, tal que:
g(c)  s1  a  s2  s1 




Escolha, aleatoriamente um dos candidatos (c1) da
lista LRC e montar a rota inicial: D – c1 – D;
Calcular o custo da rota
Até que todos os pontos tenham sido designados
Fim da 1ª Fase.
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
PCV - GRASP

2ª Fase: Melhoria

Selecione dois pontos da rota
Efetue todas as trocas possíveis
 Calcule o custo da nova rota
 Se o custo da nova rota for menor do que
o custo da rota anterior, então troque.


Parar quando não houver mais
melhoria na FO.
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
Solução do PCV - GRASP
Considere um conjunto com 6 cidades
Matriz de Distâncias
6
4
2
3
1
5
1
2
3
4
5
6
1
0
2
2
4
4
4
2
2
0
1
2
3
2
Luzia Vidal de Souza – UFPR – Meta-Heurísticas
3
2
1
0
2
2
3
4
4
2
2
0
3
3
5
4
3
2
3
0
5
6
4
2
3
3
5
0
Mecanismos de Memória




evitar trabalho redundante
guardar todas as soluções usadas
como soluções iniciais na busca local
Filtrar as soluções construídas, muito
ruins...eliminar
construir um conjunto de soluções
elites
PATH-RELINKING


Path-Relinking, melhoramento em
tempo e qualidade da solução
Path-Relinking, explora trajetórias

conectando soluções.
Path-Relinking



Originalmente proposto por Glower
(TABU)
Estratégia de intensificação que
explora trajetórias de soluções elites
obtidas por TABU ou SCATTER
Partindo de 1 ou mais soluções de
elite são gerados caminhos para
outras soluções
Caminhos

Movimentos que introduzam os
atributos presentes nas soluções são
selecionados
Implementações







Relink periódico: não sistemático,
mais periódico
Forward: aplicado entre o pior Xs e Xt
Backward:
Back e Forward
Mixed: Back e Forward ate uma
solução equidistante.
Movimentos Aleatórios
Truncada: alguns movimentos são
explorados.
GRASP com Path-Relinking

Path-Relinking é aplicado a todos os
pares de soluções elites.



seja periodicamente durante as iterações
GRASP
após todas as iterações GRASP, posotimização
path-relinking aplicado como estratégia de
intensificação após a fase local.
Soluções Elites



Cada solução da busca local
Medidas de similaridades
Soluções Geradas no Path-Relinking
3 Fases GRASP



Fase de Construção
Busca Local
Path-Relinking