Foams

Nesta seção, os algoritmos utilizando a ideia do GRASP são ilustrados. O GRASP requer dois componentes básicos: um algoritmo de criação de solução de modo aleatório e guloso e a aplicação de uma busca local a solução criada (ver apêndice C).

5.8.1 Criação de Solução

O processo de criação de solução utilizado nas versões do GRASP difere daquele que foi implementado para ser usado no NSGA2 e SPEA2. O algoritmo 5.13 ilustra como uma solução é criada.

Algoritmo 5.13: Algoritmo de criação de solução utilizando no Grasp. Entrada: Grafo G, Heurística h, Parâmetro lrc, TamanhoLista NLRC

Saída: Solucao I enquanto |K| > 0 faça 1 k −→❊s❝♦❧❤❡●r♦✉♣❆❧❡❛t♦r✐♦ (K); 2 ❘❡♠♦✈❡❆r❡st❛❙❡♠❈❛♣❛❝✐❞❛❞❡ (G,k); 3 ✴✯ ❈r✐❛ ❧✐st❛ ❞❡ ár✈♦r❡s ♣❛r❛ ♦ ❣r✉♣♦ K ❝♦♠ t❛♠❛♥❤♦ NLRC ✯✴ LRC ←−❈r✐❛▲✐st❛❉❡➪r✈♦r❡s✭h,k,NLRC✮; 4 S −→❙❡❧❡❝✐♦♥❡❈♦♠♣♦♥❡♥t❡❆❧❡❛tór✐♦✭LRC,lrc✮; 5 ❆❞✐❝✐♦♥❛r (I,S); 6 ✴✴ ❘❡st❛✉r❛ ❛s ❛r❡st❛s r❡♠♦✈✐❞❛s ❘❡st❛✉r❛r (G); 7 r❡♠♦✈❡ (K,k); 8 fim 9

No algoritmo 5.13 uma solução para o MMPP é criada utilizando a ideia de lista restrita de candidatos. Um grupo k é escolhido aleatoriamente (linha 2), em seguida remove-se as arestas da rede que não tem capacidade suficiente para acomodar o grupo k (linha 3). Neste momento, cria-se uma lista restrita de candidatos com tamanho NLRC para o grupo k utilizando uma heurística h (algoritmos 5.2 ou 5.1), cada candidato é uma árvore de Steiner (linha 4). Em seguida é feita a escolha de uma árvore S levando em consideração um percentual lrc do tamanho da lista (linha 5). Por fim, a árvore é adicionada ao indivíduo I e o grafo G é restaurado (linhas 7 e 8).

Vale ressaltar que a heurístaca h determina o comportamento da lista restrita de candidatos. Quando h representa o algoritmo 5.1, então a lista restrita de candidatos é ordenada (ordem crescente) pelo custo. Por outro lado, quando h representa o algoritmo 5.2 então a lista restrita é ordenada (ordem decrescente) avaliando a quantidade de arestas de cada árvore de Steiner.

Fase construtiva Sequencial e Fase Construtiva alatória

A utilização do GRASP em um problema monobjetivo tem por objetivo maximizar ou mi- nimizar uma função objetivo. No entanto, quando se pretende adaptar e aplicar a metaurística para problemas multiobjetivo, então se deve ter em mente como projetar a fase de construção de solução levando em consideração que há mais de um critério a ser otimizado, assim como a busca local. Diante da necessidade de definir uma forma de construção de solução a ser aplicada surge a definição de fase construtiva sequencial e fase construtiva aleatória.

As fases de construção (sequencial ou aleatória) só indicam o objetivo de otimização que será focado em um iteração t do algoritmo. Ou seja, cada fase de construção indica como o objetivo a ser otimizado será escolhido (MARTí et al., 2011).

No problema abordado neste trabalho há dois objetivos de otimização: custo e capacidade residual. Utilizar a forma de construção sequencial significa escolher o objetivo de otimização de forma sequencial. Por exemplo, na iteração t = 0 o objetivo focado será o custo, então uma solução é criada dando enfase a melhoria do custo. Em seguida na iteração t = 1 o objetivo focado será a capacidade residual. Na iteração t = 3 novamente o foco será o custo. Na iteração t = 4 o foco será na melhoria da capacidade residual. Assim o algoritmo segue até o fim de sua execução sempre alternando o objetivo utilizado na iteração t.

