Heuristicas e Metaheuristicas - p-Medianas

...

Este artigo e´ um relatorio´ tecnico´ que apresenta algumas heur´ısticas e me-taheur´ısticas para a soluc¸ao˜ aproximada do PPM. Na Sec¸ao˜ 2 sao˜ apresentadas as ca-racter´ısticas do PPM, com a definic¸ao˜ e a formulac¸ao˜ matematica´ do problema. Na Sec¸ao˜ 3 sao˜ apresentadas duas heur´ısticas construtivas presentes na literatura para o PPM e al-gumas alterac¸oes˜ propostas por este artigo. Na Sec¸ao˜ 4 sao˜ apresentadas duas estrategias´ de busca local presentes na literatura para o PPM. Na Sec¸ao˜ 5 sao˜ apresentadas duas me-taheur´ısticas para o PPM e na Sec¸ao˜ 6, o artigo descreve os resultados obtidos atraves´ de experimentos realizados com os algoritmos apresentados nas sec¸oes˜ anteriores.

2. O Problema das p-Medianas

Em geral, um problema de otimizac¸ao˜ combinatoria´ pode ser expresso como:

[pic 1]

onde f (x) e´ a func¸ao˜ objetivo a ser minimizada e X e´ o conjunto de todas as soluc¸oes˜ poss´ıveis do problema. Uma soluc¸ao˜ x* e´ chamada soluc¸ao˜ otima´ quando:

[pic 2]

Dado um grafo completo e nao˜ orientado G = (V,E), em que V e´ o conjunto dos n vertices´ do grafo e E e´ o conjunto das arestas que representam as distanciasˆ entre os

---------------------------------------------------------------

vertices,´ deve-se encontrar um conjunto Vp V com cardinalidade p, em que Vp repre-senta o conjunto das medianas do problema, de modo que a soma ponderada das distanciasˆ de cada vertice´ restante em V - Vp ate´ o vertice´ mais proximo´ em Vp seja a m´ınima poss´ıvel.

Segundo [Alp et al. 2003], a formulac¸ao˜ matematica´ do PPM e´ dada por:

[pic 3]

---------------------------------------------------------------

A restric¸ao˜ (2.4) assegura que um vertice´ de demanda seja atendido por uma unica´ mediana. A restric¸ao˜ (2.5) afirma que um vertice´ de demanda somente seja atendido por uma mediana que esteja instalada. A restric¸ao˜ (2.6) garante que sao˜ designadas exata-mente as p medianas. A restric¸ao˜ (2.7) define que as variaveis´ envolvidas sao˜ binarias´ [Amorim et al. 2011].

3. Heur´ısticas Construtivas

Uma heur´ıstica construtiva consiste na construc¸ao,˜ em tempo polinomial, de uma soluc¸ao˜ viavel´ para o problema proposto sem a preocupac¸ao˜ com a otimalidade da soluc¸ao˜ gerada. Esta estrategia´ e´ bastante utilizada para a gerac¸ao˜ da soluc¸ao˜ inicial que servira´ de base para o processo de busca local. Dentre as tecnicas´ mais utilizadas estao˜ os algoritmos gulosos e os algoritmos aleatorizados.

Um algoritmo guloso para PPM foi proposto pela primeira vez por [Kuehn and Hamburger 1963]. O algoritmo comec¸a com uma soluc¸ao˜ parcial vazia (X0 = ;) e vai adicionando uma nova mediana de cada vez ate´ que p medianas tenham sido selecionadas. Suponha-se que a soluc¸ao˜ parcial Xk inclui as localizac¸oes˜ de k me-dianas e deseja-se selecionar a proxima´ mediana para fazer parte da nova soluc¸ao˜ Xk+1. Denote por d(vi; Xk) a menor distanciaˆ entre o vertice´ de procura vi e a mediana mais proxima´ pertencente ao conjunto Xk. Do mesmo modo, d(vi; Xk [vj), a menor distanciaˆ entre o vertice´ de procura vi 2 V n(Xk [ vj) e o elemento do conjunto Xk [ vj mais proximo´ de vi. A (k + 1)-esima´ mediana sera´ o vertice´ candidato vj que minimiza a func¸ao˜ gulosa c(vj; Xk), definida por:

[pic 4]

A seguir, apresenta-se o pseudo-codigo´ do algoritmo guloso (AG) que pode ser utilizado para resolver o PPM:

Algoritmo 1: GulosoPPM (AG)

[pic 5]

Entrada: V , p

[pic 6]

Sa´ıda: X

- = ;

enquanto jXj

calcule c(vi; X), para todo vi 2 V nX

[pic 7]

v = min(c(vi; X)jvi 2 V nX)

- = X [ fv g

fim

retorna X

[pic 8]

Outra heur´ıstica construtiva gulosa, porem´ aleatorizada, e´ proposta por [dos Santos et al. 2009]. Este artigo apresenta uma versao˜ modificada desta heur´ıstica construtiva. A construc¸ao˜ da soluc¸ao˜ e´ baseada na minimizac¸ao˜ da func¸ao˜ objetivo pon-derada por um fator aleatorio´ . Iniciando com a soluc¸ao˜ vazia (sem nenhuma mediana), passo a passo escolhe-se um local candidato para ser uma mediana. A cada passo, em

---------------------------------------------------------------

vez de selecionar o melhor dentre todos os m locais candidatos restantes, escolhe-se ale-atoriamente t locais candidatos (t

t = 1:5 log2 mp

A seguir, apresenta-se o pseudo-codigo´ do algoritmo guloso aleatorizado (AGA) proposto.

Algoritmo 2: GulosoAleatorioPPM (AGA)

[pic 9]

Entrada: V , p

[pic 10]

Sa´ıda: X

- = ;

enquanto jXj

m = jV jXjj

[pic 11]

- = 1:5 log2 mp melhorcusto =INFINITO

para j de 1 ate´ t fac¸a

vi =vertice´ sorteado aleatoriamente de V nX

[pic 12]

i = valor aleatorio entre 0 e 1

custo = i c(vi; X)

se custo

melhorcusto = custo

[pic 13]