[pt] Seja G= (V, E) um grafo não-orientado com custos não-
negativos em suas arestas e D um conjunto de pares
origem -
destino. Um 2-caminho entre nós (s,t)é um caminho de s a
t
formado por , no máximo, 2 arestas. O problema de síntese
de redes com 2-caminhos (2PNDP) consiste em encontrar um
subconjunto de arestas com custo mínimo que contenha um 2-
caminho entre as extremidades dea cada para origem-
destino
pertencente a D. Apicações deste problema encontram-se no
projeto de redes de comunicação, onde caminhos com poucas
arestas são desejáveis para garantir alta confiabilidade
e
pequenos atrasos. A metaheurística GRASP é um processo
multipartida para resolver problemas combinatórios, cujas
iterações consistem de duas fases, uma fase de construção
e
outra de busca local. O algoritmo retorna a melhor
solução
encontrada depois de um número determinado de
iterações.Aplica-se a técnica de reconexão por caminhos
ao
final de cada iteração GRASP para melhorar a qualidade
das
soluções. Implementações paralelas de metaheurística são
muito robustas. A maior parte das implementações
paralelas
da metaheurística GRASP segue uma estratégia do tipo
independente , baseada na distribuição balanceada das
iterações pelos processadores. No caso de estratégias
colaboradtivas, os processadores trocam e compartilham
informações coletadas ao longo da trajetória que cada um
deles investiga. Neta tese são desenvolvidas heurísticas
seqüenciais e paralelas para 2PNDP. São analisadas
variantes e combinações de GRASP e reconexão por
caminhos , comparando-se os resultados obtidos pelos
algoritmos descritos na literatura. Heurísticas GRASP
paralelas com reconexão por caminhos são avaliadas e
comparadas para verificar qual o papel que a colaboração
entre os processadores desempenha na qualidade das
soluções
e nos tempos de processamento. Procura-se também estudar
a
melhor maneira de desenvolver implementações paralelas ,
para se utilizar da melhor forma possível os recursos
computacionais e reduzir conflitos de memória e
comunicação. / [en] Let G = ( V, E) be a connected undirected graph , where V
is the set of nodes and E denotes the set of edges. A 2-
path between nodes (s,t)is a sequence of a most two edges
connecting them. Given a non-negative weight function
associated with edges of G and a set D of origin-
destination pairs of nodes, the 2-path network design
problem (2PNDP) consists in finding a minimum weighted
subset of edges containing a 2-path between the extremities
of every origin-destination pair in D. Applications can be
found in the design of communication networks , in which
paths with few edges are sought to enforce high reliability
and small delays. The GRASP metaheuristic is a multistart
process , in which each iteration consists of two phases :
construction and local search. The best solution found
after a fixed number of iterations is returned. Path-
relinking is applied as an attempt to improve the solutions
found at the of each GRASP iteration. Parallel
implementations of metaheuistics ara very robust. Typical
parallelizations of GRASP correspond to multiple-walk
independent-thread strategies, based on the balanced
distribuiton of the iterations over the processors. In the
case of multiple-walk cooperative-thread strategies, the
processors exchange and share information collected along
the trajectories that they investigate. In this thesis,
sequential and parallel heuristics are developed for 2PNDP.
Variants and combinations of GRASP with path-relinking are
analysed by comparing the results of the proposed
algorithms with those obtained by others algoritms
described in the literature. Parallel GRASP with
pathrelinking heuristcs are compared to investigate the
influence of the cooperation among processors in terms of
solution quality and processing time. We also explore
different strategies to optimize the parallel
implementations, to make better use of the computational
resources and to reduce communication and memory
conflicts.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:4365 |
| Date | 09 January 2004 |
| Creators | ISABEL CRISTINA MELLO ROSSETI |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0027 seconds