Por outro lado, na forma de construção aleatória o objetivo é escolhido aleatoriamente. Por exemplo, na iteração t = 0 o objetivo focando é o custo. Em seguida, na iteração t = 1 o custo pode ser escolhido novamente e assim segue. Neste caso, não há como determinar que objetivo

é utilizado em cada iteração dado que ele é escolhido aleatoriamente.

Dois algoritmos são definidos com base nestas formas de construção. Note que a busca local utilizada é a PLS. É impotarte mencionar que a fases de construção definidas só determinam que objetivo será focado em cada iteração. Portanto, os algoritmos implementados estão em conformidade com a definição da metaheurística.

5.8.2 GRASP Sequencial

O algoritmo 5.14 utiliza a ideia apresentada apenas na fase de construção. A busca local aplicada utiliza o algoritmo 5.10. O algoritmo recebe como entrada um número máximo de iterações tmax e devolve o conjunto de solução não-dominadas A.

Algoritmo 5.14: Algoritmo GRASP com fase construtiva sequencial. Entrada: Grafo G, Iterações tmax, Parâmetro lrc, TamanhoLista NLRC

Saída: Não-Dominados A A ←− /0; 1 t ←− 0; 2 h ←− 0; 3

enquanto t < tmaxfaça

4 S ←− CriarSolucao(G,h,lrc,Nlrc); 5 At ←− BuscaLocal (S);✴✴ ❯s❛ ❛❧❣♦r✐t♠♦ ✺✳✶✵ 6 Q ←− A ∪ At; 7 A ←− Não-Domiandos(Q); 8 ✴✯ ▼✉❞❛♥ç❛ ❞❡ ❍❡✉ríst✐❝❛ ♣❛r❛ ❢♦❝❛r ❡♠ ♦✉tr♦ ♦❜❥❡t✐✈♦ ✯✴ se h = 0 então 9 h ←− 1; 10 senão 11 h ←− 0; 12 fim 13 fim 14

O algoritmo 5.14 começa sua execução definido a heurística h que será utilizado para cons- trução de solução (linha 3). Em seguida, o algoritmo inicia seu loop principal. Uma solução é criada usando a heurística h = 0 (usa algoritmo 5.1 foca na melhoria do custo). Neste mo- mento, cria-se a solução S usando a heurística h (linha 5), então a busca local PLS é aplicada retornando um conjunto de soluções não dominadas At (linha 6). Logo após, o conjunto de

soluçoes não-dominadas At é unido com as soluções não-dominadas encontradas em iterações

anteriores (linha 7), o conjunto Q é filtrado de modo que apenas indivíduos não-dominados sejam mantidos (linha 8). Por fim, uma nova heurística h é definida nas linhas (linhas 9 até 13).

5.8.3 GRASP Aleatório

A segunda versão do algoritmo GRASP apresenta uma fase de construção diferente da versão anterior. Neste caso, tem-se uma fase de construção aleatória. Ou seja, a escolha da heurística h na iteração t indica que a criação de solução vai focar apenas no objetivo i correspondente a heurística h. O restante do algoritmo funciona exatamente de acordo com os princípios do GRASP. A busca local aplicada é a PLS.

Algoritmo 5.15: Algoritmo Grasp com fase construtiva aleatória. Entrada: Grafo G, Iterações tmax, Parâmetro lrc, TamanhoLista NLRC

Saída: Não-Dominados A A ←− /0;

1

t ←− 0;

2

enquanto t < tmaxfaça

3 h ←− EscolheHeuristicaAleatório(); 4 S ←− CriarSolucao(G,h,lrc,Nlrc); 5 At ←− BuscaLocal (S); 6 Q ←− A ∪ At; 7 A ←− Não-Domiandos(Q); 8 fim 9

O algoritmo 5.15, diferentemente do algoritmo 5.14, inicia sua execução diretamente no loop(linhas 3 até 9) ao invés da versão anterior que define a heurísica h = 0 (algoritmo 5.14 linha 3).

No interior do loop mencionado há a definição da heurística h de modo aleatório, em se- guida uma solução S é criada focando no objetivo h (Se h=0, então foca no custo. Caso seja 1 foca na capacidade residual). Logo após, aplica-se a busca local PLS gerando o arquivo de in- divíduos não-dominados At. O conjunto Até unido com o conjunto de soluções não-dominadas

A encontradas até o momento formando o conjunto Q, este conjunto é filtrado e apenas os indivíduos não-dominados são adicionados para o conjunto A.